idnits 2.17.1 draft-josefsson-argon2-00.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 5, 2015) is 3067 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 211 -- Looks like a reference, but probably isn't: '1' on line 211 -- Looks like a reference, but probably isn't: '32' on line 407 -- Looks like a reference, but probably isn't: '16' on line 411 -- Looks like a reference, but probably isn't: '8' on line 412 -- Looks like a reference, but probably isn't: '12' on line 413 -- Looks like a reference, but probably isn't: '124' on line 451 -- Looks like a reference, but probably isn't: '125' on line 452 -- Looks like a reference, but probably isn't: '126' on line 453 -- Looks like a reference, but probably isn't: '127' on line 454 Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 11 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group A. Biryukov 3 Internet-Draft D. Dinu 4 Intended status: Informational D. Khovratovich 5 Expires: May 8, 2016 University of Luxembourg 6 S. Josefsson 7 SJD AB 8 November 5, 2015 10 The memory-hard Argon2 password hash function 11 draft-josefsson-argon2-00 13 Abstract 15 This document describes the Argon2 memory-hard function for password 16 hashing and other applications. We provide a implementer oriented 17 description together with sample code and test vectors. The purpose 18 is to simplify adoption of Argon2 for Internet protocols. 20 Status of This Memo 22 This Internet-Draft is submitted in full conformance with the 23 provisions of BCP 78 and BCP 79. 25 Internet-Drafts are working documents of the Internet Engineering 26 Task Force (IETF). Note that other groups may also distribute 27 working documents as Internet-Drafts. The list of current Internet- 28 Drafts is at http://datatracker.ietf.org/drafts/current/. 30 Internet-Drafts are draft documents valid for a maximum of six months 31 and may be updated, replaced, or obsoleted by other documents at any 32 time. It is inappropriate to use Internet-Drafts as reference 33 material or to cite them other than as "work in progress." 35 This Internet-Draft will expire on May 8, 2016. 37 Copyright Notice 39 Copyright (c) 2015 IETF Trust and the persons identified as the 40 document authors. All rights reserved. 42 This document is subject to BCP 78 and the IETF Trust's Legal 43 Provisions Relating to IETF Documents 44 (http://trustee.ietf.org/license-info) in effect on the date of 45 publication of this document. Please review these documents 46 carefully, as they describe your rights and restrictions with respect 47 to this document. Code Components extracted from this document must 48 include Simplified BSD License text as described in Section 4.e of 49 the Trust Legal Provisions and are provided without warranty as 50 described in the Simplified BSD License. 52 Table of Contents 54 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 55 2. Notation and Conventions . . . . . . . . . . . . . . . . . . 3 56 3. Argon2 Algorithm . . . . . . . . . . . . . . . . . . . . . . 3 57 3.1. Argon2 Inputs and Outputs . . . . . . . . . . . . . . . . 3 58 3.2. Argon2 Operation . . . . . . . . . . . . . . . . . . . . 4 59 3.3. Variable-length hash function H' . . . . . . . . . . . . 5 60 3.4. Indexing . . . . . . . . . . . . . . . . . . . . . . . . 5 61 3.5. Compression function G . . . . . . . . . . . . . . . . . 6 62 3.6. Permutation P . . . . . . . . . . . . . . . . . . . . . . 6 63 4. Parameter Choice . . . . . . . . . . . . . . . . . . . . . . 6 64 5. Example Code . . . . . . . . . . . . . . . . . . . . . . . . 8 65 6. Test Vectors . . . . . . . . . . . . . . . . . . . . . . . . 8 66 6.1. Argon2d Test Vectors . . . . . . . . . . . . . . . . . . 8 67 6.2. Argon2i Test Vectors . . . . . . . . . . . . . . . . . . 9 68 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 10 69 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 70 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 71 10. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 72 10.1. Normative References . . . . . . . . . . . . . . . . . . 11 73 10.2. Informative References . . . . . . . . . . . . . . . . . 11 74 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 76 1. Introduction 78 This document describes the Argon2 memory-hard function for password 79 hashing and other applications. We provide a implementer oriented 80 description together with sample code and test vectors. The purpose 81 is to simplify adoption of Argon2 for Internet protocols. 83 Argon2 summarizes the state of the art in the design of memory-hard 84 functions. It is a streamlined and simple design. It aims at the 85 highest memory filling rate and effective use of multiple computing 86 units, while still providing defense against tradeoff attacks. 87 Argon2 is optimized for the x86 architecture and exploits the cache 88 and memory organization of the recent Intel and AMD processors. 89 Argon2 has two variants: Argon2d and Argon2i. Argon2d is faster and 90 uses data-depending memory access, which makes it suitable for 91 cryptocurrencies and applications with no threats from side-channel 92 timing attacks. Argon2i uses data-independent memory access, which 93 is preferred for password hashing and password-based key derivation. 94 Argon2i is slower as it makes more passes over the memory to protect 95 from tradeoff attacks. 97 For further background and discussion, see the Argon2 paper [ARGON2]. 99 2. Notation and Conventions 101 x^y --- x multiplied by itself y times 103 a*b --- multiplication of a and b 105 c-d --- substraction of c with d 107 E_f --- variable E with subscript index f 109 g / h --- g divided by h 111 I(j) --- function I evaluated on parameters j 113 K || L --- string K concatenated with string L 115 3. Argon2 Algorithm 117 3.1. Argon2 Inputs and Outputs 119 Argon2 have the following input parameters: 121 o Message string P, typically a password. May have any length from 122 0 to 2^32 - 1 bytes. 124 o Nonce S, typically a random salt. May have any length from 8 to 125 2^32 - 1 bytes. 16 bytes is recommended for password hashing. 126 See [RFC4086] for discussion about randomness. 128 o Degree of parallelism p determines how many independent (but 129 synchronizing) computational chains can be run. It may take any 130 integer value from 1 to 255. 132 o Tag length T may be any integer number of bytes from 4 to 2^32-1. 134 o Memory size m can be any integer number of kilobytes from 8*p to 135 2^32-1. The actual number of blocks is m', which is m rounded 136 down to the nearest multiple of 4*p. 138 o Number of iterations t (used to tune the running time 139 independently of the memory size) can be any integer number from 1 140 to 2^32-1. 142 o Version number v is one byte 0x10. 144 o Secret value K (serves as key if necessary, but we do not assume 145 any key use by default) may have any length from 0 to 32 bytes. 147 o Associated data X may have any length from 0 to 2^32-1 bytes. 149 o Type y of Argon2: 0 for Argon2d, 1 for Argon2i. 151 The Argon2 output is a T-length string. 153 3.2. Argon2 Operation 155 Argon2 uses an internal compression function G with two 1024-byte 156 inputs and a 1024-byte output, and an internal hash function H. Here 157 H is the Blake2b [I-D.saarinen-blake2] hash function, and the 158 compression function G is based on its internal permutation. A 159 variable-length hash function H' built upon H is also used. G and H' 160 are described in later section. 162 The Argon2 operation is as follows. 164 1. Establish H_0 as the 64-bit value as shown in the figure below. 165 H is BLAKE2b and the non-strings p, T, m, t, v, y, length(P), 166 length(S), length(K), and length(X) are treated as a 32-bit 167 little-endian encoding of the integer. 169 H_0 = H(p, T, m, t, v, y, length(P), P, length(S), S, 170 length(K), K, length(X), X) 172 2. Allocate the memory as m' 1024-byte blocks where m' is derived 173 as: 175 m' = 4 * p * floor (m / 4p) 177 For tunable parallelism with p threads, the memory is organized 178 in a matrix B[i][j] of blocks with p rows (lanes) and q = m' / p 179 columns. 181 3. Compute B[i][0] for all i ranging from (and including) 0 to (not 182 including) p. 184 B[i][0] = H'(H0, 4byteencode(i), 4byteencode(0)) 186 Here 4byteencode is a function which takes an integer and little- 187 endian encode and padds it to 4 bytes. 189 4. Compute B[i][1] for all i ranging from (and including) 0 to (not 190 including) p. 192 B[i][1] = H'(H0, 4byteencode(i), 4byteencode(1)) 194 5. Compute B[i][j] for all i ranging from (and including) 0 to (not 195 including) p, and for all j ranging from (and including) 2) to 196 (not including) q. The block indices i' and j' are determined 197 differently for Argon2d and Argon2i. 199 B[i][j] = G(B[i][j-1], B[i'][j']) 201 6. If the number of iterations t is larger than 1, we repeat the 202 steps however replacing the computations with with the following 203 expression: 205 B[i][0] = G(B[i][q-1], B[i'][j']) 206 B[i][j] = G(B[i][j-1], B[i'][j']) 208 7. After t steps have been iterated, we compute the final block C as 209 the XOR of the last column: 211 C = B[0][q-1] XOR B[1][q-1] XOR ... XOR B[p-1][q-1] 213 8. The output tag is computed as H'(C). 215 3.3. Variable-length hash function H' 217 Let H_x be a hash function with x-byte output (in our case H_x is 218 Blake2b, which supports x between 1 and 64 inclusive). Let V_i be a 219 64-byte block, and A_i be its first 32 bytes, and T < 2^32 be the tag 220 length in bytes. Then we define 222 V_0 = T||X 223 V_1 = H_64(V_0) 224 V_2 = H_64(V_1) 225 ... 226 V_r = H_64(V_{r-1}) with r=floor(T/32)-1 227 V_{r+1} = H_{T mod 64}(V_{r-1}) absent if 64 divides T 228 H'(X) = A_1 || A_2 || ... || A_r || V_{r+1} 230 FIXME: improve this description. FIXME2: V_{r+1} is not properly 231 described, is it a 64-byte block or a {T mod 64} block? 233 3.4. Indexing 235 TBD 237 3.5. Compression function G 239 Compression function G is built upon the Blake2b round function P. P 240 operates on the 128-byte input, which can be viewed as 8 16-byte 241 registers: 243 P(A_0, A_1, ... ,A_7) = (B_0, B_1, ... ,B_7) 245 Compression function G(X, Y) operates on two 1024-byte blocks X and 246 Y. It first computes R = X XOR Y. Then R is viewed as a 8x8-matrix 247 of 16-byte registers R_0, R_1, ... , R_63. Then P is first applied 248 rowwise, and then columnwise to get Z: 250 (Q_0, Q_1, ... , Q_7 ) <- P(R_0, R_1, ... , R_7) 251 (Q_8, Q_9, ... , Q_15) <- P(R_8, R_9, ... , R_15) 252 ... 253 (Q_56, Q_57, ... , Q_63 ) <- P(R_56, R_57, ... , R_63) 254 (Z_0, Z_8, Z_16 , ... , Z_56) < P(Q_0, Q_8, Q_16, ... , Q_56) 255 (Z_1, Z_9, Z_17 , ... , Z_57) < P(Q_1, Q_9, Q_17, ... , Q_57) 256 ... 257 (Z_7, Z_15, Z 23 , ... , Z_63) < P(Q_7, Q_15, Q_23, ... , Q_63) 259 Finally, G outputs Z XOR R: 261 G: (X,Y) -> R = X XOR Y -P-> Q -P-> Z -P-> Z XOR R 263 FIXME: improve this description. 265 3.6. Permutation P 267 TBD 269 4. Parameter Choice 271 Argon2d is optimized for settings where the adversary does not get 272 regular access to system memory or CPU, i.e. he can not run side- 273 channel attacks based on the timing information, nor he can recover 274 the password much faster using garbage collection. These settings 275 are more typical for backend servers and cryptocurrency minings. For 276 practice we suggest the following settings: 278 o Cryptocurrency mining, that takes 0.1 seconds on a 2 Ghz CPU using 279 1 core -- Argon2d with 2 lanes and 250 MB of RAM. 281 o Backend server authentication, that takes 0.5 seconds on a 2 GHz 282 CPU using 4 cores -- Argon2d with 8 lanes and 4 GB of RAM. 284 Argon2i is optimized for more realistic settings, where the adversary 285 possibly can access the same machine, use its CPU or mount cold-boot 286 attacks. We use three passes to get rid entirely of the password in 287 the memory. We suggest the following settings: 289 o Key derivation for hard-drive encryption, that takes 3 seconds on 290 a 2 GHz CPU using 2 cores - Argon2i with 4 lanes and 6 GB of RAM 292 o Frontend server authentication, that takes 0.5 seconds on a 2 GHz 293 CPU using 2 cores - Argon2i with 4 lanes and 1 GB of RAM. 295 We recommend the following procedure to select the type and the 296 parameters for practical use of Argon2. 298 1. Select the type y. If you do not know the difference between 299 them or you consider side-channel attacks as viable threat, 300 choose Argon2i. 302 2. Figure out the maximum number h of threads that can be initiated 303 by each call to Argon2. 305 3. Figure out the maximum amount m of memory that each call can 306 afford. 308 4. Figure out the maximum amount x of time (in seconds) that each 309 call can afford. 311 5. Select the salt length. 128 bits is sufficient for all 312 applications, but can be reduced to 64 bits in the case of space 313 constraints. 315 6. Select the tag length. 128 bits is sufficient for most 316 applications, including key derivation. If longer keys are 317 needed, select longer tags. 319 7. If side-channel attacks is a viable threat, enable the memory 320 wiping option in the library call. 322 8. Run the scheme of type y, memory m and h lanes and threads, using 323 different number of passes t. Figure out the maximum t such that 324 the running time does not exceed x. If it exceeds x even for t = 325 1, reduce m accordingly. 327 9. Hash all the passwords with the just determined values m, h, and 328 t. 330 5. Example Code 332 TBD -- is there a python implementation? 334 6. Test Vectors 336 This section contains test vectors for Argon2. 338 6.1. Argon2d Test Vectors 340 =======================================Argon2d 341 Memory: 16 KiB 342 Iterations: 3 343 Parallelism: 4 lanes 344 Tag length: 32 bytes 345 Password[32]: 01 01 01 01 01 01 01 01 346 01 01 01 01 01 01 01 01 347 01 01 01 01 01 01 01 01 348 01 01 01 01 01 01 01 01 349 Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 350 Secret[8]: 03 03 03 03 03 03 03 03 351 Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04 352 Pre-hashing digest: ec a9 db ff fa c9 87 5c 353 d2 dc 32 67 cb 82 7f 48 354 79 af db 2f 6c b3 a5 29 355 c5 87 7c 60 7d 72 92 02 356 7c 23 15 47 fc 64 4f b8 357 81 16 1f ee f6 e2 b3 d1 358 63 49 1a 98 e8 a8 8c 8a 359 40 15 b8 b5 dc 85 ec 1b 361 After pass 0: 362 Block 0000 [ 0]: 7ddae3a315a45d2d 363 Block 0000 [ 1]: 50d8b9a49514a996 364 Block 0000 [ 2]: d5fd2f56c5085520 365 Block 0000 [ 3]: 81fa720dcf94e004 366 ... 367 Block 0031 [124]: 40b2d44e241f7a2a 368 Block 0031 [125]: 9b9658c82ba08f84 369 Block 0031 [126]: 917242b2a7a533f2 370 Block 0031 [127]: 4169db73ebcc9e9c 372 After pass 1: 373 Block 0000 [ 0]: a8daed017254d662 374 Block 0000 [ 1]: 1564d0fc4f5d07f4 375 Block 0000 [ 2]: 6a18ece1fd7d79ff 376 Block 0000 [ 3]: d04eb389a8ac7324 377 ... 379 Block 0031 [124]: c859e8ba37e79999 380 Block 0031 [125]: 0bb980cfe6552a4d 381 Block 0031 [126]: 300cea2895f4459e 382 Block 0031 [127]: 37af5d23a18f9d58 384 After pass 2: 385 Block 0000 [ 0]: e86fc8e713dbf6d3 386 Block 0000 [ 1]: b30f1bdf8b4219d6 387 Block 0000 [ 2]: a84aec198d1eaff0 388 Block 0000 [ 3]: 1be35c5c8bfc52e0 389 ... 390 Block 0031 [124]: 9ffab191789d7380 391 Block 0031 [125]: 4237012fc73e8d3e 392 Block 0031 [126]: fbea11160fe7b50e 393 Block 0031 [127]: 692210628c981931 395 Tag: 57 b0 61 3b fd d4 13 1a 396 0c 34 88 34 c6 72 9c 2c 397 72 29 92 1e 6b ba 37 66 398 5d 97 8c 4f e7 17 5e d2 400 6.2. Argon2i Test Vectors 402 =======================================Argon2i 403 Memory: 16 KiB 404 Iterations: 3 405 Parallelism: 4 lanes 406 Tag length: 32 bytes 407 Password[32]: 01 01 01 01 01 01 01 01 408 01 01 01 01 01 01 01 01 409 01 01 01 01 01 01 01 01 410 01 01 01 01 01 01 01 01 411 Salt[16]: 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 02 412 Secret[8]: 03 03 03 03 03 03 03 03 413 Associated data[12]: 04 04 04 04 04 04 04 04 04 04 04 04 414 Pre-hashing digest: c0 4e 5c 19 98 fc b1 12 415 09 3e 36 a0 76 3e 2f 95 416 57 f2 cf 53 6f b8 89 c9 417 9c c6 d8 cd b3 49 cd 0c 418 9d 48 db cc 94 57 59 8c 419 6c 2d a1 e1 d1 8b 3b aa 420 7a 37 43 cb d1 7a d8 5c 421 61 df dc 7e 7a 8e 64 2f 423 After pass 0: 424 Block 0000 [ 0]: 34e7ba2a71020326 425 Block 0000 [ 1]: 3a4e252bf033a4cb 426 Block 0000 [ 2]: 3fb8e27bb8ab6a2b 427 Block 0000 [ 3]: 65bb946635366867 428 ... 429 Block 0031 [124]: 433d8954deddd5d6 430 Block 0031 [125]: c76ead72f0c08a23 431 Block 0031 [126]: b7c6ce1154c1fdd1 432 Block 0031 [127]: 0e766420b2ee181c 434 After pass 1: 435 Block 0000 [ 0]: 614a404c54646531 436 Block 0000 [ 1]: 79f220080bfac514 437 Block 0000 [ 2]: e9da047d0e4406b4 438 Block 0000 [ 3]: 0995bc6d95590353 439 ... 440 Block 0031 [124]: 9b89e743afa7b916 441 Block 0031 [125]: 9b3f7ca7cfff2db9 442 Block 0031 [126]: 0065ff067978eab8 443 Block 0031 [127]: 0a78fa2cea2b8bb2 445 After pass 2: 446 Block 0000 [ 0]: 3fea10517d1a7476 447 Block 0000 [ 1]: e44c8bece4b3ecb2 448 Block 0000 [ 2]: e348b27d988671cb 449 Block 0000 [ 3]: 5f7f7cd33ef59e4d 450 ... 451 Block 0031 [124]: f60cb937689b55f8 452 Block 0031 [125]: 418c55d7f343df3f 453 Block 0031 [126]: 26899dd11adc7474 454 Block 0031 [127]: dd3afa472ff1d124 455 Tag: 91 3b a4 37 68 5b 61 3c 456 f1 2b 94 46 79 53 40 37 457 ac 46 cf a8 8a 02 f6 c7 458 ba 28 0e 08 89 40 19 f2 460 7. Acknowledgements 462 TBA 464 8. IANA Considerations 466 None. 468 9. Security Considerations 470 TBA 472 10. References 474 10.1. Normative References 476 [I-D.saarinen-blake2] 477 Saarinen, M. and J. Aumasson, "The BLAKE2 Cryptographic 478 Hash and MAC", draft-saarinen-blake2-06 (work in 479 progress), August 2015. 481 10.2. Informative References 483 [RFC4086] Eastlake, D., Schiller, J., and S. Crocker, "Randomness 484 Requirements for Security", BCP 106, RFC 4086, June 2005. 486 [ARGON2] Biryukov, A., Dinu, D., and D. Khovratovich, "Argon2: the 487 memory-hard function for password hashing and other 488 applications", WWW https://password-hashing.net/ 489 argon2-specs.pdf, October 2015. 491 Authors' Addresses 493 Alex Biryukov 494 University of Luxembourg 496 Daniel Dinu 497 University of Luxembourg 499 Dmitry Khovratovich 500 University of Luxembourg 502 Simon Josefsson 503 SJD AB 505 Email: simon@josefsson.org 506 URI: http://josefsson.org/