From: daw@cs.berkeley.edu (David Wagner)
Date: Tue, 9 Apr 1996 23:19:56 +0800
To: cypherpunks@toad.com
Subject: Re: RC4 improvement idea
In-Reply-To: <199604060539.VAA22611@dns1.noc.best.net>
Message-ID: <4kdcad$57@joseph.cs.berkeley.edu>
MIME-Version: 1.0
Content-Type: text/plain


In article <199604060539.VAA22611@dns1.noc.best.net>,
 <jamesd@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