Cryptography Reference
In-Depth Information
The final formulae in Theorem 3.2.11 are very close to the results pre-
sented in [110] apart from some minor differences as terms with N
2
in the
denominator or a difference in 1 in the power. For N = 256, the maximum
absolute difference between these results and the results of [110] is 0.000025
as well as the average of absolute differences is 0.000005.
However, the proof approach of [135] is different from that of [110]. In [110],
the idea of relative positions is introduced. If the current deterministic index
is i, then relative position a means the position (i+ 1 +a) mod N. The trans-
fer function T(a,b,r), which represents the probability that value in relative
position a in S will reach relative position b in the permutation generated from
S by executing r RC4 rounds, has the following explicit form by [110, Claim
C.3.3]:
p(q
a
+ q
r−(b+1)
−q
a+r−(b+1)
)
if a ≤ b;
T(a,b,r) =
p(q
a
+ q
r−(b+1)
)
if a > b,
N
and q = (
N−
N
). This solution is obtained by solving
a recurrence [110, Equation C.3.1] which expresses T(a,b,r) in terms of
T(a − 1,b − 1,r − 1). Instead, the proof idea here uses the probabilities
P(S
τ
[u] = v) in order to calculate the probabilities P(S
r
[u] = v) which im-
mediately gives P(S
N
[u] = v) with r = N. When v > u, we take τ = v + 1
and when v ≤u, we take τ = u+ 1 (see Theorem 3.2.11). However, the values
u + 1 and v + 1 are not special. If one happens to know the probabilities
P(S
τ
[u] = v) at any round τ between max{u,v}+1 and N, then it is possible
to arrive at the probabilities P(S
r
[u] = v) using Lemma 3.2.9. The recurrence
relation in [110] is over three variables a, b and r, and at each step each of
these three variables is reduced by one. On the other hand, the model of [135]
has the following features.
1
where p =
1. It connects four variables u, v, τ and r which respectively denote any
index u in the permutation (analogous to b), any value v ∈ [0,...N−1]
(analogous to the value at a), any round τ > max{u,v} and a particular
round r ≥ τ.
2. Though the formulation of [135] does not solve any recurrence and pro-
vides a direct proof, it can be considered analogous to a recurrence over
a single variable r, the other two variables u and v remaining fixed.
For graphical comparison of the theoretical and the experimental values of
P(S
N
[u] = v) versus 0 ≤ u,v ≤ N−1, experiments have been performed with
100 million randomly chosen secret keys of 32 bytes. In Figure 3.4, the empir-
ical values are plotted in the top part and the the numerical values obtained
from the formula in Theorem 3.2.11 are plotted in the bottom part. Observe
that the graph from experimental data has a few downward spikes. These ac-
tually correspond to the anomaly pairs described in Section 3.2.3 below. Had
the permutation been random, the surface would have been flat at a height
