Data Encryption Standards

Data Encryption Standards: DES and Triple DES (Part II)

In Module 2 SLP, we continue to cover DES.

Step 2: Encode each 64-bit block of data.

There is an initial permutation IP of the 64 bits of the message data M. This rearranges the bits according to the following table, where the entries in the table show the new arrangement of the bits from their initial order. The 58th bit of M becomes the first bit of IP. The 50th bit of M becomes the second bit of IP. The 7th bit of M is the last bit of IP.

                             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

Example: Applying the initial permutation to the block of text M, given previously, we get

M = 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
IP = 1100 1100 0000 0000 1100 1100 1111 11111111 0000 1010 1010 1111 0000 1010 1010

Here the 58th bit of M is "1", which becomes the first bit of IP. The 50th bit of M is "1", which becomes the second bit of IP. The 7th bit of M is "0", which becomes the last bit of IP.

Next divide the permuted block IP into a left half L₀ of 32 bits, and a right half R₀ of 32 bits.

Example: From IP, we get L₀ and R₀

L₀ = 1100 1100 0000 0000 1100 1100 1111 1111 
R₀ = 1111 0000 1010 1010 1111 0000 1010 1010

We now proceed through 16 iterations, for 1<=n<=16, using a function f which operates on two blocks -- a data block of 32 bits and a key K_n of 48 bits -- to produce a block of 32 bits. Let + denote XOR addition, (bit-by-bit addition modulo 2). Then for n going from 1 to 16 we calculate

L_n = R_n-1 
R_n = L_n-1 + f(R_n-1,K_n)

This results in a final block for n = 16, of L₁₆R₁₆. That is, in each iteration, we take the right 32 bits of the previous result and make them the left 32 bits of the current step. For the right 32 bits in the current step, we XOR the left 32 bits of the previous step with the calculation f .

Example: For n = 1, we have

K₁ = 000110 110000 001011 101111 111111 000111 000001 110010 
L₁ = R₀ = 1111 0000 1010 1010 1111 0000 1010 1010 
R₁ = L₀ + f(R₀,K₁)

It remains to explain how the function f works. To calculate f, we first expand each block R_n-1 from 32 bits to 48 bits. This is done by using a selection table that repeats some of the bits in R_n-1 . We'll call the use of this selection table the function E. Thus E(R_n-1) has a 32-bit input block, and a 48-bit output block.

Let E be such that the 48 bits of its output, written as 8 blocks of 6 bits each, are obtained by selecting the bits in its inputs in order according to the following table:

                    E BIT-SELECTION TABLE

 

                 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

Thus the first three bits of E(R_n-1) are the bits in positions 32, 1, and 2 of R_n-1 while the last 2 bits of E(R_n-1) are the bits in positions 32 and 1.

Example: We calculate E(R₀) from R₀ as follows:

R₀ = 1111 0000 1010 1010 1111 0000 1010 1010 
E(R₀) = 011110 100001 010101 010101 011110 100001 010101 010101

(Note that each block of 4 original bits has been expanded to a block of 6 output bits.)

Next in the f calculation, we XOR the output E(R_n-1) with the key K_n:

K_n + E(R_n-1).

Example: For K₁ , E(R₀), we have

K₁ = 000110 110000 001011 101111 111111 000111 000001 110010 
E(R₀) = 011110 100001 010101 010101 011110 100001 010101 010101 
K₁+E(R₀) = 011000 010001 011110 111010 100001 100110 010100 100111.

We have not yet finished calculating the function f . To this point we have expanded R_n-1 from 32 bits to 48 bits, using the selection table, and XORed the result with the key K_n . We now have 48 bits, or eight groups of six bits. We now do something strange with each group of six bits: we use them as addresses in tables called "S boxes". Each group of six bits will give us an address in a different S box. Located at that address will be a 4 bit number. This 4 bit number will replace the original 6 bits. The net result is that the eight groups of 6 bits are transformed into eight groups of 4 bits (the 4-bit outputs from the S boxes) for 32 bits total.

Write the previous result, which is 48 bits, in the form:

K_n + E(R_n-1) =B₁B₂B₃B₄B₅B₆B₇B₈,

where each B_i is a group of six bits. We now calculate

S₁(B₁)S₂(B₂)S₃(B₃)S₄(B₄)S₅(B₅)S₆(B₆)S₇(B₇)S₈(B₈)

where S_i(B_i) refers to the output of the i-th S box.

To repeat, each of the functions S1, S2,..., S8, takes a 6-bit block as input and yields a 4-bit block as output. The table to determine S₁ is shown and explained below:

 

                             S1

 

                        Column Number

Row

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

 

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

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

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

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

If S₁ is the function defined in this table and B is a block of 6 bits, then S₁(B) is determined as follows: The first and last bits of B represent in base 2 a number in the decimal range 0 to 3 (or binary 00 to 11). Let that number be i. The middle 4 bits of B represent in base 2 a number in the decimal range 0 to 15 (binary 0000 to 1111). Let that number be j. Look up in the table the number in the i-th row and j-th column. It is a number in the range 0 to 15 and is uniquely represented by a 4 bit block. That block is the output S₁(B) of S₁ for the input B. For example, for input block B = 011011 the first bit is "0" and the last bit "1" giving 01 as the row. This is row 1. The middle four bits are "1101". This is the binary equivalent of decimal 13, so the column is column number 13. In row 1, column 13 appears 5. This determines the output; 5 is binary 0101, so that the output is 0101. Hence S₁(011011) = 0101.

The tables defining the functions S₁,...,S₈ are the following:

                             S1

 

     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

 

                             S2

 

     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

 

                             S3

 

     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

 

                             S4

 

      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

 

                             S5

 

      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

 

                             S6

 

     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

 

                             S7

 

      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

 

                             S8

 

     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

Example: For the first round, we obtain as the output of the eight S boxes:

K₁ + E(R₀) = 011000 010001 011110 111010 100001 100110 010100 100111.

S₁(B₁)S₂(B₂)S₃(B₃)S₄(B₄)S₅(B₅)S₆(B₆)S₇(B₇)S₈(B₈) = 0101 1100 1000 0010 1011 0101 1001 0111

The final stage in the calculation of f is to do a permutation P of the S-box output to obtain the final value of f:

f = P(S₁(B₁)S₂(B₂)...S₈(B₈))

The permutation P is defined in the following table. P yields a 32-bit output from a 32-bit input by permuting the bits of the input block.

                                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

Example: From the output of the eight S boxes:

S₁(B₁)S₂(B₂)S₃(B₃)S₄(B₄)S₅(B₅)S₆(B₆)S₇(B₇)S₈(B₈) = 0101 1100 1000 0010 1011 0101 1001 0111

we get

f = 0010 0011 0100 1010 1010 1001 1011 1011

R₁ = L₀ + f(R₀ , K₁ )

= 1100 1100 0000 0000 1100 1100 1111 1111 
+ 0010 0011 0100 1010 1010 1001 1011 1011 
= 1110 1111 0100 1010 0110 0101 0100 0100

In the next round, we will have L₂ = R₁, which is the block we just calculated, and then we must calculate R₂ =L₁ + f(R₁, K₂), and so on for 16 rounds. At the end of the sixteenth round we have the blocks L₁₆ and R₁₆. We then reverse the order of the two blocks into the 64-bit block

R₁₆L₁₆

and apply a final permutation IP^-1 as defined by the following table:

                             IP^-1

 

            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

That is, the output of the algorithm has bit 40 of the preoutput block as its first bit, bit 8 as its second bit, and so on, until bit 25 of the preoutput block is the last bit of the output.

Example: If we process all 16 blocks using the method defined previously, we get, on the 16th round,

L₁₆ = 0100 0011 0100 0010 0011 0010 0011 0100 
R₁₆ = 0000 1010 0100 1100 1101 1001 1001 0101

We reverse the order of these two blocks and apply the final permutation to

R₁₆L₁₆ = 00001010 01001100 11011001 10010101 01000011 01000010 00110010 00110100

IP^-1 = 10000101 11101000 00010011 01010100 00001111 00001010 10110100 00000101

which in hexadecimal format is

85E813540F0AB405.

This is the encrypted form of M = 0123456789ABCDEF: namely, C = 85E813540F0AB405.

Decryption is simply the inverse of encryption, following the same steps as above, but reversing the order in which the subkeys are applied.

Triple-DES

Triple-DES is just DES with two 56-bit keys applied. Given a plaintext message, the first key is used to DES- encrypt the message. The second key is used to DES-decrypt the encrypted message. (Since the second key is not the right key, this decryption just scrambles the data further.) The twice-scrambled message is then encrypted again with the first key to yield the final ciphertext. This three-step procedure is called triple-DES.

Triple-DES is just DES done three times with two keys used in a particular order. (Triple-DES can also be done with three separate keys instead of only two. In either case the resultant key space is about 2^112.)

The Strength of DES

Since its adoption as a federal standard, there have been lingering concerns about the level of security provided by DES. These concerns, by and large, fall into two areas: key size and the nature of the algorithm.

The Use of 56-Bit Keys

With a key length of 56 bits, there are 256 possible keys, which is approximately 7.2 * 1016 keys. Thus, on the face of it, a brute-force attack appears impractical. Assuming that, on average, half the key space has to be searched, a single machine performing one DES encryption per microsecond would take more than a thousand years to break the cipher.

However, the assumption of one encryption per microsecond is overly conservative. As far back as 1977, Diffie and Hellman postulated that the technology existed to build a parallel machine with 1 million encryption devices, each of which could perform one encryption per microsecond. This would bring the average search time down to about 10 hours. The authors estimated that the cost would be about $20 million in 1977 dollars.

With current technology, it is not even necessary to use special, purpose-built hardware. Rather, the speed of commercial, off-the-shelf processors threaten the security of DES.

To learn more about DES, check the following sites:

1. DES – the algorithm
   https://www.youtube.com/watch?v=3BZRBfhpIb0
2. Simplified DES examples
   https://www.youtube.com/watch?v=qHZKze24kVo
3. Data Encryption Standard
   https://www.youtube.com/watch?v=kPBJIhpcZgE
4. Data Encryption Standard
   https://www.youtube.com/watch?v=kg4pWTqVfeU
5. Data Encryption Standard (DES)
   https://www.lri.fr/~fmartignon/documenti/systemesecurite/4-DES.pdf
6. DES
   https://www.youtube.com/watch?v=eCAHcfA-2c8
7. Block Ciphers and Data Encryption Standard (DES)
   https://engineering.purdue.edu/kak/compsec/NewLectures/Lecture3.pdf

SLP Assignment

This problem provides a numerical example of encryption using a one-round version of DES. We start with the same bit pattern for the key K and the plaintext (the key and the plaintext are the same), namely:

The plaintext and key is:

     0000 0001 0010 0011 0100 0101 0110 0111

     1000 1001 1010 1011 1100 1101 1110 1111

1. Derive L₀ and R_0. Show step-by-step how you derive L₀ and R₀ (HINT: follow the Step 2: Encode each 64-bit block of data).

SLP Assignment Expectations

Use information from the modular background readings as well as the given resources. Also, you could use any good quality resource you can find. Please cite all sources and provide a reference list at the end of your paper.

The following items will be assessed in particular:

1. Your ability to consolidate ideas from reading materials and your understanding of the materials.
2. Your ability to write a report with strong argument.
3. Some in-text references to modular background readings.