How DES Was Cracked

DES has 2^56 possible keys, which equals approximately 72 quadrillion (72,057,594,037,927,936) keys. While this sounds enormous, it is a finite space that can be systematically searched with enough computing power.

Key exhaustion (brute force) requires, on average, testing half the key space before finding the correct key. For DES, this means about 2^55 trial decryptions, each taking a few operations on modern hardware.

In 1997, RSA Data Security offered a $10,000 prize for breaking a DES-encrypted message. Rocke Verser coordinated a distributed computing effort across tens of thousands of internet-connected computers.

After 96 days of searching, the key was found. The plaintext was "Strong cryptography makes the world a safer place." The effort demonstrated that DES could be broken, though it required months and massive coordination.

The Electronic Frontier Foundation built Deep Crack for $250,000 in 1998. It contained 1,856 custom ASICs, each capable of testing 2.5 million DES keys per second, giving Deep Crack a combined rate of over 90 billion keys per second.

Deep Crack could exhaust the entire DES key space in about 9 days on average. This was proof that a determined adversary with a $250,000 investment could break DES in under two weeks.

In the DES Challenges II-1 (February 1998), Deep Crack combined with the distributed.net volunteer computing network cracked DES in just 39 days. Challenges II-2 (July 1998) fell in 56 hours.

The rapid improvement from 96 days to 56 hours in just one year demonstrated how quickly hardware improvements and better coordination could accelerate brute-force attacks.

In January 1999, the EFF's Deep Crack combined with distributed.net broke DES Challenge III in just 22 hours and 15 minutes, winning a $10,000 prize from RSA Security.

This definitive demonstration that DES could be broken in under 24 hours effectively ended any argument for DES's security. NIST shortly afterward began the process of selecting a DES replacement, which became AES.

Distributed.net organized volunteer computing efforts where ordinary internet users donated their CPU cycles to the DES challenges. At peak, hundreds of thousands of computers participated.

Each computer tested a different portion of the key space, coordinated by a central server. This pioneered the model of distributed computing for cryptanalysis that is still used today for challenges like breaking older ciphers.

Key exhaustion works because each DES decryption is fast (microseconds on hardware) and independent. There is no dependency between testing key N and key N+1, so the search parallelizes perfectly across any number of machines.

This embarrassingly parallel nature means that doubling the hardware exactly halves the time. Adding more machines has linear speedup, making the economics favorable for adversaries.

Eli Biham and Adi Shamir published differential cryptanalysis in 1990, a technique that exploits how differences in input pairs propagate through cipher rounds. For DES, it theoretically requires 2^47 chosen plaintexts.

DES's S-boxes were retroactively revealed to have been designed with resistance to differential cryptanalysis in mind, suggesting NSA knew about this technique in the 1970s. The attack is impressive theoretically but practically outclassed by hardware brute force.

Mitsuru Matsui published linear cryptanalysis in 1993, requiring 2^43 known plaintexts to attack DES. He implemented the attack and experimentally broke DES in 1994, confirming the theoretical analysis.

Linear cryptanalysis finds linear approximations to the S-box behavior and uses them to recover key bits with a statistical bias. It requires far less data than brute force in theory but was impractical before the hardware attacks.

Differential cryptanalysis was published in 1990 but requires chosen plaintexts (impractical in most real scenarios). Linear cryptanalysis was published in 1993 and works with known plaintexts but requires 2^43 of them.

Hardware brute force (Deep Crack) broke DES in 22 hours in 1999. In practice, the hardware attack was more devastating than the theoretical cryptanalytic advances, because it required no special plaintext-ciphertext pairs at all.

The public, documented breaking of DES had immediate policy implications. NIST began the AES competition process in 1997, the same year DES Challenge I succeeded. The competition was explicitly designed to avoid the weaknesses of the DES standardization process.

Banks and government agencies began transitioning to 3DES as an interim measure while AES was developed. The DES cracking timeline directly determined the urgency and timeline of the AES adoption effort.

Test your understanding of DES cracking history.

DES was broken progressively faster: 96 days in 1997, 56 hours in 1998, and 22 hours in 1999. The EFF's $250,000 Deep Crack used custom ASICs to test 90 billion keys per second.

Both differential cryptanalysis (2^47 chosen plaintexts) and linear cryptanalysis (2^43 known plaintexts) also theoretically break DES, but hardware brute force was the practical killer. The 22-hour crack ended DES's life as a viable cipher.