Cryptography Reference
In-Depth Information
1
N
. However, the surface is not flat and this identifies that the permutation
after the RC4 KSA can be distinguished from random permutation.
3.2.3 Anomaly Pairs
To evaluate how closely the theoretical formulae tally with the experimen-
tal results, we use average percentage absolute error ǫ. Let p
u,
N
and q
u,v
N
respectively denote the theoretical and the experimental value of the proba-
bility P(S
N
[u] = v), 0 ≤ u≤ N −1, 0 ≤v ≤N −1. We define
N−1
N−1
|p
u,v
N
−q
u,v
N
|
1
N
2
ǫ
u,v
=
100%
and
ǫ =
ǫ
u,v
.
q
u,v
N
u=0
v=0
We ran experiments for 100 million randomly chosen secret keys of 32 bytes
and found that ǫ = 0.22%. The maximum of the ǫ
u,v
's was 35.37% and it
occurred for u = 128 and v = 127. Though the maximum error is quite high,
we find that out of N
2
= 65536 (with N = 256) many ǫ
u,v
's, only 11 ( <
0.02% of 65536) exceeded the 5% error margin. These cases are summarized
Table 3.3 below. We call the pairs (u,v) for which ǫ
u,v
> 5% anomaly pairs.
p
u,v
N
q
u,v
N
|p
u,v
N
−q
u,v
N
u
v
| ǫ
u,v
(in %)
38
6
0.003846 0.003409
0.000437
12.82
38
31
0.003643 0.003067
0.000576
18.78
46
31
0.003649 0.003408
0.000241
7.07
47
15
0.003774 0.003991
0.000217
5.44
48
16
0.003767 0.003974
0.000207
5.21
66
2
0.003882 0.003372
0.000510
15.12
66
63
0.003454 0.002797
0.000657
23.49
70
63
0.003460 0.003237
0.000223
6.89
128
0
0.003900 0.003452
0.000448
12.98
128
127
0.003303 0.002440
0.000863
35.37
130
127
0.003311 0.003022
0.000289
9.56
TABLE 3.3: The anomaly pairs for key length 32 bytes.
The experimental values of P(S
N
[u] = v) match with the theoretical ones
given by the formula of Theorem 3.2.11 except at these few anomaly pairs.
As an illustration, we plot q
u,
N
(calculated by running the KSA with 100
million random secret keys of length 32 bytes) and p
u,v
N
versus v for u = 38 in
Figure 3.5. We see that q
38,v
N
follows the pattern predicted by p
38,
N
for all v's,
0 ≤v ≤ 255 except at v = 6 and v = 31 as pointed out in Table 3.3.
Experimentation with different key lengths (100 million random keys for
each key length) reveals that the location of the anomaly pairs and the total
number of anomaly pairs vary with the key lengths in certain cases. Table 3.4
shows the number n
5
of anomaly pairs (when ǫ
u,v
> 5%) for different key
