Data Encryption Standard - Data Encryption Algorithms - Introduction To Network Security: Theory And Practice (2015)

Introduction To Network Security: Theory And Practice (2015)

Chapter 2. Data Encryption Algorithms

2.2 Data Encryption Standard

The DES was published by the U.S. National Bureau of Standards (NBS) in 1977. NBS was the predecessor of the U.S. National Institute of Standards and Technology (NIST). DES was based on the Lucifer encryption algorithm developed by an IBM research group led by Horst Feistel. In particular, DES is a concrete realization of the Feistel cipher scheme. Its encryption and decryption structures are symmetrical, and they use four basic operations: exclusive-OR, permutation, substitution, and circular shift. DES was widely used from the mid-1970s to the early 2000s. Although gradually phasing out, DES played an important role in modern cryptography and represents a popular design paradigm for data encryption.

2.2.1 Feistel's Cipher Scheme

The Feistel cipher scheme (FCS) divides the plaintext string into a sequence of blocks, each of which is image bits long. FCS only uses basic operations of XOR and substitution. Let image be a positive integer. FCS first generates image subkeys of a fixed length from the encryption key image. Let these subkeys be image. Let image denote the substitution function that takes an image-bit binary string and a subkey as input and generates an image-bit binary string as output. Divide a image-bit plaintext block image into two halves image and image of equal length, where imageand image are, respectively, the prefix substring and the suffix substring of image. The FCS encryption and decryption algorithms each executes image rounds of a fixed sequence of operations (see Figure 2.1).

c02f001

Figure 2.1 Feistel cipher scheme block diagram

FCS encryption executes the following operations in round image, where image:

2.1equation

2.2equation

After image rounds, the plaintext block image is transformed to image. Let image and image be the output of FCS encryption. That is, the FCS encryption algorithm produces a ciphertext block image.

Rewrite image as image; namely, let image and image. The FCS decryption algorithm is symmetrical to the FCS encryption algorithm, except that the subkeys are applied in the reverse order. In particular, the FCS decryption algorithm executes the following operations in round image, where image:

2.3equation

2.4equation

After image rounds, the ciphertext block image is transformed to image. Let image and image, and let image be the output of FCS decryption.

We now show that the ciphertext block image is transformed back to the plaintext block image. Because the output of the FCS decryption is image, it suffices to show the following equality:

equation

Here is a proof. Note that image and image, and so it suffices to show that image and image. We can use mathematical induction to show that for any integer image with image, we have

2.5equation

2.6equation

Let image, and we will get what we need to prove.

The mathematical induction proof is given as follows. We first note that image and image. Thus, when image, Equalities 2.5 and 2.6 hold.

Induction hypothesis: for any positive integer image, we have

equation

It follows from Equality 2.3, the induction hypothesis, and Equality 2.1 that

equation

Thus, Equality 2.5 is true.

From Equality 2.4 (the induction hypothesis), Equality 2.2, and Equality 2.1, we have

equation

Thus, Equality 2.6 is true. This completes the proof of the correctness of the FCS decryption algorithm.

DES is an instance of FCS with image. That is, the block size of DES is image. The length of DES encryption keys is 56 bits. However, a DES encryption key is represented as a 64-bit binary string, where the imageth bit image is the parity bit of the seven bits immediately before it. The parity bit is used for error detection. Let image be an encryption key. DES first generates 16 subkeys from image, where each subkey has exactly 48 bits. There are image rounds of executions in DES.

2.2.2 DES Subkeys

Let image be an encryption key of DES. To generate 16 subkeys, DES first removes each imageth bit image from image. For convenience, we still use image to denote the new string. DES then permutes the remaining 56 bits using the initial permutation imageas follows, where bits are listed row wise:

equation

It is evident that image permutes image in the following way: the indexes of the first 28 bits start from 57 such that each next index is equal to the current index minus 8 mod 65. The indexes of the next 24 bits start from 63 such that each next index is equal to the current index minus 8 mod 63. The indexes of the last four bits start from 28 such that each next index is equal to the current index minus 8.

The modular operation is a common operation when dealing with integers in a finite domain. Let image be a positive integer and image be a non-negative integer. Then “image mod image” is the remainder of dividing image by image. If image and its absolute value image, then image mod image is equal to the smallest positive integer image such that image. For instance, image mod image.

Let image be a 56-bit binary string, where image. Let image be a compress permutation that takes image as input and produces a 48-bit string as output. image is defined as follows, where bits are listed row wise:

equation

Let image be a 28-bit binary string. Let image denote the new string obtained by shifting image circularly to the left image(image) times, where image(image) is defined as follows:

image

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

image(image)

1

1

2

2

2

2

2

2

1

2

2

2

2

2

2

1

Rewrite image as image, where both image and image are 28-bit binary strings. Then the imageth subkey image is generated as follows, where image:

equation

For instance, let

equation

Then

equation

Thus,

equation

2.2.3 DES Substitution Boxes

The substitution function image in DES is defined using eight special matrices. They are referred to as substitution boxes or S-Boxes in short. Each S-Box is a image matrix (see Table 2.1), where each row in each S-Box is a permutation of integers from 0 to 15. We label these S-Boxes as image. For each image with image, write

equation

Table 2.1 DES S-Boxes

image

14

4

13

1

2

15

11

8

3

10

6

12

5

9

0

7

0

15

7

4

14

2

13

1

10

6

12

11

9

5

3

8

4

1

14

8

13

6

2

11

15

12

9

7

3

10

5

0

15

12

8

2

4

9

1

7

5

11

3

14

10

0

6

13

image

15

1

8

14

6

11

3

4

9

7

2

13

12

0

5

10

3

13

4

7

15

2

8

14

12

0

1

10

6

9

11

5

0

14

7

11

10

4

13

1

5

8

12

6

9

3

2

15

13

8

10

1

3

15

4

2

11

6

7

12

0

5

14

9

image

10

0

9

14

6

3

15

5

1

13

12

7

11

4

2

8

13

7

0

9

3

4

6

10

2

8

5

14

12

11

15

1

13

6

4

9

8

15

3

0

11

1

2

12

5

10

14

7

1

10

13

0

6

9

8

7

4

15

14

3

11

5

2

12

image

7

13

14

3

0

6

9

10

1

2

8

5

11

12

4

15

13

8

11

5

6

15

0

3

4

7

2

12

1

10

14

9

10

6

9

0

12

11

7

13

15

1

3

14

5

2

8

4

3

15

0

6

10

1

13

8

9

4

5

11

12

7

2

14

image

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

1

14

2

13

6

15

0

9

10

4

5

3

image

12

1

10

15

9

2

6

8

0

13

3

4

14

7

5

11

10

15

4

2

7

12

9

5

6

1

13

14

0

11

3

8

9

14

15

5

2

8

12

3

7

0

4

10

1

13

11

6

4

3

2

12

9

5

15

10

11

14

1

7

6

0

8

13

image

4

11

2

14

15

0

8

13

3

12

9

7

5

10

6

1

13

0

11

7

4

9

1

10

14

3

5

12

2

15

8

6

1

4

11

13

12

3

7

14

10

15

6

8

0

5

9

2

6

11

13

8

1

4

10

7

9

5

0

15

14

2

3

12

image

13

2

8

4

6

15

11

1

10

9

3

14

5

0

12

7

1

15

13

8

10

3

7

4

12

5

6

11

0

14

9

2

7

11

4

1

9

12

14

2

0

6

10

13

15

3

5

8

2

1

14

7

4

10

8

13

15

12

9

0

3

5

6

11

Let image be a function that takes a 48-bit string as input and produces a 32-bit binary string as output. In particular, let image be a 48-bit binary string, where image. We use image to denote the substring image. Divide image into eight 6-bit blocks:

equation

For each 6-bit block image (image), we use the imageth S-Box to generate a 4-bit binary string as output, denoted by image, as follows:

Let image, where image for image. Let image denote the binary representation for a row number and image denote the binary representation for a column number. Then define image to be the number in the 4-bit binary representation at row image and column image in matrix image; namely,

equation

For example, if image, then image.

Let

equation

Then image(image) transforms the 48-bit input image to a 32-bit output.

The constructions of the S-Boxes followed a clear set of criteria for the purpose of resisting possible attacks. They were also bound by the computing technologies available in the mid-1970s. For example, the reason why an S-Box has a 6-bit input and a 4-bit output is due to the chip technology available at that time. It took several months of computing time at that time to compute the S-Boxes that satisfy all the criteria. Because the set of criteria for the S-Boxes was not published and because NSA played a role in selecting DES, many people suspected that NSA had planted backdoors in these S-Boxes so that NSA can decipher DES-encrypted messages should they decide to do so. This of course was sheer speculation. In the 1990s, the set of criteria used by the DES design team was discovered by cryptanalysts not in the team. After this, IBM finally decided to publish the original set of criteria for constructing the S-Boxes.

2.2.4 DES Encryption

DES implements its substitution function image using permutations, exclusive-OR, subkeys, and substitutions from the S-Boxes. In particular, for each 32-bit half block image, DES first uses a function called expansion permutation, denoted by EP, to expand it into a 48-bit string. It then XORs this string with a 48-bit subkey, takes the resulting 48-bit output as the input of function image to generate a 32-bit string, and permutes this string to generate a 32-bit string image.

2.2.4.1 Expansion Permutation

Let image be a 32-bit binary string. The expansion permutation EP on image is defined as follows, where bits are listed row wise:

equation

We note that in EP(image), the indexes of the four middle columns are image; the indexes of the first column start from 32, where the next index is the current index plus 4 mod 32; and the indexes of the last column start from 5, where the next index is the current index plus 4 mod 32.

2.2.4.2 DES Substitution

Let image be a 32-bit binary string. Permuting image using the following permutation image, where bits are listed row wise:

equation

DES defines its substitution function image as follows:

equation

2.2.4.3 Encryption Steps

Let image be a 64-bit binary string. Define a permutation image as follows: it first reverses image as image. It then lists the prefix image into four columns from right to left, where each column has exactly eight rows. It also lists the suffix image into four columns from right to left, where each column has exactly eight rows, and inserts them alternately in the prefix columns. That is, according to the listing order, we have

equation

The permutation enumerates the elements in this list row wise. Denote by image the inverse of image.

Let image be a plaintext block. Define an initial permutation IP by image. It is straightforward to verify that IP(image) is equal to the following string, where each number image represents bit image (image) and bits are listed row wise:

equation

It is easy to see that the indexes of the first two rows in IP(image) start from 58, where the next index is equal to the current index minus 8 mod 66; and the indexes of the last two rows in IP(image) start from 57, where the next index is equal to the current index minus 8 mod 66.

Let image. Then image is the inverse of IP(image), defined as follows, where each number image represents bit image and bits are listed row wise:

equation

It is straightforward to verify that image. For example, let image. Because IP changes image to image and image changes image to image, where image and image, we know that image changes image back to image.

Let image and image be, respectively, a 64-bit plaintext block and a 64-bit encryption key with added parity bits. Let image be the 16 subkeys generated from image as described in Section 2.2.2. The DES encryption steps are given as follows:

1. Rewrite image, where image.

2. For image, execute the following operations in order:

equation

3. Finally, let image. (Note that the input of image is image, not image.)

2.2.5 DES Decryption and Correctness Proof

DES decryption is symmetrical to DES encryption, except that subkeys are applied in the reverse order. The DES decryption steps are given as follows:

1. Rewrite image, where image.

2. For image, execute the following operations in order

equation

3. Finally, let image; we then obtain back the plaintext block image.

To prove the correctness of DES decryption, we need to show that

equation

Because image, we have image and image. We note that except IP is used before round 1 starts and image after round 16, the rest of DES is a concrete implementation of FCS. It follows from FCS decryption that image and image. Thus,

equation

This completes the proof.

2.2.6 DES Security Strength

The security strength of DES depends on the number of rounds, the length of encryption key, and the construction of the substitution function. A substantial number of experiments have demonstrated that DES encryption provides good diffusion and confusion effects.

It can be shown that if the number of rounds in DES encryption is less than 16, then differential cryptanalysis can break DES encryption in a reasonable amount of time.

The length of a DES encryption key is 56 bits, which was sufficient to resist brute-force attacks in the 1970s to 1980s. However, the 56-bit key length was no longer secure in the late 1990s due to advancements of computer technologies and algorithms. For example, in 1999, the Electronic Frontier Foundation (EFF) based in the United States spent less than $250,000 to build a special-purpose supercomputer, named “DES Cracker,” to crack DES encryptions. Working with Distributed.Net and a worldwide network of nearly 100,000 PCs on the Internet, DES Cracker broke in 22 hours the “DES Challenge III” encrypted message. The DES Challenges were a series of DES-encrypted messages posted by RSA Data Security in 1997. DES Challenge III was the last one to be broken. This indicated that the DES era was approaching its end.

Does this mean that all the manpower and resources spent over the years in developing hardware and software DES products were down the drain? It is true that DES encryption keys are too short to resist brute-force attacks, but DES has other good properties that have resisted many other attacks. Thus, it is reasonable to look for ways to effectively extend the DES encryption key length without changing the DES algorithms. Fortunately, it can be shown that DES is not a group. Therefore, applying DES multiple times is different from applying DES a single time. In other words, for any three 56-bit DES encryption keys image, we have image, where image represents DES encryption with key image. We note that this property may not be true in other encryption algorithms. For example, in XOR encryption, for any given encryption keys image and image, let image, then

equation

where image represents XOR encryption.