Resolved cases in the known IV attack on WEP

From: Shill (shill@free.fr)
Date: 01/22/03 

From: Shill <shill@free.fr>
Date: Wed, 22 Jan 2003 14:39:14 +0100

I've read "Weaknesses in the key scheduling algorithm of RC4" by Scott
Fluhrer, Itsik Mantin, and Adi Shamir about a gazillion times.

http://citeseer.nj.nec.com/fluhrer01weaknesses.html

I have a question regarding resolved cases:

In section 6, they come up with a probability of e^-3 that "none of
the elements referenced by these three values will participate in any
further swap."

This is how (I believe) they got e^-3:

Assume j is evenly distributed over {0, ..., N-1}
i.e. P(J = k) = 1/N

P(j=a OR j=b OR j=c) = 3/256 (a!=b a!=c b!=c)
P(j!=a AND j!=b AND j!=c) = 1 - 3/N

Now repeat the experience N times (independent experiences):
P(j!=a AND j!=b AND j!=c N times) = (1-3/N)^N

Now it seems they make N -> infinity

Then (1-3/N)^N = e^(N*ln(1-3/N)) -> e^(N*(-3/N)) = e^-3

I have no idea why they make N -> infinity (it is fixed!)

My calculations are these:
(N=256 is used in the RC4 implementation used with WEP)

simulate step 0, 1, and 2
we have knowledge of j0, j1, j2 and S2.
check for the resolved case:
(S2[1] < 3) && (S2[1] + S2[S2[1]] == 3)

Hope j3 != 1 AND j3 != S2[1]
   with proba 1-2/256

Hope jk != 1 AND jk != S3[1] AND jk != 3 for k=4..255
   with proba (1-3/256)^252

Proba that the three values are left undisturbed =
   (1-2/256)*(1-3/256)^252 (~ 5.087%)

Generalization i.e. guessing byte 3 <= B <= 15 (for a 128-bit seed)

In step B-1, check for the resolved case:
(S{B-1}[1] < B) && (S{B-1}[1] + S{B-1}[S{B-1}[1]] == B)

Hope jB != 1 and jB != S{B-1}[1]
   with proba 1-2/256

Hope jk != 1 AND jk != S{B}[1] AND jk != B for k=B+1..255
   with proba (1-3/256)^(255-B)

Proba that the three values are left undisturbed =
   (1-2/256)*(1-3/256)^(255-B)
for B = 15, ~ 5.86% which is quite different from e^-3

Could someone comment on this?

Shill