DES algorithms

The first algorithm presented in this chapter is DES. Its history began in 1973 when the National Bureau of Standards (NBS), which later became the National Institute of Standards and Technology (NIST), required an algorithm to adopt as a national standard. In 1974, IBM proposed Lucifer, a symmetric algorithm that was forwarded from NIST to the National Security Agency (NSA). After analysis and some modifications, it was renamed DES. In 1977, DES was adopted as a national standard and it was largely used in electronic commerce environments, such as in the financial field, for data encryption.

Remarkable debates arose over the robustness of DES within the academic and professional community of cryptologists. The criticism derived from the short key length and the perplexity that, after a review advanced by the NSA, the algorithm could be subjected to a trapdoor, expressly injected by the NSA into DES to spy on encrypted communications.

Despite the criticisms, DES was approved as a federal standard in November 1976 and was published on January 15, 1977, as FIPS PUB 46, authorized for use on all unclassified data. It was subsequently reaffirmed as the standard in 1983, 1988 (revised as FIPS-46-1), 1993 (FIPS-46-2), and again in 1999 (FIPS-46-3), the latter prescribing Triple DES (also known as 3DES, covered later in the chapter). On May 26, 2002, DES was finally superseded by the AES, which I will explain later in this chapter, following a public competition. DES is a block cipher; this means that plaintext is first divided into blocks of 64 bits and each block is encrypted separately. The encryption process is also called the Feistel cipher, to honor Horst Feistel, one of the members of the team at IBM who developed Lucifer.

Now that a little bit of the history of this progenitor of modern symmetric algorithms has been revealed, we can go further into the explanation of its logical and mathematical scheme.

Simple DES

Simple DES is nothing but a simplified version of DES. Before we delve into how DES works, let’s take a look at this simplest version of DES.

Just like DES, this simplified algorithm is also a block cipher, which means that plaintext is first divided into blocks. Because each block is encrypted separately, we are supposed to analyze only one block.

The key, [K], is made up of 9 bits and the message, [M], is made up of 12 bits.

The main part of the algorithm, just like in DES, is the S-box, where S stands for substitution. Here lies the true complexity and non-linear function of symmetric algorithms. The rest of the algorithm is only permutations and shifts over the bits, something that a normal computer can do automatically, so there is no reason to go crazy over it.

An S-box in this case is a 4 x 16 matrix consisting of 6 bits as input and 4 bits as output, which introduces non-linear mapping between the input and output and causes confusion in the data.

We will find that the S-box is present in all modern symmetric encryption algorithms, such as DES, Triple DES, Blowfish (and the more modern Twofish), and AES.

The four rows are represented by progressive 2 bits, as follows:

00

01

10

11

The 16 lines of the columns instead consist of 4 bits in this sequence:

0000 0001 0010 …… …… …… …… 1111

The matrix’s boxes consist of random numbers between 0 and 15, which means they never get repeated inside the same row.

In order to better understand how an S-box is implemented and how it works, here is an example: 011011. This string of bits has two outer bits, 0 and 1, and four middle bits, 1101.

Figure 2.7: String bits when implementing an S-box

So, let’s take the outer bits to form 01 and take the middle bits as 1101. Working in the binary system, using N2 notation, (01)2 corresponds to the 2^nd row in the matrix, and (1101)₂ corresponds to the 13th column. You can see the representation in binary numbers of the S-box matrix described here:

Figure 2.8: An S-box matrix (intersection) of 4 x 16 represented in binary numbers

As you can see, by finding the intersection of the column and the row, we obtain (1001)₂.

The same matrix can be represented in decimal numbers:

Figure 2.9: An S-box matrix of 4 x 16 represented in decimal numbers

Here, the number 9 represents the intersection between row 2 and column 13. So, the number found crossing row 2 and column 13, represented in a binary system as (1001)₂, corresponds to 9 in the decimal system.

Now that we are clear on what S-box is and how it is designed, we can see how the algorithm works.

Bit initialization

The message, M, consisting of 12 bits, is divided into two parts, L₀ and R₀, where L₀, the left half, consists of the first 6 bits, and R₀, the right half, consists of the last 6 bits:

Figure 2.10: Message (M) is split into 6 bits to the left and 6 bits to the right

Now that we have a clear concept of S-box and bit initialization, let’s proceed with the other phases of the process: bit expansion, key generation, and bit encryption. As we will see, L₀ and R₀ have the same bit expansion pattern: they are simply a division of M.

Bit expansion

Each block of bits, the left and right parts, is expanded through a particular function that is normally called f.

The DES algorithm uses an expansion at 8 bits (1 byte) starting from 6-bit input for each block of plaintext.

Moreover, DES uses a modality of partition called Electronic Code Book (ECB) to divide the 64 bits of plaintext into 8 × 8 bits for each block performing the (E_k) encryption function.

Any f could be differently implemented, but just to give you an example, the first input bit becomes the first output, the third bit becomes the fourth and the sixth, and so on. Just like the following example, let’s say we want to expand the 6-bit L₀: 011001 input with an expansion function, Exp, following this pattern:

Figure 2.11: Bit expansion function

As you can see in the preceding figure, L₀ = (011001)₂ has been expanded with f [12434356].

Then, L₀: 011001 will be expanded into (01010101)₂, as shown in the following figure:

Figure 2.12: L₀ (011001)₂ bit expansion 8 bits

By expanding the 6-bit R₀: (100110)₂ input to 8 bits with the same pattern, f [12434356], in R_i-1 = (100110)₂, we obtain the following:

Figure 2.13: R₀ (100110)₂ bit expansion 8 bits

So, the expansion of R_i-1 will be (10101010)₂.

Key generation

As we have already said, the master key, [K], is made up of 9 bits. For each round, we have a different encryption key, [K_i], generated by 8 bits of the master key, starting counting from the i^th round of encryption.

Let’s take an example to clarify the key generation K₄ (related to the fourth round):

• K = 010011001 (9-bit key, the master key)
• K₄ = 01100101 (8 bits taken by K)

The following figure will help you better understand the process:

Figure 2.14: Example of key generation

As you can see in the previous figure, we are processing the fourth round of encryption, so we start to count from the fourth bit of the master key [K] to generate [K4].

Bit encryption

To perform the bit encryption, (E), we use the XOR function between R_i-1= (100110)2 expanded and K_i = (01100101)₂. See Figure 2.6 for how to use XOR.

I call this output E(K_i):

At this point, we split E(K_i), consisting of 8 bits, into two parts, a 4-bit half for the left and a 4-bit half for the right:

Now, we process the 4 bits to the left and the 4 bits to the right with two S-box 2 x 8 matrices consisting of 3 bits for each element. The input, as I mentioned earlier, is 4 bits: the first one is the row and the last three represent a binary number to indicate the column (the same as previously, just with fewer bits). So, 0 stands for first, and 1 stands for second. Similarly, 000 stands for the first column, 001 stands for the second column, and so on until 111.

We call the two S-boxes S1 and S2. The following figure represents the elements of each one:

Figure 2.15: Examples of S-boxes

L(E(K_i)) = (1100)₂ is processed by S1; so, the element of the second row, (1)₂, and the fourth column, (100)₂, is the output, here represented by the number (000)₂.

R(E(K_i)) = (1111)₂ is processed by S2; so, the element of the second row, (1)₂, and the seventh column, (111)₂, is the output, here represented by the number (100)₂.

Now, the last step is the concatenation of the two outputs obtained, here expressed by the notation ||, which will perform the ciphertext:

The following figure shows how the encryption of the first round (the right side) of the f function mathematically works:

Figure 2.16: Mathematical scheme of (simple) DES encryption at the first round (right side)

Now that we have understood how simple DES works and covered the basics of symmetric encryption, it will be easier to understand how the DES family of algorithms works.

As you have seen, the combination of permutations, XOR and shift, is the pillar of the structure of the Feistel system.

DES

DES is a 16-round encryption/decryption symmetric algorithm. DES is a 64-bit cipher in every sense. The operations are performed by dividing the message, [M], into 64-bit blocks. The key is also 64 bits; however, it is effectively 56 bits (plus 8 bits for parity: 8^th, 16^th, 24^th…). This technique eventually allows us to check errors. Finally, the output, (c), is 64 bits too.

I would like you to focus on the DES encryption scheme of Figure 2.15 to fully understand DES encryption.

Key generation in DES

In 1945, Claude Shannon introduced the principles of confusion and diffusion in his paper, A Mathematical Theory of Cryptography (https://www.iacr.org/museum/shannon45.html). DES, just like most symmetric algorithms, uses bit scrambling to obtain these two effects.

In Shannon’s original definitions, confusion refers to making the relationship between the ciphertext and the symmetric key as complex and involved as possible, whereas diffusion refers to dissipating the statistical structure of plaintext over the bulk of ciphertext. This complexity is generally implemented through a well-defined and repeatable series of substitutions and permutations.

As already mentioned, the DES master key is a 64-bit key. The key’s bits are enumerated from 1 to 64, where every eighth bit is ignored, as you can see in the highlighted column in the following table:

Figure 2.17: Bits deselected in the DES master key

After the deselection of the bits, the new key is a 56-bit key.

At this point, the first permutation on the 56-bit key is computed. The result of this operation is confusion on the bit positions; then, the key is divided into two 28-bit sub-keys called C0 and D0. The first permutation is also known as the initial permutation and is a crucial step in DES.

After this operation (always in the same line to create a bit of confusion and diffusion), it performs a circular shift process as shown in the following table:

Figure 2.18: Showing the number of key bits shifted in each round in DES

If you look at the preceding table, you can see that rounds 1, 2, 9, and 16 shift left by only 1 bit; all the other rounds shift left by 2 bits.

Let’s take as an example C0, D0 (the original division of the key in 28-bit left and 28-bit right), expressed in binary notation as follows:

Now, from C0 and D0, C1 and D1 will be generated, as follows:

If you focus on the step of the generation of C0 --> C1, you can better understand how it works; it’s a simple shift to the left of all the bits of C0 with respect to C1:

After the circular shift, the next step is to process a selection of 48 bits over the subset key of 56 bits. It’s a simple permutation of position: just to give an example, bit number 14 moves to the first position, and bit number 32 moves to the last position (48^th). As you can see in the following table, some bits, just like bit number 18, are discarded in the new configuration, so you don’t find them in the table. At the end of the process of bit compression, only 48 bits are selected; consequently, 8 bits are discarded:

Figure 2.19: Transformation and compression in a 48-bit subset key

In the following figure, you can see the whole process of key generation, which combines parity drop, shift left, and compression:

Figure 2.20: The key generation scheme

Because of this compression/confusion/permutation technique, DES is able to determine different sub-keys, one per round of 48 bits. This makes DES difficult to crack.

Encryption

After we have generated the key, we can proceed with the encryption of the message, [M].

The encryption scheme of DES consists of three phases:

1. Initial permutation (IP): First, the bits of the message, [M], are permutated through a function that we call IP. This operation, from a cryptographic point of view, does not seem to augment the security of the algorithm. After the permutation, the 64 bits are divided into 32 bits in L0 and 32 bits in R0 just like we did in simplified DES.
2. Rounds of encryption: For 0 ≤ i ≤ 16, the following operations are executed:
   1. Li = Ri-1
   2. Compute .

   Here, K_i is a string of 48 bits obtained from the key K (round key j) and f is a function of expansion similar to the f described earlier for simple DES.

   3. Basically, for i = 1 (the first round), we have the following:

• Final permutation: The last part of the algorithm at the 16^th round (the last one) consists of the following:
  1. Exchanging the left part, L₁₆, with the right part, R₁₆, in order to obtain (R₁₆, L₁₆)
  1. Applying the inverse, INV, of the IP to obtain the ciphertext, c, where c = INV(IP (R₁₆, L₁₆))

The following figure is a representation of an intelligible scheme of DES encryption:

Figure 2.21: DES encryption

To summarize the encryption stage in DES, we performed a complex process for key generation, where a selection of 48-bit subsection keys on a master key of 64 bits was made. There are consequently three steps: IP, rounds of encryption, and final permutation.

Now that we have analyzed the encryption process, we can move on to DES decryption analysis.

Decryption

DES decryption is very easy to understand. Indeed, to get back the plaintext, we perform an inverse process of encryption.

The decryption is performed in exactly the same manner as encryption, but by inverting the order of the keys (K₁…K₁₆) so that it becomes (K₁₆…K₁).

In the following figure, you see the decryption process in a flow chart scheme:

Figure 2.22: DES decryption process

So, to describe the decryption process: you take the ciphertext and operate the first IP on it, then XOR L₀ (left part) with R₀ = f(R₀, K₁₆).

Then, you keep on going like that for each round, make a final permutation, and end up finding the plaintext.

Now that we have arrived at the end of the DES algorithm process, let’s go ahead with the analysis of the algorithm and its vulnerabilities.

Analysis of the DES algorithm

Going a little bit more into the details of the algorithm, we can discover some interesting things.

One of the most interesting steps of DES is the XOR operation performed between the sub-keys (K₁, K₂…K₁₆) and the half part of the message, [M], at each round.

In this step, we find the S-box: the f function previously described in simplified DES.

As we saw earlier, the S-box is a particular matrix in DES that consists of 4 rows and 16 columns (S-box 4×16) fixed by the NSA. In the following image, we can see eight rounds of the S-box:

Figure 2.23: The S-box matrix in DES

As you might notice, the numbers included are between 0 and (R_i-1) 16-1 = 15.

Take a look at the specifics of the S-box in the 5^th round of DES:

2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
11	8	12	7	11	14	2	13	6	15	0	9	10	4	5	3

Figure 2.24: S-box 5th round

If you observe carefully, in the 14^th column, all the numbers are very low: 0, 9, 3, and 4. This combination could pose a problem for security.

You will be perplexed if I tell you that it will not be an issue to play with little numbers inside an S-box. Let’s look into this.

A question that may come to you spontaneously might be: Why is the key only 56 bits and not 64 bits? This is because the other 8 bits are used for pairing.

Actually, the initial master key is 64 bits in length, so every 8^th bit of the key is discarded. The final result is a 56-bit key, as you see in the following figure:

Figure 2.25: Bit discarded in the DES key generation algorithm

Remember the step where we process a selection of 48 bits over the subset key of 56 bits. So, 48 bits of input will give exactly 48 bits of output after the XOR operation is performed with [K_i].

There is one more concern that could arise from the method of encryption adopted in DES. After the IP, as you can see, the bits are encrypted only on the right side through the f(R_i-1, K_i) function. You might ask whether this is less secure than encrypting all the bits. If you analyze the scheme properly, you will notice that at each round, the bits are exchanged from left to right, then encrypted, and vice versa. This technique is like a wrap that allows all the bits to be encrypted, not just the right part as it would seem at first glance.

Looking back at the initial and final permutation functions, you may ask: when making an initial and final inverse permutation, isn’t the final result neutral? As I already mentioned, there isn’t any cryptographic sense in performing a permutation of bits like that. The reason is that bit insertion into hardware in the 70s was much more complicated than it is now. To complete the discussion, I can say that the entire process adopted in DES for substitution, permutation, exponential expansion, and bit-shifting generates confusion and diffusion. At the beginning of this section, I already quoted this concept when I mentioned the security cipher principle identified by Claude Shannon in his A Mathematical Theory of Communication.

Violation of DES

The history of the attacks performed to crack DES since its creation is rich in anecdotes. In 1975, among the academic community, skepticism against the robustness of the key length with respect to the 56-bit keys started to arise. Many articles have been published; one very interesting prediction of Whitney Diffie and Martin Hellman (the same pair from the Diffie and Hellman exchange of the key seen in Chapter 3, Asymmetric Encryption Algorithms) was that a computer worth $20 million (in 1977) could be built to break DES in only 1 day.

More than 20 years later, in 1998, the Electronic Frontier Foundation (EFF) developed a dedicated computer called the DES cracker to break DES for DES Challenge 2, aiming for the $10,000 reward for the decryption of the ciphertext. The EFF spent a little less than $250,000 and employed 37,050 units embedded into 26 electronic boards. After 56 hours, the supercomputer gained the decryption of the plaintext message. DES Challenge 3 only took 22 hours and 15 minutes. The method adopted was a simple brute-force method to analyze all the possible combinations of bits given by the 256 (about 72 quadrillion) possible keys. The EFF was able to crack DES using hardware that incorporated 1,500 microchips working at 40 MHz, in 4.5 days of running time. Imagine: it would take 1 microchip 38 years to explore the entire set of keys.

At this point, the authorities decided to replace the algorithm with a new symmetric key algorithm, and here came AES. But before exploring AES, let’s analyze some possible attacks on DES.

I will present some possible attacks on DES, taking into consideration that most of these methods are used to attack most symmetric algorithms. Some of the attacks are specific to blocking ciphers, while others are valid for streaming ciphers too. The difference is that in a stream cipher, 1 byte is encrypted at a time, while in a block cipher, ~128 bits are encrypted at a time (block):

• Brute-force attack: This basic method of attack can be performed for any known cipher, meaning trying all the possibilities to find the key. If you recall, the key length of DES is a 56-bit key. But we need to try less than all the sets of keys because, statistically, as proved by Mitsuru Matsui, with (247) known plaintexts, it is possible to break 16-round DES. This is not a computation to be taken lightly, but despite this, DES has been a breakable algorithm since the early 90s. For your reference, if you are interested, you can find Mitsuru Matsui’s paper here: https://link.springer.com/content/pdf/10.1007/3-540-48285-7_33.pdf.
• Linear cryptanalysis: This is essentially a statistical method of attack based on known plaintext. It doesn’t guarantee success every time, but it does work most of the time. The idea is to start from the known input (plaintext) and arrive at determining the key of encryption and, consequently, all the other outputs generated by that key.
• Differential cryptanalysis: This method is technical and requires observing some vulnerabilities inside DES (similar to other symmetric algorithms). This attack method attempts to discover the plaintext or the key, starting from a chosen plaintext. Unlike linear cryptanalysis, which starts from improbable known plaintext, the attacker operates knowing the chosen plaintext.

Last but not least, a vulnerability of DES is called weak keys: these keys are simply not able to perform any encryption. This is very dangerous because if applied, you get back plaintext. These keys are well known in cryptography and have to be avoided.

That happens when the sequence of the 16^th key (during the key generation) produces all 16 identical keys.

Let’s see an example of this problem (for clarity’s sake, I should state that we are using binary, with no parity bits):

• A sequence of bits all equal to 0000000000000000 or 1111111111111111
• A sequence of alternate bits, 0101010101010101 or 1010101010101010

In all four cases, it turns out that the encryption is auto-reversible, or in other words, if you perform two encryptions on the same ciphertext, you will obtain the original plaintext.

Triple DES

As I mentioned previously, one of the main weaknesses found in DES was the key length of 56 bits. So, to amplify the volume of keys and to extend their life, a new version of DES was proposed in the form of Triple DES.

The logic behind 3DES is the same as DES; the difference is that here we run the algorithm three times with three different keys.

The following figure shows a scheme proposed to better understand 3DES:

Figure 2.26: Triple DES encryption/decryption scheme

Let’s see how the encryption and decryption stages work in DES, based on the scheme illustrated in the preceding figure.

Encryption in 3DES works as follows:

1. Encrypt the plaintext blocks using single DES with the [K₁] key.
2. Now, decrypt the output of Step 1 using single DES with the [K₂] key.
3. Finally, encrypt the output of Step 2 using single DES with the [K₃] key.

The output of Step 3 is the ciphertext (C).

Decryption in 3DES

The decryption of ciphertext is a reverse process. The user first decrypts using [K₃], then decrypts with [K₂], and finally, decrypts with [K₁].

DESX

The last algorithm of the DES family is DESX. This is a reinforcement of DES’s key proposed by Ronald Rivest (the same co-author of RSA).

Given that DES encryption/decryption remains the same as earlier, there are three chosen keys: [K₁], [K₂], and [K₃].

The following encryption is performed:

First, we have to perform the encryption (E_K), making an XOR between [K₂] and the message, [M]. Then, we apply DES, encrypting with [K₁] 56 bits. Finally, we add the E_K1, XOR, and [K₃] outputs. This method allows us to increase the virtual key to 64 + 56 + 64 = 184 bits, instead of the normal 56 bits:

Figure 2.27: DESX encryption scheme

After exploring the DES, 3DES, and DESX algorithms, we will approach another pillar of the symmetric encryption algorithm: AES.