1
Network Working Group M. Horowitz
2
<draft-horowitz-key-derivation-01.txt> Cygnus Solutions
3
Internet-Draft March, 1997
6
Key Derivation for Authentication, Integrity, and Privacy
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.
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.''
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
26
Distribution of this memo is unlimited. Please send comments to the
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.
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.
46
In order to use multiple keys for different functions, there are two
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.
53
- The protocol ``key'' is used to derive the cryptographic keys.
54
The implementation would perform this derivation before calling
60
Internet Draft Key Derivation March, 1997
63
the underlying cryptographic routines.
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.
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.
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.
90
To generate a derived key from a base key:
92
Derived Key = DK(Base Key, Well-Known Constant)
96
DK(Key, Constant) = n-truncate(E(Key, Constant))
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
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
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
115
K1 = E(Key, n-fold(Constant))
122
Internet Draft Key Derivation March, 1997
128
DK(Key, Constant) = n-truncate(K1 | K2 | K3 | K4 ...)
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.
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.
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
150
Deriving Keys from Passwords
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:
158
Key = DK(n-fold(Password), Well-Known Constant)
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.
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.
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
184
Internet Draft Key Derivation March, 1997
187
Determining which parts of a protocol require their own constants is
188
an issue for the designer of protocol using derived keys.
191
Security Considerations
193
This entire document deals with security considerations relating to
194
the use of cryptography in network protocols.
199
I would like to thank Uri Blumenthal, Hugo Krawczyk, and Bill
200
Sommerfeld for their contributions to this document.
205
[Blumenthal96] Blumenthal, U., "A Better Key Schedule for DES-Like
206
Ciphers", Proceedings of PRAGOCRYPT '96, 1996.
213
955 Massachusetts Avenue
216
Phone: +1 617 354 7688
217
Email: marc@cygnus.com