Cryptography Reference
In-Depth Information
0 to 255, E
v
decreases from 4.99 to 3.31 after the end of Layer 2 and from
6.99 to 5.31 after the end of Layer 3. Table 9.1 demonstrates the individual
as well as the incremental effect of each of Layer 2 and Layer 3, when they
act upon the identity permutation S
0
and the permutation S
N
obtained after
Layer 1. In the table, Lr means Layer r, r = 1,2,3. The first row labeled
“Theory” corresponds to the values obtained using Theorem 3.3.2. The data
illustrate that the effect of Layer 2 or Layer 3 on the identity permutation S
0
is similar to that of Layer 1. However, after Layer 1 is over (when we have
somewhat random permutation S
N
, the output of RC4 KSA), each of Layer 2
and Layer 3 individually enforces each entry of the permutation to be visited
uniformly (approximately twice on average). Thus, each layer incrementally
moves the graph of E
v
versus v in the positive Y-direction approximately by
an amount of 2, as is illustrated in Figure 9.1.
avg
sd
max
min
KSA
+
L1
Theory
2.0025
0.4664
3.0000
1.3700
(RC4 KSA)
Experiment
2.0000
0.4655
2.9959
1.3686
KSA
+
L2
L2 on S
0
2.0000
0.4658
2.9965
1.3683
(Experiment)
L2 on S
N
2.0000
0.0231
2.0401
1.9418
L1 + L2
4.0000
0.4716
4.9962
3.3103
KSA
+
L3)
L3 on S
0
2.0000
0.4660
3.0000
1.3676
(Experiment)
L3 on S
N
2.0000
0.0006
2.0016
1.9988
L1 + L2 + L3
6.0000
0.4715
6.9962
5.3116
TABLE 9.1: Average, standard deviation, maximum and minimum of the
expectations E
v
over all v between 0 and 255.
Uniform values of the expectations can be achieved easily with normal
RC4, by keeping a count of how many times each element is touched and
performing additional swaps involving the elements that have been touched
fewer number of times. However, this will require additional space and time.
In normal RC4, many permutation elements are touched only once (especially
those toward the right end of the permutation), leaking information on j in
the inverse permutation. The target, here, is to prevent this by increasing
the number of times each element is touched, without keeping any additional
space such as a counter. Experimental data in Table 9.1 as well as Figure 9.1
show that this purpose is served using the new strategy.
How random is S
N
+
?
Now we present experimental evidence of how the biases of Item (5) in RC4
KSA are removed. We compare the probabilities P(S[u] = v) for 0 ≤ u,v ≤
255 from standard KSA and the KSA
+
. All the experiments are performed
with 100 million runs with randomly chosen secret keys of length 16 bytes and
null IV.
