NIST SP 800-185 日本語訳

This Recommendation defines two cSHAKE variants, cSHAKE128 and cSHAKE256, in Sec. 3, based on the KECCAK[\(c\)] sponge function [3] defined in FIPS 202. It then defines three additional SHA-3-derived functions, in Secs. 4 through 6, that provide new functionality not directly available from the more basic functions. They are:

These functions are detailed in the specific sections below. In addition, a method is specified in Appendix B to facilitate using these functions to produce output that is almost uniformly distributed on the integers \(\{0, 1, 2, \ldots, R-1\}\) for any positive integer \(R\).

In this document, bits are indicated in the Courier New font. Bytes are typically written as two-digit hexadecimal numbers from the ASCII characters 0 through 9 and A through F, preceded by the prefix “0x”. In binary representation, bytes are written with the low-order bit first, while in hexadecimal representation, bytes are written with the high-order digit first. E.g., \(\mathrm{0x01} = \mathtt{10000000}\) and \(\mathrm{0x80} = \mathtt{00000001}\). These bit-ordering conventions follow the conventions established in Sec. B.1 of FIPS 202. Character strings appear in this document in double-quotes. Character strings are interpreted as bit strings whose length is a multiple of 8 bits, consisting of a 0 bit, followed by the 7-bit ASCII representation of each successive character.

\(\lceil x \rceil\)

For a real number \(x\), \(\lceil x \rceil\) is the least integer that is not strictly less than \(x\). For example, \(\lceil 3.2 \rceil = 4\), \(\lceil -3.2 \rceil = -3\), and \(\lceil 6 \rceil = 6\).

\(\mathtt{0}^s\)

For a positive integer \(s\), \(\mathtt{0}^s\) is the string that consists of \(s\) consecutive 0 bits.

\(a \bmod b\)

The modulo operation of integers \(a\) and \(b\). “\(a \bmod b\)” returns the remainder after dividing \(a\) by \(b\).

\(\mathrm{enc}_8(i)\)

For an integer \(i\) ranging from 0 to 255, \(\mathrm{enc}_8(i)\) is the byte encoding of \(i\), with bit 0 being the low-order bit of the byte.

\(\operatorname{len}(X)\)

For a bit string \(X\), \(\operatorname{len}(X)\) is the length of \(X\) in bits.

\(X \parallel Y\)

For strings \(X\) and \(Y\), \(X \parallel Y\) is the concatenation of \(X\) and \(Y\). For example, \(\mathtt{11001} \parallel \mathtt{010} = \mathtt{11001010}\).

Two internal functions, \(\mathit{left\_encode}\) and \(\mathit{right\_encode}\), are defined to encode integers as byte strings. Both functions can encode integers up to an extremely large maximum, \(2^{2040}-1\).

\(\mathrm{left\_encode}(x)\) encodes the integer \(x\) as a byte string in a way that can be unambiguously parsed from the beginning of the string by inserting the length of the byte string before the byte string representation of \(x\).

\(\mathrm{right\_encode}(x)\) encodes the integer \(x\) as a byte string in a way that can be unambiguously parsed from the end of the string by inserting the length of the byte string after the byte string representation of \(x\).

Using the function \(\mathit{enc}_8()\) to encode the individual bytes, these two functions are defined as follows:

\(\mathbf{right\_encode}(\boldsymbol{x})\):
Validity Conditions: \(0 \le x < 2^{2040}\)

1. Let \(n\) be the smallest positive integer for which \(2^{8n} > x\).

2. Let \(x_1, x_2, \ldots, x_n\) be the base-256 encoding of \(x\) satisfying:

3. Let \(O_i = \mathrm{enc}_8(x_i)\), for \(i = 1\) to \(n\).

4. Let \(O_{n+1} = \mathrm{enc}_8(n)\).

5. Return \(O = O_1 \parallel O_2 \parallel \ldots \parallel O_n \parallel O_{n+1}\).

\(\mathbf{left\_encode}(\boldsymbol{x})\):
Validity Conditions: \(0 \le x < 2^{2040}\)

1. Let \(n\) be the smallest positive integer for which \(2^{8n} > x\).

2. Let \(x_1, x_2, \ldots, x_n\) be the base-256 encoding of \(x\) satisfying:

3. Let \(O_i = \mathrm{enc}_8(x_i)\), for \(i = 1\) to \(n\).

4. Let \(O_0 = \mathrm{enc}_8(n)\).

5. Return \(O = O_0 \parallel O_1 \parallel \ldots \parallel O_{n-1} \parallel O_n\).

The \(\mathrm{encode\_string}\) function is used to encode bit strings in a way that may be parsed unambiguously from the beginning of the string, \(S\). The function is defined as follows:

\(\mathbf{encode\_string}(\boldsymbol{S})\):
Validity Conditions: \(0 \le \operatorname{len}(S) < 2^{2040}\)

1. Return \(\mathrm{left\_encode}(\operatorname{len}(S)) \parallel S\).

As an example, \(\mathrm{encode\_string}(S)\) where \(S\) is the empty string "" will yield 10000000 00000000.

Note that if the bit string \(S\) is not byte-oriented (i.e., \(\operatorname{len}(S)\) is not a multiple of 8), the bit string returned from \(\mathrm{encode\_string}(S)\) is also not byte-oriented. However, if \(\operatorname{len}(S)\) is a multiple of 8, then the length of the output of \(\mathrm{encode\_string}(S)\) will also be a multiple of 8.

The \(\mathrm{bytepad}(X, w)\) function prepends an encoding of the integer \(w\) to an input string \(X\), then pads the result with zeros until it is a byte string whose length in bytes is a multiple of \(w\). In general, \(\mathrm{bytepad}\) is intended to be used on encoded strings—the byte string \(\mathrm{bytepad}(\mathrm{encode\_string}(S), w)\) can be parsed unambiguously from its beginning, whereas \(\mathrm{bytepad}\) does not provide unambiguous padding for all input strings.

The definition of \(\mathrm{bytepad}()\) is as follows:

\(\mathbf{bytepad}(\boldsymbol{X}, \boldsymbol{w})\):
Validity Conditions: \(w > 0\)

1. \(z = \mathrm{left\_encode}(w) \parallel X\).

2. while \(\operatorname{len}(z) \bmod 8 \ne 0\):
\(z = z \parallel \mathtt{0}\)

3. while \((\operatorname{len}(z)/8) \bmod w \ne 0\):
\(\mathrm{z} = \mathrm{z} \parallel \mathtt{00000000}\)

4. return \(z\).

Let parameters \(a\) and \(b\) be non-negative integers that denote a specific position in a bit string \(X\). Informally, the \(\mathrm{substring}(X, a, b)\) function returns a substring from the bit string \(X\) containing the values at bit positions \(a, a+1, \ldots, b-1\), inclusive. More precisely, the \(\mathrm{substring}\) function operates as defined below. Note that all bit positions in the input and output strings are indexed from zero. Thus, the first bit in a string is in position 0, and the last bit in an \(n\)-bit string is in position \(n-1\).

\(\mathbf{substring}(\boldsymbol{X}, \boldsymbol{a}, \boldsymbol{b})\):

1. If \(a \ge b\) or \(a \ge \operatorname{len}(X)\):
return the empty string.

2. Else if \(b \le \operatorname{len}(X)\):
return the bits of \(X\) from position \(a\) to position \(b-1\), inclusive.

3. Else:
return the bits of \(X\) from position \(a\) to position \(\operatorname{len}(X)-1\), inclusive.

The two variants of cSHAKE—\(\mathrm{cSHAKE128}\) and \(\mathrm{cSHAKE256}\)—are defined in terms of the SHAKE and \(\mathrm{KECCAK}[c]\) functions specified in FIPS 202. \(\mathrm{cSHAKE128}\) provides a 128-bit security strength, while \(\mathrm{cSHAKE256}\) provides a 256-bit security strength.

• \(X\) is the main input bit string. It may be of any length³, including zero.

• \(L\) is an integer representing the requested output length⁴ in bits.

• \(N\) is a function-name bit string, used by NIST to define functions based on cSHAKE. When no function other than cSHAKE is desired, \(N\) is set to the empty string.

• \(S\) is a customization bit string. The user selects this string to define a variant of the function. When no customization is desired, \(S\) is set to the empty string⁵.

When \(N\) and \(S\) are both empty strings, \(\mathrm{cSHAKE}(X, L, N, S)\) is equivalent to SHAKE as defined in FIPS 202. Thus,

³ When a string is specified to be “of any length” in this document, a theoretical limit (e.g., \(2^{2040}-1\) bits) may apply. This limit is imposed by the integer encoding schemes \(\mathrm{left\_encode}\) and \(\mathrm{right\_encode}\), defined in Sec. 2.3.1. Beyond this limit, the string cannot be encoded. In the remainder of this document, absurdly large limits like \(2^{2040}-1\) bits will often be treated interchangeably with no limit at all.

⁴ When the requested output length is zero, i.e., \(L=0\), cSHAKE, KMAC, TupleHash, and ParallelHash return the empty string as the output.

⁵ In computing languages that support default values for parameters, a natural way to implement this function would be to set the default values for \(N\) and \(S\) to empty strings.

cSHAKE is defined in terms of SHAKE or \(\mathrm{KECCAK}[c]\), as follows: it either returns the result of a call to SHAKE (if \(N\) and \(S\) are both empty strings), or returns the result of a call to \(\mathrm{KECCAK}(c)\) with a padded encoding of \(N\) and \(S\) concatenated to the input string \(X\).

\(\mathrm{cSHAKE128}(X, L, N, S)\):
Validity Conditions: \(\mathit{len}(N) < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. If \(N = \text{""}\) and \(S = \text{""}\):
return \(\mathrm{SHAKE128}(X, L)\);

2. Else:
return \(\mathrm{KECCAK}[256](\mathrm{bytepad}(\mathrm{encode\_string}(N) \parallel \mathrm{encode\_string}(S), 168) \parallel X \parallel \mathtt{00}, L)\).

\(\mathrm{cSHAKE256}(X, L, N, S)\):
Validity Conditions: \(\mathit{len}(N) < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. If \(N = \text{""}\) and \(S = \text{""}\):
return \(\mathrm{SHAKE256}(X, L)\);

2. Else:
return \(\mathrm{KECCAK}[512](\mathrm{bytepad}(\mathrm{encode\_string}(N) \parallel \mathrm{encode\_string}(S), 136) \parallel X \parallel \mathtt{00}, L)\).

Note that the numbers 168 and 136 are rates (in bytes) of the \(\mathrm{KECCAK}[256]\) and \(\mathrm{KECCAK}[512]\) sponge functions, respectively; the characters \(\mathtt{00}\) in the Courier New font in these definitions specify two zero bits.

The cSHAKE function includes an input string that may be used to provide a function name (\(N\)). This is intended for use by NIST in defining SHA-3-derived functions, and should only be set to values defined by NIST⁶. This parameter provides a level of domain separation by function name. Users of cSHAKE should not make up their own names—that kind of customization is the purpose of the customization string \(S\), to be discussed in Sec. 3.5. Nonstandard values of \(N\) could cause interoperability problems with future NIST-defined functions.

⁶ NIST will always make the function name \(N\) a byte-oriented value.

The cSHAKE function also includes an input string (\(S\)) to allow users to customize their use of the function. For example, someone using cSHAKE128 to compute a key fingerprint (the hash value for a public key) might use:

\(\mathrm{cSHAKE128}(\mathit{public\_key}, 256, \text{""}, \text{"key fingerprint"})\),

where "key fingerprint" is a customization string \(S\).

\(\mathrm{cSHAKE128}(\mathit{email\_contents}, 256, \text{""}, \text{"email signature"})\),

where "email signature" is the customization string \(S\).

The customization string is intended to avoid a collision between these two cSHAKE values—it will be very difficult for an attacker to somehow force one computation (the email signature) to yield the same result as the other computation (the key fingerprint) if different values of \(S\) are used.

The customization string may be of any length less than \(2^{2040}\); however, implementations may restrict the length of \(S\) that they will accept.

• \(K\) is a key bit string of any length⁷, including zero.

• \(X\) is the main input bit string. It may be of any length, including zero.

• \(L\) is an integer representing the requested output length⁸ in bits.

• \(S\) is an optional customization bit string of any length, including zero. If no customization is desired, \(S\) is set to the empty string.

KMAC concatenates a padded version of the key \(K\) with the input \(X\) and an encoding of the requested output length \(L\). The result is then passed to cSHAKE, along with the requested output length \(L\), the name \(N\) ="KMAC" = 11010010 10110010 10000010 11000010⁹, and the optional customization string \(S\).

\(\mathrm{KMAC128}(K, X, L, S)\):

Validity Conditions: \(\mathit{len}(K) < 2^{2040}\) and \(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(\mathit{newX} = \mathrm{bytepad}(\mathrm{encode\_string}(K), 168) \parallel X \parallel \mathrm{right\_encode}(L)\).

2. return \(\mathrm{cSHAKE128}(\mathit{newX}, L, \text{“KMAC”}, S)\).

⁷ Approved uses of KMAC require the length of \(K\) to be at least the required security strength, as discussed in Sec. 8.4.1.

⁸ Note that there is a limit of \(2^{2040}-1\) bits of output from this function unless the function is used as a XOF, as discussed in Sec. 4.3.1.

\(\mathrm{KMAC256}(K, X, L, S)\):

Validity Conditions: \(\mathit{len}(K) < 2^{2040}\) and \(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(\mathit{newX} = \mathrm{bytepad}(\mathrm{encode\_string}(K), 136) \parallel X \parallel \mathrm{right\_encode}(L)\).

2. return \(\mathrm{cSHAKE256}(\mathit{newX}, L, \text{“KMAC”}, S)\).

Note that the numbers 168 and 136 are rates (in bytes) of the \(\mathrm{KECCAK}[256]\) and \(\mathrm{KECCAK}[512]\) sponge functions, respectively.

When used as a XOF, KMAC is computed by setting the encoded output length to 0, as shown in \(\mathrm{right\_encode}(0)\) in Step 1 of the \(\mathrm{KMACXOF128}(K, X, L, S)\) and \(\mathrm{KMACXOF256}(K, X, L, S)\) pseudocodes below. Conceptually, KMAC in XOF mode produces an infinite-length output string, and the caller simply uses as many bits of the output string as are needed. Truncated outputs of KMAC in XOF mode can be computed by the function \(\mathrm{KMACXOF128}(K, X, L, S)\) or \(\mathrm{KMACXOF256}(K, X, L, S)\) given by the following pseudocode:

\(\mathrm{KMACXOF128}(K, X, L, S)\):

Validity Conditions: \(\mathit{len}(K) < 2^{2040}\) and \(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(\mathit{newX} = \mathrm{bytepad}(\mathrm{encode\_string}(K), 168) \parallel X \parallel \mathrm{right\_encode}(0)\).

2. return \(\mathrm{cSHAKE128}(\mathit{newX}, L, \text{“KMAC”}, S)\).

\(\mathrm{KMACXOF256}(K, X, L, S)\):

Validity Conditions: \(\mathit{len}(K) < 2^{2040}\) and \(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(\mathit{newX} = \mathrm{bytepad}(\mathrm{encode\_string}(K), 136) \parallel X \parallel \mathrm{right\_encode}(0)\).

2. return \(\mathrm{cSHAKE256}(\mathit{newX}, L, \text{“KMAC”}, S)\).

• \(X\) is a tuple of zero or more bit strings, any or all of which may be an empty string.

• \(L\) is an integer representing the requested output length in bits.

• \(S\) is an optional customization bit string of any length, including zero. If no customization is desired, \(S\) is set to the empty string.

TupleHash encodes the sequence of input strings in an unambiguous way, then encodes the requested output length at the end of the string, and passes the result into cSHAKE, along with the function name (\(N\)) of “TupleHash” = 00101010 10101110 00001110 00110110 10100110 00010010 10000110 11001110 00010110, and the optional customization string \(S\).

If \(X\) is a tuple of \(n\) bit strings, let \(X[i]\) be the \(i\)th bit string, numbering from 0. The TupleHash functions are defined in pseudocode as follows:

\(\mathrm{TupleHash128}(X, L, S)\):
Validity Conditions: \(0 \le L < 2^{2040}\) and \(\operatorname{len}(S) < 2^{2040}\)

1. \(z\) = "".

2. \(n\) = the number of input strings in the tuple \(X\).

3. for \(i = 1\) to \(n\):
\(z = z \parallel \mathrm{encode\_string}(X[i])\).

4. \(\mathit{newX} = z \parallel \mathrm{right\_encode}(L)\).

5. return \(\mathrm{cSHAKE128}(\mathit{newX}, L, \text{“TupleHash”}, S)\).

\(\mathrm{TupleHash256}(X, L, S)\):
Validity Conditions: \(0 \le L < 2^{2040}\) and \(\operatorname{len}(S) < 2^{2040}\)

1. \(z\) = "".

2. \(n\) = the number of input strings in the tuple \(X\).

3. for \(i = 1\) to \(n\):
\(z = z \parallel \mathrm{encode\_string}(X[i])\).

4. \(\mathit{newX} = z \parallel \mathrm{right\_encode}(L)\).

5. return \(\mathrm{cSHAKE256}(\mathit{newX}, L, \text{“TupleHash”}, S)\).

When used as a XOF, TupleHash is computed by setting the encoded output length to 0, as shown in \(\mathrm{right\_encode}(0)\) in Step 1 of the \(\mathrm{TupleHashXOF128}(X, L, S)\) and \(\mathrm{TupleHashXOF256}(X, L, S)\) pseudocodes below. Conceptually, TupleHash in XOF mode produces an infinite-length output string, and the caller simply uses as many bits of the output string as are needed. Truncated outputs of TupleHash in XOF mode can be computed by the function \(\mathrm{TupleHashXOF128}(X, L, S)\) or \(\mathrm{TupleHashXOF256}(X, L, S)\) given by the following pseudocode:

\(\mathrm{TupleHashXOF128}(X, L, S)\):
Validity Conditions: \(0 \le L\) and \(\operatorname{len}(S) < 2^{2040}\)

1. \(z\) = "".

2. \(n\) = the number of input strings in the tuple \(X\).

3. for \(i = 1\) to \(n\):
\(z = z \parallel \mathrm{encode\_string}(X[i])\).

4. \(\mathit{newX} = z \parallel \mathrm{right\_encode}(0)\).

5. return \(\mathrm{cSHAKE128}(\mathit{newX}, L, \text{“TupleHash”}, S)\).

\(\mathrm{TupleHashXOF256}(X, L, S)\):
Validity Conditions: \(0 \le L\) and \(\operatorname{len}(S) < 2^{2040}\)

1. \(z\) = "".

2. \(n\) = the number of input strings in the tuple \(X\).

3. for \(i = 1\) to \(n\):
\(z = z \parallel \mathrm{encode\_string}(X[i])\).

4. \(\mathit{newX} = z \parallel \mathrm{right\_encode}(0)\).

5. return \(\mathrm{cSHAKE256}(\mathit{newX}, L, \text{“TupleHash”}, S)\).

• \(X\) is the main input bit string. It may be of any length¹¹, including zero.

• \(B\) is the block size in bytes for parallel hashing. It may be any integer such that \(0 < B < 2^{2040}\).

• \(L\) is an integer representing the requested output length in bits.

• \(S\) is an optional customization bit string of any length, including zero. If no customization is desired, \(S\) is set to the empty string.

ParallelHash divides the input bit string \(X\) into a sequence of contiguous, non-overlapping blocks, each of length \(B\) bytes, and then computes the hash value for each block separately. Finally, these hash values are combined and passed to cSHAKE along with the function name (\(N\)) of "ParallelHash" = 00001010 10000110 01001110 10000110 00110110 00110110 10100110 00110110 00010010 10000110 11001110 00010110, the optional customization string \(S\), and some encoded integer values (as shown below in the pseudocode), to generate the final hash value of the function.

\(\mathrm{ParallelHash128}(X, B, L, S)\):
Validity Conditions: \(0 < B < 2^{2040}\) and \(\lceil \mathit{len}(X)/B \rceil < 2^{2040}\) and \(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(n = \lceil (\mathrm{len}(X)/8) / B \rceil\).

¹¹ Where \(\lceil \mathit{len}(X)/B \rceil < 2^{2040}\) and \(B\) is the block size in bytes as defined in Sec. 6.2. As specified in Footnote 2, NIST will treat such absurdly large limit as interchangeable with having no limit at all.

2. \(z = \mathrm{left\_encode}(B)\).

3. for \(i = 0\) to \(n-1\):
\(z = z \parallel \mathrm{cSHAKE128}(\mathrm{substring}(X, i*B*8, (i+1)*B*8), 256, \text{""}, \text{""})\).

4. \(z = z \parallel \mathrm{right\_encode}(n) \parallel \mathrm{right\_encode}(L)\).

5. \(\mathit{newX} = z\).

6. return \(\mathrm{cSHAKE128}(\mathit{newX}, L, \text{“ParallelHash”}, S)\).

\(\mathrm{ParallelHash256}(X, B, L, S)\):
Validity Conditions: \(0 < B < 2^{2040}\) and \(\lceil \mathit{len}(X)/B \rceil < 2^{2040}\) and \(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(n = \lceil (\mathrm{len}(X)/8) / B \rceil\).

2. \(z = \mathrm{left\_encode}(B)\).

3. for \(i = 0\) to \(n-1\):
\(z = z \parallel \mathrm{cSHAKE256}(\mathrm{substring}(X, i*B*8, (i+1)*B*8), 512, \text{""}, \text{""})\).

4. \(z = z \parallel \mathrm{right\_encode}(n) \parallel \mathrm{right\_encode}(L)\).

5. \(\mathit{newX} = z\).

6. return \(\mathrm{cSHAKE256}(\mathit{newX}, L, \text{“ParallelHash”}, S)\).

When used as a XOF, ParallelHash is computed by setting the encoded output length to 0, as shown in \(\mathrm{right\_encode}(0)\) in Step 1 of the \(\mathrm{ParallelHashXOF128}(X, B, L, S)\) and \(\mathrm{ParallelHashXOF256}(X, B, L, S)\) pseudocodes below. Conceptually, ParallelHash in XOF mode produces an infinite-length output string, and the caller simply uses as many bits of the output string as are needed. Truncated outputs of ParallelHash in XOF mode can be computed by the function \(\mathrm{ParallelHashXOF128}(X, B, L, S)\) or \(\mathrm{ParallelHashXOF256}(X, B, L, S)\) given by the following pseudocode:

\(\mathrm{ParallelHashXOF128}(X, B, L, S)\):
Validity Conditions: \(0 < B < 2^{2040}\) and \(\lceil \mathit{len}(X)/B \rceil < 2^{2040}\) and \(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(n = \lceil (\mathrm{len}(X)/8) / B \rceil\).

2. \(z = \mathrm{left\_encode}(B)\).

3. for \(i = 0\) to \(n-1\):
\(z = z \parallel \mathrm{cSHAKE128}(\mathrm{substring}(X, i*B*8, (i+1)*B*8), 256, \text{""}, \text{""})\).

4. \(z = z \parallel \mathrm{right\_encode}(n) \parallel \mathrm{right\_encode}(0)\).

5. \(\mathit{newX} = z\).

6. return \(\mathrm{cSHAKE128}(\mathit{newX}, L, \text{“ParallelHash”}, S)\).

\(\mathrm{ParallelHashXOF256}(X, B, L, S)\):

Validity Conditions: \(0 < B < 2^{2040}\) and \(\lceil \mathit{len}(X)/B \rceil < 2^{2040}\) and \(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(n = \lceil (\mathrm{len}(X)/8) / B \rceil\).

2. \(z = \mathrm{left\_encode}(B)\).

3. for \(i = 0\) to \(n-1\):
\(z = z \parallel \mathrm{cSHAKE256}(\mathrm{substring}(X, i*B*8, (i+1)*B*8), 512, \text{""}, \text{""})\).

4. \(z = z \parallel \mathrm{right\_encode}(n) \parallel \mathrm{right\_encode}(0)\).

5. \(\mathit{newX} = z\).

6. return \(\mathrm{cSHAKE256}(\mathit{newX}, L, \text{“ParallelHash”}, S)\).

cSHAKE is defined so that all the calls to the underlying \(\mathrm{KECCAK}\text{-}f\) function [1] to accommodate the function name \(N\) and the customization string \(S\) will process an integer multiple of \(r\) bits, where \(r\) is the rate parameter. An implementation can precompute the result of processing this padded block of \(N\) and \(S\) with cSHAKE, and thus, will suffer no performance penalty when reusing the same choices of \(N\) and \(S\) in multiple cSHAKE executions. Since TupleHash and ParallelHash are defined in terms of cSHAKE, this same precomputation is available to implementations of those functions as well.

KMAC can precompute the result of processing \(N\) and \(S\), and the result of processing the key \(K\). Thus, KMAC128 using a fixed, precomputed customization string and key will process an input string as efficiently as SHAKE128.

Specific implementations of ParallelHash are permitted to restrict their implementation to a small subset of the allowed values. For example, it would be acceptable for a particular implementation to only allow a single value of \(B\) if it were only expected to interoperate with another implementation that similarly restricted \(B\) to that same value.

cSHAKE128, KMAC128, TupleHash128, and ParallelHash128 each provide a security strength of 128 bits. This means that, for a given output length \(L\), there is no generic attack on one of these functions requiring less than \(2^{128}\) work that does not also exist for any hash function with the same output length. Similarly, cSHAKE256, KMAC256, TupleHash256, and ParallelHash256 each provides a security strength of 256 bits against generic attacks.

8.2.1 Equivalent Security to SHAKE for Any Legal \(N\) and \(S\)

For a given choice of the function name \(N\) and the customization string \(S\), \(\mathrm{cSHAKE128}(X, L, N, S)\) has exactly the same security properties as \(\mathrm{SHAKE128}(X, L)\); \(\mathrm{cSHAKE256}(X, L, N, S)\) has exactly the same security properties as \(\mathrm{SHAKE256}(X, L)\). There are no "weak" values for \(N\) or \(S\).

8.2.2 Different \(N\) and \(S\) Give Unrelated Outputs

Suppose that \((n1, s1)\) and \((n2, s2)\) are two name and customization string pairs, and either \(n1 \ne n2\), or \(s1 \ne s2\). Furthermore, suppose that \(q1\) and \(q2\) are the lengths of the requested output. Then, \(\mathrm{cSHAKE}(X, q1, n1, s1)\) and \(\mathrm{cSHAKE}(X, q2, n2, s2)\) can be treated as unrelated functions of \(X\). That is, they can be treated as if they were two completely different functions, with output lengths \(q1\) and \(q2\), respectively. This means, for example, that:

• Keys \(k1\) and \(k2\), where \(k1 = \mathrm{cSHAKE}(x1, q1, n1, s1)\), and \(k2 = \mathrm{cSHAKE}(x2, q2, n2, s2)\), and both keys are derived from secret, but related, quantities \(x1\) and \(x2\), will not be susceptible to related key attacks (with complexity less than the claimed security strength of the cSHAKE function.)

• Finding a collision such that \(\mathrm{cSHAKE128}(x1, L, n1, s1) = \mathrm{cSHAKE128}(x2, L, n2, s2)\) will require a computational complexity on the order of \(\min(2^{L/2}, 2^{128})\). Similarly, finding a collision such that \(\mathrm{cSHAKE256}(x1, L, n1, s1) = \mathrm{cSHAKE256}(x2, L, n2, s2)\), will require a computational complexity on the order of \(\min(2^{L/2}, 2^{256})\).

• For any of these functions, using a different customization string gives an unrelated output. Thus, if \(s1 \ne s2\), \(\mathrm{ParallelHash}(X, B, L, s1)\) and \(\mathrm{ParallelHash}(X, B, L, s2)\) are expected to have no particular relationship.

Except when used in XOF mode, KMAC, TupleHash, and ParallelHash have the additional property that, even with the same customization string, blocksize, key, etc., instances of the functions with different output lengths can be treated as unrelated functions of their remaining inputs. Thus, for example, \(\mathrm{ParallelHash}(X, B, q1, S)\) and \(\mathrm{ParallelHash}(X, B, q2, S)\) can be treated as independent hash functions with input \(X\) and output lengths \(q1\) and \(q2\), respectively.

Note that cSHAKE does not share this property. For \(q1 < q2\), \(\mathrm{cSHAKE}(X, q1, N, S)\) is a prefix of \(\mathrm{cSHAKE}(X, q2, N, S)\). This is a property that cSHAKE shares with SHAKE and other XOFs. This property is discussed in more detail in Appendix A.2 of FIPS 202.

A function like cSHAKE128, with a claimed security strength of 128 bits, may be vulnerable to a collision or preimage attack with \(2^{128}\) work regardless of its output length—a longer output does not, in general, improve its security against these attacks. However, a shorter output can make the function more vulnerable to these attacks. With an output of \(L\) bits, a collision attack will require \(\min(2^{L/2}, 2^{128})\) work, and a preimage attack will require at least \(\min(2^{L}, 2^{128})\) work.

For maximum flexibility and usefulness, the KMAC functions are defined for arbitrary-sized output lengths and key lengths (up to \(2^{2040}-1\) bits). However, not all such output and key lengths are secure.

The input key length is the parameter that is most straightforwardly translated into a security strength. Given a small number of known (MAC, plaintext) pairs, an attacker requires at most \(2^{\mathrm{len}(K)}\) operations to find the key \(K\).

Applications of this Recommendation shall not select an input key, \(K\), whose length is less than their required security strength. Guidance for cryptographic algorithm and key-size selection is available in [4].

The output length is another important security parameter for KMAC—it determines the probability that an online guessing attack will succeed in forging a MAC tag. In particular, an attacker will need to submit, on average, \(2^{L}\) invalid (message, MAC) pairs for each successful forgery. Since \(L\) only affects online attacks, a system that uses KMAC for message authentication can mitigate attacks that exploit a short \(L\) by limiting the total number of verification failures allowed under a given key.

When used as a MAC, applications of this Recommendation shall not select an output length \(L\) that is less than 32 bits, and shall only select an output length less than 64 bits after a careful risk analysis is performed.

Appendix A—KMAC, TupleHash, and ParallelHash in Terms of \(\mathrm{KECCAK}[c]\)

FIPS 202 specifies the \(\mathrm{KECCAK}[c]\) function, on which the SHA-3 and SHAKE functions are built. KMAC, TupleHash, and ParallelHash are defined in terms of cSHAKE, as specified in Sec. 3. In this appendix, KMAC, TupleHash, ParallelHash and these functions in XOF mode are defined directly in terms of \(\mathrm{KECCAK}[c]\). These definitions are exactly equivalent to the definitions made in terms of cSHAKE in Secs. 4, 5, and 6.

\(\mathrm{KMAC128}(K, X, L, S)\):

Validity Conditions: \(\mathit{len}(K) < 2^{2040}\) and \(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(\mathit{newX} = \operatorname{bytepad}(\operatorname{encode\_string}(K), 168) \parallel X \parallel \operatorname{right\_encode}(L)\).

2. \(T = \operatorname{bytepad}(\operatorname{encode\_string}(\text{“KMAC”}) \parallel \operatorname{encode\_string}(S), 168)\).

3. return \(\mathrm{KECCAK}[256](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathrm{KMAC256}(K, X, L, S)\):

Validity Conditions: \(\mathit{len}(K) < 2^{2040}\) and \(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(\mathit{newX} = \operatorname{bytepad}(\operatorname{encode\_string}(K), 136) \parallel X \parallel \operatorname{right\_encode}(L)\).

2. \(T = \operatorname{bytepad}(\operatorname{encode\_string}(\text{“KMAC”}) \parallel \operatorname{encode\_string}(S), 136)\).

3. return \(\mathrm{KECCAK}[512](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathrm{KMACXOF128}(K, X, L, S)\):

Validity Conditions: \(\mathit{len}(K) < 2^{2040}\) and \(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(\mathit{newX} = \operatorname{bytepad}(\operatorname{encode\_string}(K), 168) \parallel X \parallel \operatorname{right\_encode}(0)\).

2. \(T = \operatorname{bytepad}(\operatorname{encode\_string}(\text{“KMAC”}) \parallel \operatorname{encode\_string}(S), 168)\).

3. return \(\mathrm{KECCAK}[256](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathrm{KMACXOF256}(K, X, L, S)\):

Validity Conditions: \(\mathit{len}(K) < 2^{2040}\) and \(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(\mathit{newX} = \operatorname{bytepad}(\operatorname{encode\_string}(K), 136) \parallel X \parallel \operatorname{right\_encode}(0)\).

2. \(T = \operatorname{bytepad}(\operatorname{encode\_string}(\text{“KMAC”}) \parallel \operatorname{encode\_string}(S), 136)\).

3. return \(\mathrm{KECCAK}[512](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathrm{TupleHash128}(X, L, S)\):
Validity Conditions: \(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(z = \text{""}\).

2. \(n\) = the number of input strings in the tuple \(X\).

3. for \(i = 1\) to \(n\):
\(z = z \parallel \operatorname{encode\_string}(X[i])\).

4. \(\mathit{newX} = z \parallel \operatorname{right\_encode}(L)\).

5. \(T = \operatorname{bytepad}(\operatorname{encode\_string}(\text{“TupleHash”}) \parallel \operatorname{encode\_string}(S), 168)\).

6. return \(\mathrm{KECCAK}[256](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathrm{TupleHash256}(X, L, S)\):
Validity Conditions: \(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(z = \text{""}\).

2. \(n =\) the number of input strings in the tuple \(X\).

3. for \(i = 1\) to \(n\):

4. \(\mathit{newX} = z \parallel \mathrm{right\_encode}(L)\).

5. \(T = \mathrm{bytepad}(\mathrm{encode\_string}(\text{“TupleHash”}) \parallel \mathrm{encode\_string}(S), 136)\).

6. return \(\mathrm{KECCAK}[512](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathbf{TupleHashXOF128}(X, L, S)\):
Validity Conditions: \(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(z = \text{""}\).

2. \(n =\) the number of input strings in the tuple \(X\).

3. for \(i = 1\) to \(n\):

4. \(\mathit{newX} = z \parallel \mathrm{right\_encode}(0)\).

5. \(T = \mathrm{bytepad}(\mathrm{encode\_string}(\text{“TupleHash”}) \parallel \mathrm{encode\_string}(S), 168)\).

6. return \(\mathrm{KECCAK}[256](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathbf{TupleHashXOF256}(X, L, S)\):
Validity Conditions: \(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(z = \text{""}\).

2. \(n =\) the number of input strings in the tuple \(X\).

3. for \(i = 1\) to \(n\):

4. \(\mathit{newX} = z \parallel \mathrm{right\_encode}(0)\).

5. \(T = \mathrm{bytepad}(\mathrm{encode\_string}(\text{“TupleHash”}) \parallel \mathrm{encode\_string}(S), 136)\).

6. return \(\mathrm{KECCAK}[512](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathbf{ParallelHash128}(X, B, L, S)\):
Validity Conditions: \(0 < B < 2^{2040}\) and \(\lceil \mathit{len}(X)/B \rceil < 2^{2040}\) and
\(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(n = \lceil (\operatorname{len}(X)/8) / B \rceil\).

2. \(z = \mathrm{left\_encode}(B)\).

3. for \(i = 0\) to \(n-1\):

4. \(z = z \parallel \mathrm{right\_encode}(n) \parallel \mathrm{right\_encode}(L)\).

5. \(\mathit{newX} = z\).

6. \(T = \mathrm{bytepad}(\mathrm{encode\_string}(\text{“ParallelHash”}) \parallel \mathrm{encode\_string}(S), 168)\).

7. return \(\mathrm{KECCAK}[256](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathbf{ParallelHash256}(X, B, L, S)\):

Validity Conditions: \(0 < B < 2^{2040}\) and \(\lceil \mathit{len}(X)/B \rceil < 2^{2040}\) and
\(0 \le L < 2^{2040}\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(n = \lceil (\operatorname{len}(X)/8) / B \rceil\).

2. \(z = \mathrm{left\_encode}(B)\).

3. for \(i = 0\) to \(n-1\):

4. \(z = z \parallel \mathrm{right\_encode}(n) \parallel \mathrm{right\_encode}(L)\).

5. \(\mathit{newX} = z\).

6. \(T = \mathrm{bytepad}(\mathrm{encode\_string}(\text{“ParallelHash”}) \parallel \mathrm{encode\_string}(S), 136)\).

7. return \(\mathrm{KECCAK}[512](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathbf{ParallelHashXOF128}(X, B, L, S)\):
Validity Conditions: \(0 < B < 2^{2040}\) and \(\lceil \mathit{len}(X)/B \rceil < 2^{2040}\) and
\(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(n = \lceil (\operatorname{len}(X)/8) / B \rceil\).

2. \(z = \mathrm{left\_encode}(B)\).

3. for \(i = 0\) to \(n-1\):

4. \(z = z \parallel \mathrm{right\_encode}(n) \parallel \mathrm{right\_encode}(0)\).

5. \(\mathit{newX} = z\).

6. \(T = \mathrm{bytepad}(\mathrm{encode\_string}(\text{“ParallelHash”}) \parallel \mathrm{encode\_string}(S), 168)\).

7. return \(\mathrm{KECCAK}[256](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

\(\mathbf{ParallelHashXOF256}(X, B, L, S)\):
Validity Conditions: \(0 < B < 2^{2040}\) and \(\lceil \mathit{len}(X)/B \rceil < 2^{2040}\) and
\(0 \le L\) and \(\mathit{len}(S) < 2^{2040}\)

1. \(n = \lceil (\operatorname{len}(X)/8) / B \rceil\).

2. \(z = \mathrm{left\_encode}(B)\).

3. for \(i = 0\) to \(n-1\):

4. \(z = z \parallel \mathrm{right\_encode}(n) \parallel \mathrm{right\_encode}(0)\).

5. \(\mathit{newX} = z\).

6. \(T = \mathrm{bytepad}(\mathrm{encode\_string}(\text{“ParallelHash”}) \parallel \mathrm{encode\_string}(S), 136)\).

7. return \(\mathrm{KECCAK}[512](T \parallel \mathit{newX} \parallel \mathtt{00}, L)\).

XOFs, PRFs, and hash functions with variable-length output like cSHAKE, KMAC, TupleHash, and ParallelHash can easily be used to generate an integer \(X\) within the range \(0 \le X < R\), denoted as \(0..R-1\) in this document, for any positive integer \(R\). The following method will produce outputs that are extremely close to a uniform distribution over that range, assuming that the above functions approximate a uniform random variable.

In order to hash into an integer in the range \(0..R-1\), do the following:

1. Let \(k = \lceil \lg(R) \rceil + 128\).

2. Call the hash function with a requested length of at least \(k\) bits. Let the resulting bit string be \(Z\).

3. Let \(N = \mathit{bits\_to\_integer}(Z) \bmod R\), where the \(\mathit{bits\_to\_integer}\) function is defined below.

At the end of this process, the variable \(N\) contains an integer that is extremely close to being uniformly distributed in the range \(0..R-1\). For any possible output value \(t\) such that \(0 \le t < R\), the following statement is true¹².

In other words, the output of this process will have a very small bias. No value will be very much more or less likely to appear as the result of this process than it would have been, had an integer been selected uniformly at random from the integers between 0 and \(R-1\), inclusive.

This technique can be applied to SHAKE, cSHAKE, KMAC, TupleHash, or ParallelHash whenever an integer within a specific range is needed, so long as it is acceptable for the resulting integer to have this very small deviation from the uniform distribution on the integers \(\{0, 1, \ldots, R-1\}\).

The \(\mathit{bits\_to\_integer}\) function converts a bit string to an integer as follows:

\(\mathbf{bits\_to\_integer}(b_1, b_2, \ldots, b_n)\):

1. Let \((b_1, b_2, \ldots, b_n)\) be the bits of a bit string from the most significant to the least significant bits.

2. \(x = \sum_{i=1}^{n} 2^{(n-i)} b_i\).

3. Return \((x)\).

¹² In fact, the bound is slightly tighter than this. If \(w\) = the length of the bitstring \(Z\) in bits (\(w \ge \lceil \lg(R) \rceil + 128\)), then \(|\mathrm{Prob}(N=t) - 1/R| \le 2^{-\mathrm{w}}\).