1Network Working Group M. Horowitz 2<draft-horowitz-key-derivation-01.txt> Cygnus Solutions 3Internet-Draft March, 1997 4 5 6 Key Derivation for Authentication, Integrity, and Privacy 7 8Status of this Memo 9 10 This document is an Internet-Draft. Internet-Drafts are working 11 documents of the Internet Engineering Task Force (IETF), its areas, 12 and its working groups. Note that other groups may also distribute 13 working documents as Internet-Drafts. 14 15 Internet-Drafts are draft documents valid for a maximum of six months 16 and may be updated, replaced, or obsoleted by other documents at any 17 time. It is inappropriate to use Internet-Drafts as reference 18 material or to cite them other than as ``work in progress.'' 19 20 To learn the current status of any Internet-Draft, please check the 21 ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow 22 Directories on ds.internic.net (US East Coast), nic.nordu.net 23 (Europe), ftp.isi.edu (US West Coast), or munnari.oz.au (Pacific 24 Rim). 25 26 Distribution of this memo is unlimited. Please send comments to the 27 author. 28 29Abstract 30 31 Recent advances in cryptography have made it desirable to use longer 32 cryptographic keys, and to make more careful use of these keys. In 33 particular, it is considered unwise by some cryptographers to use the 34 same key for multiple purposes. Since most cryptographic-based 35 systems perform a range of functions, such as authentication, key 36 exchange, integrity, and encryption, it is desirable to use different 37 cryptographic keys for these purposes. 38 39 This RFC does not define a particular protocol, but defines a set of 40 cryptographic transformations for use with arbitrary network 41 protocols and block cryptographic algorithm. 42 43 44Deriving Keys 45 46 In order to use multiple keys for different functions, there are two 47 possibilities: 48 49 - Each protocol ``key'' contains multiple cryptographic keys. The 50 implementation would know how to break up the protocol ``key'' for 51 use by the underlying cryptographic routines. 52 53 - The protocol ``key'' is used to derive the cryptographic keys. 54 The implementation would perform this derivation before calling 55 56 57 58Horowitz [Page 1] 59 60Internet Draft Key Derivation March, 1997 61 62 63 the underlying cryptographic routines. 64 65 In the first solution, the system has the opportunity to provide 66 separate keys for different functions. This has the advantage that 67 if one of these keys is broken, the others remain secret. However, 68 this comes at the cost of larger ``keys'' at the protocol layer. In 69 addition, since these ``keys'' may be encrypted, compromising the 70 cryptographic key which is used to encrypt them compromises all the 71 component keys. Also, the not all ``keys'' are used for all possible 72 functions. Some ``keys'', especially those derived from passwords, 73 are generated from limited amounts of entropy. Wasting some of this 74 entropy on cryptographic keys which are never used is unwise. 75 76 The second solution uses keys derived from a base key to perform 77 cryptographic operations. By carefully specifying how this key is 78 used, all of the advantages of the first solution can be kept, while 79 eliminating some disadvantages. In particular, the base key must be 80 used only for generating the derived keys, and this derivation must 81 be non-invertible and entropy-preserving. Given these restrictions, 82 compromise of one derived keys does not compromise the other subkeys. 83 Attack of the base key is limited, since it is only used for 84 derivation, and is not exposed to any user data. 85 86 Since the derived key has as much entropy as the base keys (if the 87 cryptosystem is good), password-derived keys have the full benefit of 88 all the entropy in the password. 89 90 To generate a derived key from a base key: 91 92 Derived Key = DK(Base Key, Well-Known Constant) 93 94 where 95 96 DK(Key, Constant) = n-truncate(E(Key, Constant)) 97 98 In this construction, E(Key, Plaintext) is a block cipher, Constant 99 is a well-known constant defined by the protocol, and n-truncate 100 truncates its argument by taking the first n bits; here, n is the key 101 size of E. 102 103 If the output of E is is shorter than n bits, then some entropy in 104 the key will be lost. If the Constant is smaller than the block size 105 of E, then it must be padded so it may be encrypted. If the Constant 106 is larger than the block size, then it must be folded down to the 107 block size to avoid chaining, which affects the distribution of 108 entropy. 109 110 In any of these situations, a variation of the above construction is 111 used, where the folded Constant is encrypted, and the resulting 112 output is fed back into the encryption as necessary (the | indicates 113 concatentation): 114 115 K1 = E(Key, n-fold(Constant)) 116 K2 = E(Key, K1) 117 118 119 120Horowitz [Page 2] 121 122Internet Draft Key Derivation March, 1997 123 124 125 K3 = E(Key, K2) 126 K4 = ... 127 128 DK(Key, Constant) = n-truncate(K1 | K2 | K3 | K4 ...) 129 130 n-fold is an algorithm which takes m input bits and ``stretches'' 131 them to form n output bits with no loss of entropy, as described in 132 [Blumenthal96]. In this document, n-fold is always used to produce n 133 bits of output, where n is the key size of E. 134 135 If the size of the Constant is not equal to the block size of E, then 136 the Constant must be n-folded to the block size of E. This number is 137 used as input to E. If the block size of E is less than the key 138 size, then the output from E is taken as input to a second invocation 139 of E. This process is repeated until the number of bits accumulated 140 is greater than or equal to the key size of E. When enough bits have 141 been computed, the first n are taken as the derived key. 142 143 Since the derived key is the result of one or more encryptions in the 144 base key, deriving the base key from the derived key is equivalent to 145 determining the key from a very small number of plaintext/ciphertext 146 pairs. Thus, this construction is as strong as the cryptosystem 147 itself. 148 149 150Deriving Keys from Passwords 151 152 When protecting information with a password or other user data, it is 153 necessary to convert an arbitrary bit string into an encryption key. 154 In addition, it is sometimes desirable that the transformation from 155 password to key be difficult to reverse. A simple variation on the 156 construction in the prior section can be used: 157 158 Key = DK(n-fold(Password), Well-Known Constant) 159 160 The n-fold algorithm is reversible, so recovery of the n-fold output 161 is equivalent to recovery of Password. However, recovering the n- 162 fold output is difficult for the same reason recovering the base key 163 from a derived key is difficult. 164 165 166 167 Traditionally, the transformation from plaintext to ciphertext, or 168 vice versa, is determined by the cryptographic algorithm and the key. 169 A simple way to think of derived keys is that the transformation is 170 determined by the cryptographic algorithm, the constant, and the key. 171 172 For interoperability, the constants used to derive keys for different 173 purposes must be specified in the protocol specification. The 174 constants must not be specified on the wire, or else an attacker who 175 determined one derived key could provide the associated constant and 176 spoof data using that derived key, rather than the one the protocol 177 designer intended. 178 179 180 181 182Horowitz [Page 3] 183 184Internet Draft Key Derivation March, 1997 185 186 187 Determining which parts of a protocol require their own constants is 188 an issue for the designer of protocol using derived keys. 189 190 191Security Considerations 192 193 This entire document deals with security considerations relating to 194 the use of cryptography in network protocols. 195 196 197Acknowledgements 198 199 I would like to thank Uri Blumenthal, Hugo Krawczyk, and Bill 200 Sommerfeld for their contributions to this document. 201 202 203References 204 205 [Blumenthal96] Blumenthal, U., "A Better Key Schedule for DES-Like 206 Ciphers", Proceedings of PRAGOCRYPT '96, 1996. 207 208 209Author's Address 210 211 Marc Horowitz 212 Cygnus Solutions 213 955 Massachusetts Avenue 214 Cambridge, MA 02139 215 216 Phone: +1 617 354 7688 217 Email: marc@cygnus.com 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244Horowitz [Page 4] 245