What does j9T mean in yescrypt (from /etc/shadow)?

Question

Consider this Shadow string

$y$j9T$PaFEMV0mbpeadmHDv0Lp31$G/LliR3MqgdjEBcFC1E.s/3vlRofsZ0Wn5JyZHXAol5

There are 4 parts

• id : y (yescrypt)
• param : j9T
• salt : PaFEMV0mbpeadmHDv0Lp31
• hash : G/LliR3MqgdjEBcFC1E.s/3vlRofsZ0Wn5JyZHXAol5

Q:

1. What does j9T in param field mean?
2. Are there other options in this field?
3. Where can we find official documentation?

I've seen this question; The format of encrypted password in /etc/shadow, however, there is no explanation there.

Answer 1

Disclaimer

Below are my own findings and the way I interpreted them without having an expert understanding of cryptography and the concepts involved.

Signatures

Notably, as the yescrypt CHANGES file on the OpenWall GitHub states about the Changes made between 0.8.1 (2015/10/25) and 1.0.0 (2018/03/09), yescrypt has two signatures:

• $7$ - classic scrypt hashes, not very compact fixed-length encoding
• $y$ - native yescrypt and classic scrypt hashes, new extremely compact variable-length encoding

This extremely compact variable-length encoding is what introduces much but not all of the complexity that the end of the second-to-last paragraph in this UNIX StackExchange answer talks about.

Parameters

For a simple description of the parameters, the BitcoinWiki Yescrypt parameters section can be helpful:

Parameter	Description
password	password to hash
salt	salt to use
flags	flags to toggle features
N	increasing N increases running time and memory use
r	increasing R increases the size of blocks operated on by the algorithm (and thus increases memory use)
p	parallelism factor
t	increasing T increases running time without increasing memory use
g	the number of times the hash has been "upgraded", used for strengthening stored password hashes without requiring knowledge of the original password
NROM	read-only memory that the resulting key will be made to depend on
DKLen	the length of key to derive (output)

Format

Of these, $7$ hashes only use the following:

• N - encoded with 1 byte (character)
• r - encoded with 5 bytes (characters)
• p - encoded with 5 bytes (characters)

Since $7$ also means fixed-length encoding, every parameter has a prespecified number of bytes that encode it and every one of the parameters comes in order: $7$Nrrrrrppppp$...$.

Let's enclose each byte in [] square brackets: $7$[N][r1][r2][r3][r4][r5][p1][p2][p3][p4][p5]$...$. Further, this means 11 is the exact number of bytes required (hence why it's not compact) for parameters in the sequence specified.

On the other hand, $y$ hashes require three parameters:

• flags - encoded with at least 1 byte (character)
• N - encoded with at least 1 byte (character)
• r - encoded with at least 1 byte (character)

Still, $y$ hashes can use all parameters by encoding them with variable-length. Effectively, this means each parameter is prefixed with its own size # encoded in the first byte and continues with # bytes:

$y$[flags_len=#][flags1]...[flags#][N_len=#][N1]...[N#][r_len=#][r1]...$...$

To make things even more complex, the mandatory parameters are followed by an optional have parameter. Based on the value of have, yescrypt decides which, if any of p, t, g, and NROM are also part of the supplied data.

For comprehensive guidelines about the parameters and which ones to use in what situations, it's probably best to consult the yescrypt PARAMETERS file on the OpenWall GitHub.

Encoding

Decoding the parameter fields is done via decode64_uint32(), which uses an array, indexed by atoi64() with the difference between the ASCII values of the current byte and the . period character (46), which is the base:

atoi64_partial[77] = {
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11,
  64, 64, 64, 64, 64, 64, 64,
  12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
  25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37,
  64, 64, 64, 64, 64, 64,
  38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50,
  51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63
};

For each field, starting from the first field byte yescrypt performs the following actions:

1. Use the first field byte to index the array as described above.
2. Perform calculations with the array item to get a partial value for the field.
3. Perform calculations with the array item to get the number of following bytes that encode the rest of the field value.
4. For each next byte, the algorithm uses it to index the array again and adds the data to reach the final field value.

There is some pseudo-code for other processes in the BitcoinWiki Yescrypt functions section.

Demo Parameter Encoding

Let's take an example from the PARAMETERS file above:

• flags = YESCRYPT_DEFAULTS
• N = 4096
• r = 32
• p = 1
• t = 0
• g = 0
• NROM = 0

The above set of values is described as a standard Large and slow (memory usage 16 MiB, performance like bcrypt cost 2^8 - latency 10-30 ms and throughput 1000+ per second on a 16-core server) choice for Password hashing for user authentication, no ROM.

$y$ is the signature.

flags = YESCRYPT_DEFAULT = 182 = 0xB6 = j in yescrypt variable-length encoding.

Here, flags should decode to YESCRYPT_DEFAULT, which is equivalent to YESCRYPT_RW_DEFAULTS, defined as (YESCRYPT_RW | YESCRYPT_ROUNDS_6 | YESCRYPT_GATHER_4 | YESCRYPT_SIMPLE_2 | YESCRYPT_SBOX_12K):

• YESCRYPT_RW = 0x002
• YESCRYPT_ROUNDS_6 = 0x004
• YESCRYPT_GATHER_4 = 0x010
• YESCRYPT_SIMPLE_2 = 0x020
• YESCRYPT_SBOX_12K = 0x080

Performing the logical OR operation, yescrypt arrives at the final number and encodes it.

N = 4096 = 0x1000 = 9 in yescrypt variable-length encoding. In fact, N = 2^{decoded_N_field}.

r = 32 = 0x20 = T in yescrypt variable-length encoding.

$ at this point tells yescript that no optional parameters were specified.

Finally, the salt is added. It is theoretically of arbitrary length. However, the salt must be of a length that's a power of 4.

$y$j9T$SALT$

Examples

Here are a couple of valid but not secure examples, which may be visually helpful after the descriptions above:

• $7$9/..../..../$SALTS$
• $y$./.$SALT$
• $y$8/.$SALT$