diff options
Diffstat (limited to 'doc/rfc/rfc9106.txt')
| -rw-r--r-- | doc/rfc/rfc9106.txt | 975 |
1 files changed, 975 insertions, 0 deletions
diff --git a/doc/rfc/rfc9106.txt b/doc/rfc/rfc9106.txt new file mode 100644 index 0000000..f950898 --- /dev/null +++ b/doc/rfc/rfc9106.txt @@ -0,0 +1,975 @@ + + + + +Internet Research Task Force (IRTF) A. Biryukov +Request for Comments: 9106 D. Dinu +Category: Informational University of Luxembourg +ISSN: 2070-1721 D. Khovratovich + ABDK Consulting + S. Josefsson + SJD AB + September 2021 + + + Argon2 Memory-Hard Function for Password Hashing and Proof-of-Work + Applications + +Abstract + + This document describes the Argon2 memory-hard function for password + hashing and proof-of-work applications. We provide an implementer- + oriented description with test vectors. The purpose is to simplify + adoption of Argon2 for Internet protocols. This document is a + product of the Crypto Forum Research Group (CFRG) in the IRTF. + +Status of This Memo + + This document is not an Internet Standards Track specification; it is + published for informational purposes. + + This document is a product of the Internet Research Task Force + (IRTF). The IRTF publishes the results of Internet-related research + and development activities. These results might not be suitable for + deployment. This RFC represents the consensus of the Crypto Forum + Research Group of the Internet Research Task Force (IRTF). Documents + approved for publication by the IRSG are not candidates for any level + of Internet Standard; see Section 2 of RFC 7841. + + Information about the current status of this document, any errata, + and how to provide feedback on it may be obtained at + https://www.rfc-editor.org/info/rfc9106. + +Copyright Notice + + Copyright (c) 2021 IETF Trust and the persons identified as the + document authors. All rights reserved. + + This document is subject to BCP 78 and the IETF Trust's Legal + Provisions Relating to IETF Documents + (https://trustee.ietf.org/license-info) in effect on the date of + publication of this document. Please review these documents + carefully, as they describe your rights and restrictions with respect + to this document. + +Table of Contents + + 1. Introduction + 1.1. Requirements Language + 2. Notation and Conventions + 3. Argon2 Algorithm + 3.1. Argon2 Inputs and Outputs + 3.2. Argon2 Operation + 3.3. Variable-Length Hash Function H' + 3.4. Indexing + 3.4.1. Computing the 32-Bit Values J_1 and J_2 + 3.4.2. Mapping J_1 and J_2 to Reference Block Index [l][z] + 3.5. Compression Function G + 3.6. Permutation P + 4. Parameter Choice + 5. Test Vectors + 5.1. Argon2d Test Vectors + 5.2. Argon2i Test Vectors + 5.3. Argon2id Test Vectors + 6. IANA Considerations + 7. Security Considerations + 7.1. Security as a Hash Function and KDF + 7.2. Security against Time-Space Trade-off Attacks + 7.3. Security for Time-Bounded Defenders + 7.4. Recommendations + 8. References + 8.1. Normative References + 8.2. Informative References + Acknowledgements + Authors' Addresses + +1. Introduction + + This document describes the Argon2 [ARGON2ESP] memory-hard function + for password hashing and proof-of-work applications. We provide an + implementer-oriented description with test vectors. The purpose is + to simplify adoption of Argon2 for Internet protocols. This document + corresponds to version 1.3 of the Argon2 hash function. + + Argon2 is a memory-hard function [HARD]. It is a streamlined design. + It aims at the highest memory-filling rate and effective use of + multiple computing units, while still providing defense against + trade-off attacks. Argon2 is optimized for the x86 architecture and + exploits the cache and memory organization of the recent Intel and + AMD processors. Argon2 has one primary variant, Argon2id, and two + supplementary variants, Argon2d and Argon2i. Argon2d uses data- + dependent memory access, which makes it suitable for cryptocurrencies + and proof-of-work applications with no threats from side-channel + timing attacks. Argon2i uses data-independent memory access, which + is preferred for password hashing and password-based key derivation. + Argon2id works as Argon2i for the first half of the first pass over + the memory and as Argon2d for the rest, thus providing both side- + channel attack protection and brute-force cost savings due to time- + memory trade-offs. Argon2i makes more passes over the memory to + protect from trade-off attacks [AB15]. + + Argon2id MUST be supported by any implementation of this document, + whereas Argon2d and Argon2i MAY be supported. + + Argon2 is also a mode of operation over a fixed-input-length + compression function G and a variable-input-length hash function H. + Even though Argon2 can be potentially used with an arbitrary function + H, as long as it provides outputs up to 64 bytes, the BLAKE2b + function [BLAKE2] is used in this document. + + For further background and discussion, see the Argon2 paper [ARGON2]. + + This document represents the consensus of the Crypto Forum Research + Group (CFRG). + +1.1. Requirements Language + + The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", + "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and + "OPTIONAL" in this document are to be interpreted as described in + BCP 14 [RFC2119] [RFC8174] when, and only when, they appear in all + capitals, as shown here. + +2. Notation and Conventions + + x^y integer x multiplied by itself integer y times + + a*b multiplication of integer a and integer b + + c-d subtraction of integer d from integer c + + E_f variable E with subscript index f + + g / h integer g divided by integer h. The result is a + rational number. + + I(j) function I evaluated at j + + K || L string K concatenated with string L + + a XOR b bitwise exclusive-or between bitstrings a and b + + a mod b remainder of integer a modulo integer b, always in + range [0, b-1] + + a >>> n rotation of 64-bit string a to the right by n bits + + trunc(a) the 64-bit value, truncated to the 32 least + significant bits + + floor(a) the largest integer not bigger than a + + ceil(a) the smallest integer not smaller than a + + extract(a, i) the i-th set of 32 bits from bitstring a, starting + from 0-th + + |A| the number of elements in set A + + LE32(a) 32-bit integer a converted to a byte string in little + endian (for example, 123456 (decimal) is 40 E2 01 00) + + LE64(a) 64-bit integer a converted to a byte string in little + endian (for example, 123456 (decimal) is 40 E2 01 00 + 00 00 00 00) + + int32(s) 32-bit string s is converted to a non-negative integer + in little endian + + int64(s) 64-bit string s is converted to a non-negative integer + in little endian + + length(P) the byte length of string P expressed as 32-bit + integer + + ZERO(P) the P-byte zero string + +3. Argon2 Algorithm + +3.1. Argon2 Inputs and Outputs + + Argon2 has the following input parameters: + + * Message string P, which is a password for password hashing + applications. It MUST have a length not greater than 2^(32)-1 + bytes. + + * Nonce S, which is a salt for password hashing applications. It + MUST have a length not greater than 2^(32)-1 bytes. 16 bytes is + RECOMMENDED for password hashing. The salt SHOULD be unique for + each password. + + * Degree of parallelism p determines how many independent (but + synchronizing) computational chains (lanes) can be run. It MUST + be an integer value from 1 to 2^(24)-1. + + * Tag length T MUST be an integer number of bytes from 4 to 2^(32)- + 1. + + * Memory size m MUST be an integer number of kibibytes from 8*p to + 2^(32)-1. The actual number of blocks is m', which is m rounded + down to the nearest multiple of 4*p. + + * Number of passes t (used to tune the running time independently of + the memory size) MUST be an integer number from 1 to 2^(32)-1. + + * Version number v MUST be one byte 0x13. + + * Secret value K is OPTIONAL. If used, it MUST have a length not + greater than 2^(32)-1 bytes. + + * Associated data X is OPTIONAL. If used, it MUST have a length not + greater than 2^(32)-1 bytes. + + * Type y MUST be 0 for Argon2d, 1 for Argon2i, or 2 for Argon2id. + + The Argon2 output, or "tag", is a string T bytes long. + +3.2. Argon2 Operation + + Argon2 uses an internal compression function G with two 1024-byte + inputs, a 1024-byte output, and an internal hash function H^x(), with + x being its output length in bytes. Here, H^x() applied to string A + is the BLAKE2b ([BLAKE2], Section 3.3) function, which takes + (d,ll,kk=0,nn=x) as parameters, where d is A padded to a multiple of + 128 bytes and ll is the length of d in bytes. The compression + function G is based on its internal permutation. A variable-length + hash function H' built upon H is also used. G is described in + Section 3.5, and H' is described in Section 3.3. + + The Argon2 operation is as follows. + + 1. Establish H_0 as the 64-byte value as shown below. If K, X, or S + has zero length, it is just absent, but its length field remains. + + H_0 = H^(64)(LE32(p) || LE32(T) || LE32(m) || LE32(t) || + LE32(v) || LE32(y) || LE32(length(P)) || P || + LE32(length(S)) || S || LE32(length(K)) || K || + LE32(length(X)) || X) + + Figure 1: H_0 Generation + + 2. Allocate the memory as m' 1024-byte blocks, where m' is derived + as: + + m' = 4 * p * floor (m / 4p) + + Figure 2: Memory Allocation + + For p lanes, the memory is organized in a matrix B[i][j] of + blocks with p rows (lanes) and q = m' / p columns. + + 3. Compute B[i][0] for all i ranging from (and including) 0 to (not + including) p. + + B[i][0] = H'^(1024)(H_0 || LE32(0) || LE32(i)) + + Figure 3: Lane Starting Blocks + + 4. Compute B[i][1] for all i ranging from (and including) 0 to (not + including) p. + + B[i][1] = H'^(1024)(H_0 || LE32(1) || LE32(i)) + + Figure 4: Second Lane Blocks + + 5. Compute B[i][j] for all i ranging from (and including) 0 to (not + including) p and for all j ranging from (and including) 2 to (not + including) q. The computation MUST proceed slicewise + (Section 3.4): first, blocks from slice 0 are computed for all + lanes (in an arbitrary order of lanes), then blocks from slice 1 + are computed, etc. The block indices l and z are determined for + each i, j differently for Argon2d, Argon2i, and Argon2id. + + B[i][j] = G(B[i][j-1], B[l][z]) + + Figure 5: Further Block Generation + + 6. If the number of passes t is larger than 1, we repeat step 5. We + compute B[i][0] and B[i][j] for all i raging from (and including) + 0 to (not including) p and for all j ranging from (and including) + 1 to (not including) q. However, blocks are computed differently + as the old value is XORed with the new one: + + B[i][0] = G(B[i][q-1], B[l][z]) XOR B[i][0]; + B[i][j] = G(B[i][j-1], B[l][z]) XOR B[i][j]. + + Figure 6: Further Passes + + 7. After t steps have been iterated, the final block C is computed + as the XOR of the last column: + + C = B[0][q-1] XOR B[1][q-1] XOR ... XOR B[p-1][q-1] + + Figure 7: Final Block + + 8. The output tag is computed as H'^T(C). + +3.3. Variable-Length Hash Function H' + + Let V_i be a 64-byte block and W_i be its first 32 bytes. Then we + define function H' as follows: + + if T <= 64 + H'^T(A) = H^T(LE32(T)||A) + else + r = ceil(T/32)-2 + V_1 = H^(64)(LE32(T)||A) + V_2 = H^(64)(V_1) + ... + V_r = H^(64)(V_{r-1}) + V_{r+1} = H^(T-32*r)(V_{r}) + H'^T(X) = W_1 || W_2 || ... || W_r || V_{r+1} + + Figure 8: Function H' for Tag and Initial Block Computations + +3.4. Indexing + + To enable parallel block computation, we further partition the memory + matrix into SL = 4 vertical slices. The intersection of a slice and + a lane is called a segment, which has a length of q/SL. Segments of + the same slice can be computed in parallel and do not reference + blocks from each other. All other blocks can be referenced. + + slice 0 slice 1 slice 2 slice 3 + ___/\___ ___/\___ ___/\___ ___/\___ + / \ / \ / \ / \ + +----------+----------+----------+----------+ + | | | | | > lane 0 + +----------+----------+----------+----------+ + | | | | | > lane 1 + +----------+----------+----------+----------+ + | | | | | > lane 2 + +----------+----------+----------+----------+ + | ... ... ... | ... + +----------+----------+----------+----------+ + | | | | | > lane p - 1 + +----------+----------+----------+----------+ + + Figure 9: Single-Pass Argon2 with p Lanes and 4 Slices + +3.4.1. Computing the 32-Bit Values J_1 and J_2 + +3.4.1.1. Argon2d + + J_1 is given by the first 32 bits of block B[i][j-1], while J_2 is + given by the next 32 bits of block B[i][j-1]: + + J_1 = int32(extract(B[i][j-1], 0)) + J_2 = int32(extract(B[i][j-1], 1)) + + Figure 10: Deriving J1,J2 in Argon2d + +3.4.1.2. Argon2i + + For each segment, we do the following. First, we compute the value Z + as: + + Z= ( LE64(r) || LE64(l) || LE64(sl) || LE64(m') || + LE64(t) || LE64(y) ) + + Figure 11: Input to Compute J1,J2 in Argon2i + + where + + r: the pass number + l: the lane number + sl: the slice number + m': the total number of memory blocks + t: the total number of passes + y: the Argon2 type (0 for Argon2d, 1 for Argon2i, 2 for Argon2id) + + Then we compute: + + q/(128*SL) 1024-byte values + G(ZERO(1024),G(ZERO(1024), + Z || LE64(1) || ZERO(968) )), + G(ZERO(1024),G(ZERO(1024), + Z || LE64(2) || ZERO(968) )),... , + G(ZERO(1024),G(ZERO(1024), + Z || LE64(q/(128*SL)) || ZERO(968) )), + + which are partitioned into q/(SL) 8-byte values X, which are viewed + as X1||X2 and converted to J_1=int32(X1) and J_2=int32(X2). + + The values r, l, sl, m', t, y, and i are represented as 8 bytes in + little endian. + +3.4.1.3. Argon2id + + If the pass number is 0 and the slice number is 0 or 1, then compute + J_1 and J_2 as for Argon2i, else compute J_1 and J_2 as for Argon2d. + +3.4.2. Mapping J_1 and J_2 to Reference Block Index [l][z] + + The value of l = J_2 mod p gives the index of the lane from which the + block will be taken. For the first pass (r=0) and the first slice + (sl=0), the block is taken from the current lane. + + The set W contains the indices that are referenced according to the + following rules: + + 1. If l is the current lane, then W includes the indices of all + blocks in the last SL - 1 = 3 segments computed and finished, as + well as the blocks computed in the current segment in the current + pass excluding B[i][j-1]. + + 2. If l is not the current lane, then W includes the indices of all + blocks in the last SL - 1 = 3 segments computed and finished in + lane l. If B[i][j] is the first block of a segment, then the + very last index from W is excluded. + + Then take a block from W with a nonuniform distribution over [0, |W|) + using the following mapping: + + J_1 -> |W|(1 - J_1^2 / 2^(64)) + + Figure 12: Computing J1 + + To avoid floating point computation, the following approximation is + used: + + x = J_1^2 / 2^(32) + y = (|W| * x) / 2^(32) + zz = |W| - 1 - y + + Figure 13: Computing J1, Part 2 + + Then take the zz-th index from W; it will be the z value for the + reference block index [l][z]. + +3.5. Compression Function G + + The compression function G is built upon the BLAKE2b-based + transformation P. P operates on the 128-byte input, which can be + viewed as eight 16-byte registers: + + P(A_0, A_1, ... ,A_7) = (B_0, B_1, ... ,B_7) + + Figure 14: Blake Round Function P + + The compression function G(X, Y) operates on two 1024-byte blocks X + and Y. It first computes R = X XOR Y. Then R is viewed as an 8x8 + matrix of 16-byte registers R_0, R_1, ... , R_63. Then P is first + applied to each row, and then to each column to get Z: + + ( Q_0, Q_1, Q_2, ... , Q_7) <- P( R_0, R_1, R_2, ... , R_7) + ( Q_8, Q_9, Q_10, ... , Q_15) <- P( R_8, R_9, R_10, ... , R_15) + ... + (Q_56, Q_57, Q_58, ... , Q_63) <- P(R_56, R_57, R_58, ... , R_63) + ( Z_0, Z_8, Z_16, ... , Z_56) <- P( Q_0, Q_8, Q_16, ... , Q_56) + ( Z_1, Z_9, Z_17, ... , Z_57) <- P( Q_1, Q_9, Q_17, ... , Q_57) + ... + ( Z_7, Z_15, Z 23, ... , Z_63) <- P( Q_7, Q_15, Q_23, ... , Q_63) + + Figure 15: Core of Compression Function G + + Finally, G outputs Z XOR R: + + G: (X, Y) -> R -> Q -> Z -> Z XOR R + + +---+ +---+ + | X | | Y | + +---+ +---+ + | | + ---->XOR<---- + --------| + | \ / + | +---+ + | | R | + | +---+ + | | + | \ / + | P rowwise + | | + | \ / + | +---+ + | | Q | + | +---+ + | | + | \ / + | P columnwise + | | + | \ / + | +---+ + | | Z | + | +---+ + | | + | \ / + ------>XOR + | + \ / + + Figure 16: Argon2 Compression Function G + +3.6. Permutation P + + Permutation P is based on the round function of BLAKE2b. The eight + 16-byte inputs S_0, S_1, ... , S_7 are viewed as a 4x4 matrix of + 64-bit words, where S_i = (v_{2*i+1} || v_{2*i}): + + v_0 v_1 v_2 v_3 + v_4 v_5 v_6 v_7 + v_8 v_9 v_10 v_11 + v_12 v_13 v_14 v_15 + + Figure 17: Matrix Element Labeling + + It works as follows: + + GB(v_0, v_4, v_8, v_12) + GB(v_1, v_5, v_9, v_13) + GB(v_2, v_6, v_10, v_14) + GB(v_3, v_7, v_11, v_15) + + GB(v_0, v_5, v_10, v_15) + GB(v_1, v_6, v_11, v_12) + GB(v_2, v_7, v_8, v_13) + GB(v_3, v_4, v_9, v_14) + + Figure 18: Feeding Matrix Elements to GB + + GB(a, b, c, d) is defined as follows: + + a = (a + b + 2 * trunc(a) * trunc(b)) mod 2^(64) + d = (d XOR a) >>> 32 + c = (c + d + 2 * trunc(c) * trunc(d)) mod 2^(64) + b = (b XOR c) >>> 24 + + a = (a + b + 2 * trunc(a) * trunc(b)) mod 2^(64) + d = (d XOR a) >>> 16 + c = (c + d + 2 * trunc(c) * trunc(d)) mod 2^(64) + b = (b XOR c) >>> 63 + + Figure 19: Details of GB + + The modular additions in GB are combined with 64-bit multiplications. + Multiplications are the only difference from the original BLAKE2b + design. This choice is done to increase the circuit depth and thus + the running time of ASIC implementations, while having roughly the + same running time on CPUs thanks to parallelism and pipelining. + +4. Parameter Choice + + Argon2d is optimized for settings where the adversary does not get + regular access to system memory or CPU, i.e., they cannot run side- + channel attacks based on the timing information, nor can they recover + the password much faster using garbage collection. These settings + are more typical for backend servers and cryptocurrency minings. For + practice, we suggest the following settings: + + * Cryptocurrency mining, which takes 0.1 seconds on a 2 GHz CPU + using 1 core -- Argon2d with 2 lanes and 250 MB of RAM. + + Argon2id is optimized for more realistic settings, where the + adversary can possibly access the same machine, use its CPU, or mount + cold-boot attacks. We suggest the following settings: + + * Backend server authentication, which takes 0.5 seconds on a 2 GHz + CPU using 4 cores -- Argon2id with 8 lanes and 4 GiB of RAM. + + * Key derivation for hard-drive encryption, which takes 3 seconds on + a 2 GHz CPU using 2 cores -- Argon2id with 4 lanes and 6 GiB of + RAM. + + * Frontend server authentication, which takes 0.5 seconds on a 2 GHz + CPU using 2 cores -- Argon2id with 4 lanes and 1 GiB of RAM. + + We recommend the following procedure to select the type and the + parameters for practical use of Argon2. + + 1. If a uniformly safe option that is not tailored to your + application or hardware is acceptable, select Argon2id with t=1 + iteration, p=4 lanes, m=2^(21) (2 GiB of RAM), 128-bit salt, and + 256-bit tag size. This is the FIRST RECOMMENDED option. + + 2. If much less memory is available, a uniformly safe option is + Argon2id with t=3 iterations, p=4 lanes, m=2^(16) (64 MiB of + RAM), 128-bit salt, and 256-bit tag size. This is the SECOND + RECOMMENDED option. + + 3. Otherwise, start with selecting the type y. If you do not know + the difference between the types or you consider side-channel + attacks to be a viable threat, choose Argon2id. + + 4. Select p=4 lanes. + + 5. Figure out the maximum amount of memory that each call can + afford and translate it to the parameter m. + + 6. Figure out the maximum amount of time (in seconds) that each + call can afford. + + 7. Select the salt length. A length of 128 bits is sufficient for + all applications but can be reduced to 64 bits in the case of + space constraints. + + 8. Select the tag length. A length of 128 bits is sufficient for + most applications, including key derivation. If longer keys are + needed, select longer tags. + + 9. If side-channel attacks are a viable threat or if you're + uncertain, enable the memory-wiping option in the library call. + + 10. Run the scheme of type y, memory m, and p lanes using a + different number of passes t. Figure out the maximum t such + that the running time does not exceed the affordable time. If + it even exceeds for t = 1, reduce m accordingly. + + 11. Use Argon2 with determined values m, p, and t. + +5. Test Vectors + + This section contains test vectors for Argon2. + +5.1. Argon2d Test Vectors + + We provide test vectors with complete outputs (tags). For the + convenience of developers, we also provide some interim variables -- + concretely, the first and last memory blocks of each pass. + + ======================================= + Argon2d version number 19 + ======================================= + Memory: 32 KiB + Passes: 3 + Parallelism: 4 lanes + Tag length: 32 bytes + Password[32]: 01 01 01 01 01 01 01 01 + 01 01 01 01 01 01 01 01 + 01 01 01 01 01 01 01 01 + 01 01 01 01 01 01 01 01 + Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 + Secret[8]: 03 03 03 03 03 03 03 03 + Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04 + Pre-hashing digest: b8 81 97 91 a0 35 96 60 + bb 77 09 c8 5f a4 8f 04 + d5 d8 2c 05 c5 f2 15 cc + db 88 54 91 71 7c f7 57 + 08 2c 28 b9 51 be 38 14 + 10 b5 fc 2e b7 27 40 33 + b9 fd c7 ae 67 2b ca ac + 5d 17 90 97 a4 af 31 09 + + After pass 0: + Block 0000 [ 0]: db2fea6b2c6f5c8a + Block 0000 [ 1]: 719413be00f82634 + Block 0000 [ 2]: a1e3f6dd42aa25cc + Block 0000 [ 3]: 3ea8efd4d55ac0d1 + ... + Block 0031 [124]: 28d17914aea9734c + Block 0031 [125]: 6a4622176522e398 + Block 0031 [126]: 951aa08aeecb2c05 + Block 0031 [127]: 6a6c49d2cb75d5b6 + + After pass 1: + Block 0000 [ 0]: d3801200410f8c0d + Block 0000 [ 1]: 0bf9e8a6e442ba6d + Block 0000 [ 2]: e2ca92fe9c541fcc + Block 0000 [ 3]: 6269fe6db177a388 + ... + Block 0031 [124]: 9eacfcfbdb3ce0fc + Block 0031 [125]: 07dedaeb0aee71ac + Block 0031 [126]: 074435fad91548f4 + Block 0031 [127]: 2dbfff23f31b5883 + + After pass 2: + Block 0000 [ 0]: 5f047b575c5ff4d2 + Block 0000 [ 1]: f06985dbf11c91a8 + Block 0000 [ 2]: 89efb2759f9a8964 + Block 0000 [ 3]: 7486a73f62f9b142 + ... + Block 0031 [124]: 57cfb9d20479da49 + Block 0031 [125]: 4099654bc6607f69 + Block 0031 [126]: f142a1126075a5c8 + Block 0031 [127]: c341b3ca45c10da5 + Tag: 51 2b 39 1b 6f 11 62 97 + 53 71 d3 09 19 73 42 94 + f8 68 e3 be 39 84 f3 c1 + a1 3a 4d b9 fa be 4a cb + +5.2. Argon2i Test Vectors + + ======================================= + Argon2i version number 19 + ======================================= + Memory: 32 KiB + Passes: 3 + Parallelism: 4 lanes + Tag length: 32 bytes + Password[32]: 01 01 01 01 01 01 01 01 + 01 01 01 01 01 01 01 01 + 01 01 01 01 01 01 01 01 + 01 01 01 01 01 01 01 01 + Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 + Secret[8]: 03 03 03 03 03 03 03 03 + Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04 + Pre-hashing digest: c4 60 65 81 52 76 a0 b3 + e7 31 73 1c 90 2f 1f d8 + 0c f7 76 90 7f bb 7b 6a + 5c a7 2e 7b 56 01 1f ee + ca 44 6c 86 dd 75 b9 46 + 9a 5e 68 79 de c4 b7 2d + 08 63 fb 93 9b 98 2e 5f + 39 7c c7 d1 64 fd da a9 + + After pass 0: + Block 0000 [ 0]: f8f9e84545db08f6 + Block 0000 [ 1]: 9b073a5c87aa2d97 + Block 0000 [ 2]: d1e868d75ca8d8e4 + Block 0000 [ 3]: 349634174e1aebcc + ... + Block 0031 [124]: 975f596583745e30 + Block 0031 [125]: e349bdd7edeb3092 + Block 0031 [126]: b751a689b7a83659 + Block 0031 [127]: c570f2ab2a86cf00 + + After pass 1: + Block 0000 [ 0]: b2e4ddfcf76dc85a + Block 0000 [ 1]: 4ffd0626c89a2327 + Block 0000 [ 2]: 4af1440fff212980 + Block 0000 [ 3]: 1e77299c7408505b + ... + Block 0031 [124]: e4274fd675d1e1d6 + Block 0031 [125]: 903fffb7c4a14c98 + Block 0031 [126]: 7e5db55def471966 + Block 0031 [127]: 421b3c6e9555b79d + + After pass 2: + Block 0000 [ 0]: af2a8bd8482c2f11 + Block 0000 [ 1]: 785442294fa55e6d + Block 0000 [ 2]: 9256a768529a7f96 + Block 0000 [ 3]: 25a1c1f5bb953766 + ... + Block 0031 [124]: 68cf72fccc7112b9 + Block 0031 [125]: 91e8c6f8bb0ad70d + Block 0031 [126]: 4f59c8bd65cbb765 + Block 0031 [127]: 71e436f035f30ed0 + Tag: c8 14 d9 d1 dc 7f 37 aa + 13 f0 d7 7f 24 94 bd a1 + c8 de 6b 01 6d d3 88 d2 + 99 52 a4 c4 67 2b 6c e8 + +5.3. Argon2id Test Vectors + + ======================================= + Argon2id version number 19 + ======================================= + Memory: 32 KiB, Passes: 3, + Parallelism: 4 lanes, Tag length: 32 bytes + Password[32]: 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 + 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 + Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 + Secret[8]: 03 03 03 03 03 03 03 03 + Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04 + Pre-hashing digest: 28 89 de 48 7e b4 2a e5 00 c0 00 7e d9 25 2f + 10 69 ea de c4 0d 57 65 b4 85 de 6d c2 43 7a 67 b8 54 6a 2f 0a + cc 1a 08 82 db 8f cf 74 71 4b 47 2e 94 df 42 1a 5d a1 11 2f fa + 11 43 43 70 a1 e9 97 + + After pass 0: + Block 0000 [ 0]: 6b2e09f10671bd43 + Block 0000 [ 1]: f69f5c27918a21be + Block 0000 [ 2]: dea7810ea41290e1 + Block 0000 [ 3]: 6787f7171870f893 + ... + Block 0031 [124]: 377fa81666dc7f2b + Block 0031 [125]: 50e586398a9c39c8 + Block 0031 [126]: 6f732732a550924a + Block 0031 [127]: 81f88b28683ea8e5 + + After pass 1: + Block 0000 [ 0]: 3653ec9d01583df9 + Block 0000 [ 1]: 69ef53a72d1e1fd3 + Block 0000 [ 2]: 35635631744ab54f + Block 0000 [ 3]: 599512e96a37ab6e + ... + Block 0031 [124]: 4d4b435cea35caa6 + Block 0031 [125]: c582210d99ad1359 + Block 0031 [126]: d087971b36fd6d77 + Block 0031 [127]: a55222a93754c692 + + After pass 2: + Block 0000 [ 0]: 942363968ce597a4 + Block 0000 [ 1]: a22448c0bdad5760 + Block 0000 [ 2]: a5f80662b6fa8748 + Block 0000 [ 3]: a0f9b9ce392f719f + ... + Block 0031 [124]: d723359b485f509b + Block 0031 [125]: cb78824f42375111 + Block 0031 [126]: 35bc8cc6e83b1875 + Block 0031 [127]: 0b012846a40f346a + Tag: 0d 64 0d f5 8d 78 76 6c 08 c0 37 a3 4a 8b 53 c9 d0 + 1e f0 45 2d 75 b6 5e b5 25 20 e9 6b 01 e6 59 + +6. IANA Considerations + + This document has no IANA actions. + +7. Security Considerations + +7.1. Security as a Hash Function and KDF + + The collision and preimage resistance levels of Argon2 are equivalent + to those of the underlying BLAKE2b hash function. To produce a + collision, 2^(256) inputs are needed. To find a preimage, 2^(512) + inputs must be tried. + + The KDF security is determined by the key length and the size of the + internal state of hash function H'. To distinguish the output of the + keyed Argon2 from random, a minimum of (2^(128),2^length(K)) calls to + BLAKE2b are needed. + +7.2. Security against Time-Space Trade-off Attacks + + Time-space trade-offs allow computing a memory-hard function storing + fewer memory blocks at the cost of more calls to the internal + compression function. The advantage of trade-off attacks is measured + in the reduction factor to the time-area product, where memory and + extra compression function cores contribute to the area and time is + increased to accommodate the recomputation of missed blocks. A high + reduction factor may potentially speed up the preimage search. + + The best-known attack on the 1-pass and 2-pass Argon2i is the low- + storage attack described in [CBS16], which reduces the time-area + product (using the peak memory value) by the factor of 5. The best + attack on Argon2i with 3 passes or more is described in [AB16], with + the reduction factor being a function of memory size and the number + of passes (e.g., for 1 gibibyte of memory, a reduction factor of 3 + for 3 passes, 2.5 for 4 passes, 2 for 6 passes). The reduction + factor grows by about 0.5 with every doubling of the memory size. To + completely prevent time-space trade-offs from [AB16], the number of + passes MUST exceed the binary logarithm of memory minus 26. + Asymptotically, the best attack on 1-pass Argon2i is given in [BZ17], + with maximal advantage of the adversary upper bounded by + O(m^(0.233)), where m is the number of blocks. This attack is also + asymptotically optimal as [BZ17] also proves the upper bound on any + attack is O(m^(0.25)). + + The best trade-off attack on t-pass Argon2d is the ranking trade-off + attack, which reduces the time-area product by the factor of 1.33. + + The best attack on Argon2id can be obtained by complementing the best + attack on the 1-pass Argon2i with the best attack on a multi-pass + Argon2d. Thus, the best trade-off attack on 1-pass Argon2id is the + combined low-storage attack (for the first half of the memory) and + the ranking attack (for the second half), which generate the factor + of about 2.1. The best trade-off attack on t-pass Argon2id is the + ranking trade-off attack, which reduces the time-area product by the + factor of 1.33. + +7.3. Security for Time-Bounded Defenders + + A bottleneck in a system employing the password hashing function is + often the function latency rather than memory costs. A rational + defender would then maximize the brute-force costs for the attacker + equipped with a list of hashes, salts, and timing information for + fixed computing time on the defender's machine. The attack cost + estimates from [AB16] imply that for Argon2i, 3 passes is almost + optimal for most reasonable memory sizes; for Argon2d and Argon2id, 1 + pass maximizes the attack costs for the constant defender time. + +7.4. Recommendations + + The Argon2id variant with t=1 and 2 GiB memory is the FIRST + RECOMMENDED option and is suggested as a default setting for all + environments. This setting is secure against side-channel attacks + and maximizes adversarial costs on dedicated brute-force hardware. + The Argon2id variant with t=3 and 64 MiB memory is the SECOND + RECOMMENDED option and is suggested as a default setting for memory- + constrained environments. + +8. References + +8.1. Normative References + + [BLAKE2] Saarinen, M-J., Ed. and J-P. Aumasson, "The BLAKE2 + Cryptographic Hash and Message Authentication Code (MAC)", + RFC 7693, DOI 10.17487/RFC7693, November 2015, + <https://www.rfc-editor.org/info/rfc7693>. + + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, + DOI 10.17487/RFC2119, March 1997, + <https://www.rfc-editor.org/info/rfc2119>. + + [RFC8174] Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC + 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, + May 2017, <https://www.rfc-editor.org/info/rfc8174>. + +8.2. Informative References + + [AB15] Biryukov, A. and D. Khovratovich, "Tradeoff Cryptanalysis + of Memory-Hard Functions", ASIACRYPT 2015, + DOI 10.1007/978-3-662-48800-3_26, December 2015, + <https://eprint.iacr.org/2015/227.pdf>. + + [AB16] Alwen, J. and J. Blocki, "Efficiently Computing Data- + Independent Memory-Hard Functions", CRYPTO 2016, + DOI 10.1007/978-3-662-53008-5_9, March 2016, + <https://eprint.iacr.org/2016/115.pdf>. + + [ARGON2] Biryukov, A., Dinu, D., and D. Khovratovich, "Argon2: the + memory-hard function for password hashing and other + applications", March 2017, + <https://www.cryptolux.org/images/0/0d/Argon2.pdf>. + + [ARGON2ESP] + Biryukov, A., Dinu, D., and D. Khovratovich, "Argon2: New + Generation of Memory-Hard Functions for Password Hashing + and Other Applications", Euro SnP 2016, + DOI 10.1109/EuroSP.2016.31, March 2016, + <https://www.cryptolux.org/images/d/d0/Argon2ESP.pdf>. + + [BZ17] Blocki, J. and S. Zhou, "On the Depth-Robustness and + Cumulative Pebbling Cost of Argon2i", TCC 2017, + DOI 10.1007/978-3-319-70500-2_15, May 2017, + <https://eprint.iacr.org/2017/442.pdf>. + + [CBS16] Boneh, D., Corrigan-Gibbs, H., and S. Schechter, "Balloon + Hashing: A Memory-Hard Function Providing Provable + Protection Against Sequential Attacks", ASIACRYPT 2016, + DOI 10.1007/978-3-662-53887-6_8, May 2017, + <https://eprint.iacr.org/2016/027.pdf>. + + [HARD] Alwen, J. and V. Serbinenko, "High Parallel Complexity + Graphs and Memory-Hard Functions", STOC '15, + DOI 10.1145/2746539.2746622, June 2015, + <https://eprint.iacr.org/2014/238.pdf>. + +Acknowledgements + + We greatly thank the following individuals who helped in preparing + and reviewing this document: Jean-Philippe Aumasson, Samuel Neves, + Joel Alwen, Jeremiah Blocki, Bill Cox, Arnold Reinhold, Solar + Designer, Russ Housley, Stanislav Smyshlyaev, Kenny Paterson, Alexey + Melnikov, and Gwynne Raskind. + + The work described in this document was done before Daniel Dinu + joined Intel, while he was at the University of Luxembourg. + +Authors' Addresses + + Alex Biryukov + University of Luxembourg + + Email: alex.biryukov@uni.lu + + + Daniel Dinu + University of Luxembourg + + Email: daniel.dinu@intel.com + + + Dmitry Khovratovich + ABDK Consulting + + Email: khovratovich@gmail.com + + + Simon Josefsson + SJD AB + + Email: simon@josefsson.org + URI: http://josefsson.org/ |