Cryptography Reference
In-Depth Information
Experimental Results for 5 Byte Keys
In Table 4.6, we present the search complexity and success probability
related to all the bytes for a 5 byte secret key using both Method 1 and Method
1A. Here “Succ.” denotes the success probability and “Comp.” denotes the
search complexity. The complexity of retrieving the entire key is calculated
by multiplying the average number of values that need to be searched for
individual key bytes. The success probability of recovering the entire key is
computed empirically. This value is typically more than the product of the
individual probabilities, indicating that the values of the key bytes are not
independent given the final permutation bytes. Observe that just applying
Method 1 helps to achieve 89.46% success rate in a complexity 12.4×(12.2)
4
≈
2
18.1
.
Threshold c = 0
Threshold c = 1
Threshold c = 2
Key byte
Method
Succ.
Comp.
Succ.
Comp.
Succ.
Comp.
1
0.9997
138.9
0.9967
47.9
0.9836
12.4
κ
[0]
1A
0.9998
140.2
0.9980
49.2
0.9900
13.0
1
0.9995
138.2
0.9950
47.4
0.9763
12.2
κ
[1]
1A
0.9997
149.2
0.9971
56.6
0.9857
16.1
1
0.9995
138.2
0.9949
47.4
0.9764
12.2
κ
[2]
1A
0.9996
142.2
0.9965
50.7
0.9834
13.6
1
0.9995
138.2
0.9950
47.4
0.9761
12.2
κ
[3]
1A
0.9996
138.7
0.9958
47.8
0.9796
12.4
1
0.9995
138.2
0.9950
47.4
0.9766
12.2
κ
[4]
1A
0.9996
138.7
0.9958
47.8
0.9796
12.4
2
35.6
2
27.8
2
18.1
1
0.9976
0.9768
0.8946
Entire Key
2
35.7
2
28.3
2
18.7
1A
0.9983
0.9830
0.9203
TABLE 4.6: Experimental results for all key bytes using different thresholds
for l = 5.
Next, we discuss some enhancements of the basic technique for a 5-byte
key. For each key byte, first the value with the maximum frequency is tried,
then the second maximum and so on. The search is performed in an iterative
deepening manner. If d
w
is the depth (starting from the most frequent guess)
of the correct value for κ[w], then the search never goes beyond depth d
max
=
max{d
w
,0 ≤ w ≤ 4} for any key byte. The complexity is determined by
finding the average of d
5
max
over 1 million trials, each with a different key.
A depth limit D is also set, which denotes the maximum number of different
values that are to be tried for each key in descending order of their frequencies,
starting from the most frequent value. We denote this strategy as Method 2. If
the frequency table is updated as in Method 1A before performing the search
in descending order of frequencies, then we name it Method 2A.
The experimental results for the above enhancements are presented in
Table 4.7. The decimal fractions and the powers of 2 denote the success
probabilities and the search complexities respectively.
