Cryptography Reference
In-Depth Information
concerns were about the
S-boxes
, a series of 8 substitutions that form the core of the
algorithm and that were suspected to have been designed or modified by the NSA—
which collaborated with IBM for the final design—to hide some backdoor that could
allow people in the know to break the system (also, it has been widely suggested
that the key was reduced, at the NSA's request, to its 56-bit size from the 112-bit
size of the original IBM proposal (see, e.g. [61] although other sources claim that
the original proposal had a 64-bit key, [189]). The alleged S-box weaknesses were
never confirmed but from the beginning it was clear that, even if it was reasonably
secure when introduced, in view of Moore's lawwhose first version had already been
formulated ten years earlier in [145], DES would soon be vulnerable to a brute-force
attack.
Before the brute-force attack could be successfully completed, several important
theoretical cryptanalytic attacks were developed. The first of them, called
differential
cryptanalysis
, was developed by Biham and Shamir in the late 1980s. It requires the
attacker to analyze a great quantity of plaintext-ciphertext pairs, which makes the
attack hardly feasible in practice. One of the surprising—or perhaps not so surprising
after all—consequences of the Biham-Shamir discovery is that the designers of
DES acknowledged that they already knew differential cryptanalysis and that they
designed the algorithmwith 16 rounds precisely in order tomake this attack infeasible
in practice.
An even more powerful attack called
linear cryptanalysis
was discovered by
Matsui in the early nineties. This is a known plaintext attack (so that plaintexts
need not be chosen by the attacker) that requires 2
43
plaintext-ciphertext pairs to be
successful against DES. Again, this number is so large that it is hardly conceivable
that the attack might be successfully implemented in practice.
Both differential and linear cryptanalysis are not specifically addressed at DES;
rather, they are generic attacks against block ciphers and they should be taken into
account when designing such ciphers.We refer to [114, 189, 190] for detailed descrip-
tions of these attacks.
The intense cryptanalytic work done on DES means that it is an extremely well
designed block cipher for which no practical
shortcut attacks
—i.e., practical attacks
requiring significantly less time than a brute-force search—are known. But, as had
been expected from the beginning, DES finally succumbed to a brute-force attack.
In 1997 the RSA Data Security company launched a challenge to recover a DES
key from an encrypted message and, after a collaborative Internet-based effort, the
key was found just five months later (with a bit of luck since only roughly 25% of
the key space had been searched by that time). In the following years there were
new versions of this challenge, culminating with the “DES Challenge III”, issued in
1999. In 1998 the Electronic Frontier Foundation had built, at the cost of $250,000, a
special-purpose machine called “DES Cracker”, containing 1,536 chips and able to
search 88
10
9
DES keys per second. The “DES Challenge III” was then solved by a
cooperative effort where the DES Cracker worked in conjunction with a network of
some 100,000 computers searching at a rate of 245
·
10
9
keys per second and finding
the key in just over 22 hours. A detailed description of this attack can be found
in [61].
·
