Subject: Re: Encrypted compressed vnds
To: None <>
From: der Mouse <mouse@Rodents.Montreal.QC.CA>
List: tech-kern
Date: 08/07/2006 13:23:02
> One of the nice things that RC4 has over its block cipher competition
> is a potentially very, very large key space.  Generally most folks
> don't use it with keys larger than 128 bits, but IIRC the key space
> can be as large as 256 bytes (i.e. 2048 bit).

It looks that way from the API, perhaps, but most of those are
functionally identical.  Arcfour (and presumably RC4) has 256!*256*256
possible internal states; this number is substantially less than
2^2048.  (And, while I'd have to think about it to be sure, it feels to
me as though there is effective duplication among those internal states
as well, bringing the number of different arcfour keystreams down to
something more like 256!*256.)

> And when running with these longer keys, RC4 performance is unchanged
> relative to a shorter key size.

Well, encryption/decryption performance is.  Rekeying performance is
worse (though not very much worse, especially if you do the "discard
the first N bytes of keystream" thing the way you should).

> Of course, many implementations of RC4 may not allow the use of these
> larger keys.  But that is an implementation defect, not a limitation
> of the algorithm itself.

Totally true.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B