idnits 2.17.1 draft-josefsson-scrypt-kdf-02.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 249: '... keyLength INTEGER (1..MAX) OPTIONAL }...' RFC 2119 keyword, line 285: '... 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 (January 26, 2015) is 3371 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- -- Looks like a reference, but probably isn't: '0' on line 318 -- Looks like a reference, but probably isn't: '2' on line 153 -- Looks like a reference, but probably isn't: '1' on line 323 -- Looks like a reference, but probably isn't: '3' on line 154 ** 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: July 30, 2015 SJD AB 6 January 26, 2015 8 The scrypt Password-Based Key Derivation Function 9 draft-josefsson-scrypt-kdf-02 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 July 30, 2015. 36 Copyright Notice 38 Copyright (c) 2015 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 54 2. The Salsa20/8 Core Function . . . . . . . . . . . . . . . . . 3 55 3. The scryptBlockMix Algorithm . . . . . . . . . . . . . . . . 3 56 4. The scryptROMix Algorithm . . . . . . . . . . . . . . . . . . 4 57 5. The scrypt Algorithm . . . . . . . . . . . . . . . . . . . . 5 58 6. ASN.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . 6 59 6.1. ASN.1 Module . . . . . . . . . . . . . . . . . . . . . . 7 60 7. Test Vectors for Salsa20/8 Core . . . . . . . . . . . . . . . 8 61 8. Test Vectors for scryptBlockMix . . . . . . . . . . . . . . . 8 62 9. Test Vectors for scryptROMix . . . . . . . . . . . . . . . . 9 63 10. Test Vectors for PBKDF2 with HMAC-SHA-256 . . . . . . . . . . 9 64 11. Test Vectors for scrypt . . . . . . . . . . . . . . . . . . . 10 65 12. Copying Conditions . . . . . . . . . . . . . . . . . . . . . 11 66 13. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 11 67 14. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 68 15. Security Considerations . . . . . . . . . . . . . . . . . . . 11 69 16. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 70 16.1. Normative References . . . . . . . . . . . . . . . . . . 12 71 16.2. Informative References . . . . . . . . . . . . . . . . . 12 72 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 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 section 8 of [SALSA20SPEC] for its 121 specification, and [SALSA20CORE] for more information. 123 3. The scryptBlockMix Algorithm 125 The scryptBlockMix algorithm is the same as the BlockMix algorithm 126 described in [SCRYPT] but with Salsa20/8 Core used as the hash 127 function H. Below, Salsa(T) corresponds to the Salsa20/8 Core 128 function applied to the octet vector T. 130 Algorithm scryptBlockMix 132 Parameters: 133 r Block size parameter. 135 Input: 136 B[0], ..., B[2 * r - 1] 137 Input vector of 2 * r 64-octet blocks. 139 Output: 140 B'[0], ..., B'[2 * r - 1] 141 Output vector of 2 * r 64-octet blocks. 143 Steps: 145 1. X = B[2 * r - 1] 147 2. for i = 0 to 2 * r - 1 do 148 T = X xor B[i] 149 X = Salsa (T) 150 Y[i] = X 151 end for 153 3. B' = (Y[0], Y[2], ..., Y[2 * r - 2], 154 Y[1], Y[3], ..., Y[2 * r - 1]) 156 4. The scryptROMix Algorithm 158 The scryptROMix algorithm is the same as the ROMix algorithm 159 described in [SCRYPT] but with scryptBlockMix used as the hash 160 function H and the Integerify function explained inline. 162 Algorithm scryptROMix 164 Input: 165 r Block size parameter. 166 B Input octet vector of length 128 * r octets. 167 N CPU/Memory cost parameter, must be larger than 1, 168 a power of 2 and less than 2^(128 * r / 8). 170 Output: 171 B' Output octet vector of length 128 * r octets. 173 Steps: 175 1. X = B 177 2. for i = 0 to N - 1 do 178 V[i] = X 179 X = scryptBlockMix (X) 180 end for 182 3. for i = 0 to N - 1 do 183 j = Integerify (X) mod N 184 where Integerify (B[0] ... B[2 * r - 1]) is defined 185 as the result of interpreting B[2 * r - 1] as a 186 little-endian integer. 187 T = X xor V[j] 188 X = scryptBlockMix (T) 189 end for 191 4. B' = X 193 5. The scrypt Algorithm 195 The PBKDF2-HMAC-SHA-256 function used below denote the PBKDF2 196 algorithm [RFC2898] used with HMAC-SHA-256 [RFC6234] as the PRF. The 197 HMAC-SHA-256 function generates 32 octet outputs. 199 Algorithm scrypt 201 Input: 202 P Passphrase, an octet string. 203 S Salt, an octet string. 204 N CPU/Memory cost parameter, must be larger than 1, 205 a power of 2 and less than 2^(128 * r / 8). 206 r Block size parameter. 207 p Parallelization parameter, a positive integer 208 less than or equal to ((2^32-1) * hLen) / MFLen 209 where hLen is 32 and MFlen is 128 * r. 210 dkLen Intended output length in octets of the derived 211 key; a positive integer less than or equal to 212 (2^32 - 1) * hLen where hLen is 32. 214 Output: 215 DK Derived key, of length dkLen octets. 217 Steps: 219 1. B[0] || B[1] || ... || B[p - 1] = 220 PBKDF2-HMAC-SHA256 (P, S, 1, p * 128 * r) 222 2. for i = 0 to p - 1 do 223 B[i] = scryptROMix (r, B[i], N) 224 end for 226 3. DK = PBKDF2-HMAC-SHA256 (P, B[0] || B[1] || ... || B[p - 1], 227 1, dkLen) 229 6. ASN.1 Syntax 231 This section defines ASN.1 syntax for the scrypt key derivation 232 function. The intended application of these definitions includes 233 PKCS #8 and other syntax for key management. (Various aspects of 234 ASN.1 are specified in several ISO/IEC standards.) 236 The object identifier id-scrypt identifies the scrypt key derivation 237 function. 239 id-scrypt OBJECT IDENTIFIER ::= {1 3 6 1 4 1 11591 4 11} 241 The parameters field associated with this OID in an 242 AlgorithmIdentifier shall have type scrypt-params: 244 scrypt-params ::= SEQUENCE { 245 salt OCTET STRING, 246 costParameter INTEGER (1..MAX), 247 blockSize INTEGER (1..MAX), 248 parallelizationParameter INTEGER (1..MAX), 249 keyLength INTEGER (1..MAX) OPTIONAL } 251 The fields of type scrypt-params have the following meanings: 253 - salt specifies the salt value. It shall be an octet string. 255 - costParameter specifies the CPU/Memory cost parameter N. 257 - blockSize specifies the block size parameter r. 259 - parallelizationParameter specifies the parallelization parameter. 261 - keyLength, an optional field, is the length in octets of the 262 derived key. The maximum key length allowed depends on the 263 implementation; it is expected that implementation profiles may 264 further constrain the bounds. This field only provides convenience; 265 the key length is not cryptographically protected. 267 6.1. ASN.1 Module 269 For reference purposes, the ASN.1 syntax is presented as an ASN.1 270 module here. 272 -- scrypt ASN.1 Module 274 scrypt-0 {1 3 6 1 4 1 11591 4 10} 276 DEFINITIONS ::= BEGIN 278 id-scrypt OBJECT IDENTIFIER ::= {1 3 6 1 4 1 11591 4 11} 280 scrypt-params ::= SEQUENCE { 281 salt OCTET STRING, 282 costParameter INTEGER (1..MAX), 283 blockSize INTEGER (1..MAX), 284 parallelizationParameter INTEGER (1..MAX), 285 keyLength INTEGER (1..MAX) OPTIONAL 286 } 288 END 290 7. Test Vectors for Salsa20/8 Core 292 Below is a sequence of octets to illustrate input and output values 293 for the Salsa20/8 Core. The octets are hex encoded and whitespace is 294 inserted for readability. The value corresponds to the first input 295 and output pair generated by the first scrypt test vector below. 297 INPUT: 298 7e 87 9a 21 4f 3e c9 86 7c a9 40 e6 41 71 8f 26 299 ba ee 55 5b 8c 61 c1 b5 0d f8 46 11 6d cd 3b 1d 300 ee 24 f3 19 df 9b 3d 85 14 12 1e 4b 5a c5 aa 32 301 76 02 1d 29 09 c7 48 29 ed eb c6 8d b8 b8 c2 5e 303 OUTPUT: 304 a4 1f 85 9c 66 08 cc 99 3b 81 ca cb 02 0c ef 05 305 04 4b 21 81 a2 fd 33 7d fd 7b 1c 63 96 68 2f 29 306 b4 39 31 68 e3 c9 e6 bc fe 6b c5 b7 a0 6d 96 ba 307 e4 24 cc 10 2c 91 74 5c 24 ad 67 3d c7 61 8f 81 309 8. Test Vectors for scryptBlockMix 311 Below is a sequence of octets to illustrate input and output values 312 for scryptBlockMix. The test vector uses an r value of 1. The 313 octets are hex encoded and whitespace is inserted for readability. 314 The value corresponds to the first input and output pair generated by 315 the first scrypt test vector below. 317 INPUT 318 B[0] = f7 ce 0b 65 3d 2d 72 a4 10 8c f5 ab e9 12 ff dd 319 77 76 16 db bb 27 a7 0e 82 04 f3 ae 2d 0f 6f ad 320 89 f6 8f 48 11 d1 e8 7b cc 3b d7 40 0a 9f fd 29 321 09 4f 01 84 63 95 74 f3 9a e5 a1 31 52 17 bc d7 323 B[1] = 89 49 91 44 72 13 bb 22 6c 25 b5 4d a8 63 70 fb 324 cd 98 43 80 37 46 66 bb 8f fc b5 bf 40 c2 54 b0 325 67 d2 7c 51 ce 4a d5 fe d8 29 c9 0b 50 5a 57 1b 326 7f 4d 1c ad 6a 52 3c da 77 0e 67 bc ea af 7e 89 328 OUTPUT 329 B'[0] = a4 1f 85 9c 66 08 cc 99 3b 81 ca cb 02 0c ef 05 330 04 4b 21 81 a2 fd 33 7d fd 7b 1c 63 96 68 2f 29 331 b4 39 31 68 e3 c9 e6 bc fe 6b c5 b7 a0 6d 96 ba 332 e4 24 cc 10 2c 91 74 5c 24 ad 67 3d c7 61 8f 81 334 B'[1] = 20 ed c9 75 32 38 81 a8 05 40 f6 4c 16 2d cd 3c 335 21 07 7c fe 5f 8d 5f e2 b1 a4 16 8f 95 36 78 b7 336 7d 3b 3d 80 3b 60 e4 ab 92 09 96 e5 9b 4d 53 b6 337 5d 2a 22 58 77 d5 ed f5 84 2c b9 f1 4e ef e4 25 339 9. Test Vectors for scryptROMix 341 Below is a sequence of octets to illustrate input and output values 342 for scryptROMix. The test vector uses an r value of 1 and an N value 343 of 16. The octets are hex encoded and whitespace is inserted for 344 readability. The value corresponds to the first input and output 345 pair generated by the first scrypt test vector below. 347 INPUT: 348 B = f7 ce 0b 65 3d 2d 72 a4 10 8c f5 ab e9 12 ff dd 349 77 76 16 db bb 27 a7 0e 82 04 f3 ae 2d 0f 6f ad 350 89 f6 8f 48 11 d1 e8 7b cc 3b d7 40 0a 9f fd 29 351 09 4f 01 84 63 95 74 f3 9a e5 a1 31 52 17 bc d7 352 89 49 91 44 72 13 bb 22 6c 25 b5 4d a8 63 70 fb 353 cd 98 43 80 37 46 66 bb 8f fc b5 bf 40 c2 54 b0 354 67 d2 7c 51 ce 4a d5 fe d8 29 c9 0b 50 5a 57 1b 355 7f 4d 1c ad 6a 52 3c da 77 0e 67 bc ea af 7e 89 357 OUTPUT: 358 B = 79 cc c1 93 62 9d eb ca 04 7f 0b 70 60 4b f6 b6 359 2c e3 dd 4a 96 26 e3 55 fa fc 61 98 e6 ea 2b 46 360 d5 84 13 67 3b 99 b0 29 d6 65 c3 57 60 1f b4 26 361 a0 b2 f4 bb a2 00 ee 9f 0a 43 d1 9b 57 1a 9c 71 362 ef 11 42 e6 5d 5a 26 6f dd ca 83 2c e5 9f aa 7c 363 ac 0b 9c f1 be 2b ff ca 30 0d 01 ee 38 76 19 c4 364 ae 12 fd 44 38 f2 03 a0 e4 e1 c4 7e c3 14 86 1f 365 4e 90 87 cb 33 39 6a 68 73 e8 f9 d2 53 9a 4b 8e 367 10. Test Vectors for PBKDF2 with HMAC-SHA-256 369 Below is a sequence of octets illustring input and output values for 370 PBKDF2-HMAC-SHA-256. The octets are hex encoded and whitespace is 371 inserted for readability. The test vectors below can be used to 372 verify the PBKDF2-HMAC-SHA-256 [RFC2898] function. The password and 373 salt strings are passed as sequences of ASCII [RFC0020] 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 381 PBKDF2-HMAC-SHA-256 (P="Password", S="NaCl", 382 c=80000, dkLen=64) = 383 4d dc d8 f6 0b 98 be 21 83 0c ee 5e f2 27 01 f9 384 64 1a 44 18 d0 4c 04 14 ae ff 08 87 6b 34 ab 56 385 a1 d4 25 a1 22 58 33 54 9a db 84 1b 51 c9 b3 17 386 6a 27 2b de bb a1 d0 78 47 8f 62 b3 97 f3 3c 8d 388 11. Test Vectors for scrypt 390 For reference purposes, we provide the following test vectors for 391 scrypt, where the password and salt strings are passed as sequences 392 of ASCII [RFC0020] octets. 394 The parameters to the scrypt function below are, in order, the 395 password P (octet string), the salt S (octet string), the CPU/Memory 396 cost parameter N, the block size parameter r, and the parallelization 397 parameter p, and the output size dkLen. The output is hex encoded 398 and whitespace is inserted for readability. 400 scrypt (P="", S="", 401 N=16, r=1, p=1, dklen=64) = 402 77 d6 57 62 38 65 7b 20 3b 19 ca 42 c1 8a 04 97 403 f1 6b 48 44 e3 07 4a e8 df df fa 3f ed e2 14 42 404 fc d0 06 9d ed 09 48 f8 32 6a 75 3a 0f c8 1f 17 405 e8 d3 e0 fb 2e 0d 36 28 cf 35 e2 0c 38 d1 89 06 407 scrypt (P="password", S="NaCl", 408 N=1024, r=8, p=16, dkLen=64) = 409 fd ba be 1c 9d 34 72 00 78 56 e7 19 0d 01 e9 fe 410 7c 6a d7 cb c8 23 78 30 e7 73 76 63 4b 37 31 62 411 2e af 30 d9 2e 22 a3 88 6f f1 09 27 9d 98 30 da 412 c7 27 af b9 4a 83 ee 6d 83 60 cb df a2 cc 06 40 414 scrypt (P="pleaseletmein", S="SodiumChloride", 415 N=16384, r=8, p=1, dkLen=64) = 416 70 23 bd cb 3a fd 73 48 46 1c 06 cd 81 fd 38 eb 417 fd a8 fb ba 90 4f 8e 3e a9 b5 43 f6 54 5d a1 f2 418 d5 43 29 55 61 3f 0f cf 62 d4 97 05 24 2a 9a f9 419 e6 1e 85 dc 0d 65 1e 40 df cf 01 7b 45 57 58 87 421 scrypt (P="pleaseletmein", S="SodiumChloride", 422 N=1048576, r=8, p=1, dkLen=64) = 423 21 01 cb 9b 6a 51 1a ae ad db be 09 cf 70 f8 81 424 ec 56 8d 57 4a 2f fd 4d ab e5 ee 98 20 ad aa 47 425 8e 56 fd 8f 4b a5 d0 9f fa 1c 6d 92 7c 40 f4 c3 426 37 30 40 49 e8 a9 52 fb cb f4 5c 6f a7 7a 41 a4 428 12. Copying Conditions 430 The authors agree to grant third parties the irrevocable right to 431 copy, use and distribute this entire document or any portion of it, 432 with or without modification, in any medium, without royalty, 433 provided that, unless separate permission is granted, redistributed 434 modified works do not contain misleading author, version, name of 435 work, or endorsement information. 437 13. Acknowledgements 439 Text in this document was borrowed from [SCRYPT] and [RFC2898]. 441 Feedback on this document were received from Dmitry Chestnykh, 442 Alexander Klink, Rob Kendrick, Royce Williams Ted Rolle, Jr., and 443 Eitan Adler. 445 14. IANA Considerations 447 None. 449 15. Security Considerations 451 This document specifies a cryptographic algorithm. The reader must 452 follow cryptographic research of published attacks. ROMix has been 453 proven sequential memory-hard under the Random Oracle model for the 454 hash function. The security of scrypt relies on the assumption that 455 BlockMix with Salsa20/8 Core does not exhibit any "shortcuts" which 456 would allow it to be iterated more easily than a random oracle. For 457 other claims about the security properties see [SCRYPT]. 459 Passwords and other sensitive data, such as intermediate values, may 460 continue to be stored in memory, core dumps, swap areas, etc, for a 461 long time after the implementation has processed them. This makes 462 attacks on the implementation easier. Thus, implementation should 463 consider storing sensitive data in protected memory areas. How to 464 achieve this is system dependent. 466 By nature and depending on parameters, running the scrypt algorithm 467 may require large amounts of memory. Systems should protect against 468 a denial of service attack resulting from attackers presenting 469 unreasonably large parameters. 471 16. References 472 16.1. Normative References 474 [RFC2898] Kaliski, B., "PKCS #5: Password-Based Cryptography 475 Specification Version 2.0", RFC 2898, September 2000. 477 [RFC6234] Eastlake, D. and T. Hansen, "US Secure Hash Algorithms 478 (SHA and SHA-based HMAC and HKDF)", RFC 6234, May 2011. 480 [SALSA20SPEC] 481 Bernstein, D., "Salsa20 specification", WWW 482 http://cr.yp.to/snuffle/spec.pdf, April 2005. 484 [SALSA20CORE] 485 Bernstein, D., "The Salsa20 Core", WWW 486 http://cr.yp.to/salsa20.html, March 2005. 488 16.2. Informative References 490 [RFC0020] Cerf, V., "ASCII format for network interchange", RFC 20, 491 October 1969. 493 [SCRYPT] Percival, C., "Stronger key derivation via sequential 494 memory-hard functions", BSDCan'09 495 http://www.tarsnap.com/scrypt/scrypt.pdf, May 2009. 497 Authors' Addresses 499 Colin Percival 500 Tarsnap 502 Email: cperciva@tarsnap.com 504 Simon Josefsson 505 SJD AB 507 Email: simon@josefsson.org 508 URI: http://josefsson.org/