Limited Entropy Dot Com Not so random thoughts on security featured by Eloi Sanfèlix

Crypto Series: Block Ciphers – Data Encryption Standard (DES)

The Data Encryption Standard ( DES ) was designed by IBM in 1973 as a submit for a call for proposals by the National Bureau of Standards of the United States.  There was some controversy regarding to the involvement of the NSA in the development of the cipher, especially to the mysterious S-boxes and the reduced key size used, but years later it was shown that the S-boxes used where more resistant to Differential Cryptanalysis than if they had been selected at random.

The algorithm was approved as a FIPS standard in 1976, and revised up to three times in 1988,1993 and 1999. The last revision FIPS-46-3 describes the 3DES extension as a method to enlarge the key size of the DES cipher by using 3 DES operations in a row, encrypting the first time, decrypting the second time, and encrypting again the third time. This was done in order to withstand an efficient brute force attack published in 1998.

After the break (click Read more!) we'll see how it works and the main components of the algorithm.

NOTE: All images in this post are directly linked to Wikipedia. If the images are not visible anymore, let me know in the comments and I'll post my own version of the images.

DES structure

DES is a block cipher which encrypts 64 bits blocks under a 56 bits key. Actually, normally one supplies the DES algorithm with a 64 bits key, but the lowest significant bit of each key byte is not used for the encryption and could be used for parity checking.

The overall structure of DES is depicted in the following figure:

DES structure

It starts by applying the so called Initial Permutation (IP), which obviously performs a permutation, i.e. scrambles the input bits. Then the data block is divided into the upper 32 bits (L0) and the lower 32 bits (Ro) creating a left and a right part. Now 16 identical rounds are applied: a function F (Feistel's function) is applied to the right half and a round key, and the result is XORed with the left half. Then both halves are swapped.

After the 16 rounds have been applied, a Final Permutation (FP) is applied. This permutation is actually the inverse of the Initial Permutation ( ). All these things together conform what we call a Feistel's network, with a great property: we can decrypt the ciphertext with the same algorithm, changing only the order in which we apply the round keys.

This means that the decryption process for DES is identical to the encryption process. Only that round key 16 is applied first, then round key 15, and so on.

The F function

The F function is at the very core of the DES cipher. As explained above, this function is applied in each round to the right half and the round key, and its output is XORed with the left half. At the beginning of the F function, there is an Expansion function (E), which expands the 32 bits input into 48 bits. These 48 bits are then XORed with the 48 bits round key coming from the key scheduling algorithm.

Then, these 48 bits are supplied in groups of 6 bits to the S-boxes. The S-boxes are just substitution functions, which are implemented as a substitution table, and output 4 bits each one. Therefore, the output of the 8 S-boxes is again 32 bits, same size as the input and output of the F function. After the S-boxes, a permutation, P, is applied. The output of the permutation is the result of the F function.

Feistel's function

Key Scheduling

In order to have the complete picture of how DES works, we still need to know how the round keys are computed from the DES key. This is done by the so-called key scheduling algorithm, which can be run in parallel with the DES cipher or precomputed and stored in a table of round keys.

The process looks like this:

DES key schedule

First, a permutation PC1 is performed. The name comes from Permuted Choice, due to the fact that this permutation also choses some bits from the key: the last bit of each byte (i.e, bits 8,16, etc) is discarded as we said earlier, and the rest are used for the permutation.

After this, the structure is repeated for each round key: the result of applying PC1 is divided into left and right halves, these halves are shifted (cyclically) one or two bits to the left depending on the round number. After that, the shifted key is fed to a second permutation, PC2, which selects 48 bits out of the 56 input bits.

Detailed information

So far, we've seen how DES works. However, you wouldn't be able to implement the DES algorithm without knowing exactly how permutations, expansion functions and S-boxes actually modify the data. To that end, you can go to the standard itself or to the DES Supplementary material page on Wikipedia.

As usual, implementing your own crypto is not recommended. Do it only for educational purposes, otherwise things could easily go VERY wrong.

Triple DES

As explained in the introduction of this article, a brute force attack to DES was presented long ago. This attack motivated the introduction of a new variant of DES. This variant, called triple DES, uses three DES operations in a row to enlarge the key space.

Typically the data is DES encrypted with key K1, then decrypted with key K2, and then encrypted again with key K1. This raises the key length to 112 bits (8 bits of K1 and 8 bits of K2 are discarded by PC1), which makes a brute force attack much more difficult.

There exists also a 3DES variant which uses three different keys, achieving a key size of 168 bits. Of course, 3DES can also be used with 3 identical keys. This would give you a DES encryption and allow devices that do not implement 3DES to be used together with devices that implement 3DES.