[238] in cryptography@c2.net mail archive
standardizing key schedules
daemon@ATHENA.MIT.EDU (John Kelsey)
Mon Feb 17 14:39:58 1997
To: "Perry's Crypto List" <cryptography@c2.net>
Reply-To: kelsey@email.plnet.net
From: John Kelsey <kelsey@email.plnet.net>
Date: Mon, 17 Feb 97 05:26:36 CST
-----BEGIN PGP SIGNED MESSAGE-----
[ To: Cryptography list ## Date: 02/15/97 02:59 pm ##
Subject: standardizing key schedules. ]
Arnold Reinhold writes:
>The recent discussion in the cryptography mailing list about key
>scheduling in RC-4/5 and DES suggests to me that key scheduling
>has been glossed over in modern public cryptography. I believe
>that key scheduling algorithms are cryptographic objects in
>their own right and should be considered separately from
>ciphers.
This is reasonable, but there are a couple of obvious problems.
1. Different ciphers sometimes have radically different
structures, and thus radically different key schedule
requirements. RC4 was discussed by Hal Finney as one example.
Most ciphers need only a few hundred or a few thousand bits.
However, there are also a few ciphers, such as Blowfish, SEAL,
and Khufu, that need huge numbers of bits from their key
schedules. All of this can change the requirements of the key
schedule.
2. Adopting a one-size-fits-all approach to key schedules
means making your key schedule strong enough that it can be used
properly by virtually all ciphers. This may rule out some
techniques to make a cheap-but-reasonably-secure key schedule
for some ciphers, where (for example) an attacker might be able
to choose differences in the keys that lead to differences in
the inputs to some rounds, without being able to break the
whole cipher.
All that said, though, I think it would make sense to build
standard strong key schedules. In our paper on related-key
attacks at last year's Crypto, Bruce, David and I talked a
little about this idea. Lars Knudsen has discussed a more
concrete proposal for making product block ciphers resistant to
related-key attacks. Neither of these give a whole key schedule
specification, but both point out ways to strengthen existing
key schedules in most cases. (The typical solution is to do
something cryptographic to the key before it's put into its
standard key schedule. Note that this won't always work--you
still need to analyze their standard key schedule for
weaknesses--but it clearly makes some attacks much harder.)
>Key schedulers take an input bit stream, and deterministically
>produce an output stream that is then used as the cipher's raw
>key. Often the input stream is smaller than the output stream,
>but not always. (e.g. Reducing a user passphrase to a 128 bit
>key). There should be a variety of standard key schedulers
>available so that designers can mix and match key schedulers and
>ciphers to achieve optimal system designs.
I think you're mixing two different issues here. Passphrase
hashing (probably including a salt and lots of iterations to
foil various classes of dictionary attack) is a different issue
than key scheduling.
I think the key schedule should have a very simple interface:
We have a fixed input keylength which is long enough that
brute-force attacks aren't a problem if we're really choosing
random keys. (Call it 128 bits, though some people might prefer
extending it to more, maybe as many as 256 bits.) We produce a
fixed, much longer output sequence, which has some useful
properties:
1. There should be a well-defined way to handle short keys.
If we're expecting a 256-bit key, but we only have a 128-bit
key, the key schedule's designer should tell the user how to
pad it to avoid any new weaknesses.
2. Changing the key should have a radical, nonlinear effect on
the subkeys. In general, to prevent related-key attacks, we
don't want attackers to be able to use key differences to drop
chosen input differences into the middle of our cipher. That
means that it should be very hard to find a change in a key that
results in only a small change in the expanded key, or a change
only in one area of the expanded key. (This is just a
requirement for diffusion.)
3. Knowledge of a few bits of the key should give very little
knowledge about any expanded key bits. Knowledge of patterns in
the key shouldn't give much help in predicting patterns in the
expanded key. This prevents various keysearch speedups based on
known or guessed key bits, and also protects us againt simple
classes of detectable keys that leave some artifact in the
expanded keys that can be detected during encryption. (This is
just a requirement for confusion.)
4. The key schedule should be as efficient as possible, while
meeting the above constraints.
>There are four reasons that I can think of for using a key
>scheduler:
>1. Reducing the storage requirements and data transmission times
>in key management
>2. Reducing the cryptographic overhead associated with
>encrypting session keys with a more expensive cryptosystem such
>as public key cryptography or a one time pad.
>3. Maximizing the amount of security that can be obtained with
>keys that are memorized by individuals, given human factors
>limits on the entropy of keys that people are able and willing
>generate and remember.
>4. Maximizing security in the face regulatory limits on key size
I would add:
5. Defending the cipher from related-key attacks, detectable key
classes, and other key-schedule problems.
6. Taking some of the load off of key generation mechanisms,
which may not be able to securely generate the 33,344 bit key
needed for Blowfish by itself.
7. Ensuring that the expanded key sequence meets whatever
security criteria are necessary. (For Blowfish, ideally, this
would mean checking for duplicate S-box entries. For RC4 this
means that the byte permutation is, in fact, a permutation, has
no obvious relationships with its key values, etc.)
>Reasons 1 and 2 generally favors key schedulers with low
>computational requirements.
>Reasons 3 and 4, on the other hand favor key schedulers with
>high computational requirements. In these cases the threat is
>exhaustive key search. The trade off is between the cost
>imposed on the key search attacker and how much setup time the
>user will tolerate.
I really think it makes sense to separate the normal key
schedule from intentionally-slow passphrase crunching routines.
There will be situations where the cipher needs to have its keys
changed very quickly, and its keys are being generated by a
mechanism which we trust. There will be other situations where
the key will be set based on someone's passphrase, and we will
need to use random salts, hashing, and lots of iterations to add
cost to dictionary attacks.
Of course, in export-restricted ciphers, making the key schedule
cost 1024 encryption operations probably means that instead of
40 bits, we are limited to 30 bits.
>Arnold Reinhold
--John Kelsey, kelsey@email.plnet.net / kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMwg/9EHx57Ag8goBAQEbhAQA7BjauIAlC/ZQ/7u+9HbQc0BEwU1F3rzu
JMy6mgW79uGEI+WJuNt0gF1ItfaBlBdx9+NQpjO5ZoCir85p5Cy0+OE5XheQYNB7
iDXOUVSMOL8UNTKd/7cJZNYH69/PO6yCDM2c5vwo20QgOWK/hY3g7cw16vocZJUt
j9mxzzy7bu8=
=8S+W
-----END PGP SIGNATURE-----
--John Kelsey, kelsey@email.plnet.net / kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
