Cryptography Reference
In-Depth Information
3.5.2 Analytical Attacks
As was shown in the first chapter, analytical attacks can be very powerful. Since
the introduction of DES in the mid-1970s, many excellent researchers in academia
(and without doubt many excellent researchers in intelligence agencies) tried to find
weaknesses in the structure of DES which allowed them to break the cipher. It is
a major triumph for the designers of DES that no weakness was found until 1990.
In this year, Eli Biham and Adi Shamir discovered what is called
differential crypt-
analysis (DC)
. This is a powerful attack which is
in principle
applicable to any block
cipher. However, it turned out that the DES S-boxes are particularly resistant against
this attack. In fact, one member of the original IBM design team declared after the
discovery of DC that they had been aware of the attack at the time of design. Al-
legedly, the reason why the S-box design criteria were not made public was that the
design team did not want to make such a powerful attack public. If this claim is true
— and all circumstances support it — it means that the IBM and NSA team was
15 years ahead of the research community. It should be noted, however, that in the
1970s and 1980s relatively few people did active research in cryptography.
In 1993 a related but distinct analytical attack was published by Mitsuru Matsui,
which was named
linear cryptanalysis (LC)
. Similar to differential cryptanalysis,
the effectiveness of this attack also heavily depends on the structure of the S-boxes.
What is the practical relevance of these two analytical attacks against DES?
It
turns out that an attacker needs 2
47
plaintext-ciphertext pairs for a successful DC
attack. This assumes particularly chosen plaintext blocks; for random plaintext 2
55
pairs are needed! In the case of LC, an attacker needs 2
43
plaintext-ciphertext pairs.
All these numbers seem highly impractical for several reasons. First, an attacker
needs to know an extremely large number of plaintexts, i.e., pieces of data which
are supposedly encrypted and thus hidden from the attacker. Second, collecting and
storing such an amount of data takes a long time and requires considerable memory
resources. Third, the attack only recovers one key. (This is actually one of many
arguments for introducing key freshness in cryptographic applications.) As a result
of all these arguments, it does not seem likely that DES can be broken with either
DC or LC in real-world systems. However, both DC and LC are very powerful
attacks which are applicable to many other block ciphers. Table 3.13 provides an
overview of proposed and realized attacks against DES over the last three decades.
Some entries refer to what is known as the DES Challenges. Starting in 1997, several
DES-breaking challenges were organized by the company RSA Security.
3.6 Implementation in Software and Hardware
In the following, we provide a brief assessment of DES implementation properties in
software and hardware. When we talk about software, we refer to DES implemen-
tations running on desktop CPUs or embedded microprocessors like smart cards
