third_party/heimdal/doc/standardisation/draft-horowitz-key-derivation-01.txt

   1 Network Working Group                                        M. Horowitz
   2 <draft-horowitz-key-derivation-01.txt>                  Cygnus Solutions
   3 Internet-Draft                                               March, 1997
   4
   5
   6        Key Derivation for Authentication, Integrity, and Privacy
   7
   8 Status 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
  29 Abstract
  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
  44 Deriving 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
  58 Horowitz                                                        [Page 1]
  59
  60 Internet 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
 120 Horowitz                                                        [Page 2]
 121
 122 Internet 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
 150 Deriving 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
 182 Horowitz                                                        [Page 3]
 183
 184 Internet 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
 191 Security Considerations
 192
 193    This entire document deals with security considerations relating to
 194    the use of cryptography in network protocols.
 195
 196
 197 Acknowledgements
 198
 199    I would like to thank Uri Blumenthal, Hugo Krawczyk, and Bill
 200    Sommerfeld for their contributions to this document.
 201
 202
 203 References
 204
 205    [Blumenthal96] Blumenthal, U., "A Better Key Schedule for DES-Like
 206       Ciphers", Proceedings of PRAGOCRYPT '96, 1996.
 207
 208
 209 Author'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
 244 Horowitz                                                        [Page 4]