[224] in cryptography@c2.net mail archive
Key Scheduling vs. Ciphering -- A Hole In Modern Cryptography?
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Sat Feb 15 11:20:35 1997
Date: Fri, 14 Feb 1997 14:52:57 -0400
To: cryptography@c2.net
From: "Arnold G. Reinhold" <reinhold@world.std.com>
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.
First let me point out that every cipher has a "raw" key size, namely the
string of all bits within the cipher algorithm, as it is designed, that may
be set randomly and independently without reducing security. (I am
excluding "cryptographic constants" here.)
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.
While there is some overlap between a key scheduler and a hash function,
they have distinct design criteria. The strict anti-collision requirement
on hash functions may be overkill for key scheduling. In addition, where
hash functions are designed for speed, high computational requirements are
sometimes a desired feature in a key scheduler.
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
Reasons 1 and 2 generally favors key schedulers with low computational
requirements.
For example, designers of a wideband video conferencing system might choose
RC4 ciphering for it's computational simplicity. However, if they want to
change keys frequently, RC4's set up might be onerous. Therefore the
designers might choose a different scheme implementable in hardware without
iterations. For example, each output bit might be the XOR of, say, 9 input
bits chosen randomly at design time. (I am not asserting that this would be
as strong as the RC4 key schedule, but it might do.)
Indeed, if they had a slow but secure back channel available, designers
might elect to send a fresh 2K random bit stream every few frames to serve
as RC4's raw key (the S array), skipping the scheduling step altogether.
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.
As far as I know, developing key schedulers that maximize the cost to
searchers while minimizing the burden for users has not received much
attention.
In my paper on PGP passphrase usage
<http://world.std.com/~reinhold/passphrase.survey.asc>
I argued that the transformation from user passphrase input to key should
be highly computational intensive. A Pentium owner would hardly notice a
1/2 second delay in opening his PGP secret key. If the passpharase to key
algorithm were designed to make maximum use of the hardware available,
using lots of 32 bit multiplies and megabytes of memory, it could well take
on the order of 10 million gates to duplicate. 1/2 second on a fully used
Pentium could easily add a factor of a million in strength. This translates
to about 10 bits key entropy, a substantial security improvement, given
what people actually use for passphrases.
Arnold Reinhold
