Section 3.2. The Data Encryption Standard


[Page 72 (continued)]

3.2. The Data Encryption Standard

The most widely used encryption scheme is based on the Data Encryption Standard (DES) adopted in 1977 by the National Bureau of Standards, now the National Institute of Standards and Technology (NIST), as Federal Information Processing Standard 46 (FIPS PUB 46). The algorithm itself is referred to as the Data Encryption Algorithm (DEA).[6] For DES, data are encrypted in 64-bit blocks using a 56-bit key. The algorithm transforms 64-bit input in a series of steps into a 64-bit output. The same steps, with the same key, are used to reverse the encryption.

[6] The terminology is a bit confusing. Until recently, the terms DES and DEA could be used interchangeably. However, the most recent edition of the DES document includes a specification of the DEA described here plus the triple DEA (TDEA) described in Chapter 6. Both DEA and TDEA are part of the Data Encryption Standard. Further, until the recent adoption of the official term TDEA, the triple DEA algorithm was typically referred to as triple DES and written as 3DES. For the sake of convenience, we use the term 3DES.


[Page 73]

The DES enjoys widespread use. It has also been the subject of much controversy concerning how secure the DES is. To appreciate the nature of the controversy, let us quickly review the history of the DES.

In the late 1960s, IBM set up a research project in computer cryptography led by Horst Feistel. The project concluded in 1971 with the development of an algorithm with the designation LUCIFER [FEIS73], which was sold to Lloyd's of London for use in a cash-dispensing system, also developed by IBM. LUCIFER is a Feistel block cipher that operates on blocks of 64 bits, using a key size of 128 bits. Because of the promising results produced by the LUCIFER project, IBM embarked on an effort to develop a marketable commercial encryption product that ideally could be implemented on a single chip. The effort was headed by Walter Tuchman and Carl Meyer, and it involved not only IBM researchers but also outside consultants and technical advice from NSA. The outcome of this effort was a refined version of LUCIFER that was more resistant to cryptanalysis but that had a reduced key size of 56 bits, to fit on a single chip.

In 1973, the National Bureau of Standards (NBS) issued a request for proposals for a national cipher standard. IBM submitted the results of its Tuchman-Meyer project. This was by far the best algorithm proposed and was adopted in 1977 as the Data Encryption Standard.

Before its adoption as a standard, the proposed DES was subjected to intense criticism, which has not subsided to this day. Two areas drew the critics' fire. First, the key length in IBM's original LUCIFER algorithm was 128 bits, but that of the proposed system was only 56 bits, an enormous reduction in key size of 72 bits. Critics feared that this key length was too short to withstand brute-force attacks. The second area of concern was that the design criteria for the internal structure of DES, the S-boxes, were classified. Thus, users could not be sure that the internal structure of DES was free of any hidden weak points that would enable NSA to decipher messages without benefit of the key. Subsequent events, particularly the recent work on differential cryptanalysis, seem to indicate that DES has a very strong internal structure. Furthermore, according to IBM participants, the only changes that were made to the proposal were changes to the S-boxes, suggested by NSA, that removed vulnerabilities identified in the course of the evaluation process.

Whatever the merits of the case, DES has flourished and is widely used, especially in financial applications. In 1994, NIST reaffirmed DES for federal use for another five years; NIST recommended the use of DES for applications other than the protection of classified information. In 1999, NIST issued a new version of its standard (FIPS PUB 46-3) that indicated that DES should only be used for legacy systems and that triple DES (which in essence involves repeating the DES algorithm three times on the plaintext using two or three different keys to produce the ciphertext) be used. We study triple DES in Chapter 6. Because the underlying encryption and decryption algorithms are the same for DES and triple DES, it remains important to understand the DES cipher.

DES Encryption

The overall scheme for DES encryption is illustrated in Figure 3.4. As with any encryption scheme, there are two inputs to the encryption function: the plaintext to be encrypted and the key. In this case, the plaintext must be 64 bits in length and the key is 56 bits in length.[7]

[7] Actually, the function expects a 64-bit key as input. However, only 56 of these bits are ever used; the other 8 bits can be used as parity bits or simply set arbitrarily.


[Page 74]

Figure 3.4. General Depiction of DES Encryption Algorithm


Looking at the left-hand side of the figure, we can see that the processing of the plaintext proceeds in three phases. First, the 64-bit plaintext passes through an initial permutation (IP) that rearranges the bits to produce the permuted input. This is followed by a phase consisting of 16 rounds of the same function, which involves both permutation and substitution functions. The output of the last (sixteenth) round consists of 64 bits that are a function of the input plaintext and the key. The left and right halves of the output are swapped to produce the preoutput. Finally, the preoutput is passed through a permutation (IP-1) that is the inverse of the initial permutation function, to produce the 64-bit ciphertext. With the exception of the initial and final permutations, DES has the exact structure of a Feistel cipher, as shown in Figure 3.2.


[Page 75]

The right-hand portion of Figure 3.4 shows the way in which the 56-bit key is used. Initially, the key is passed through a permutation function. Then, for each of the 16 rounds, a subkey (Ki) is produced by the combination of a left circular shift and a permutation. The permutation function is the same for each round, but a different subkey is produced because of the repeated shifts of the key bits.

Initial Permutation

The initial permutation and its inverse are defined by tables, as shown in Tables 3.2a and 3.2b, respectively. The tables are to be interpreted as follows. The input to a table consists of 64 bits numbered from 1 to 64. The 64 entries in the permutation table contain a permutation of the numbers from 1 to 64. Each entry in the permutation table indicates the position of a numbered input bit in the output, which also consists of 64 bits.

Table 3.2. Permutation Tables for DES
(This item is displayed on page 76 in the print version)

(a) Initial Permutation (IP)

58

50

42

34

26

18

10

2

60

52

44

36

28

20

12

4

62

54

46

38

30

22

14

6

64

56

48

40

32

24

16

8

57

49

41

33

25

17

9

1

59

51

43

35

27

19

11

3

61

53

45

37

29

21

13

5

63

55

47

39

31

23

15

7

(b) Inverse Initial Permutation (IP1)

40

8

48

16

56

24

64

32

39

7

47

15

55

23

63

31

38

6

46

14

54

22

62

30

37

5

45

13

53

21

61

29

36

4

44

12

52

20

60

28

35

3

43

11

51

19

59

27

34

2

42

10

50

18

58

26

33

1

41

9

49

17

57

25

(c) Expansion Permutation (E)

 

32

1

2

3

4

5

 
 

4

5

6

7

8

9

 
 

8

9

10

11

12

13

 
 

12

13

14

15

16

17

 
 

16

17

18

19

20

21

 
 

20

21

22

23

24

25

 
 

24

25

26

27

28

29

 
 

28

29

30

31

32

1

 

(d) Permutation Function (P)

16

7

20

21

29

12

28

17

1

15

23

26

5

18

31

10

2

8

24

14

32

27

3

9

19

13

30

6

22

11

4

25


To see that these two permutation functions are indeed the inverse of each other, consider the following 64-bit input M:

M1

M2

M3

M4

M5

M6

M7

M8

M9

M10

M11

M12

M13

M14

M15

M16

M17

M18

M19

M20

M21

M22

M23

M24

M25

M26

M27

M28

M29

M30

M31

M32

M33

M34

M35

M36

M37

M38

M39

M40

M41

M42

M43

M44

M45

M46

M47

M48

M49

M50

M51

M52

M53

M54

M55

M56

M57

M58

M59

M60

M61

M62

M63

M64


where Mi is a binary digit. Then the permutation X = IP(M) is as follows:

M58

M50

M42

M34

M26

M18

M10

M2

M60

M52

M44

M36

M28

M20

M12

M4

M62

M54

M46

M38

M30

M22

M14

M6

M64

M56

M48

M40

M32

M24

M16

M8

M57

M49

M41

M33

M25

M17

M9

M1

M59

M51

M43

M35

M27

M19

M11

M3

M61

M53

M45

M37

M29

M21

M13

M5

M63

M55

M47

M39

M31

M23

M15

M7


If we then take the inverse permutation Y = IP-1(X) = IP-1(IP(M)), it can be seen that the original ordering of the bits is restored.

Details of Single Round

Figure 3.5 shows the internal structure of a single round. Again, begin by focusing on the left-hand side of the diagram. The left and right halves of each 64-bit intermediate value are treated as separate 32-bit quantities, labeled L (left) and R (right). As in any classic Feistel cipher, the overall processing at each round can be summarized in the following formulas:


[Page 76]

Li = Ri-1

Ri = Li-1 x F(Ri-1, Ki)


[Page 77]

Figure 3.5. Single Round of DES Algorithm


The round key Ki is 48 bits. The R input is 32 bits. This R input is first expanded to 48 bits by using a table that defines a permutation plus an expansion that involves duplication of 16 of the R bits (Table 3.2c). The resulting 48 bits are XORed with Ki. This 48-bit result passes through a substitution function that produces a 32-bit output, which is permuted as defined by Table 3.2d.

The role of the S-boxes in the function F is illustrated in Figure 3.6. The substitution consists of a set of eight S-boxes, each of which accepts 6 bits as input and produces 4 bits as output. These transformations are defined in Table 3.3, which is interpreted as follows: The first and last bits of the input to box Si form a 2-bit binary number to select one of four substitutions defined by the four rows in the table for Si. The middle four bits select one of the sixteen columns. The decimal value in the cell selected by the row and column is then converted to its 4-bit representation to produce the output. For example, in S1 for input 011001, the row is 01 (row 1) and the column is 1100 (column 12). The value in row 1, column 12 is 9, so the output is 1001.

Figure 3.6. Calculation of F(R, K)
(This item is displayed on page 78 in the print version)


Table 3.3. Definition of DES S-Boxes
(This item is displayed on page 79 in the print version)


Each row of an S-box defines a general reversible substitution. Figure 3.1 may be useful in understanding the mapping. The figure shows the substitution for row 0 of box S1.

The operation of the S-boxes is worth further comment. Ignore for the moment the contribution of the key (Ki). If you examine the expansion table, you see that the 32 bits of input are split into groups of 4 bits, and then become groups of 6 bits by taking the outer bits from the two adjacent groups. For example, if part of the input word is


[Page 78]

... efgh ijkl mnop ...

this becomes

... defghi hijklm lmnopq ...

The outer two bits of each group select one of four possible substitutions (one row of an S-box). Then a 4-bit output value is substituted for the particular 4-bit input (the middle four input bits). The 32-bit output from the eight S-boxes is then permuted, so that on the next round the output from each S-box immediately affects as many others as possible.

Key Generation

Returning to Figures 3.4 and 3.5, we see that a 64-bit key is used as input to the algorithm. The bits of the key are numbered from 1 through 64; every eighth bit is ignored, as indicated by the lack of shading in Table 3.4a. The key is first subjected to a permutation governed by a table labeled Permuted Choice One (Table 3.4b). The resulting 56-bit key is then treated as two 28-bit quantities, labeled C0 and D0. At each round, Ci-1 and Di-1 are separately subjected to a circular left shift, or rotation, of 1 or 2 bits, as governed by Table 3.4d. These shifted values serve as input to the next round. They also serve as input to Permuted Choice Two (Table 3.4c), which produces a 48-bit output that serves as input to the function F(Ri-1, Ki).


[Page 80]

Table 3.4. DES Key Schedule Calculation

(a) Input Key

 

1

 

2

 

3

 

4

 

5

 

6

 

7

 

8

 
 

9

 

10

 

11

 

12

 

13

 

14

 

15

 

16

 
 

17

 

18

 

19

 

20

 

21

 

22

 

23

 

24

 
 

25

 

26

 

27

 

28

 

29

 

30

 

31

 

32

 
 

33

 

34

 

35

 

36

 

37

 

38

 

39

 

40

 
 

41

 

42

 

43

 

44

 

45

 

46

 

47

 

48

 
 

49

 

50

 

51

 

52

 

53

 

54

 

55

 

56

 
 

57

 

58

 

59

 

60

 

61

 

62

 

63

 

64

 

(b) Permuted Choice One (PC-1)

  

57

 

49

 

41

 

33

 

25

 

17

 

9

  
  

1

 

58

 

50

 

42

 

34

 

26

 

18

  
  

10

 

2

 

59

 

51

 

43

 

35

 

27

  
  

19

 

11

 

3

 

60

 

52

 

44

 

36

  
  

63

 

55

 

47

 

39

 

31

 

23

 

15

  
  

7

 

62

 

54

 

46

 

38

 

30

 

22

  
  

14

 

6

 

61

 

53

 

45

 

37

 

29

  
  

21

 

13

 

5

 

28

 

20

 

12

 

4

  

(c) Permuted Choice Two (PC-2)

 

14

 

17

 

11

 

24

 

1

 

5

 

3

 

28

 
 

15

 

6

 

21

 

10

 

23

 

19

 

12

 

4

 
 

26

 

8

 

16

 

7

 

27

 

20

 

13

 

2

 
 

41

 

52

 

31

 

37

 

47

 

55

 

30

 

40

 
 

51

 

45

 

33

 

48

 

44

 

49

 

39

 

56

 
 

34

 

53

 

46

 

42

 

50

 

36

 

29

 

32

 

(d) Schedule of Left Shifts

Round number

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Bits rotated

1

1

2

2

2

2

2

2

1

2

2

2

2

2

2

1


DES Decryption

As with any Feistel cipher, decryption uses the same algorithm as encryption, except that the application of the subkeys is reversed.

The Avalanche Effect

A desirable property of any encryption algorithm is that a small change in either the plaintext or the key should produce a significant change in the ciphertext. In particular, a change in one bit of the plaintext or one bit of the key should produce a change in many bits of the ciphertext. If the change were small, this might provide a way to reduce the size of the plaintext or key space to be searched.


[Page 81]

DES exhibits a strong avalanche effect. Table 3.5 shows some results taken from [KONH81]. In Table 3.5a, two plaintexts that differ by one bit were used:

00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

with the key

0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010

Table 3.5. Avalanche Effect in DES

(a) Change in Plaintext

(b) Change in Key

Round

Number of bits that differ

Round

Number of bits that differ

0

1

0

0

1

6

1

2

2

21

2

14

3

35

3

28

4

39

4

32

5

34

5

30

6

32

6

32

7

31

7

35

8

29

8

34

9

42

9

40

10

44

10

38

11

32

11

31

12

30

12

33

13

30

13

28

14

26

14

26

15

29

15

34

16

34

16

35


The Table 3.5a shows that after just three rounds, 21 bits differ between the two blocks. On completion, the two ciphertexts differ in 34 bit positions.

Table 3.5b shows a similar test in which a single plaintext is input:

01101000 10000101 00101111 01111010 00010011 01110110 11101011 10100100

with two keys that differ in only one bit position:

1110010 1111011 1101111 0011000 0011101 0000100 0110001 11011100

0110010 1111011 1101111 0011000 0011101 0000100 0110001 11011100

Again, the results show that about half of the bits in the ciphertext differ and that the avalanche effect is pronounced after just a few rounds.




Cryptography and Network Security Principles and Practices
Cryptography and Network Security (4th Edition)
ISBN: 0131873164
EAN: 2147483647
Year: 2005
Pages: 209

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net