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/