idnits 2.17.1 draft-josefsson-scrypt-kdf-01.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 : ---------------------------------------------------------------------------- ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 248: '... keyLength INTEGER (1..MAX) OPTIONAL }...' RFC 2119 keyword, line 284: '... keyLength INTEGER (1..MAX) OPTIONAL...' Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (September 24, 2012) is 4222 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 317 -- Looks like a reference, but probably isn't: '2' on line 152 -- Looks like a reference, but probably isn't: '1' on line 322 -- Looks like a reference, but probably isn't: '3' on line 153 ** Obsolete normative reference: RFC 2898 (Obsoleted by RFC 8018) Summary: 2 errors (**), 0 flaws (~~), 1 warning (==), 5 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group C. Percival 3 Internet-Draft Tarsnap 4 Intended status: Informational S. Josefsson 5 Expires: March 28, 2013 SJD AB 6 September 24, 2012 8 The scrypt Password-Based Key Derivation Function 9 draft-josefsson-scrypt-kdf-01 11 Abstract 13 This document specifies the password-based key derivation function 14 scrypt. The function derives one or more secret keys from a secret 15 string. It is based on memory-hard functions which offer added 16 protection against attacks using custom hardware. The document also 17 provides an ASN.1 schema. 19 Status of this Memo 21 This Internet-Draft is submitted in full conformance with the 22 provisions of BCP 78 and BCP 79. 24 Internet-Drafts are working documents of the Internet Engineering 25 Task Force (IETF). Note that other groups may also distribute 26 working documents as Internet-Drafts. The list of current Internet- 27 Drafts is at http://datatracker.ietf.org/drafts/current/. 29 Internet-Drafts are draft documents valid for a maximum of six months 30 and may be updated, replaced, or obsoleted by other documents at any 31 time. It is inappropriate to use Internet-Drafts as reference 32 material or to cite them other than as "work in progress." 34 This Internet-Draft will expire on March 28, 2013. 36 Copyright Notice 38 Copyright (c) 2012 IETF Trust and the persons identified as the 39 document authors. All rights reserved. 41 This document is subject to BCP 78 and the IETF Trust's Legal 42 Provisions Relating to IETF Documents 43 (http://trustee.ietf.org/license-info) in effect on the date of 44 publication of this document. Please review these documents 45 carefully, as they describe your rights and restrictions with respect 46 to this document. Code Components extracted from this document must 47 include Simplified BSD License text as described in Section 4.e of 48 the Trust Legal Provisions and are provided without warranty as 49 described in the Simplified BSD License. 51 Table of Contents 53 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 54 2. The Salsa20/8 Core Function . . . . . . . . . . . . . . . . . 4 55 3. The scryptBlockMix Algorithm . . . . . . . . . . . . . . . . . 5 56 4. The scryptROMix Algorithm . . . . . . . . . . . . . . . . . . 6 57 5. The scrypt Algorithm . . . . . . . . . . . . . . . . . . . . . 7 58 6. ASN.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . 8 59 6.1. ASN.1 Module . . . . . . . . . . . . . . . . . . . . . . . 8 60 7. Test Vectors for Salsa20/8 Core . . . . . . . . . . . . . . . 10 61 8. Test Vectors for scryptBlockMix . . . . . . . . . . . . . . . 11 62 9. Test Vectors for scryptROMix . . . . . . . . . . . . . . . . . 12 63 10. Test Vectors for PBKDF2 with HMAC-SHA-256 . . . . . . . . . . 13 64 11. Test Vectors for scrypt . . . . . . . . . . . . . . . . . . . 14 65 12. Copying Conditions . . . . . . . . . . . . . . . . . . . . . . 15 66 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 16 67 14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 17 68 15. Security Considerations . . . . . . . . . . . . . . . . . . . 18 69 16. References . . . . . . . . . . . . . . . . . . . . . . . . . . 19 70 16.1. Normative References . . . . . . . . . . . . . . . . . . . 19 71 16.2. Informative References . . . . . . . . . . . . . . . . . . 19 72 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 20 74 1. Introduction 76 Password-based key derivation functions are used in cryptography for 77 deriving one or more secret keys from a secret value. Over the 78 years, several password-based key derivation functions have been 79 used, including the original DES-based UNIX Crypt-function, FreeBSD 80 MD5 crypt, PKCS#5 PBKDF2 [RFC2898] (typically used with SHA-1), GNU 81 SHA-256/512 crypt, Windows NT LAN Manager (NTLM) hash, and the 82 Blowfish-based bcrypt. These algorithms are based on similar 83 techniques that employ a cryptographic primitive, salting and/or 84 iteration. The iteration count is used to slow down the computation. 86 Providing that the number of iterations used is increased as computer 87 systems get faster, this allows legitimate users to spend a constant 88 amount of time on key derivation without losing ground to an 89 attackers' ever-increasing computing power - as long as attackers are 90 limited to the same software implementations as legitimate users. 91 However, as Bernstein pointed out in the context of integer 92 factorization, while parallelized hardware implementations may not 93 change the number of operations performed compared to software 94 implementations, this does not prevent them from dramatically 95 changing the asymptotic cost, since in many contexts - including the 96 embarrassingly parallel task of performing a brute-force search for a 97 passphrase - dollar-seconds are the most appropriate units for 98 measuring the cost of a computation. As semiconductor technology 99 develops, circuits do not merely become faster; they also become 100 smaller, allowing for a larger amount of parallelism at the same 101 cost. Consequently, existing key derivation algorithms, even when 102 the iteration count is increased so that the time taken to verify a 103 password remains constant, the cost of finding a password by using a 104 brute force attack implemented in hardware drops each year. 106 The scrypt function aims to reduce the advantage which attackers can 107 gain by using custom-designed parallel circuits for breaking 108 password-based key derivation functions. 110 For further background, see the original scrypt paper [SCRYPT]. 112 The rest of this document is divided into sections that each describe 113 algorithms needed for the final "scrypt" algorithm. 115 2. The Salsa20/8 Core Function 117 Salsa20/8 Core is a round-reduced variant of the Salsa20 Core. It is 118 a hash function from 64-octet strings to 64-octet strings. Note that 119 Salsa20/8 Core is not a cryptographic hash function since it is not 120 collision-resistant. See [SALSA20CORE] for the specification. 122 3. The scryptBlockMix Algorithm 124 The scryptBlockMix algorithm is the same as the BlockMix algorithm 125 described in [SCRYPT] but with Salsa20/8 Core used as the hash 126 function H. Below, Salsa(T) corresponds to the Salsa20/8 Core 127 function applied to the octet vector T. 129 Algorithm scryptBlockMix 131 Parameters: 132 r Block size parameter. 134 Input: 135 B[0], ..., B[2 * r - 1] 136 Input vector of 2 * r 64-octet blocks. 138 Output: 139 B'[0], ..., B'[2 * r - 1] 140 Output vector of 2 * r 64-octet blocks. 142 Steps: 144 1. X = B[2 * r - 1] 146 2. for i = 0 to 2 * r - 1 do 147 T = X xor B[i] 148 X = Salsa (T) 149 Y[i] = X 150 end for 152 3. B' = (Y[0], Y[2], ..., Y[2 * r - 2], 153 Y[1], Y[3], ..., Y[2 * r - 1]) 155 4. The scryptROMix Algorithm 157 The scryptROMix algorithm is the same as the ROMix algorithm 158 described in [SCRYPT] but with scryptBlockMix used as the hash 159 function H and the Integerify function explained inline. 161 Algorithm scryptROMix 163 Input: 164 r Block size parameter. 165 B Input octet vector of length 128 * r octets. 166 N CPU/Memory cost parameter, must be larger than 1, 167 a power of 2 and less than 2^(128 * r / 8). 169 Output: 170 B' Output octet vector of length 128 * r octets. 172 Steps: 174 1. X = B 176 2. for i = 0 to N - 1 do 177 V[i] = X 178 X = scryptBlockMix (X) 179 end for 181 3. for i = 0 to N - 1 do 182 j = Integerify (X) mod N 183 where Integerify (B[0] ... B[2 * r - 1]) is defined 184 as the result of interpreting B[2 * r - 1] as a 185 little-endian integer. 186 T = X xor V[j] 187 X = scryptBlockMix (T) 188 end for 190 4. B' = X 192 5. The scrypt Algorithm 194 The PBKDF2-HMAC-SHA-256 function used below denote the PBKDF2 195 algorithm [RFC2898] used with HMAC-SHA-256 [RFC6234] as the PRF. The 196 HMAC-SHA-256 function generates 32 octet outputs. 198 Algorithm scrypt 200 Input: 201 P Passphrase, an octet string. 202 S Salt, an octet string. 203 N CPU/Memory cost parameter, must be larger than 1, 204 a power of 2 and less than 2^(128 * r / 8). 205 r Block size parameter. 206 p Parallelization parameter, a positive integer 207 less than or equal to ((2^32-1) * hLen) / MFLen 208 where hLen is 32 and MFlen is 128 * r. 209 dkLen Intended output length in octets of the derived 210 key; a positive integer less than or equal to 211 (2^32 - 1) * hLen where hLen is 32. 213 Output: 214 DK Derived key, of length dkLen octets. 216 Steps: 218 1. B[0] || B[1] || ... || B[p - 1] = 219 PBKDF2-HMAC-SHA256 (P, S, 1, p * 128 * r) 221 2. for i = 0 to p - 1 do 222 B[i] = scryptROMix (r, B[i], N) 223 end for 225 3. DK = PBKDF2-HMAC-SHA256 (P, B[0] || B[1] || ... || B[p - 1], 226 1, dkLen) 228 6. ASN.1 Syntax 230 This section defines ASN.1 syntax for the scrypt key derivation 231 function. The intended application of these definitions includes 232 PKCS #8 and other syntax for key management. (Various aspects of 233 ASN.1 are specified in several ISO/IEC standards.) 235 The object identifier id-scrypt identifies the scrypt key derivation 236 function. 238 id-scrypt OBJECT IDENTIFIER ::= {1 3 6 1 4 1 11591 4 11} 240 The parameters field associated with this OID in an 241 AlgorithmIdentifier shall have type scrypt-params: 243 scrypt-params ::= SEQUENCE { 244 salt OCTET STRING, 245 costParameter INTEGER (1..MAX), 246 blockSize INTEGER (1..MAX), 247 parallelizationParameter INTEGER (1..MAX), 248 keyLength INTEGER (1..MAX) OPTIONAL } 250 The fields of type scrypt-params have the following meanings: 252 - salt specifies the salt value. It shall be an octet string. 254 - costParameter specifies the CPU/Memory cost parameter N. 256 - blockSize specifies the block size parameter r. 258 - parallelizationParameter specifies the parallelization parameter. 260 - keyLength, an optional field, is the length in octets of the 261 derived key. The maximum key length allowed depends on the 262 implementation; it is expected that implementation profiles may 263 further constrain the bounds. This field only provides convenience; 264 the key length is not cryptographically protected. 266 6.1. ASN.1 Module 268 For reference purposes, the ASN.1 syntax is presented as an ASN.1 269 module here. 271 -- scrypt ASN.1 Module 273 scrypt-0 {1 3 6 1 4 1 11591 4 10} 275 DEFINITIONS ::= BEGIN 277 id-scrypt OBJECT IDENTIFIER ::= {1 3 6 1 4 1 11591 4 11} 279 scrypt-params ::= SEQUENCE { 280 salt OCTET STRING, 281 costParameter INTEGER (1..MAX), 282 blockSize INTEGER (1..MAX), 283 parallelizationParameter INTEGER (1..MAX), 284 keyLength INTEGER (1..MAX) OPTIONAL 285 } 287 END 289 7. Test Vectors for Salsa20/8 Core 291 Below is a sequence of octets to illustrate input and output values 292 for the Salsa20/8 Core. The octets are hex encoded and whitespace is 293 inserted for readability. The value corresponds to the first input 294 and output pair generated by the first scrypt test vector below. 296 INPUT: 297 7e 87 9a 21 4f 3e c9 86 7c a9 40 e6 41 71 8f 26 298 ba ee 55 5b 8c 61 c1 b5 0d f8 46 11 6d cd 3b 1d 299 ee 24 f3 19 df 9b 3d 85 14 12 1e 4b 5a c5 aa 32 300 76 02 1d 29 09 c7 48 29 ed eb c6 8d b8 b8 c2 5e 302 OUTPUT: 303 a4 1f 85 9c 66 08 cc 99 3b 81 ca cb 02 0c ef 05 304 04 4b 21 81 a2 fd 33 7d fd 7b 1c 63 96 68 2f 29 305 b4 39 31 68 e3 c9 e6 bc fe 6b c5 b7 a0 6d 96 ba 306 e4 24 cc 10 2c 91 74 5c 24 ad 67 3d c7 61 8f 81 308 8. Test Vectors for scryptBlockMix 310 Below is a sequence of octets to illustrate input and output values 311 for scryptBlockMix. The test vector uses an r value of 1. The 312 octets are hex encoded and whitespace is inserted for readability. 313 The value corresponds to the first input and output pair generated by 314 the first scrypt test vector below. 316 INPUT 317 B[0] = f7 ce 0b 65 3d 2d 72 a4 10 8c f5 ab e9 12 ff dd 318 77 76 16 db bb 27 a7 0e 82 04 f3 ae 2d 0f 6f ad 319 89 f6 8f 48 11 d1 e8 7b cc 3b d7 40 0a 9f fd 29 320 09 4f 01 84 63 95 74 f3 9a e5 a1 31 52 17 bc d7 322 B[1] = 89 49 91 44 72 13 bb 22 6c 25 b5 4d a8 63 70 fb 323 cd 98 43 80 37 46 66 bb 8f fc b5 bf 40 c2 54 b0 324 67 d2 7c 51 ce 4a d5 fe d8 29 c9 0b 50 5a 57 1b 325 7f 4d 1c ad 6a 52 3c da 77 0e 67 bc ea af 7e 89 327 OUTPUT 328 B'[0] = a4 1f 85 9c 66 08 cc 99 3b 81 ca cb 02 0c ef 05 329 04 4b 21 81 a2 fd 33 7d fd 7b 1c 63 96 68 2f 29 330 b4 39 31 68 e3 c9 e6 bc fe 6b c5 b7 a0 6d 96 ba 331 e4 24 cc 10 2c 91 74 5c 24 ad 67 3d c7 61 8f 81 333 B'[1] = 20 ed c9 75 32 38 81 a8 05 40 f6 4c 16 2d cd 3c 334 21 07 7c fe 5f 8d 5f e2 b1 a4 16 8f 95 36 78 b7 335 7d 3b 3d 80 3b 60 e4 ab 92 09 96 e5 9b 4d 53 b6 336 5d 2a 22 58 77 d5 ed f5 84 2c b9 f1 4e ef e4 25 338 9. Test Vectors for scryptROMix 340 Below is a sequence of octets to illustrate input and output values 341 for scryptROMix. The test vector uses an r value of 1 and an N value 342 of 16. The octets are hex encoded and whitespace is inserted for 343 readability. The value corresponds to the first input and output 344 pair generated by the first scrypt test vector below. 346 INPUT: 347 B = f7 ce 0b 65 3d 2d 72 a4 10 8c f5 ab e9 12 ff dd 348 77 76 16 db bb 27 a7 0e 82 04 f3 ae 2d 0f 6f ad 349 89 f6 8f 48 11 d1 e8 7b cc 3b d7 40 0a 9f fd 29 350 09 4f 01 84 63 95 74 f3 9a e5 a1 31 52 17 bc d7 351 89 49 91 44 72 13 bb 22 6c 25 b5 4d a8 63 70 fb 352 cd 98 43 80 37 46 66 bb 8f fc b5 bf 40 c2 54 b0 353 67 d2 7c 51 ce 4a d5 fe d8 29 c9 0b 50 5a 57 1b 354 7f 4d 1c ad 6a 52 3c da 77 0e 67 bc ea af 7e 89 356 OUTPUT: 357 B = 79 cc c1 93 62 9d eb ca 04 7f 0b 70 60 4b f6 b6 358 2c e3 dd 4a 96 26 e3 55 fa fc 61 98 e6 ea 2b 46 359 d5 84 13 67 3b 99 b0 29 d6 65 c3 57 60 1f b4 26 360 a0 b2 f4 bb a2 00 ee 9f 0a 43 d1 9b 57 1a 9c 71 361 ef 11 42 e6 5d 5a 26 6f dd ca 83 2c e5 9f aa 7c 362 ac 0b 9c f1 be 2b ff ca 30 0d 01 ee 38 76 19 c4 363 ae 12 fd 44 38 f2 03 a0 e4 e1 c4 7e c3 14 86 1f 364 4e 90 87 cb 33 39 6a 68 73 e8 f9 d2 53 9a 4b 8e 366 10. Test Vectors for PBKDF2 with HMAC-SHA-256 368 Below is a sequence of octets illustring input and output values for 369 PBKDF2-HMAC-SHA-256. The octets are hex encoded and whitespace is 370 inserted for readability. The test vectors below can be used to 371 verify the PBKDF2-HMAC-SHA-256 [RFC2898] function. The password and 372 salt strings are passed as sequences of ASCII [ANSI.X3-4.1986] 373 octets. 375 PBKDF2-HMAC-SHA-256 (P="passwd", S="salt", 376 c=1, dkLen=64) = 377 55 ac 04 6e 56 e3 08 9f ec 16 91 c2 25 44 b6 05 378 f9 41 85 21 6d de 04 65 e6 8b 9d 57 c2 0d ac bc 379 49 ca 9c cc f1 79 b6 45 99 16 64 b3 9d 77 ef 31 380 7c 71 b8 45 b1 e3 0b d5 09 11 20 41 d3 a1 97 83 382 PBKDF2-HMAC-SHA-256 (P="Password", S="NaCl", 383 c=80000, dkLen=64) = 384 4d dc d8 f6 0b 98 be 21 83 0c ee 5e f2 27 01 f9 385 64 1a 44 18 d0 4c 04 14 ae ff 08 87 6b 34 ab 56 386 a1 d4 25 a1 22 58 33 54 9a db 84 1b 51 c9 b3 17 387 6a 27 2b de bb a1 d0 78 47 8f 62 b3 97 f3 3c 8d 389 11. Test Vectors for scrypt 391 For reference purposes, we provide the following test vectors for 392 scrypt, where the password and salt strings are passed as sequences 393 of ASCII [ANSI.X3-4.1986] octets. 395 The parameters to the scrypt function below are, in order, the 396 password P (octet string), the salt S (octet string), the CPU/Memory 397 cost parameter N, the block size parameter r, and the parallelization 398 parameter p, and the output size dkLen. The output is hex encoded 399 and whitespace is inserted for readability. 401 scrypt (P="", S="", 402 N=16, r=1, p=1, dklen=64) = 403 77 d6 57 62 38 65 7b 20 3b 19 ca 42 c1 8a 04 97 404 f1 6b 48 44 e3 07 4a e8 df df fa 3f ed e2 14 42 405 fc d0 06 9d ed 09 48 f8 32 6a 75 3a 0f c8 1f 17 406 e8 d3 e0 fb 2e 0d 36 28 cf 35 e2 0c 38 d1 89 06 408 scrypt (P="password", S="NaCl", 409 N=1024, r=8, p=16, dkLen=64) = 410 fd ba be 1c 9d 34 72 00 78 56 e7 19 0d 01 e9 fe 411 7c 6a d7 cb c8 23 78 30 e7 73 76 63 4b 37 31 62 412 2e af 30 d9 2e 22 a3 88 6f f1 09 27 9d 98 30 da 413 c7 27 af b9 4a 83 ee 6d 83 60 cb df a2 cc 06 40 415 scrypt (P="pleaseletmein", S="SodiumChloride", 416 N=16384, r=8, p=1, dkLen=64) = 417 70 23 bd cb 3a fd 73 48 46 1c 06 cd 81 fd 38 eb 418 fd a8 fb ba 90 4f 8e 3e a9 b5 43 f6 54 5d a1 f2 419 d5 43 29 55 61 3f 0f cf 62 d4 97 05 24 2a 9a f9 420 e6 1e 85 dc 0d 65 1e 40 df cf 01 7b 45 57 58 87 422 scrypt (P="pleaseletmein", S="SodiumChloride", 423 N=1048576, r=8, p=1, dkLen=64) = 424 21 01 cb 9b 6a 51 1a ae ad db be 09 cf 70 f8 81 425 ec 56 8d 57 4a 2f fd 4d ab e5 ee 98 20 ad aa 47 426 8e 56 fd 8f 4b a5 d0 9f fa 1c 6d 92 7c 40 f4 c3 427 37 30 40 49 e8 a9 52 fb cb f4 5c 6f a7 7a 41 a4 429 12. Copying Conditions 431 The authors agree to grant third parties the irrevocable right to 432 copy, use and distribute this entire document or any portion of it, 433 with or without modification, in any medium, without royalty, 434 provided that, unless separate permission is granted, redistributed 435 modified works do not contain misleading author, version, name of 436 work, or endorsement information. 438 13. Acknowledgements 440 Text in this document was borrowed from [SCRYPT] and [RFC2898]. 442 Feedback on this document were received from Dmitry Chestnykh, 443 Alexander Klink, Rob Kendrick, Royce Williams Ted Rolle, Jr., and 444 Eitan Adler. 446 14. IANA Considerations 448 None. 450 15. Security Considerations 452 This document specifies a cryptographic algorithm. The reader must 453 follow cryptographic research of published attacks. ROMix has been 454 proven sequential memory-hard under the Random Oracle model for the 455 hash function. The security of scrypt relies on the assumption that 456 BlockMix with Salsa20/8 Core does not exhibit any "shortcuts" which 457 would allow it to be iterated more easily than a random oracle. For 458 other claims about the security properties see [SCRYPT]. 460 Passwords and other sensitive data, such as intermediate values, may 461 continue to be stored in memory, core dumps, swap areas, etc, for a 462 long time after the implementation has processed them. This makes 463 attacks on the implementation easier. Thus, implementation should 464 consider storing sensitive data in protected memory areas. How to 465 achieve this is system dependent. 467 By nature and depending on parameters, running the scrypt algorithm 468 may require large amounts of memory. Systems should protect against 469 a denial of service attack resulting from attackers presenting 470 unreasonably large parameters. 472 16. References 474 16.1. Normative References 476 [RFC2898] Kaliski, B., "PKCS #5: Password-Based Cryptography 477 Specification Version 2.0", RFC 2898, September 2000. 479 [RFC6234] Eastlake, D. and T. Hansen, "US Secure Hash Algorithms 480 (SHA and SHA-based HMAC and HKDF)", RFC 6234, May 2011. 482 [SALSA20CORE] 483 Bernstein, D., "The Salsa20 Core", 484 WWW http://cr.yp.to/salsa20.html, March 2005. 486 16.2. Informative References 488 [ANSI.X3-4.1986] 489 American National Standards Institute, "Coded Character 490 Set - 7-bit American Standard Code for Information 491 Interchange", ANSI X3.4, 1986. 493 [SCRYPT] Percival, C., "Stronger key derivation via sequential 494 memory-hard functions", 495 BSDCan'09 http://www.tarsnap.com/scrypt/scrypt.pdf, 496 May 2009. 498 Authors' Addresses 500 Colin Percival 501 Tarsnap 503 Email: cperciva@tarsnap.com 505 Simon Josefsson 506 SJD AB 508 Email: simon@josefsson.org 509 URI: http://josefsson.org/