HOME

TheInfoList



OR:

In
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adve ...
, the EFF DES cracker (nicknamed "Deep Crack") is a machine built by the
Electronic Frontier Foundation The Electronic Frontier Foundation (EFF) is an international non-profit digital rights group based in San Francisco, California. The foundation was formed on 10 July 1990 by John Gilmore, John Perry Barlow and Mitch Kapor to promote Internet civ ...
(EFF) in 1998, to perform a
brute force Brute Force or brute force may refer to: Techniques * Brute force method or proof by exhaustion, a method of mathematical proof * Brute-force attack, a cryptanalytic attack * Brute-force search, a computer problem-solving technique People * Brut ...
search of the
Data Encryption Standard The Data Encryption Standard (DES ) is a symmetric-key algorithm for the encryption of digital data. Although its short key length of 56 bits makes it too insecure for modern applications, it has been highly influential in the advancement of cryp ...
(DES) cipher's key space – that is, to decrypt an encrypted message by trying every possible key. The aim in doing this was to prove that the
key size In cryptography, key size, key length, or key space refer to the number of bits in a key used by a cryptographic algorithm (such as a cipher). Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the faste ...
of DES was not sufficient to be secure.


Background

DES uses a 56-bit
key Key or The Key may refer to: Common meanings * Key (cryptography), a piece of information that controls the operation of a cryptography algorithm * Key (lock), device used to control access to places or facilities restricted by a lock * Key (ma ...
, meaning that there are 256 possible keys under which a message can be encrypted. This is exactly 72,057,594,037,927,936, or approximately 72
quadrillion Two naming scales for large numbers have been used in English and other European languages since the early modern era: the long and short scales. Most English variants use the short scale today, but the long scale remains dominant in many non-Eng ...
possible keys. One of the major criticisms of DES, when proposed in 1975, was that the key size was too short.
Martin Hellman Martin Edward Hellman (born October 2, 1945) is an American cryptologist and mathematician, best known for his involvement with public key cryptography in cooperation with Whitfield Diffie and Ralph Merkle. Hellman is a longtime contributor to t ...
and
Whitfield Diffie Bailey Whitfield 'Whit' Diffie (born June 5, 1944), ForMemRS, is an American cryptographer and mathematician and one of the pioneers of public-key cryptography along with Martin Hellman and Ralph Merkle. Diffie and Hellman's 1976 paper ''New Dir ...
of
Stanford University Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is considere ...
estimated that a machine fast enough to test that many keys in a day would have cost about $20 million in 1976, an affordable sum to national intelligence agencies such as the US
National Security Agency The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collectio ...
. Subsequent advances in the price/performance of chips kept reducing that cost until, twenty years later, it became affordable for even a small nonprofit organization such as the EFF to mount a realistic attack.


The DES challenges

DES was a federal standard, and the
US government The federal government of the United States (U.S. federal government or U.S. government) is the national government of the United States, a federal republic located primarily in North America, composed of 50 states, a city within a feder ...
encouraged the use of DES for all non-classified data.
RSA Security RSA Security LLC, formerly RSA Security, Inc. and doing business as RSA, is an American computer and network security company with a focus on encryption and encryption standards. RSA was named after the initials of its co-founders, Ron Rivest ...
wished to demonstrate that DES's key length was not enough to ensure security, so they set up the
DES Challenges The DES Challenges were a series of brute force attack contests created by RSA Security to highlight the lack of security provided by the Data Encryption Standard. The Contests The first challenge began in 1997 and was solved in 96 days by the ...
in 1997, offering a monetary prize. The first DES Challenge was solved in 96 days by the
DESCHALL Project DESCHALL, short for DES Challenge, was the first group to publicly break a message which used the Data Encryption Standard (DES), becoming the $10,000 winner of the first of the set of DES Challenges proposed by RSA Security in 1997. It was establis ...
led by Rocke Verser in
Loveland, Colorado The City of Loveland is the home rule municipality that is the second most populous municipality in Larimer County, Colorado, United States. Loveland is situated north of the Colorado State Capitol in Denver and is the 14th most populous city ...
. RSA Security set up DES Challenge II-1, which was solved by
distributed.net Distributed.net is a volunteer computing effort that is attempting to solve large scale problems using otherwise idle CPU or GPU time. It is governed by Distributed Computing Technologies, Incorporated (DCTI), a non-profit organization under U. ...
in 39 days in January and February 1998. In 1998, the EFF built Deep Crack (named in reference to IBM's
Deep Blue Deep Blue may refer to: Film * ''Deep Blues: A Musical Pilgrimage to the Crossroads'', a 1992 documentary film about Mississippi Delta blues music * Deep Blue (2001 film), ''Deep Blue'' (2001 film), a film by Dwight H. Little * Deep Blue (2003 ...
chess computer) for less than $250,000. In response to DES Challenge II-2, on July 15, 1998, Deep Crack decrypted a DES-encrypted message after only 56 hours of work, winning $10,000. The brute force attack showed that cracking DES was actually a very practical proposition. Most governments and large corporations could reasonably build a machine like Deep Crack. Six months later, in response to RSA Security's DES Challenge III, and in collaboration with distributed.net, the EFF used Deep Crack to decrypt another DES-encrypted message, winning another $10,000. This time, the operation took less than a day – 22 hours and 15 minutes. The decryption was completed on January 19, 1999. In October of that year, DES was reaffirmed as a federal standard, but this time the standard recommended
Triple DES In cryptography, Triple DES (3DES or TDES), officially the Triple Data Encryption Algorithm (TDEA or Triple DEA), is a symmetric-key block cipher, which applies the DES cipher algorithm three times to each data block. The Data Encryption Stand ...
. The small key space of DES and relatively high computational costs of Triple DES resulted in its replacement by AES as a Federal standard, effective May 26, 2002.


Technology

Deep Crack was designed by Cryptography Research, Inc., Advanced Wireless Technologies, and the EFF. The principal designer was Paul Kocher, president of Cryptography Research. Advanced Wireless Technologies built 1,856 custom
ASIC An application-specific integrated circuit (ASIC ) is an integrated circuit (IC) chip customized for a particular use, rather than intended for general-purpose use, such as a chip designed to run in a digital voice recorder or a high-efficien ...
DES chips (called ''Deep Crack'' or ''AWT-4500''), housed on 29 circuit boards of 64 chips each. The boards were then fitted in six cabinets and mounted in a Sun-4/470 chassis. The search was coordinated by a single PC which assigned ranges of keys to the chips. The entire machine was capable of testing over 90 billion keys per second. It would take about 9 days to test every possible key at that rate. On average, the correct key would be found in half that time. In 2006, another
custom hardware attack In cryptography, a custom hardware attack uses specifically designed application-specific integrated circuits (ASIC) to decipher encrypted messages. Mounting a cryptographic brute force attack requires a large number of similar computations: ...
machine was designed based on
FPGA A field-programmable gate array (FPGA) is an integrated circuit designed to be configured by a customer or a designer after manufacturinghence the term '' field-programmable''. The FPGA configuration is generally specified using a hardware de ...
s. COPACOBANA (COst-optimized PArallel COdeBreaker) is able to crack DES at considerably lower cost. This advantage is mainly due to progress in
integrated circuit An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny M ...
technology. In July 2012, security researchers David Hulton and
Moxie Marlinspike Moxie Marlinspike is an American entrepreneur, cryptographer, and computer security researcher. Marlinspike is the creator of Signal, co-founder of the Signal Technology Foundation, and served as the first CEO of Signal Messenger LLC. He is a ...
unveiled a cloud computing tool for breaking the MS-CHAPv2 protocol by recovering the protocol's DES encryption keys by brute force. This tool effectively allows members of the general public to recover a DES key from a known plaintext–ciphertext pair in about 24 hours.


References


External links


The DES Cracker
at the
Electronic Frontier Foundation The Electronic Frontier Foundation (EFF) is an international non-profit digital rights group based in San Francisco, California. The foundation was formed on 10 July 1990 by John Gilmore, John Perry Barlow and Mitch Kapor to promote Internet civ ...

Photos of the machine
at
Cryptography Research Cryptography Research, Inc. is a San Francisco based cryptography company specializing in applied cryptographic engineering, including technologies for building tamper-resistant semiconductors. It was purchased on June 6, 2011 by Rambus for $342. ...

A FPGA implementation using 48 Virtex-6 LX240Ts

ASIC design from 1994 that could crack DES in 24 hours with 256 custom chips
{{Cryptography navbox , block Cryptographic hardware Cryptanalytic devices Data Encryption Standard One-of-a-kind computers