Cryptography Reference
In-Depth Information
Thus, π
y
= P(A
y
) can be computed as a function of y, N, and π
y−1
, depending
on the occurrence or non-occurrence of various terms in u. This completes
the proof of the induction as well as that of the Lemma.
Theorem 3.1.8. Assume that the index j takes its value from Z
N
indepen-
dently and uniformly at random at each round of the GKSA. Then, one can
always construct functions f
y
(S
0
,K), which depend only on y, the secret key
bytes and the initial permutation, such that for 0 ≤ y ≤ r−1, 1 ≤ r ≤ N,
r
π
y
+
N −y
N
N −1
N
1
N
.
P(S
r
[y] = f
y
(S
0
,K)) ≈
Proof: Let us first show that
f
y
(S
0
,K) = S
0
[h
y
(S
0
,K)],
where the function h
y
's are given by Lemma 3.1.7. Let A
y
denote the event
as defined in the proof of Lemma 3.1.7. Now, S
r
[y] can equal S
0
[h
y
(S
0
,K)]
in two ways.
Case I: One possibility is that the event A
y
and the event S
r
[y] = S
0
[j
y+1
]
occur together (recall that P(E
y
|A
y
) = 1)). Combining Lemma 3.1.7
and Lemma 3.1.4, we find that the probability of this case is approxi-
mately (
N−y
N
)(
N−1
N
)
r−1
π
y
.
Case II: Another possibility is that neither of the above events happen and
still S
r
[y] = S
0
[h
y
(S
0
,K)] due to random association. The contribution
of this part is approximately
1−(
N−y
N
)(
N−1
N
)
r−1
π
y
N
.
Adding the above two contributions, we get the total probability to be ap-
proximately
r
π
y
+
N−y
N
N−1
N
1
N
.
Next we demonstrate some special cases of the update rule u as examples
of how to construct the functions f
y
's and the probabilities π
y
's for small
values of y using Lemma 3.1.7. In all the following cases, we assume S
0
to be
an identity permutation and hence f
y
(S
0
,K) is the same as h
y
(S
0
,K).
Example 3.1.9. Consider the KSA of RC4, where
u(y,j
y
,S
y
[y],S
y
[j
y
],K[y],K[j
y
]) = j
y
+ S
y
[y] + K[y].
We have
h
0
(S
0
,K)
= u(0,0,S
0
[0],S
0
[0],K[0],K[0])
= 0 + 0 + K[0]
= K[0].
