[310] in cryptography@c2.net mail archive
Re: standardizing key schedules
daemon@ATHENA.MIT.EDU (Arnold G. Reinhold)
Wed Feb 26 09:52:11 1997
Date: Tue, 25 Feb 1997 16:54:28 -0400
To: cryptography@c2.net
From: "Arnold G. Reinhold" <reinhold@world.std.com>
>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
Since I started this, I should point out that with 256 byte random keys the
resulting permutations are uniformly random as well. Each swap depends on a
sum mod 256 one of whose terms is a random 8 bit quantity (a key byte) that
differs for each swap. Since each of the S array values is swapped at least
once, one can know nothing about their final values without the key.
Of course, I suspect just about no one uses 256 byte keys with RC4. It is
the 128 bit case that leaves me a tad uncomfortable.
Arnold Reinhold
