Re: RC4 improvement idea

["D.A. Wagner" <daw27@newton.cam.ac.uk>]

> At 02:57 AM 4/9/96 -0700, David Wagner wrote:
> > 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.
> 
> Why do you not just assume the last byte of the key is 0x4A
> 
> Then for one key in 256 the effective keylength is reduced by a
> whole 8 bits instead of a measly 5.1 bits.

No.  The 5.1 bit figure is averaged over the whole damn keyspace.
If you pick a random 40 bit key (not necessarily a weak key), and
I apply the Andrew Woos attack, I can guess your key with 2^{40-5.1}
= 2^34.9 work factor, on average.

Look.  1 in 256 keys are weak.  For a weak key, you have a 1/7.35 = 13.6%
chance of recovering 16 bits of the key.  This is an advantage for the
attacker, as 2^16 / (256*7.35) = 34.8 = 2^5.1 > 1.

Suppose you called keys with the last byte 0x4A jamesd-weak.  1 in 256
keys are jamesd-weak.  For a jamesd-weak key, you have a 1.0 = 100% chance
of recovering 8 bits of the key.  This is not an advantage for the attacker,
as 2^8 / (256*1.0) = 1.0.

Keep an open mind,
-- Dave Wagner