Record Breaking DES Key Search Completed
A machine built by Cryptography Research, Advanced Wireless Technologies, and EFF has demonstrated fast key search for the Data Encryption Standard (DES). DES, the most widely used commercial encryption algorithm, protects financial transactions and electronic communications worldwide. Developed by the US Government and IBM in the 1970s, DES is the government-approved symmetric algorithm for protecting sensitive information.
The DES algorithm uses a 56-bit encryption key, meaning that there are 72,057,594,037,927,936 possible keys. The DES Key Search Project developed specially designed hardware and software to search 90 billion keys per second, determining the key and winning the $10,000 RSA DES Challenge after searching for 56 hours.
The DES Key Search Machine was a collaborative project by Cryptography Research, Advanced Wireless Technologies, and EFF. The hardware and software design and chip simulators were developed by Paul Kocher with assistance from Joshua Jaffe and other researchers at Cryptography Research. Advanced Wireless Technologies developed the chip specification, board layout, and system assembly. John Gilmore of the EFF also assisted with aspects of the project.
DES Key Search Machine Design Information
The DES Key Search Machine uses a sieve-and-check search process that can find keys even when little is known about the plaintext. Each chip processes two separate ciphertexts and contains a 256-bit vector specifying which bytes can appear in the plaintext — making it possible, for example, to find a key if the input message is simply known to consist of ASCII text.
As assembled, the machine is housed in six recycled SUN-2 cabinets and consists of 27 circuit boards that hold over 1800 custom chips. Each chip contains 24 search units, which independently scan through a range of keys, filtering out those that do not pass the search criteria for both of the ciphertexts. For example, search units may check the decrypted block to determine that it contains only ASCII text characters, or may verify that specific bytes match known or expected values. When a search unit finds a potential match, it stops until the the controlling computer (a PC running Windows 95 or Linux) retrieves the key and restarts that search unit. The PC tests keys against another more strict set of criteria to eliminate any incorrect keys that pass the search unit’s tests. Over 37000 search units were active, testing more than 92 billion keys per second, when the RSA DES Challenge key was discovered on July 15, 1998.
Cost and development time were major factors the machine’s design. Most of the expenses were one-time research and design costs. The total project budget remained under $250,000, making the machine the fastest, most economical key search device ever known to have been produced.
Designed by Cryptography Research, Advanced Wireless Technologies, and EFF, the record-breaking DES Key Search Machine won the RSA DES Challenge on July 15, 1998 after searching for 56 hours.
Paul Kocher, the machine’s principal designer, displays one of the boards holding 64 custom search microchips. The six cabinets (behind) house 29 boards whose searching is coordinated by a PC.
Additional DES and DES Key Search Information
DES specification (publication FIPS 46-2).
Previous DES Challenge winners’ info from distributed.net, Rocke Verser.
Description of DESCHALL in the RSA Secret Key Challenge.