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