Questions and Answers
What is the RSA DES Challenge III?
The RSA DES Challenge III is the third contest sponsored by RSA Laboratories that consists of one 56-bit DES challenge. The challenge offers prizes of $1,000, $5,000, and $10,000 for cracking a fixed-key size, 56-bit DES cipher.
Why was the challenge established?
The original RSA Labs´ Secret-Key Challenge was developed to quantify the security offered by the government-endorsed data encryption standard (DES) and other secret-key ciphers with keys of various sizes. The Challenge was announced at the RSA Data Security Conference on January 28, 1997. In addition, the Challenge has provided an excellent investigative tool for discerning the potential and practical application of distributed Internet-based computing efforts.
What is DES?
DES is the Data Encryption Standard, an encryption block cipher defined and endorsed by the U.S. government in 1977 as an official standard; the details can be found in the latest official FIPS (Federal Information Processing Standards) publication concerning DES. DES has been extensively studied since its publication and is one of the most well-known and widely used secret-key cryptosystems in the world.
DES has a 64-bit block size and uses a 56-bit key during encryption. It is a 16-round Feistel cipher and was originally designed at IBM for implementation in hardware.
In 1997, the NIST announced it would be developing an Advanced Encryption Standard (AES) as a successor to DES. There are now 15 AES candidate algorithms being analyzed by an international group of experts.
The DES Challenge II consisted of two contests posted on January 13th, 1998, and July 13th, 1998.
The first constest was cracked by a distributed computing effort coordinated by distributed.net, who met the challenge in 39 days, less than half the 90 days of computing time it took the to solve the DES Challenge I.
The second contest was solved by the Electronic Frontier Foundation, which developed a DES Cracker computer specially designed for the task of cracking DES keys. The machine shattered the previous challenge record of 39 days by solving the contest in less than three.
Who cracked the DES Challenge I?
Rocke Verser of Loveland, Colorado led a group of Internet users in a distributed brute force attack of 56-bit DES. The project, code-named DESCHALL, began on March 13th and was successfully completed on Tuesday, June 17th, 1997 at 10:39 PST.
What is a brute force attack?
Exhaustive key search, or brute-force search, is the basic technique of trying every possible key in turn until the correct key is identified. To identify the correct key it may be necessary to possess a plaintext and its corresponding ciphertext, or if the plaintext has some recognizable characteristic, ciphertext alone might suffice. Exhaustive key search can be mounted on any cipher and sometimes a weakness in the key schedule of the cipher can help improve the efficiency of an exhaustive key search attack.
Advances in technology and computing performance will always make exhaustive key search an increasingly practical attack against keys of a fixed length. When DES was designed, it was generally considered secure against exhaustive key search without a vast financial investment in hardware. Over the years, this line of attack will become increasingly attractive to a potential adversary.
What is NIST?
NIST is an acronym for the National Institute of Standards and Technology, a division of the U.S. Department of Commerce; it was formerly known as the National Bureau of Standards (NBS). Through its Computer Systems Laboratory it aims to promote open systems and interoperability that will spur development of computer-based economic activity. NIST issues standards and guidelines that it hopes will be adopted by all computer systems in the U.S., and also sponsors workshops and seminars. Official standards are published as FIPS (Federal Information Processing Standards) publications.
In 1987 Congress passed the Computer Security Act, which authorized NIST to develop standards for ensuring the security of sensitive but unclassified information in government computer systems. It encouraged NIST to work with other government agencies and private industry in evaluating proposed computer security standards. However, it seems that NIST-standard cryptography such as the Escrowed Encryption Standard and DSS are hardly used in government, and virtually not at all by industry.
What does 72 quadrillion mean?
Solving a DES challenge requires finding one key in 72 quadrillion. Finding a DES key amongst 72 quadrillion keys seems an unfathomable, incomprehensible task. We decided to convert this notion of 72 quadrillion into some interesting real-world equivalents.
- 72 quadrillion golf balls would massively overfill the entire San Francisco Bay and then some, with over 5 times as many pouring out into the Pacific Ocean. (based on assumptions that a standard 1.7 inch diameter golf ball, packed approximately 404 balls/ per cubic foot in volume (using hexagonal close packing) would yield a volume of 1.78 x 10^14 cubic feet, and that the San Francisco Bay runs 90 miles long, 30 miles wide, and 500 feet deep. Yielding a volume of 3.76 x 10^13 cubic feet.)
- 72 quadrillion people would weigh, (assuming 150 lbs each,) 1.08 x 10^19 lbs. (Which is surprisingly still only one millionth the weight of the Earth, at a whopping 1.3 x 10^25 lbs. However, if 72 quadrillion people could stand 4 per square meter, and could stand on every square meter of the earth's surface (including the ocean floors), they would need 350,000 earths for a modest amount of elbow room.
- If you didn't have a computer, but could somehow check one DES key per second in your head, it would still take over 9 billion years to test the DES key space. This is comparable or possibly longer than the time the Universe has existed (estimates on the existence of the Universe vary from 7 to 20 billion years, talk about your margins of error!).
- 72 quadrillion inches, a little over 1.82 x 10^12 kilometers, is still a little shy of the distance light travels in one year, 9.5 x 10^12 km, but if you decided to travel it in the Earth's orbit around the sun instead, (1.49 x 108 km) you could go around the sun more than 10,000 times