The DES encryption algorithm
The Data Encryption Standard (DES) is a secret key encryption scheme adopted as standard in the USA in 1977. It uses a 56-bit key, which is today considered by many to be insufficient as it can with moderate effort be cracked by brute force. A variant called Triple-DES (TDES or 3DES) uses a longer key and is more secure, but has never become popular. The Advanced Encryption Standard (AES) is expected to supersede DES (and 3DES) as the standard encryption algorithm.
Introduction
The Data Encryption Standard (DES) was jointly developed in 1974 by IBM and the U.S. government (US patent 3,962,539) to set a standard that everyone could use to securely communicate with each other. It operates on blocks of 64 bits using a secret key that is 56 bits long. The original proposal used a secret key that was 64 bits long. It is widely believed that the removal of these 8 bits from the key was done to make it possible for U.S. government agencies to secretly crack messages.
DES started out as the "Lucifer" algorithm developed by IBM. The US National Security Agency (NSA) made several modifications, after which it was adopted as Federal Information Processing Standard (FIPS) standard 46-3 and ANSI standard X3.92.
How DES works
Encryption of a block of the message takes place in 16 stages or rounds. From the input key, sixteen 48 bit keys are generated, one for each round. In each round, eight so-called S-boxes are used. These S-boxes are fixed in the specification of the standard. Using the S-boxes, groups of six bits are mapped to groups of four bits. The contents of these S-boxes has been determined by the U.S. National Security Agency (NSA). The S-boxes appear to be randomly filled, but this is not the case. Recently it has been discovered that these S-boxes, determined in the 1970s, are resistant against an attack called differential cryptanalysis which was first known in the 1990s.
The block of the message is divided into two halves. The right half is expanded from 32 to 48 bits using another fixed table. The result is combined with the subkey for that round using the XOR operation. Using the S-boxes the 48 resulting bits are then transformed again to 32 bits, which are subsequently permutated again using yet another fixed table. This by now thoroughly shuffled right half is now combined with the left half using the XOR operation. In the next round, this combination is used as the new left half.
The figure should hopefully make this process a bit more clear. In the figure, the left and right halves are denotes as L0 and R0, and in subsequent rounds as L1, R1, L2, R2 and so on. The function f is responsible for all the mappings described above.
Security of DES
This secret key encryption algorithm uses a key that is 56 bits, or seven characters long. At the time it was believed that trying out all 72,057,594,037,927,936 possible keys (a seven with 16 zeros) would be impossible because computers could not possibly ever become fast enough. In 1998 the Electronic Frontier Foundation (EFF) built a special-purpose machine that could decrypt a message by trying out all possible keys in less than three days. The machine cost less than $250,000 and searched over 88 billion keys per second.
Triple-DES
The Triple-DES variant was developed after it became clear that DES by itself was too easy to crack. It uses three 56-bit DES keys, giving a total key length of 168 bits. Encryption using Triple-DES is simply
- encryption using DES with the first 56-bit key
- decryption using DES with the second 56-bit key
- encryption using DES with the third 56-bit key
Because Triple-DES applies the DES algorithm three times (hence the name), Triple-DES takes three times as long as standard DES. Decryption using Triple-DES is the same as the encryption, except it is executed in reverse.