Cryptography Reference
In-Depth Information
Threshold c = 0
Threshold c = 1
Threshold c = 2
l
Key byte
Succ.
Search
Succ.
Search
Succ.
Search
κ
[0]
0.9997
138.9
0.9967
47.9
0.9836
12.4
5
κ
[1]
0.9995
138.2
0.9950
47.4
0.9763
12.2
κ
[0]
0.9927
97.6
0.9526
22.2
0.8477
4.1
8
κ
[1]
0.9902
98.9
0.9400
22.9
0.8190
4.2
κ
[0]
0.9827
82.5
0.9041
15.7
0.7364
2.6
10
κ
[1]
0.9761
84.0
0.8797
16.3
0.6927
2.7
κ
[0]
0.9686
71.6
0.8482
11.8
0.6315
1.8
12
κ
[1]
0.9577
73.2
0.8118
12.3
0.5763
1.8
κ
[0]
0.9241
54.1
0.7072
6.7
0.4232
0.9
16
κ
[1]
0.8969
55.8
0.6451
7.1
0.3586
0.9
TABLE 4.5: Experimental results for first two key bytes using different
thresholds.
Based on Algorithm 4.5.1, several variants of complete key recovery strat-
egy exist. By Method 1, we refer to the simple strategy of guessing the com-
plete key using different thresholds on the basic table obtained from Build-
KeyTable algorithm.
Method 1A improves upon Method 1. It updates the basic frequency table
obtained from the BuildKeyTable algorithm by considering the values obtained
from the S[S[y]] types of biases. In Section 3.1.3, it is demonstrated that there
exist biases toward
y
f
y
=
y(y + 1)
2
+
K[y]
x=0
at S
N
[y], S
N
[S
N
[y]], S
N
[S
N
[S
N
[y]]], S
N
[S
N
[S
N
[S
N
[y]]]], and so on. In Method
1A, we guess K[0] first. Then, we increment y one by one starting from 1 and
given the values of K[0],K[1],...,K[y − 1], we compute the value of K[y]
from the equations S
I
N
[y] = f
y
, where I denotes the level of indirections
considered. For frequency updates of κ[0], the first four levels of indirections
(i.e., I = 1,2,3 and 4) are used. For frequency updates of other four key
bytes, only the first two levels of indirections are used. Further, for frequency
updates of κ[1], only the values of κ[0] with frequency > 2 are considered.
Similarly, for κ[2], the values of κ[0] with frequency > 3 and the values of κ[1]
with frequency > 4 respectively are considered. These values (e.g., 2, 3, 4
above) are called the threshold frequencies. For κ[3], the threshold frequencies
of κ[0],κ[1] and κ[2] are 4 and 5 and 6 respectively. Finally, for κ[4], the
threshold frequencies of κ[0],κ[1],κ[2] and κ[3] are taken to be 4, 5, 6 and 7
respectively. Observe that while updating the table for the key byte κ[w] for a
fixed w, the thresholds for κ[0],...,κ[w−1] are increased as w increases. Small
thresholds for κ[0],...,κ[w−1] substantially increase the number of choices for
κ[w] without significantly increasing the probability for obtaining the correct
value of κ[w]. The thresholds mentioned above are tuned empirically.
