Re: RC4 improvement idea

<jamesd@echeque.com> wrote:
> > Such keys are not weak.

At 02:57 AM 4/9/96 -0700, David Wagner wrote:
> 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.

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.
 ---------------------------------------------------------------------
              				|  
We have the right to defend ourselves	|   http://www.jim.com/jamesd/
and our property, because of the kind	|  
of animals that we are. True law	|   James A. Donald
derives from this right, not from the	|  
arbitrary power of the state.		|   jamesd@echeque.com

> 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