Network Working Group B. Kaliski Request for Comments: 2898 RSA Laboratories Category: Informational September 2000 PKCS #5: Password-Based Cryptography Specification Version 2.0 Status of this Memo This memo provides information for the Internet community. It does not specify an Internet standard of any kind. Distribution of this memo is unlimited. Copyright Notice Copyright (C) The Internet Society (2000). All Rights Reserved. Abstract This memo represents a republication of PKCS #5 v2.0 from RSA Laboratories' Public-Key Cryptography Standards (PKCS) series, and change control is retained within the PKCS process. The body of this document, except for the security considerations section, is taken directly from that specification. This document provides recommendations for the implementation of password-based cryptography, covering key derivation functions, encryption schemes, message-authentication schemes, and ASN.1 syntax identifying the techniques. The recommendations are intended for general application within computer and communications systems, and as such include a fair amount of flexibility. They are particularly intended for the protection of sensitive information such as private keys, as in PKCS #8 [25]. It is expected that application standards and implementation profiles based on these specifications may include additional constraints. Other cryptographic techniques based on passwords, such as password- based key entity authentication and key establishment protocols [4][5][26] are outside the scope of this document. Guidelines for the selection of passwords are also outside the scope. Kaliski Informational [Page 1] RFC 2898 Password-Based Cryptography September 2000 Table of Contents 1. Introduction ............................................... 3 2. Notation ................................................... 3 3. Overview ................................................... 4 4. Salt and iteration count ................................... 6 4.1 Salt ................................................... 6 4.2 Iteration count ........................................ 8 5. Key derivation functions ................................... 8 5.1 PBKDF1 ................................................. 9 5.2 PBKDF2 ................................................. 9 6. Encryption schemes ......................................... 11 6.1 PBES1 .................................................. 12 6.1.1 Encryption operation ............................ 12 6.1.2 Decryption operation ............................ 13 6.2 PBES2 .................................................. 14 6.2.1 Encryption operation ............................ 14 6.2.2 Decryption operation ............................ 15 7. Message authentication schemes ............................. 15 7.1 PBMAC1 ................................................. 16 7.1.1 MAC generation .................................. 16 7.1.2 MAC verification ................................ 16 8. Security Considerations .................................... 17 9. Author's Address............................................ 17 A. ASN.1 syntax ............................................... 18 A.1 PBKDF1 ................................................. 18 A.2 PBKDF2 ................................................. 18 A.3 PBES1 .................................................. 20 A.4 PBES2 .................................................. 20 A.5 PBMAC1 ................................................. 21 B. Supporting techniques ...................................... 22 B.1 Pseudorandom functions ................................. 22 B.2 Encryption schemes ..................................... 23 B.3 Message authentication schemes ......................... 26 C. ASN.1 module ............................................... 26 Intellectual Property Considerations ............................ 30 Revision history ................................................ 30 References ...................................................... 31 Contact Information & About PKCS ................................ 33 Full Copyright Statement ........................................ 34 Kaliski Informational [Page 2] RFC 2898 Password-Based Cryptography September 2000 1. Introduction This document provides recommendations for the implementation of password-based cryptography, covering the following aspects: - key derivation functions - encryption schemes - message-authentication schemes - ASN.1 syntax identifying the techniques The recommendations are intended for general application within computer and communications systems, and as such include a fair amount of flexibility. They are particularly intended for the protection of sensitive information such as private keys, as in PKCS #8 [25]. It is expected that application standards and implementation profiles based on these specifications may include additional constraints. Other cryptographic techniques based on passwords, such as password- based key entity authentication and key establishment protocols [4][5][26] are outside the scope of this document. Guidelines for the selection of passwords are also outside the scope. This document supersedes PKCS #5 version 1.5 [24], but includes compatible techniques. 2. Notation C ciphertext, an octet string c iteration count, a positive integer DK derived key, an octet string dkLen length in octets of derived key, a positive integer EM encoded message, an octet string Hash underlying hash function hLen length in octets of pseudorandom function output, a positive integer l length in blocks of derived key, a positive integer IV initialization vector, an octet string K encryption key, an octet string Kaliski Informational [Page 3] RFC 2898 Password-Based Cryptography September 2000 KDF key derivation function M message, an octet string P password, an octet string PRF underlying pseudorandom function PS padding string, an octet string psLen length in octets of padding string, a positive integer S salt, an octet string T message authentication code, an octet string T_1, ..., T_l, U_1, ..., U_c intermediate values, octet strings 01, 02, ..., 08 octets with value 1, 2, ..., 8 \xor bit-wise exclusive-or of two octet strings || || octet length operator || concatenation operator substring extraction operator: extracts octets i through j, 0 <= i <= j 3. Overview In many applications of public-key cryptography, user security is ultimately dependent on one or more secret text values or passwords. Since a password is not directly applicable as a key to any conventional cryptosystem, however, some processing of the password is required to perform cryptographic operations with it. Moreover, as passwords are often chosen from a relatively small space, special care is required in that processing to defend against search attacks. A general approach to password-based cryptography, as described by Morris and Thompson [8] for the protection of password tables, is to combine a password with a salt to produce a key. The salt can be viewed as an index into a large set of keys derived from the password, and need not be kept secret. Although it may be possible for an opponent to construct a table of possible passwords (a so- called "dictionary attack"), constructing a table of possible keys Kaliski Informational [Page 4] RFC 2898 Password-Based Cryptography September 2000 will be difficult, since there will be many possible keys for each password. An opponent will thus be limited to searching through passwords separately for each salt. Another approach to password-based cryptography is to construct key derivation techniques that are relatively expensive, thereby increasing the cost of exhaustive search. One way to do this is to include an iteration count in the key derivation technique, indicating how many times to iterate some underlying function by which keys are derived. A modest number of iterations, say 1000, is not likely to be a burden for legitimate parties when computing a key, but will be a significant burden for opponents. Salt and iteration count formed the basis for password-based encryption in PKCS #5 v1.5, and adopted here as well for the various cryptographic operations. Thus, password-based key derivation as defined here is a function of a password, a salt, and an iteration count, where the latter two quantities need not be kept secret. From a password-based key derivation function, it is straightforward to define password-based encryption and message authentication schemes. As in PKCS #5 v1.5, the password-based encryption schemes here are based on an underlying, conventional encryption scheme, where the key for the conventional scheme is derived from the password. Similarly, the password-based message authentication scheme is based on an underlying conventional scheme. This two-layered approach makes the password-based techniques modular in terms of the underlying techniques they can be based on. It is expected that the password-based key derivation functions may find other applications than just the encryption and message authentication schemes defined here. For instance, one might derive a set of keys with a single application of a key derivation function, rather than derive each key with a separate application of the function. The keys in the set would be obtained as substrings of the output of the key derivation function. This approach might be employed as part of key establishment in a session-oriented protocol. Another application is password checking, where the output of the key derivation function is stored (along with the salt and iteration count) for the purposes of subsequent verification of a password. Throughout this document, a password is considered to be an octet string of arbitrary length whose interpretation as a text string is unspecified. In the interest of interoperability, however, it is recommended that applications follow some common text encoding rules. ASCII and UTF-8 [27] are two possibilities. (ASCII is a subset of UTF-8.) Kaliski Informational [Page 5] RFC 2898 Password-Based Cryptography September 2000 Although the selection of passwords is outside the scope of this document, guidelines have been published [17] that may well be taken into account. 4. Salt and Iteration Count Inasmuch as salt and iteration count are central to the techniques defined in this document, some further discussion is warranted. 4.1 Salt A salt in password-based cryptography has traditionally served the purpose of producing a large set of keys corresponding to a given password, among which one is selected at random according to the salt. An individual key in the set is selected by applying a key derivation function KDF, as DK = KDF (P, S) where DK is the derived key, P is the password, and S is the salt. This has two benefits: 1. It is difficult for an opponent to precompute all the keys corresponding to a dictionary of passwords, or even the most likely keys. If the salt is 64 bits long, for instance, there will be as many as 2^64 keys for each password. An opponent is thus limited to searching for passwords after a password-based operation has been performed and the salt is known. 2. It is unlikely that the same key will be selected twice. Again, if the salt is 64 bits long, the chance of "collision" between keys does not become significant until about 2^32 keys have been produced, according to the Birthday Paradox. This addresses some of the concerns about interactions between multiple uses of the same key, which may apply for some encryption and authentication techniques. In password-based encryption, the party encrypting a message can gain assurance that these benefits are realized simply by selecting a large and sufficiently random salt when deriving an encryption key from a password. A party generating a message authentication code can gain such assurance in a similar fashion. The party decrypting a message or verifying a message authentication code, however, cannot be sure that a salt supplied by another party has actually been generated at random. It is possible, for instance, that the salt may have been copied from another password-based operation, in an attempt to exploit interactions between multiple Kaliski Informational [Page 6] RFC 2898 Password-Based Cryptography September 2000 uses of the same key. For instance, suppose two legitimate parties exchange a encrypted message, where the encryption key is an 80-bit key derived from a shared password with some salt. An opponent could take the salt from that encryption and provide it to one of the parties as though it were for a 40-bit key. If the party reveals the result of decryption with the 40-bit key, the opponent may be able to solve for the 40-bit key. In the case that 40-bit key is the first half of the 80-bit key, the opponent can then readily solve for the remaining 40 bits of the 80-bit key. To defend against such attacks, either the interaction between multiple uses of the same key should be carefully analyzed, or the salt should contain data that explicitly distinguishes between different operations. For instance, the salt might have an additional, non-random octet that specifies whether the derived key is for encryption, for message authentication, or for some other operation. Based on this, the following is recommended for salt selection: 1. If there is no concern about interactions between multiple uses of the same key (or a prefix of that key) with the password- based encryption and authentication techniques supported for a given password, then the salt may be generated at random and need not be checked for a particular format by the party receiving the salt. It should be at least eight octets (64 bits) long. 2. Otherwise, the salt should contain data that explicitly distinguishes between different operations and different key lengths, in addition to a random part that is at least eight octets long, and this data should be checked or regenerated by the party receiving the salt. For instance, the salt could have an additional non-random octet that specifies the purpose of the derived key. Alternatively, it could be the encoding of a structure that specifies detailed information about the derived key, such as the encryption or authentication technique and a sequence number among the different keys derived from the password. The particular format of the additional data is left to the application. Note. If a random number generator or pseudora