The Data Encryption Standard aka DES, is the good old encryption standard, that has been around since the 1970's. It's a well designed symmetric encryption algorithm, but the key size is way too small, at only 56 bits. This is a major problem, as brute force attacking a cipher with such a small key is starting to become a real threat with todays modern computers.

Let's start with the history of the algorithm.
It all started in 1971 when the National Bureau of Standards (aka NBS, now known as National Institute of Standards and Technology, or NIST) issued a public request for a secure encryption algorithm. IBM answered their request with a algorithm based on Lucifer, crafted by a group of higly skilled people:

NBS requested that the National Security Agency (aka NSA) help them analyze and try to break the algorithm. Amongst the things NSA did was reduce the keysize from 128 bit, to 56 bit. They also changed some of the S-boxes, which some people have worried might have been to insert a trapdoor.

Still, the algorithm was accepted for federal use in 1976. It was however not until 1981 that the American National Standards Institute (aka ANSI) approved it for use in the private sector.

Over to the internals of the algorithm itself
It's a block cipher, a feistel network to be more specific.
While the keys used with DES are limited to 56 bit, it's using 64 bit blocks. This means that all data encrypted is cut up in chucks of 64 bit, and padded with NUL's if need be, then encrypted, and 64 new encrypted bits gets spit out. The 56 bit key is in fact represented as 64 bits, with evey 8 bit being parity bits.

The internal working of DES is well known, and available online in many different locations, and as it's of limited intrest to the end user, I won't focus too much on it here.

DES can be used in varius different encryption modes, including but not limited to:

What seems to be the biggest problem with DES is the key size. This was demonstrated in 1998 when the Electronic Frontier Foundation (aka EFF) built a hardware encryption machine (named "Deep Crack"), designed to brute force attack a DES challenge. The computer was built using only standard components, and with a total price of about $250,000. It cracked the contest key in less than 3 days.

Half a year later, distributed.net took down another DES challenge, this time in only 22 hours and 15 minutes, using a distributed network of people using only idle cpu time, and some help from the Deep Crack machine.

Not only this, but as DES cracking can be run in parallel, all you have to do to double the speed is to double your spendings, or wait 18 months. At least accoring to Moore's law.

With this information, one can quickly calculate how easy it would be for a international corporation to set up DES key cracking on a large scale basis. If they're able to spend a bit, they should be able to crack any DES key within at most a few hours. It's really quite unlikely that such hardware have not already been built and deployed on a large scale basis withing the intelligence community, and even privately held corporations.

There are also several so called weak keys in DES, but these are few, and easy to for a implementation to drop when making the key, so it's not a issue one need to worry about.

Another issue with DES is the number of rounds. It's designed with 16 rounds, and it's been proven that it's possible to attack DES with 15 or less rounds in a way more effective than a brute force attack, with a known-plaintext attack. This is not a realistic attack, but it does indicate that the National Security Agency knew about this kind of attack a long time before the academic sector did.

Finally, the NSA modified the contents of the sboxes, but have refused to answer questions about their reasons for doing so.
The Lexar Corporation and Bell Laboratories analyzed the sboxes in the 1970's. The conclution was that the sboxes had more features in common with a linear transformation than one would expect if chosen randomly. Also a interesting quote from Bell Laboritories:

"Structures have been found in DES that were undoubtedly inserted to strenghten the system against certain types of attacks. Structures have also been found that appear to weaken the system."
As a final note I should mention that various intelligence agencies are believed to have more effective attacks against DES. If the algorithm itself have not been completely broken, it's quite possible they have a attack much more effective than brute force. I haven't been able to get this confirmed, which should also be taken into account.

See also:
Xamot's node on lucifer, which is what DES started as.
Other ciphers:
3des, idea, blowfish, twofish, rc4, rc5, rc6.

Sources:
Dates and quotes from Applied Cryptography by Bruce Schneier. Information on the EFF Hardware DES cracker from the eff web site http://www.eff.org/pub/Privacy/Crypto/Crypto_misc/DESCracker/

DES: diethylstilbestrol. A synthetic drug, not a steroid, that acts as a female sex hormone. Structural variants include dipropionate, dilaurate, and dibutyrate esters, and C14-diethylstilbestrol dibutyrate, the radioactive form used only for special investigative procedures.

Dictionary of Sexology Project: Main Index

DES, short for diethylstilbestrol, is a synthetic estrogen. DES was administered to pregnant women in the U.S. between 1938 and 1971. It was believed to reduce the risk of miscarriage, and was so widely accepted that doctors often pushed it on women as being "completely safe" or even "a vitamin." In fact, children prenatally exposed to DES show a variety of health problems. Women are at increased risk for a rare type of cervical cancer, for infertility, and, ironically, for miscarriage and other birth complications. Men show an increased incidence of testicular cysts. Mothers who took DES show higher rates of breast cancer.

Because DES was removed from the market, obstetricians tend to think the problem is over, and DES information is disappearing from both parenting resources and medical handbooks. In fact, there are between 5 and 10 million people who were prenatally exposed to DES, and many are still of childbearing age. Worse, because the drug was used so freely, many may not even know they have to take precautions.

Women whose mothers took DES should be considered moderate or high-risk when pregnant, until proven otherwise. If you think you may have been exposed to DES, please see http://www.desaction.org for more information.
The widespread rumor or belief that the DES design was in any way weakened by the attention it received from NSA was largely answered in Biham and Shamir's paper on differential cryptanalysis.

In their 1992 work presenting chosen plaintext attacks on DES was the first cryptanalytic attack which could break DES with less effort than an exhaustive key search. However it requires the attacker to trick the target into encrypting 247 attacker-supplied plaintexts - not a small task.

This work observed that the S-boxes seem to have been optimally designed and that any changes to the S-boxes rendered DES substantially easier to break using differential cryptanalysis.

Following the publication of this work Don Coppersmith broke a 20 year long silence on the details of the design, indicating that the IBM team had independently discovered the differential attack on block ciphers and taken the appropriate steps to modify it. He also indicated that aside from key-length, NSA made no other modifications to either strengthen or weaken the design.

Additionally this work demonstrated that the number of rounds used in DES was optimal to protect against the differential analysis attack (i.e. any fewer number of rounds introduces weaknesses while adding rounds does not gain any benefit.

It is acknowledged that US federal policy has long mandated that the spread of strong encryption technology be minimized. The use of a 56 bit key did accomplish that, however 3DES with 112 bits remains proof against attack. AES is destined to eventually replace triple DES in financial and other secure applications.


Reference:
Differential Cryptanalysis, 1992 Eli Biham, Adi Shamir
See also: linear cryptanalysis

Log in or registerto write something here or to contact authors.