Cryptography Reference
In-Depth Information
Results and More Methods
If we use linear cryptanalysis, we need 2
43
known
plaintexts to break a complete
16-round DES. That's 16 times less than the
chosen
plaintexts required in
differential cryptanalysis, and even 4096 times (2
55
/
2
43
) less than the
known
plaintexts needed in differential cryptanalysis. It is currently the most effective
attack against DES. And how does all this look in practice?
The data volume to be analyzed is only 70 terabytes. This means that, if some-
body sends DES-encrypted data (of course, assuming that the same key is used)
over a 34-Mbit/s line, then an attacker needs to listen in on the communica-
tion for the better part of half a year. Subsequently, the attacker (similarly to
what Matsui did in 1994) puts twelve HP-9735 workstations (which correspond
roughly to very fast Pentium Pro computers for this purpose) to work and will
retrieve the key within another 50 days.
You can see that even the time - memory tradeoff discussed in Section 4.4.1
has more chances, let alone hardware-based brute force (using
Deep Crack
).
In contrast to time - memory tradeoff and 'direct' brute force, however, the
methods mentioned here can be expanded, which makes them more interest-
ing. In 1994, Hellman and Langford introduced an attack against an 8-round
DES using so-called
differential linear cryptanalysis
. With only 512 chosen
plaintexts, this attack recovers ten key bits with a probability of 80 % — which
increases to a 95 % probability with 768 chosen plaintexts. The computing
power it required was amazing: a Sun-4 workstation, which is a rather slow
computer by today's standards, took only 10 seconds. Our Web site includes a
description of this method.
4.4.5 DFA and the Chip Crackers
There's actually only one important conclusion we can draw from the last
few sections: no practicable attack against the DES
algorithm
has become
known in public cryptological research. On the other hand, cryptanalysts also
try to attack the
use
of DES. This topic is not about spying out keys through
vulnerabilities in an operating system or in an application. Another approach
targeted to revealing DES keys hidden in chip cards has much more to do with
cryptanalysis and is currently making headlines.
Biham's DFA Method
An article titled 'Hot chip cards leak code' appeared in
Computerzeitung
[CZ96] at the end of October 1996. The article referred to chip cards that do a
