[294] in cryptography@c2.net mail archive
Re: standardizing key schedules
daemon@ATHENA.MIT.EDU (D.Mignone+C.Maeder)
Mon Feb 24 15:38:18 1997
Date: Mon, 24 Feb 1997 09:46:24 +0100
From: mignone@isi.ee.ethz.ch (D.Mignone+C.Maeder)
To: cryptography@c2.net
Cc: yoda@nym.alias.net
Yoda wrote:
> Domenico Mignone & Christoph Maeder wrote:
> >A. G. Reinhold wrote:
> >> 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.
> >
> >You will reach only a subset of the possible permutations if you consider very
> >short userkeys. But if the userkey is long enough then every permutation can be
> >reached, as you can find in D.E.Knuth ``The Art Of Computer Programming'', Vol.2
>
> But in the standard RC4 initialization, the maximal userkey is 256. How
> do you know that this is sufficiently long?
>
> You are claiming that the map is surjective (onto). The fact that
> 256^256 > 256^2 * 256! does not imply this.
We are claiming that the map is surjective by theoretical considerations, but not
by statistical reflexions. The idea is to look at the key scheduling "backwards".
Given any of the 256! possible permutations, you can always find a sequence of
swappings (these are the values of the variables i and j in AC2), which transform
the identity permutation [0,1,2,...,255] to the chosen permutation. This algorithm
is described in Knuth, Vol.2, page 139.
Once you found the swappings, you can always produce a userkey, which leads to
these swappings. You just have to solve at each step the expression
j_{i+1} = (j_i + S_i + K_i) mod 256 (AC2)
for K_i.
Domenico Mignone & Christoph Maeder
