What is DES?

History

The Data Encryption Standard (DES) was developed in the 1970s by the National Bureau of Standards with the help of the National Security Agency. Its purpose is to provide a standard method for protecting sensitive commercial and unclassified data. IBM created the first draft of the algorithm, calling it LUCIFER. DES officially became a federal standard in November of 1976.

Algorithm

Figure 5: DES Block Diagram

Fundamentally DES performs only two operations on its input, bit shifting, and bit substitution. The key controls exactly how this process works. By doing these operations repeatedly and in a non-linear manner you end up with a result which can not be used to retrieve the original without the key. Those familiar with chaos theory should see a great deal of similarity to what DES does. By applying relatively simple operations repeatedly a system can achieve a state of near total randomness.

DES works on 64 bits of data at a time. Each 64 bits of data is iterated on from 1 to 16 times (16 is the DES standard). For each iteration a 48 bit subset of the 56 bit key is fed into the encryption block represented by the dashed rectangle above. Decryption is the inverse of the encryption process. The "F" module shown in the diagram is the heart of DES. It actually consists of several different transforms and non-linear substitutions. Consult one of the references in the bibliography for details.

What is the Limited DES that Enigma Implements?

The limited DES mode available in the freeware version of Enigma modifies the DES standard in two ways. First of all, a 32 bit key is used instead of 56 bits [note: 32 bits, NOT 28 bits]. Secondly the data is iterated on only 4 times instead of 16. These changes reduce the computational complexity of the algorithm by at least 2^26 times. Nevertheless a naive user would still have to guess on average 2 billion times before the correct key was determined. However, by using only 4 iterations over the F module there are known attacks better than brute force which could be used for a more sophisticated attack.

What is Cipher Block Chaining?

The full DES version of Enigma takes the basic DES algorithm one step further by adding what is known as cipher block chaining. Without modification the standard DES algorithm encrypts data in 64 bit blocks independent of their context. Cipher block chaining increases security by exclusive ORing the previous 64 bit block with the current 64 bit block. This makes the encrypted value of a block context dependent, making it much more difficult to decipher. [Note this capability is only implemented in full DES versions of Enigma starting with version 2.3.]

How Secure is DES?

Users of Enigma will most likely be subject to ciphertext only attacks. That is an attack in which the cryptographer has access only to encrypted documents. Under such conditions there is no known method of attack better than randomly guessing keys. This discussion assumes you meet this condition.

The limited DES version of Enigma has 2^32 or 4,294,967,296 possible keys. The full DES version of Enigma has 2^56 or 72,057,594,037,900,000 possible keys. To determine the time it will take to break a file protected by Enigma multiply the number of keys by the time it takes your computer to try one key (times one half because on average you will guess the key by the time you have tried half the keys).

For comparison I have done some rough (but conservative) calculations. Using brute force a Mac LC-II can break into a file protected by the free version of Enigma in about 1 day of non-stop computing. It would take that same Mac almost a million years to break into the same file protected by the full DES version. Equivalent numbers for a single Cray super computer (estimate somewhat rougher) would be about 10 minutes versus 3,000 years.

What about back doors?

Because the NSA was involved in the development of DES there has been a constant concern there is a back door. Here DES's greatest weakness that it was developed almost 20 years ago is a strength. In those 20 years no one has ever described a way to break DES except by brute force (ciphertext ONLY attacks). Concerns about DES's weakness are centered solely on how fast it will take a computer to try those 72 quintillion possible combinations. Massively parallel computers are a significant threat because each processor can be assigned a small piece of the total problem. Nevertheless even the most optimistic estimates place the cost of a theoretical DES breaking machine into the several millions of dollars range. This is not to say that no one can read a message protected by DES. If the NSA decides they need to read your document, they will.

It is easy to be paranoid when it comes to encryption, but keep this in mind. It is in the US Governments interest to provide a good encryption standard. If the NSA could read industrial and technology secrets protected by DES than so could the KGB. It is my opinion that DES was designed to balance the competing interests of a government reading its citizens secrets and being sure that no other government could read them. I believe that this resulted in an algorithm of very high security, but one that can be broken through brute force by a truly massive assault. The inevitable march of technology has slowly eroded the amount of technological know-how needed to break DES but the hurdle remains high for the next decade or two.

Back to the Next Wave Home Page