[249] in cryptography@c2.net mail archive
Re: standardizing key schedules
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Thu Feb 20 15:11:26 1997
In-Reply-To: <MAPI.Id.0016.00656c73657920203430334230303030@MAPI.to.RFC822>
Date: Tue, 18 Feb 1997 11:35:30 -0400
To: cryptography@c2.net
From: "Arnold G. Reinhold" <reinhold@world.std.com>
Cc: hal@rain.org, kelsey@email.plnet.net
I proposed:
>>that key scheduling algorithms are cryptographic objects in
>>their own right and should be considered separately from
>>ciphers.
>
Hal Finney pointed out that in the examples I used I overlooked RC4's
requirement for the S array be a permutation of 0..255, and John Kelsey
cited the limitations of a "one-size-fits-all" approach while pointing out
additional criteria a key schedule must meet.
I am not advocating a single-standard approach to key scheduling at all,
but rather a modular approach that lets cryptosystem designers build a key
schedule that is optimal for their needs.
I would argue that RC4's key schedule is an example of "one-size-fits-all."
Ron Rivest designed a reasonable compromise but it is still a compromise.
RC4 tries to:
1. Pick a permutations of 0..255 that is cryptographically acceptable in
some sense.
2. Be hard to implement in hardware
3. Still be fast enough in software
Depending on what tradeoffs you wanted, you can do better on each of these:
The initial permutations RC4 produces are hardly random. Counting all key
lengths, RC4 can only produce 2**257 different permutations, a very sparse
subset of the 256! ~= 2**1684 possible permutations. I don't see any
cryptoanalytic weakness that results from RC4's use of this limited subset,
but one can produce true random permuations of 0..255. A designer might
choose to do this to eliminate one source of cryptoanalytic uncertainty. In
the video example I gave, one could transmit such a true random permutation
over a trusted channel before each frame.
As John points out, if one is using a long enough key, slow key setup is
not so important and might be a big disadvantage. I think it is possible to
create in hardware an acceptable initial permutation of 0..255 in much less
than 256 cycles by using more complex shuffles one each round.
For some applications, you might prefer slower key setup. If you and a
friend are using RC4 to encrypt personal e-mail on their 150 MHz, there is
no reason to only use 256 initial permutation cycles. You could use 256,000
cycles and never notice a delay. One simple modification to RC4 would make
the number of initial permutation cycles a variable whose value is either
agreed to ahead of time or transmitted with the message header.
John writes:
>I really think it makes sense to separate the normal key
>schedule from intentionally-slow passphrase crunching routines.
The question of how to design an optimal slow-down routine does not depend
on whether it is to be used for passphrase hashing or key scheduling. I
think the former is critically important now -- and much neglected since
most security chains start with some kind of human-memorized secret. But
the later may become important too:
>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.
Maybe, maybe not. I am curious how 40 bit RC4 with 88-bit salt and an MD5
pass got approved for SSL. Depending on how the GAK politics play out, we
could see blanket approval of 40-bit keys.
Arnold Reinhold
