Cryptography Reference
In-Depth Information
numbers, for which we would need a 1000-Tbyte memory. For the time being,
that's too much by six orders of magnitude.
Refinements and Results
Biham and Shamir looked at characteristics not for a 15-round DES, but for
only 13 rounds. Reducing the number of rounds makes higher probabilities
stand out more and leads to success faster. Moreover, they found a method that
allowed them to test for the correct key immediately. This meant that the 2
48
counters for frequencies were no longer required.
Of course, we are mainly interested in practically usable results. Figure 4.12
gives an overview that requires several comments.
The third column shows the number of plaintext blocks
not
especially chosen,
but required for a plaintext attack. Only among that many plaintexts will we find
a sufficiently large number of right pairs (i.e., pairs with the desired differences).
The fourth column is surprising: many cases will also evaluate extremely few
right pairs, you just don't know in advance which ones. For these cases, the
computation cost (in this method called 'complexity') required is higher once
we have found appropriate plaintexts, which shouldn't come as a surprise.
The first and last rows of the table are the most interesting. As mentioned
in Section 4.1.4, product algorithms can sometimes have a 'sound barrier' for
cryptanalysis to overcome. We can see clearly from the table that an 8-round
DES is still vulnerable — we could imagine success in deliberately introducing
2
14
, i.e., 16 384 plaintext pairs. In contrast, 2
47
plaintexts correspond to a data
Number of
Chosen
Known
Analyzed
Complexity of
rounds
plaintexts
plaintexts
plaintexts
analysis
2
14
2
38
2
9
8
4
2
24
2
44
2
32
9
2
2
24
2
43
2
14
2
15
10
2
31
2
47
2
32
11
2
12
2
31
2
47
2
21
2
21
13
2
39
2
52
2
2
32
2
39
2
51
2
29
2
29
14
2
47
2
56
2
7
2
37
15
2
47
2
55
2
36
2
37
16
Figure 4.12:
Cost for differential cryptanalysis against DES.
