Network Working Group M. Horowitz <draft-horowitz-key-derivation-01.txt> Cygnus Solutions Internet-Draft March, 1997 Key Derivation for Authentication, Integrity, and Privacy Status of this Memo This document is an Internet-Draft. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as ``work in progress.'' To learn the current status of any Internet-Draft, please check the ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow Directories on ds.internic.net (US East Coast), nic.nordu.net (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific Rim). Distribution of this memo is unlimited. Please send comments to the author. Abstract Recent advances in cryptography have made it desirable to use longer cryptographic keys, and to make more careful use of these keys. In particular, it is considered unwise by some cryptographers to use the same key for multiple purposes. Since most cryptographic-based systems perform a range of functions, such as authentication, key exchange, integrity, and encryption, it is desirable to use different cryptographic keys for these purposes. This RFC does not define a particular protocol, but defines a set of cryptographic transformations for use with arbitrary network protocols and block cryptographic algorithm. Deriving Keys In order to use multiple keys for different functions, there are two possibilities: - Each protocol ``key'' contains multiple cryptographic keys. The implementation would know how to break up the protocol ``key'' for use by the underlying cryptographic routines. - The protocol ``key'' is used to derive the cryptographic keys. The implementation would perform this derivation before calling Horowitz [Page 1] Internet Draft Key Derivation March, 1997 the underlying cryptographic routines. In the first solution, the system has the opportunity to provide separate keys for different functions. This has the advantage that if one of these keys is broken, the others remain secret. However, this comes at the cost of larger ``keys'' at the protocol layer. In addition, since these ``keys'' may be encrypted, compromising the cryptographic key which is used to encrypt them compromises all the component keys. Also, the not all ``keys'' are used for all possible functions. Some ``keys'', especially those derived from passwords, are generated from limited amounts of entropy. Wasting some of this entropy on cryptographic keys which are never used is unwise. The second solution uses keys derived from a base key to perform cryptographic operations. By carefully specifying how this key is used, all of the advantages of the first solution can be kept, while eliminating some disadvantages. In particular, the base key must be used only for generating the derived keys, and this derivation must be non-invertible and entropy-preserving. Given these restrictions, compromise of one derived keys does not compromise the other subkeys. Attack of the base key is limited, since it is only used for derivation, and is not exposed to any user data. Since the derived key has as much entropy as the base keys (if the cryptosystem is good), password-derived keys have the full benefit of all the entropy in the password. To generate a derived key from a base key: Derived Key = DK(Base Key, Well-Known Constant) where DK(Key, Constant) = n-truncate(E(Key, Constant)) In this construction, E(Key, Plaintext) is a block cipher, Constant is a well-known constant defined by the protocol, and n-truncate truncates its argument by taking the first n bits; here, n is the key size of E. If the output of E is is shorter than n bits, then some entropy in the key will be lost. If the Constant is smaller than the block size of E, then it must be padded so it may be encrypted. If the Constant is larger than the block size, then it must be folded down to the block size to avoid chaining, which affects the distribution of entropy. In any of these situations, a variation of the above construction is used, where the folded Constant is encrypted, and the resulting output is fed back into the encryption as necessary (the | indicates concatentation): K1 = E(Key, n-fold(Constant)) K2 = E(Key, K1) Horowitz [Page 2] Internet Draft Key Derivation March, 1997 K3 = E(Key, K2) K4 = ... DK(Key, Constant) = n-truncate(K1 | K2 | K3 | K4 ...) n-fold is an algorithm which takes m input bits and ``stretches'' them to form n output bits with no loss of entropy, as described in [Blumenthal96]. In this document, n-fold is always used to produce n bits of output, where n is the key size of E. If the size of the Constant is not equal to the block size of E, then the Constant must be n-folded to the block size of E. This number is used as input to E. If the block size of E is less than the key size, then the output from E is taken as input to a second invocation of E. This process is repeated until the number of bits accumulated is greater than or equal to the key size of E. When enough bits have been computed, the first n are taken as the derived key. Since the derived key is the result of one or more encryptions in the base key, deriving the base key from the derived key is equivalent to determining the key from a very small number of plaintext/ciphertext pairs. Thus, this construction is as strong as the cryptosystem itself. Deriving Keys from Passwords When protecting information with a password or other user data, it is necessary to convert an arbitrary bit string into an encryption key. In addition, it is sometimes desirable that the transformation from password to key be difficult to reverse. A simple variation on the construction in the prior section can be used: Key = DK(n-fold(Password), Well-Known Constant) The n-fold algorithm is reversible, so recovery of the n-fold output is equivalent to recovery of Password. However, recovering the n- fold output is difficult for the same reason recovering the base key from a derived key is difficult. Traditionally, the transformation from plaintext to ciphertext, or vice versa, is determined by the cryptographic algorithm and the key. A simple way to think of derived keys is that the transformation is determined by the cryptographic algorithm, the constant, and the key. For interoperability, the constants used to derive keys for different purposes must be specified in the protocol specification. The constants must not be specified on the wire, or else an attacker who determined one derived key could provide the associated constant and spoof data using that derived key, rather than the one the protocol designer intended. Horowitz [Page 3] Internet Draft Key Derivation March, 1997 Determining which parts of a protocol require their own constants is an issue for the designer of protocol using derived keys. Security Considerations This entire document deals with security considerations relating to the use of cryptography in network protocols. Acknowledgements I would like to thank Uri Blumenthal, Hugo Krawczyk, and Bill Sommerfeld for their contributions to this document. References [Blumenthal96] Blumenthal, U., "A Better Key Schedule for DES-Like Ciphers", Proceedings of PRAGOCRYPT '96, 1996. Author's Address Marc Horowitz Cygnus Solutions 955 Massachusetts Avenue Cambridge, MA 02139 Phone: +1 617 354 7688 Email: marc@cygnus.com Horowitz [Page 4]