[305] in cryptography@c2.net mail archive
RC4 key schedule comments
daemon@ATHENA.MIT.EDU (John Kelsey)
Tue Feb 25 18:17:11 1997
To: "Perry's Crypto List" <cryptography@c2.net>
Reply-To: kelsey@email.plnet.net
From: John Kelsey <kelsey@email.plnet.net>
Date: Mon, 24 Feb 97 01:16:59 CST
-----BEGIN PGP SIGNED MESSAGE-----
[ To: Perry's Crypto List ## Date: 02/23/97 04:57 am ##
Subject: RC4 key schedule comments. ]
>From: D.Mignone+C.Maeder
>Subject: Re: standardizing key schedules
>To: Perry's Crypto List
>Date: Thu, 20 Feb 97 15:3
>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 The only
>thing you can say is that initial permutations will probably not
>be equally distributed. How did you compute 2**257 as the number
>of different permutations that RC4 can produce?
Does anyone know whether the unequal distribution of the initial
permutations turns out to be large enough, in practice, to
introduce any weaknesses? Barring some really clever analysis,
I don't think the cipher is made practically weaker by this, but
I'm not sure. I do recall that there are some classes of weak
keys that cannot ever happen in RC4, but could, if all possible
permutations were allowed. Search Dejanews for early RC4 posts
for the reference.
>To our knowledge
>256**256 different userkey can be chosen at random, using the
>full userkey length. This number is much bigger than 256!.
>Therefore you can expect that each permutation is reached at
>least once.
Is there a strong reason to believe that the RC4 key setup
doesn't have large classes of equivalent keys? It looks to me
like the 256-byte key version has many ways to get equivalent
keys, (and of course, there *must* be collisions at that point,
since the keyspace is larger than the total number of
permutations), but I haven't ever worked out the portion of the
keyspace that is eaten up that way with more normal keylengths.
It's not obvious to me that there *are* equivalent keys in (say)
RC4 with 16-byte keys. At least, I don't see an obvious
construction for 16-byte keys, and we don't expect any
randomly-occurring collisions in mapping 128-bit strings to 256!
different permutations. Anyone want to contradict me?
>Domenico Mignone & Christoph Maeder
--John Kelsey, kelsey@email.plnet.net / kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
-----BEGIN PGP SIGNATURE-----
Version: 2.6.2
iQCVAwUBMxE3nUHx57Ag8goBAQF0IQP/ZlFUoVnoQgK05RzBKeXsHHjrjsbexx/i
rk1bGHU7uSK8oqkP6Xm1gZySBkRfaAmV1UosI+MnJGQ4bkhKshSocVLs0PtXEGhG
6JnpZQOu8gsETeVrH51hjHlu7TFsEH6Y59gqcBtQctG9YRXYO/Q15faPy0Yjvfzh
6Qxw0YUUJwE=
=1LCv
-----END PGP SIGNATURE-----
--John Kelsey, kelsey@email.plnet.net / kelsey@counterpane.com
PGP 2.6 fingerprint = 4FE2 F421 100F BB0A 03D1 FE06 A435 7E36
