[510] in cryptography@c2.net mail archive
Re: Key Scheduling vs. Ciphering -- A Hole In Modern Cryptography?
daemon@ATHENA.MIT.EDU (Hal Finney)
Sat Apr 5 16:02:13 1997
Date: Sat, 5 Apr 1997 12:12:58 -0800
From: Hal Finney <hal@rain.org>
To: cryptography@c2.net, jamesd@echeque.com
James Donald, jamesd@echeque.com, writes:
> At 09:38 AM 2/15/97 -0800, Hal Finney wrote:
> > This is an example of the point I was making above. RC4's internal
> > key table MUST be a permutation of 0..255. Filling it with random
> > bits will not work and will potentially produce a much weaker cipher.
>
> I seem to recollect that it cannot be just any permutation either.
> The key setup routine is designed to avoid generating certain
> disastrous permutations.
RC4 goes like this:
Initialize i=j=0, and the s[] array by the key setup, then loop forever
(all mod 256):
i += 1;
j += s[i];
swap s[i] and s[j]
output s[s[i]+s[j]]
You might be thinking of the infamous RC4 "steady state" defined as
j = i+1 and s[j] = 1. i increments to be equal to j, then j increments
by 1 since s[i] is now 1. We swap s[i] and s[j], leaving s[j] as 1,
and we are back in the steady state.
RC4 avoids this not by constraining the permutation in any way, but
by starting with i=j=0. This is not in the state above since j != i+1.
And you can't fall into the steady state since the state is preserved
backwards in time as well as forwards. So this initial state is safe.
BTW I see there will be a paper at Eurocrypt in May titled "Linear
Statistical Weakness of Alleged RC4 Keystream Generator".
Hal
