DES (Data Encryption Standard)
 Description
 Algorithm
 Block diagrams
 Mathematical functions
 Implementation
At the beginning of the 21st century, DES started to be considered insecure, mainly due to its relatively short secret key length, what makes it vulnerable to brute force attacks. In 2001 DES cipher was replaced by AES. DES is still one of the most popular cipher.
DES uses the key which is 64bit long, however only 56 bits are actually used by the algorithm. Every 8th bit of the key is a control one and it can be used for parity control.
In the encryption process, the data is first divided into 64bit long blocks. Then, each block undergoes the following operations:
 Initial permutation rearranges bits in a certain, predefined way. This step does not enhance the security of algorithm. It was introduced to make passing data into encryption machines easier, at the times when the cipher was invented.
 The input data is divided into two 32bit parts: the left one and the right one.
 56 bits are selected from the 64bit key (Permutation PC1). They are then divided into two 28bit parts.
 Sixteen rounds of the following operations (so called Feistel functions) are then performed:
 Both halves of key are rotated left by one or two bits (specified for each round). Then 48 subkey bits are selected by Permutation PC2.
 The right half of data is expanded to 48 bits using the Expansion Permutation.
 The expanded half of data is combined using XOR operation with the 48bit subkey chosen earlier.
 The combined data is divided into eight 6bit pieces. Each part is then an input to one of the SBoxes (the first 6bit part is the input to the first SBox, the second 6bit part enters the second SBox, and so on). The first and the last bits stand for the row, and the rest of bits define the column of an SBox table. After determining the location in the table, the value is read and converted to binary format. The output from each SBox is 4bit long, so the output from all SBoxes is 32bit long. Each Sbox has a different structure.
 The output bits from SBoxes are combined, and they undergo PBox Permutation.
 Then, the bits of the changed right side are added to the bits of the left side.
 The modified left half of data becomes a new right half, and the previous right half becomes a new left side.
 After all sixteen rounds, the left and the right halves of data are combined using the XOR operation.
 The Final Permutation is performed.
During decryption, the same set of operations is performed but in reverse order. The subkeys are also selected in reverse order (compared to encryption).
Weak keys in DES
A weak key in the DES cipher is a key which generates the same subkeys in all the successive rounds of encryption algorithm. There are four known weak keys in DES (expressed in hexadecimal):
 0x00000000000000 (only zeros)
 0xFFFFFFFFFFFFFF (only ones)
 0x0000000FFFFFFF (only zeros and ones)
 0xFFFFFFF0000000 (only ones and zeros)
Semiweak keys in DES
A semiweak key in the DES cipher is a key for which one can find another key that produces the same encrypted ciphertext from the same given plaintext. There are twelve known semiweak keys in DES (expressed in hexadecimal, along with parity bits):
 0x01E001E001F101F1 and 0xE001E001F101F101
 0xFE01FE01FE01FE01 and 0x01FE01FE01FE01FE
 0x1FE01FE00EF10EF1 and 0xE01FE01FF10EF10E
 0xE0FEE0FEF1FEF1FE and 0xFEE0FEE0FEF1FEF1
 0x1F011F010E010E01 and 0x011F011F010E010E
 0xFE1FFE1FFE0EFE0E and 0x1FFE1FFE0EFE0EFE
Initial and Final Permutations in DES
The Initial and Final Permutations have no influence on security. They don't use a secret key and can be undone by anybody. They were introduced to make hardware implementation easier in some contexts. A hardware circuit which receives data over an 8bit bus can accumulate the bits into eight shift registers, which is more efficient (in terms of circuit area) than a single 64bit register. This process naturally performs the Initial Permutation of DES.
Let's assume that somebody is designing a hardware circuit which should do some encryption with DES. The data will be received in blocks of 8 bits. This means that there are 8 lines, each yielding one bit at each clock. A common device for accumulating data is a shift register: the input line plugs into a onebit register, which itself plugs into another, which plugs into a third register, and so on. At each clock, each register receives the contents from the previous register, and the first register accepts the new bit. Therefore, the contents are shifted.
With an 8bit bus, 8 shift registers are needed, each receiving 8 bits for every input block. The first register receives bits 1, 9, 17, 25, 33, 41, 49 and 57. The second register receives bits 2, 10, 18, ..., and so on. After eight clocks, eight registers received the complete 64bit block and it is time to proceed with the DES algorithm itself.
If initial permutation was not used, then the first step of the first round would extract the 'left half' (32 bits) which, at that point, would consist of the leftmost 4 bits of each of the 8 shift registers. The 'right half' would also get bits from all the 8 shift registers. If you think of it as wires from the shift registers to the units which use the bits, then you end up with a bunch of wires which heavily cross each other. Crossing is doable but requires some circuit area, which is the expensive resource in hardware designs.
On the other hand, if you consider that the wires must extract the input bits and permute them as per the DES specification, you will find out that there is no crossing anymore. In other words, the accumulation of bits into the shift registers inherently performs a permutation of the bits, which is exactly the initial permutation of DES. By defining that initial permutation, the DES standard says: 'well, now that you have accumulated the bits in eight shift registers, just use them in that order, that's fine'.
The same thing is done again at the end of the algorithm during the Final Permutation.
DES was designed at a time when 8bit bus were the top of the technology and one thousand transistors were an awfully expensive amount of logic.
Security of DES
DES is considered to be a welldesigned and effective algorithm. However, just after its publication, many cryptographers believed that the size of its key is too small. At present, the 56bit long key can be broken relatively cheaply, by using brute force attacks within a few days.
It is quite easy to attack DES knowing some parts of plaintext. The intruder can try all 2^{56} possible keys. He looks for a key, which used for decryption of an encrypted block of the known plaintext, produces exactly the same plaintext. In practice, it is enough to know two or three blocks of plaintext to be able to determine if the currently testing key which works for them, will be working for other blocks as well. Probability that the found key is incorrect and converts correctly only the known plaintext blocks is negligibly small.
The fastest known attacks on DES use linear cryptanalysis. They require knowing 2^{43} blocks of plaintext and their time complexity is around 2^{39} to 2^{43}.
Permutations are presented in the form of tables only to make them easier to comprehend; one should bear in mind that input data is vectors, not matrices. Click to learn more on how to read the permutation table.














