Cryptography Reference
In-Depth Information
pairs of j's give four possible values of a key byte with good probability. Since
each key is repeated at least ⌊
N
l
⌋ times, a frequency table can be constructed
for each secret key byte, by accumulating many suggestive values for the key.
4.5.1 Related Theoretical Results
Each value y in the permutation is touched at least once during the KSA
by the indices i,j, 0 ≤ y ≤ N −1. Initially, y is located at index y. In round
y + 1, when i equals y, either the value y is still in index y, or it has been
moved due to swaps in one of the previous y rounds. In the former case, i
touches it in round y + 1 and in the latter case, one of {j
1
,j
2
,...,j
y
} has
touched it already.
Theorem 4.5.1. For 0 ≤ y ≤N −1,
N−1
j
y+1
= S
−1
=
N −2
N
N −1
N
2
N
.
P
[y] or j
y+1
= S
N
[y]
+
N
Proof: The event (j
y+1
= S
−
N
[y]), i.e., the event (S
N
[j
y+1
] = y) occurs,
if A
1
(y), which is a combination of the following two events, holds.
1. y is not touched by any of {j
1
,j
2
,...,j
y
} in the first y rounds. This
happens with probability (
N−1
N
)
y
.
2. In round y + 1, when i becomes y, j
y+1
moves y to one of the indices in
{0,...,y} due to the swap and y remains there until the end of KSA.
This happens with probability
P(j
y+1
∈{0,...,y})P(j
τ
= j
y+1
,y + 2 ≤τ ≤ N)
N−y−1
y + 1
N
N −1
N
=
.
Thus,
y
y + 1
N
N−y−1
N −1
N
N −1
N
P (A
1
(y))
=
N−1
y + 1
N
N −1
N
=
.
Again, the event (j
y+1
= S
N
[y]) occurs, if A
2
(y), which is a combination
of the following two events, holds. (Note that the event A
2
(y) is taken from
Lemma 3.1.4. We here outline the proof of the probability of A
2
(y) for easy
reference.)
1. S
y
[j
y+1
] = j
y+1
and therefore after the swap in round y + 1, S
y+1
[y] =
j
y+1
. This happens if j
y+1
∈{y,...,N − 1} and had not been touched
by any of {j
1
,j
2
,...,j
y
} in the first y rounds. The probability of this is
N−y
N
(
N−1
N
)
y
.
