Re: Resolved cases in the known IV attack on WEP

From: Shill (shill@free.fr)
Date: 02/08/03 

From: Shill <shill@free.fr>
Date: Sat, 08 Feb 2003 18:52:57 +0100

> - If you generate X IV's, and you see two (or more) values the same number
> of times, what do you do? There are three obvious strategies:
> A) Since we don't have a clear winner, say we don't know
> B) If the correct value occurs as many times as any other value, say we
> succeeded
> C) Pick randomly among the highest occuring values, and if that one is the
> correct one, say we succeeded.
>
> I have just simulated this, and with strategy (B) (and your probability
> distribution), that at X=31, the probability of success is 0.5061, and at
> X=64, probability=0.7468 -- I assume that this is the strategy you used.
> We, in contrast, used strategy (A) (which, with our probability
> distribution, and at X=54, gives probability 0.5019 -- I don't quite
> remember why we rounded it up to 60 -- possibly out out the spirit of
> conservatism).

You are correct. I made the mistake to "guess" the correct key
byte EVEN when I had two (or more) ties. I cancelled my post when
I realised this but my message reached you anyway :)

There is a different method which (I think) gives a better
estimate: simply count how many IVs are needed to witness the Nth
occurence of any key byte.

Since the frequency of the correct key byte is much higher than
any other (incorrect) key byte, for a reasonable N we will be
fairly confident that we have the correct key byte.

Simulation results
- averaged over 4 million runs
- frequency of the correct key byte = 0.05, other = 0.95/255
- using FreeBSD's random() number generator

N avg # of IVs needed confidence

2 18 29.1%
3 48 64.9%
4 76 87.6%
5 99 96.4%
6 120 99.1%

The interesting thing to note here is for N=3. Whereas the former
method hints at 60 IVs for a 50% confidence, this scheme suggests
only 48 IVs for a 65% confidence (I hope I didn't get anything
wrong THIS time).

Any comments?