Section 6.4 Data Encryption Standard
This section is a brief introduction to some of the ideas used in more modern block ciphers. We will present an overview of the ideas of the Data Encryption Standard (DES). DES was developed in the 1970s at IBM and endorsed by the National Bureau of Standards (now called the National Institute of Standards and Technology) as a national standard in 1977. Bruce Schneier in his Schneier on Security blog writes that “For over two decades, DES was the workhorse of commercial cryptography.” For security reasons, it was updated to Triple DES in 1999, and eventually superseded by a new algorithm called AES (Advanced Encryption Standard) in 2001. AES would require an excursion into polynomials over finite fields, and that is more than we have time for in this course, so we will just broadly discuss some of the important building blocks of DES.
DES encrypts plaintext blocks of 64 bits. It is used with a key of 64 bits where 56 bits are independent key bits and every eighth bit is a parity check bit. There are 16 rounds of permutations and S-boxes in which the goal is to combine the 64 bits of key with the 64 bits of plaintext so thoroughly that it is impossible to separate message and key without knowing the key. The algorithm was designed for both maximum security and speed of implementation.
Example 6.4.1.
A permutation box is an \(n \times k\) matrix. These are also called permutation tables or just permutations, but we will use the permutation box terminology. The entries of the matrix specify how to permute the bits of the input. The permutation box
acts on 6 bits of input. Suppose the input is \(M=101101\text{.}\) Then to apply \(P[M]\) we permute the bits of \(M\) according to the permutation box, reading from left to right and from first row to second row, so \(P[M]=\)2nd bit of M, 5th bit of M, 6th bit of M, 3rd bit of M, 1st bit of M, and 4th bit of M. For this permutation box, \(P[ 101101 ] = 001111\text{.}\)
A permutation box could shrink the input to fewer bits. For example, for the permutation box
we have \(P_2[101101] = 0011\text{.}\)
A permutation box can also enlarge the input to more bits. For example, for the permutation box
we have \(P_2[101101] =01101101\text{.}\)
Investigation Time!
Time for you to investigate permutation boxes and S-boxes in Investigation: Permutation and S-boxes.
Example 6.4.2.
To see an example of an \(S\)-box in action, consider the first DES \(S\)-box.
| 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 |
To apply the \(S\)-box to a six bit input, we use the first and last bit to determine the row of the \(S\)-box, and the middle four bits to determine the column. We combine the first and last bit to form a two bit number. These numbers range from 0 to 3 and we associate them to the rows in that order. That is, 0=00 corresponds to the first row and 3=11 corresponds to the last row. We interpret the middle four bits as a four bit number. These numbers range from 0 to 15 and we associate them to the columns in that order, again starting with 0. We find the number in the given row and column and convert that to binary to give the output for the \(S\)-box.
To apply the \(S\)-box to the six bit input \(M=110110\text{,}\) we would find the number in row 10=2 and column 1011=11, so we get the output 7. Converting 7 to binary we have 0111.
If we consider input 100110 we get row 10=2 and column 0011=3. This gives us output 8=0100. Note that one bit change in the input produced a two bit change in the output.
In general, \(S\)-boxes are constructed so that a change in one bit of the input results in changes in at least two different bits in the output. They are also constructed to maximize speed and performance based on chip size.
Step One. The message is permuted with an initial 64-bit permutation box to produce 64 bits of output. This output is split into the left hand 32 bits and the right hand 32 bits. Thus, the output is \(IP(M)=(L_0, R_0)\text{.}\)
-
Step Two. There are 16 rounds of applying permutation and \(S\) boxes to combinations of the message and key. Each round uses a different 48 bits of the key. For each of 16 rounds:
- Compute \(A=P_E(R_i)\text{.}\) The right side is permuted and expanded to 48 bits.
- Compute \(B=K_i= P_{S_i}(K)\text{.}\) The key is permuted and shrunk to 48 bits. The permutation box is different for each round, so a different 48 bits of key is used in each round.
- Compute \(C=A \oplus B\text{.}\) The \(\oplus\) represents the xor operation. The output \(C\) is 48 bits.
- Compute \(D=S(C) \) where \(S\) represents 8 different \(S\)-boxes. Each \(S\)-box acts on a 6 bit block and reduces it to a 4 bit output. The output \(D\) is 32 bits.
- Compute \(E=P(D)\) where \(P\) is a permutation box where the input and output are both 32 bits.
- Compute \(F=E \oplus L_i\text{.}\) Note that all of the previous operations have only acted on \(R_i\text{,}\) so this piece now involves \(L_i\text{.}\)
- Lastly, set \(L_{i+1} = R_i\) and \(R_{i+1}=F\) and repeat.
Step 3: The inverse permutation box from step 1 is applied. The main purpose here is to make decoding more similar to encoding. Steps 1 and 3 are the same for both encoding and decoding, but step 2 must be done in reverse. This now gives us the ciphertext! \(CT = IP^{-1}(R_{16},L_{16})\text{.}\) Note, that the left and right sides are swapped.
This may seem slow and tedious by hand (and it is!), but it can be computed very efficiently by computers. There are important considerations for how to choose the permutations and the S-boxes so that the algorithm is secure. See Coppersmith's article ([6.4.1]) for details.