idnits 2.17.1 draft-irtf-cfrg-argon2-09.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 21, 2019) is 1617 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 285 -- Looks like a reference, but probably isn't: '1' on line 285 -- Looks like a reference, but probably isn't: '32' on line 725 -- Looks like a reference, but probably isn't: '16' on line 727 -- Looks like a reference, but probably isn't: '8' on line 728 -- Looks like a reference, but probably isn't: '12' on line 729 -- Looks like a reference, but probably isn't: '124' on line 764 -- Looks like a reference, but probably isn't: '125' on line 765 -- Looks like a reference, but probably isn't: '126' on line 766 -- Looks like a reference, but probably isn't: '127' on line 767 Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 CFRG A. Biryukov 3 Internet-Draft D. Dinu 4 Intended status: Informational University of Luxembourg 5 Expires: May 24, 2020 D. Khovratovich 6 ABDK Consulting 7 S. Josefsson 8 SJD AB 9 November 21, 2019 11 The memory-hard Argon2 password hash and proof-of-work function 12 draft-irtf-cfrg-argon2-09 14 Abstract 16 This document describes the Argon2 memory-hard function for password 17 hashing and proof-of-work applications. We provide an implementer- 18 oriented description with test vectors. The purpose is to simplify 19 adoption of Argon2 for Internet protocols. This document is a 20 product of the Crypto Forum Research Group (CFRG) in the IRTF. 22 Status of This Memo 24 This Internet-Draft is submitted in full conformance with the 25 provisions of BCP 78 and BCP 79. 27 Internet-Drafts are working documents of the Internet Engineering 28 Task Force (IETF). Note that other groups may also distribute 29 working documents as Internet-Drafts. The list of current Internet- 30 Drafts is at https://datatracker.ietf.org/drafts/current/. 32 Internet-Drafts are draft documents valid for a maximum of six months 33 and may be updated, replaced, or obsoleted by other documents at any 34 time. It is inappropriate to use Internet-Drafts as reference 35 material or to cite them other than as "work in progress." 37 This Internet-Draft will expire on May 24, 2020. 39 Copyright Notice 41 Copyright (c) 2019 IETF Trust and the persons identified as the 42 document authors. All rights reserved. 44 This document is subject to BCP 78 and the IETF Trust's Legal 45 Provisions Relating to IETF Documents 46 (https://trustee.ietf.org/license-info) in effect on the date of 47 publication of this document. Please review these documents 48 carefully, as they describe your rights and restrictions with respect 49 to this document. Code Components extracted from this document must 50 include Simplified BSD License text as described in Section 4.e of 51 the Trust Legal Provisions and are provided without warranty as 52 described in the Simplified BSD License. 54 Table of Contents 56 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 57 2. Notation and Conventions . . . . . . . . . . . . . . . . . . 3 58 3. Argon2 Algorithm . . . . . . . . . . . . . . . . . . . . . . 4 59 3.1. Argon2 Inputs and Outputs . . . . . . . . . . . . . . . . 4 60 3.2. Argon2 Operation . . . . . . . . . . . . . . . . . . . . 5 61 3.3. Variable-length hash function H' . . . . . . . . . . . . 7 62 3.4. Indexing . . . . . . . . . . . . . . . . . . . . . . . . 7 63 3.4.1. Getting the 32-bit values J_1 and J_2 . . . . . . . . 8 64 3.4.2. Mapping J_1 and J_2 to reference block index . . . . 8 65 3.5. Compression function G . . . . . . . . . . . . . . . . . 9 66 3.6. Permutation P . . . . . . . . . . . . . . . . . . . . . . 11 67 4. Parameter Choice . . . . . . . . . . . . . . . . . . . . . . 12 68 5. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 13 69 5.1. Argon2d Test Vectors . . . . . . . . . . . . . . . . . . 13 70 5.2. Argon2i Test Vectors . . . . . . . . . . . . . . . . . . 14 71 5.3. Argon2id Test Vectors . . . . . . . . . . . . . . . . . . 16 72 6. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 17 73 7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 74 8. Security Considerations . . . . . . . . . . . . . . . . . . . 17 75 8.1. Security as hash function and KDF . . . . . . . . . . . . 17 76 8.2. Security against time-space tradeoff attacks . . . . . . 17 77 8.3. Security for time-bounded defenders . . . . . . . . . . . 18 78 8.4. Recommendations . . . . . . . . . . . . . . . . . . . . . 18 79 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 18 80 9.1. Normative References . . . . . . . . . . . . . . . . . . 18 81 9.2. Informative References . . . . . . . . . . . . . . . . . 19 82 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 19 84 1. Introduction 86 This document describes the Argon2 [ARGON2ESP] memory-hard function 87 for password hashing and proof-of-work applications. We provide an 88 implementer oriented description with test vectors. The purpose is 89 to simplify adoption of Argon2 for Internet protocols. This document 90 corresponds to version 1.3 of the Argon2 hash function. 92 Argon2 summarizes the state of the art in the design of memory-hard 93 functions [HARD]. It is a streamlined and simple design. It aims at 94 the highest memory filling rate and effective use of multiple 95 computing units, while still providing defense against tradeoff 96 attacks. Argon2 is optimized for the x86 architecture and exploits 97 the cache and memory organization of the recent Intel and AMD 98 processors. Argon2 has one primary variant: Argon2id, and two 99 supplementary variants: Argon2d and Argon2i. Argon2d uses data- 100 dependent memory access, which makes it suitable for cryptocurrencies 101 and proof-of-work applications with no threats from side-channel 102 timing attacks. Argon2i uses data-independent memory access, which 103 is preferred for password hashing and password-based key derivation. 104 Argon2id works as Argon2i for the first half of the first iteration 105 over the memory, and as Argon2d for the rest, thus providing both 106 side-channel attack protection and brute-force cost savings due to 107 time-memory tradeoffs. Argon2i makes more passes over the memory to 108 protect from tradeoff attacks [AB15]. 110 Argon2 can be viewed as a mode of operation over a fixed-input-length 111 compression function G and a variable-input-length hash function H. 112 Even though Argon2 can be potentially used with arbitrary function H, 113 as long as it provides outputs up to 64 bytes, in this document it 114 MUST be BLAKE2b [BLAKE2]. 116 For further background and discussion, see the Argon2 paper [ARGON2]. 118 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 119 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 120 document are to be interpreted as described in RFC 2119 [RFC2119]. 122 This document represents the consensus of the Crypto Forum Research 123 Group (CFRG). 125 2. Notation and Conventions 127 x^y --- integer x multiplied by itself integer y times 129 a*b --- multiplication of integer a and integer b 131 c-d --- substraction of integer c with integer d 133 E_f --- variable E with subscript index f 135 g / h --- integer g divided by integer h. The result is rational 136 number 138 I(j) --- function I evaluated on integer parameter j 140 K || L --- string K concatenated with string L 142 a XOR b --- bitwise exclusive-or between bitstrings a and b 143 a mod b --- remainder of integer a modulo integer b, always in range 144 [0, b-1] 146 a >>> n --- rotation of 64-bit string a to the right by n bits 148 trunc(a) --- the 64-bit value, truncated to the 32 least significant 149 bits 151 floor(a) --- the largest integer not bigger than a 153 ceil(a) --- the smallest integer not smaller than a 155 extract(a, i) --- the i-th set of 32-bits from bitstring a, starting 156 from 0-th 158 |A| --- the number of elements in set A 160 LE32(a) --- 32-bit integer a converted to bytestring in little 161 endian. Example: 123456 (decimal) is 40 E2 01 00. 163 LE64(a) --- 64-bit integer a converted to bytestring in little 164 endian. Example: 123456 (decimal) is 40 E2 01 00 00 00 00 00. 166 int32(s) --- 32-bit string s is converted to non-negative integer in 167 little endian. 169 int64(s) --- 64-bit string s is converted to non-negative integer in 170 little endian. 172 length(P) --- the bytelength of string P expressed as 32-bit integer 174 3. Argon2 Algorithm 176 3.1. Argon2 Inputs and Outputs 178 Argon2 has the following input parameters: 180 o Message string P, which is a password for password hashing 181 applications. MUST have length from 0 to 2^(32) - 1 bytes. 183 o Nonce S, which is a salt for password hashing applications. MUST 184 have length not greater than 2^(32)-1 bytes. 16 bytes is 185 RECOMMENDED for password hashing. Salt SHOULD be unique for each 186 password. 188 o Degree of parallelism p determines how many independent (but 189 synchronizing) computational chains (lanes) can be run. It MUST 190 be an integer value from 1 to 2^(24)-1. 192 o Tag length T MUST be an integer number of bytes from 4 to 2^(32)- 193 1. 195 o Memory size m MUST be an integer number of kibibytes from 8*p to 196 2^(32)-1. The actual number of blocks is m', which is m rounded 197 down to the nearest multiple of 4*p. 199 o Number of iterations t (used to tune the running time 200 independently of the memory size) MUST be an integer number from 1 201 to 2^(32)-1. 203 o Version number v MUST be one byte 0x13. 205 o Secret value K is OPTIONAL. If used, it MUST have length not 206 greater than 2^(32)-1 bytes. 208 o Associated data X is OPTIONAL. If used, it MUST have length not 209 greater than 2^(32)-1 bytes. 211 o Type y of Argon2: MUST be 0 for Argon2d, 1 for Argon2i, 2 for 212 Argon2id. 214 The Argon2 output, or "tag" is a string T bytes long. 216 3.2. Argon2 Operation 218 Argon2 uses an internal compression function G with two 1024-byte 219 inputs and a 1024-byte output, and an internal hash function H^x() 220 with x being its output length in bytes. Here H^x() applied to 221 string A is the BLAKE2b [BLAKE2] function, which takes 222 (d,|dd|,kk=0,nn=x) as parameters where d is A padded to a multiple of 223 128 bytes and partitioned into 128-byte blocks. The compression 224 function G is based on its internal permutation. A variable-length 225 hash function H' built upon H is also used. G is described in 226 Section Section 3.5 and H' is described in Section Section 3.3. 228 The Argon2 operation is as follows. 230 1. Establish H_0 as the 64-byte value as shown below. 232 H_0 = H^(64)(LE32(p) || LE32(T) || LE32(m) || LE32(t) || 233 LE32(v) || LE32(y) || LE32(length(P)) || P || 234 LE32(length(S)) || S || LE32(length(K)) || K || 235 LE32(length(X)) || X) 237 H_0 generation 239 2. Allocate the memory as m' 1024-byte blocks where m' is derived 240 as: 242 m' = 4 * p * floor (m / 4p) 244 Memory allocation 246 For p lanes, the memory is organized in a matrix B[i][j] of 247 blocks with p rows (lanes) and q = m' / p columns. 249 3. Compute B[i][0] for all i ranging from (and including) 0 to (not 250 including) p. 252 B[i][0] = H'^(128)(H_0 || LE32(0) || LE32(i)) 254 Lane starting blocks 256 4. Compute B[i][1] for all i ranging from (and including) 0 to (not 257 including) p. 259 B[i][1] = H'^(128)(H_0 || LE32(1) || LE32(i)) 261 Second lane blocks 263 5. Compute B[i][j] for all i ranging from (and including) 0 to (not 264 including) p, and for all j ranging from (and including) 2) to 265 (not including) q. The block indices l and z are determined for 266 each i, j differently for Argon2d, Argon2i, and Argon2id 267 (Section Section 3.4). 269 B[i][j] = G(B[i][j-1], B[l][z]) 271 Further block generation 273 6. If the number of iterations t is larger than 1, we repeat the 274 steps however replacing the computations with the following 275 expression: 277 B[i][0] = G(B[i][q-1], B[l][z]) 278 B[i][j] = G(B[i][j-1], B[l][z]) 280 Further passes 282 7. After t steps have been iterated, the final block C is computed 283 as the XOR of the last column: 285 C = B[0][q-1] XOR B[1][q-1] XOR ... XOR B[p-1][q-1] 287 Final block 289 8. The output tag is computed as H'^T(C). 291 3.3. Variable-length hash function H' 293 Let V_i be a 64-byte block, and W_i be its first 32 bytes. Then we 294 define: 296 if T <= 64 297 H'^T(A) = H^T(LE32(T)||A) 298 else 299 r = ceil(T/32)-2 300 V_1 = H^(64)(LE32(T)||A) 301 V_2 = H^(64)(V_1) 302 ... 303 V_r = H^(64)(V_{r-1}) 304 V_{r+1} = H^(T-32*r)(V_{r}) 305 H'^T(X) = W_1 || W_2 || ... || W_r || V_{r+1} 307 Tag computation 309 3.4. Indexing 311 To enable parallel block computation, we further partition the memory 312 matrix into S = 4 vertical slices. The intersection of a slice and a 313 lane is a segment of length q/S. Segments of the same slice can be 314 computed in parallel and do not reference blocks from each other. 315 All other blocks can be referenced. 317 slice 0 slice 1 slice 2 slice 3 318 ___/\___ ___/\___ ___/\___ ___/\___ 319 / \ / \ / \ / \ 320 +----------+----------+----------+----------+ 321 | | | | | > lane 0 322 +----------+----------+----------+----------+ 323 | | | | | > lane 1 324 +----------+----------+----------+----------+ 325 | | | | | > lane 2 326 +----------+----------+----------+----------+ 327 | ... ... ... | ... 328 +----------+----------+----------+----------+ 329 | | | | | > lane p - 1 330 +----------+----------+----------+----------+ 332 Single-pass Argon2 with p lanes and 4 slices 334 3.4.1. Getting the 32-bit values J_1 and J_2 336 3.4.1.1. Argon2d 338 J_1 is given by the first 32 bits of block B[i][j-1], while J_2 is 339 given by the next 32-bits of block B[i][j-1]: 341 J_1 = int32(extract(B[i][j-1], 1)) 342 J_2 = int32(extract(B[i][j-1], 2)) 344 Deriving J1,J2 in Argon2d 346 3.4.1.2. Argon2i 348 Each application of the 2-round compression function G in the counter 349 mode gives 128 64-bit values X, which are viewed as X1||X2 and 350 converted to J_1=int32(X1) and J_2=int32(X2). The first input to G 351 is the all zero block and the second input to G is constructed as 352 follows: 354 ( LE64(r) || LE64(l) || LE64(s) || LE64(m') || 355 LE64(t) || LE64(y) || LE64(i) || ZERO ), where 357 r -- the pass number 358 l -- the lane number 359 s -- the slice number 360 m' -- the total number of memory blocks 361 t -- the total number of passes 362 y -- the Argon2 type (0 for Argon2d, 363 1 for Argon2i, 2 for Argon2id) 364 i -- the counter (starts from 1 in each segment) 365 ZERO -- the 968-byte zero string. 367 Input to compute J1,J2 in Argon2i 369 The values r, l, s, m', t, x, i are represented as 8 bytes in little- 370 endian. 372 3.4.1.3. Argon2id 374 If the pass number is 0 and the slice number is 0 or 1, then compute 375 J_1 and J_2 as for Argon2i, else compute J_1 and J_2 as for Argon2d. 377 3.4.2. Mapping J_1 and J_2 to reference block index 379 The value of l = J_2 mod p gives the index of the lane from which the 380 block will be taken. For the firt pass (r=0) and the first slice 381 (s=0) the block is taken from the current lane. 383 The set W contains the indices that can be referenced according to 384 the following rules: 386 1. If l is the current lane, then W includes the indices of all 387 blocks in the last S - 1 = 3 segments computed and finished, as 388 well as the blocks computed in the current segment in the current 389 pass excluding B[i][j-1]. 391 2. If l is not the current lane, then W includes the indices of all 392 blocks in the last S - 1 = 3 segments computed and finished in 393 lane l. If B[i][j] is the first block of a segment, then the 394 very last index from W is excluded. 396 We are going to take a block from W with a non-uniform distribution 397 over [0, |W|) using the mapping 399 J_1 -> |W|(1 - J_1^2 / 2^(64)) 401 Computing J1 403 To avoid floating point computation, the following approximation is 404 used: 406 x = J_1^2 / 2^(32) 407 y = (|W| * x) / 2^(32) 408 z = |W| - 1 - y 410 Computing J1, part 2 412 The value of z gives the reference block index in W. 414 3.5. Compression function G 416 Compression function G is built upon the BLAKE2b round function P. P 417 operates on the 128-byte input, which can be viewed as 8 16-byte 418 registers: 420 P(A_0, A_1, ... ,A_7) = (B_0, B_1, ... ,B_7) 422 Blake round function P 424 Compression function G(X, Y) operates on two 1024-byte blocks X and 425 Y. It first computes R = X XOR Y. Then R is viewed as a 8x8 matrix 426 of 16-byte registers R_0, R_1, ... , R_63. Then P is first applied 427 to each row, and then to each column to get Z: 429 ( Q_0, Q_1, Q_2, ... , Q_7) <- P( R_0, R_1, R_2, ... , R_7) 430 ( Q_8, Q_9, Q_10, ... , Q_15) <- P( R_8, R_9, R_10, ... , R_15) 431 ... 432 (Q_56, Q_57, Q_58, ... , Q_63) <- P(R_56, R_57, R_58, ... , R_63) 433 ( Z_0, Z_8, Z_16, ... , Z_56) <- P( Q_0, Q_8, Q_16, ... , Q_56) 434 ( Z_1, Z_9, Z_17, ... , Z_57) <- P( Q_1, Q_9, Q_17, ... , Q_57) 435 ... 436 ( Z_7, Z_15, Z 23, ... , Z_63) <- P( Q_7, Q_15, Q_23, ... , Q_63) 438 Core of compression function G 440 Finally, G outputs Z XOR R: 442 G: (X, Y) -> R -> Q -> Z -> Z XOR R 444 +---+ +---+ 445 | X | | Y | 446 +---+ +---+ 447 | | 448 ---->XOR<---- 449 --------| 450 | \ / 451 | +---+ 452 | | R | 453 | +---+ 454 | | 455 | \ / 456 | P rowwise 457 | | 458 | \ / 459 | +---+ 460 | | Q | 461 | +---+ 462 | | 463 | \ / 464 | P columnwise 465 | | 466 | \ / 467 | +---+ 468 | | Z | 469 | +---+ 470 | | 471 | \ / 472 ------>XOR 473 | 474 \ / 476 Argon2 compression function G. 478 3.6. Permutation P 480 Permutation P is based on the round function of BLAKE2b. The 8 481 16-byte inputs S_0, S_1, ... , S_7 are viewed as a 4x4 matrix of 482 64-bit words, where S_i = (v_{2*i+1} || v_{2*i}): 484 v_0 v_1 v_2 v_3 485 v_4 v_5 v_6 v_7 486 v_8 v_9 v_10 v_11 487 v_12 v_13 v_14 v_15 489 Matrix element labeling 491 It works as follows: 493 GB(v_0, v_4, v_8, v_12) 494 GB(v_1, v_5, v_9, v_13) 495 GB(v_2, v_6, v_10, v_14) 496 GB(v_3, v_7, v_11, v_15) 498 GB(v_0, v_5, v_10, v_15) 499 GB(v_1, v_6, v_11, v_12) 500 GB(v_2, v_7, v_8, v_13) 501 GB(v_3, v_4, v_9, v_14) 503 Feeding matrix elements to GB 505 GB(a, b, c, d) is defined as follows: 507 a = (a + b + 2 * trunc(a) * trunc(b)) mod 2^(64) 508 d = (d XOR a) >>> 32 509 c = (c + d + 2 * trunc(c) * trunc(d)) mod 2^(64) 510 b = (b XOR c) >>> 24 512 a = (a + b + 2 * trunc(a) * trunc(b)) mod 2^(64) 513 d = (d XOR a) >>> 16 514 c = (c + d + 2 * trunc(c) * trunc(d)) mod 2^(64) 515 b = (b XOR c) >>> 63 517 Details of GB 519 The modular additions in GB are combined with 64-bit multiplications. 520 Multiplications are the only difference to the original BLAKE2b 521 design. This choice is done to increase the circuit depth and thus 522 the running time of ASIC implementations, while having roughly the 523 same running time on CPUs thanks to parallelism and pipelining. 525 4. Parameter Choice 527 Argon2d is optimized for settings where the adversary does not get 528 regular access to system memory or CPU, i.e. he can not run side- 529 channel attacks based on the timing information, nor he can recover 530 the password much faster using garbage collection. These settings 531 are more typical for backend servers and cryptocurrency minings. For 532 practice we suggest the following settings: 534 o Cryptocurrency mining, that takes 0.1 seconds on a 2 Ghz CPU using 535 1 core -- Argon2d with 2 lanes and 250 MB of RAM. 537 Argon2id is optimized for more realistic settings, where the 538 adversary possibly can access the same machine, use its CPU or mount 539 cold-boot attacks. We suggest the following settings: 541 o Backend server authentication, that takes 0.5 seconds on a 2 GHz 542 CPU using 4 cores -- Argon2id with 8 lanes and 4 GiB of RAM. 544 o Key derivation for hard-drive encryption, that takes 3 seconds on 545 a 2 GHz CPU using 2 cores - Argon2id with 4 lanes and 6 GiB of 546 RAM. 548 o Frontend server authentication, that takes 0.5 seconds on a 2 GHz 549 CPU using 2 cores - Argon2id with 4 lanes and 1 GiB of RAM. 551 We recommend the following procedure to select the type and the 552 parameters for practical use of Argon2. 554 1. Select the type y. If you do not know the difference between 555 them or you consider side-channel attacks as viable threat, 556 choose Argon2id. 558 2. Figure out the maximum number h of threads that can be initiated 559 by each call to Argon2. 561 3. Figure out the maximum amount m of memory that each call can 562 afford. 564 4. Figure out the maximum amount x of time (in seconds) that each 565 call can afford. 567 5. Select the salt length. 128 bits is sufficient for all 568 applications, but can be reduced to 64 bits in the case of space 569 constraints. 571 6. Select the tag length. 128 bits is sufficient for most 572 applications, including key derivation. If longer keys are 573 needed, select longer tags. 575 7. If side-channel attacks are a viable threat, or if you're 576 uncertain, enable the memory wiping option in the library call. 578 8. Run the scheme of type y, memory m and h lanes and threads, using 579 different number of passes t. Figure out the maximum t such that 580 the running time does not exceed x. If it exceeds x even for t = 581 1, reduce m accordingly. 583 9. Hash all the passwords with the just determined values m, h, and 584 t. 586 5. Test Vectors 588 This section contains test vectors for Argon2. 590 5.1. Argon2d Test Vectors 592 We provide test vectors with complete outputs (tags). For the 593 convenience of developers, we also provide some interim variables, 594 concretely, first and last memory blocks of each pass. 596 ======================================= 597 Argon2d version number 19 598 ======================================= 599 Memory: 32 KiB 600 Iterations: 3 601 Parallelism: 4 lanes 602 Tag length: 32 bytes 603 Password[32]: 01 01 01 01 01 01 01 01 604 01 01 01 01 01 01 01 01 605 01 01 01 01 01 01 01 01 606 01 01 01 01 01 01 01 01 607 Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 608 Secret[8]: 03 03 03 03 03 03 03 03 609 Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04 610 Pre-hashing digest: b8 81 97 91 a0 35 96 60 611 bb 77 09 c8 5f a4 8f 04 612 d5 d8 2c 05 c5 f2 15 cc 613 db 88 54 91 71 7c f7 57 614 08 2c 28 b9 51 be 38 14 615 10 b5 fc 2e b7 27 40 33 616 b9 fd c7 ae 67 2b ca ac 617 5d 17 90 97 a4 af 31 09 619 After pass 0: 620 Block 0000 [ 0]: db2fea6b2c6f5c8a 621 Block 0000 [ 1]: 719413be00f82634 622 Block 0000 [ 2]: a1e3f6dd42aa25cc 623 Block 0000 [ 3]: 3ea8efd4d55ac0d1 624 ... 625 Block 0031 [124]: 28d17914aea9734c 626 Block 0031 [125]: 6a4622176522e398 627 Block 0031 [126]: 951aa08aeecb2c05 628 Block 0031 [127]: 6a6c49d2cb75d5b6 630 After pass 1: 631 Block 0000 [ 0]: d3801200410f8c0d 632 Block 0000 [ 1]: 0bf9e8a6e442ba6d 633 Block 0000 [ 2]: e2ca92fe9c541fcc 634 Block 0000 [ 3]: 6269fe6db177a388 635 ... 636 Block 0031 [124]: 9eacfcfbdb3ce0fc 637 Block 0031 [125]: 07dedaeb0aee71ac 638 Block 0031 [126]: 074435fad91548f4 639 Block 0031 [127]: 2dbfff23f31b5883 641 After pass 2: 642 Block 0000 [ 0]: 5f047b575c5ff4d2 643 Block 0000 [ 1]: f06985dbf11c91a8 644 Block 0000 [ 2]: 89efb2759f9a8964 645 Block 0000 [ 3]: 7486a73f62f9b142 646 ... 647 Block 0031 [124]: 57cfb9d20479da49 648 Block 0031 [125]: 4099654bc6607f69 649 Block 0031 [126]: f142a1126075a5c8 650 Block 0031 [127]: c341b3ca45c10da5 651 Tag: 51 2b 39 1b 6f 11 62 97 652 53 71 d3 09 19 73 42 94 653 f8 68 e3 be 39 84 f3 c1 654 a1 3a 4d b9 fa be 4a cb 656 5.2. Argon2i Test Vectors 658 ======================================= 659 Argon2i version number 19 660 ======================================= 661 Memory: 32 KiB 662 Iterations: 3 663 Parallelism: 4 lanes 664 Tag length: 32 bytes 665 Password[32]: 01 01 01 01 01 01 01 01 666 01 01 01 01 01 01 01 01 667 01 01 01 01 01 01 01 01 668 01 01 01 01 01 01 01 01 669 Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 670 Secret[8]: 03 03 03 03 03 03 03 03 671 Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04 672 Pre-hashing digest: c4 60 65 81 52 76 a0 b3 673 e7 31 73 1c 90 2f 1f d8 674 0c f7 76 90 7f bb 7b 6a 675 5c a7 2e 7b 56 01 1f ee 676 ca 44 6c 86 dd 75 b9 46 677 9a 5e 68 79 de c4 b7 2d 678 08 63 fb 93 9b 98 2e 5f 679 39 7c c7 d1 64 fd da a9 681 After pass 0: 682 Block 0000 [ 0]: f8f9e84545db08f6 683 Block 0000 [ 1]: 9b073a5c87aa2d97 684 Block 0000 [ 2]: d1e868d75ca8d8e4 685 Block 0000 [ 3]: 349634174e1aebcc 686 ... 687 Block 0031 [124]: 975f596583745e30 688 Block 0031 [125]: e349bdd7edeb3092 689 Block 0031 [126]: b751a689b7a83659 690 Block 0031 [127]: c570f2ab2a86cf00 692 After pass 1: 693 Block 0000 [ 0]: b2e4ddfcf76dc85a 694 Block 0000 [ 1]: 4ffd0626c89a2327 695 Block 0000 [ 2]: 4af1440fff212980 696 Block 0000 [ 3]: 1e77299c7408505b 697 ... 698 Block 0031 [124]: e4274fd675d1e1d6 699 Block 0031 [125]: 903fffb7c4a14c98 700 Block 0031 [126]: 7e5db55def471966 701 Block 0031 [127]: 421b3c6e9555b79d 703 After pass 2: 704 Block 0000 [ 0]: af2a8bd8482c2f11 705 Block 0000 [ 1]: 785442294fa55e6d 706 Block 0000 [ 2]: 9256a768529a7f96 707 Block 0000 [ 3]: 25a1c1f5bb953766 708 ... 709 Block 0031 [124]: 68cf72fccc7112b9 710 Block 0031 [125]: 91e8c6f8bb0ad70d 711 Block 0031 [126]: 4f59c8bd65cbb765 712 Block 0031 [127]: 71e436f035f30ed0 713 Tag: c8 14 d9 d1 dc 7f 37 aa 714 13 f0 d7 7f 24 94 bd a1 715 c8 de 6b 01 6d d3 88 d2 716 99 52 a4 c4 67 2b 6c e8 718 5.3. Argon2id Test Vectors 720 ======================================= 721 Argon2id version number 19 722 ======================================= 723 Memory: 32 KiB, Iterations: 3, 724 Parallelism: 4 lanes, Tag length: 32 bytes 725 Password[32]: 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 726 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 727 Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 728 Secret[8]: 03 03 03 03 03 03 03 03 729 Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04 730 Pre-hashing digest: 28 89 de 48 7e b4 2a e5 00 c0 00 7e d9 25 2f 731 10 69 ea de c4 0d 57 65 b4 85 de 6d c2 43 7a 67 b8 54 6a 2f 0a 732 cc 1a 08 82 db 8f cf 74 71 4b 47 2e 94 df 42 1a 5d a1 11 2f fa 733 11 43 43 70 a1 e9 97 735 After pass 0: 736 Block 0000 [ 0]: 6b2e09f10671bd43 737 Block 0000 [ 1]: f69f5c27918a21be 738 Block 0000 [ 2]: dea7810ea41290e1 739 Block 0000 [ 3]: 6787f7171870f893 740 ... 741 Block 0031 [124]: 377fa81666dc7f2b 742 Block 0031 [125]: 50e586398a9c39c8 743 Block 0031 [126]: 6f732732a550924a 744 Block 0031 [127]: 81f88b28683ea8e5 746 After pass 1: 747 Block 0000 [ 0]: 3653ec9d01583df9 748 Block 0000 [ 1]: 69ef53a72d1e1fd3 749 Block 0000 [ 2]: 35635631744ab54f 750 Block 0000 [ 3]: 599512e96a37ab6e 751 ... 752 Block 0031 [124]: 4d4b435cea35caa6 753 Block 0031 [125]: c582210d99ad1359 754 Block 0031 [126]: d087971b36fd6d77 755 Block 0031 [127]: a55222a93754c692 757 After pass 2: 758 Block 0000 [ 0]: 942363968ce597a4 759 Block 0000 [ 1]: a22448c0bdad5760 760 Block 0000 [ 2]: a5f80662b6fa8748 761 Block 0000 [ 3]: a0f9b9ce392f719f 762 ... 764 Block 0031 [124]: d723359b485f509b 765 Block 0031 [125]: cb78824f42375111 766 Block 0031 [126]: 35bc8cc6e83b1875 767 Block 0031 [127]: 0b012846a40f346a 768 Tag: 0d 64 0d f5 8d 78 76 6c 08 c0 37 a3 4a 8b 53 c9 d0 769 1e f0 45 2d 75 b6 5e b5 25 20 e9 6b 01 e6 59 771 6. Acknowledgements 773 We thank greatly the following authors who helped a lot in preparing 774 and reviewing this document: Jean-Philippe Aumasson, Samuel Neves, 775 Joel Alwen, Jeremiah Blocki, Bill Cox, Arnold Reinhold, Solar 776 Designer, Russ Housley, Stanislav Smyshlyaev, Kenny Paterson, Alexey 777 Melnikov. 779 7. IANA Considerations 781 None. 783 8. Security Considerations 785 8.1. Security as hash function and KDF 787 The collision and preimage resistance levels of Argon2 are equivalent 788 to those of the underlying BLAKE2b hash function. To produce a 789 collision, 2^(256) inputs are needed. To find a preimage, 2^(512) 790 inputs must be tried. 792 The KDF security is determined by the key length and the size of the 793 internal state of hash function H'. To distinguish the output of 794 keyed Argon2 from random, minimum of (2^(128),2^length(K)) calls to 795 BLAKE2b are needed. 797 8.2. Security against time-space tradeoff attacks 799 Time-space tradeoffs allow computing a memory-hard function storing 800 fewer memory blocks at the cost of more calls to the internal 801 comression function. The advantage of tradeoff attacks is measured 802 in the reduction factor to the time-area product, where memory and 803 extra compression function cores contribute to the area, and time is 804 increased to accomodate the recomputation of missed blocks. A high 805 reduction factor may potentially speed up preimage search. 807 The best known attacks on the 1-pass and 2-pass Argon2i is the low- 808 storage attack described in [CBS16], which reduces the time-area 809 product (using the peak memory value) by the factor of 5. The best 810 attack on 3-pass and more Argon2i is [AB16] with reduction factor 811 being a function of memory size and the number of passes. For 1 812 gibibyte of memory: 3 for 3 passes, 2.5 for 4 passes, 2 for 6 passes. 813 The reduction factor grows by about 0.5 with every doubling the 814 memory size. To completely prevent time-space tradeoffs from [AB16], 815 the number of passes MUST exceed binary logarithm of memory minus 26. 816 Asymptotically, the best attack on 1-pass Argon2i is given in [BZ17] 817 with maximal advantage of the adversary upper bounded by O(m^(0.233)) 818 where m is the number of blocks. This attack is also asymptotically 819 optimal as [BZ17] also prove the upper bound on any attack of 820 O(m^(0.25)). 822 The best tradeoff attack on t-pass Argon2d is the ranking tradeoff 823 attack, which reduces the time-area product by the factor of 1.33. 825 The best attack on Argon2id can be obtained by complementing the best 826 attack on the 1-pass Argon2i with the best attack on a multi-pass 827 Argon2d. Thus the best tradeoff attack on 1-pass Argon2id is the 828 combined low-storage attack (for the first half of the memory) and 829 the ranking attack (for the second half), which bring together the 830 factor of about 2.1. The best tradeoff attack on t-pass Argon2id is 831 the ranking tradeoff attack, which reduces the time-area product by 832 the factor of 1.33. 834 8.3. Security for time-bounded defenders 836 A bottleneck in a system employing the password-hashing function is 837 often the function latency rather than memory costs. A rational 838 defender would then maximize the bruteforce costs for the attacker 839 equipped with a list of hashes, salts, and timing information, for 840 fixed computing time on the defender's machine. The attack cost 841 estimates from [AB16] imply that for Argon2i, 3 passes is almost 842 optimal for the most of reasonable memory sizes, and that for Argon2d 843 and Argon2id, 1 pass maximizes the attack costs for the constant 844 defender time. 846 8.4. Recommendations 848 The Argon2id variant with t=1 and maximum available memory is 849 RECOMMENDED as a default setting for all environments. This setting 850 is secure against side-channel attacks and maximizes adversarial 851 costs on dedicated bruteforce hardware. 853 9. References 855 9.1. Normative References 857 [BLAKE2] Saarinen, M-J., Ed. and J-P. Aumasson, "The BLAKE2 858 Cryptographic Hash and Message Authentication Code (MAC)", 859 RFC 7693, November 2015, 860 . 862 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 863 Requirement Levels", RFC 2119, March 1997, 864 . 866 9.2. Informative References 868 [AB15] Biryukov, A. and D. Khovratovich, "Tradeoff Cryptanalysis 869 of Memory-Hard Functions", Asiacrypt 2015, December 2015, 870 . 872 [AB16] Alwen, J. and J. Blocki, "Efficiently Computing Data- 873 Independent Memory-Hard Functions", Crypto 2016, December 874 2015, . 876 [ARGON2] Biryukov, A., Dinu, D., and D. Khovratovich, "Argon2: the 877 memory-hard function for password hashing and other 878 applications", WWW www.cryptolux.org, October 2015, 879 . 881 [ARGON2ESP] 882 Biryukov, A., Dinu, D., and D. Khovratovich, "Argon2: New 883 Generation of Memory-Hard Functions for Password Hashing 884 and Other Applications", Euro SnP 2016, March 2016, 885 . 887 [BZ17] Blocki, J. and S. Zhou, "On the Depth-Robustness and 888 Cumulative Pebbling Cost of Argon2i", TCC 2017, May 2017, 889 . 891 [CBS16] Corrigan-Gibbs, H., Boneh, D., and S. Schechter, "Balloon 892 Hashing: Provably Space-Hard Hash Functions with Data- 893 Independent Access Patterns", Asiacrypt 2016, January 894 2016, . 896 [HARD] Alwen, J. and V. Serbinenko, "High Parallel Complexity 897 Graphs and Memory-Hard Functions", STOC 2015, 2014, 898 . 900 Authors' Addresses 901 Alex Biryukov 902 University of Luxembourg 904 Email: alex.biryukov@uni.lu 906 Daniel Dinu 907 University of Luxembourg 909 Email: dumitru-daniel.dinu@uni.lu 911 Dmitry Khovratovich 912 ABDK Consulting 914 Email: khovratovich@gmail.com 916 Simon Josefsson 917 SJD AB 919 Email: simon@josefsson.org 920 URI: http://josefsson.org/