Cryptography Reference
In-Depth Information
Input: The permutation S
N
after the KSA.
Output: A frequency table for each key byte.
Data: Arrays jarr1[N + 1],jarr2[N + 1],karr[l][N].
jarr1[0] = jarr2[0] = 0;
for y = 0 to N −1 do
jarr1[y + 1] = S[y] and jarr2[y + 1] = S
−1
N
[y];
end
for w = 0 to l−1 and y = 0 to N −1 do
karr[w][y] = 0;
end
karr
0
jarr1[1]
+= 1 ;
karr
+= 1 ;
for y = 1 to N −1 do
karr
0
jarr2[1]
y mod l
jarr1[y + 1]−jarr1[y]−y
+= 1 ;
karr
y mod l
jarr1[y + 1]−jarr2[y]−y
+= 1 ;
karr
y mod l
jarr2[y + 1]−jarr1[y]−y
+= 1 ;
karr
y mod l
jarr2[y + 1]−jarr2[y]−y
+= 1 ;
end
Algorithm 4.5.1: BuildKeyTable
also be attempted, such as considering only those values in in Z
N
that have
frequency above a certain threshold c.
Experiments reveal that the BuildKeyTable algorithm recovers each indi-
vidual key byte with a very high probability. Table 4.5 shows data for the first
two bytes of secret keys with key lengths 5, 8, 10, 12 and 16. The results are
obtained by considering 1 million randomly chosen secret keys of different key
lengths. In Table 4.5, “Succ.” denotes the success probability and “Search”
denotes the number of values ∈
Z
N
with frequency > c. Theoretical estimates
of these values are given in Theorem 4.5.2 and Theorem 4.5.6 respectively.
As an example, each key byte for l = 5 can be guessed with a probability >
0.97 among only around 12 values from {0,1,...,255}, each having frequency
at least 3; whereas, for random guess, one need to consider at least 248 (≈
256×0.97) values to achieve the same probability.
For any key length, the success probability and search complexity of the
key bytes from κ[2] onwards are almost the same as those of κ[1]. Thus the
data for κ[1] is a representative of the other key bytes. Note that the success
probability for κ[0] is always little more than that for the other key bytes. This
happens because κ[0] is estimated as j
1
−0, where the event j
0
= 0 occurs
with probability 1. This is also consistent with item (1) of Theorem 4.5.2.
For the same threshold c, the probability as well as the search complexity
for each key byte decreases with increasing key length. This is due to the fact
that the number of repetitions corresponding to each key byte also decreases
with increasing key length.
−j
0
