RC4 improvement idea

David Wagner daw at cs.berkeley.edu
Tue Apr 9 08:19:56 PDT 1996


In article <199604060539.VAA22611 at dns1.noc.best.net>,
 <jamesd at echeque.com> wrote:
> At 12:01 PM 4/5/96 -0500, Jack Mott wrote:
> >I got a paper from the cryptography technical report server  
> >"http://www.itribe.net/CTRS/" about a weak class of RC4 keys.
> 
> The report was bogus:
> 
> For one key in 256, you can tell what eight bits of the state box are.  
> For one key in 64000 you can tell what sixteen bits of the state box are, 
> and so on and so forth.
> 
> Such keys are not weak.

No, the report was right: the weak keys are real.

For one key in 256, you have a 13.6% chance of recovering 16 bits of
the original key.

On average, the work factor per key recovered is reduced by a factor
of 35 (i.e. the effective keylength is reduced by 5.1 bits) by using
this class of weak keys.
	- quoting from the report

I've experimentally confirmed this effect myself.  Andrew Roos did
some good work.

Take care,
-- Dave Wagner






More information about the cypherpunks-legacy mailing list