While many ciphers have been created based upon the Feistel structure, the most famous of these is the Data Encryption Standard (DES). DES was based off of the original Lucifer cipher developed by Feistel and Coppersmith and submitted as an entry to the US National Bureau of Standards as a candidate for the US official encryption standard. After some modification (to improve security against differential cryptanalysis), it was selected and published as a standard in 1977.

Encryption with DES

The DES algorithm is a 16-round Feistel cipher. It takes as input a 64-bit input and a 64-bit secret key, and consists of three main stages:

• The initial permutation
• The round function (repeated 16 times)
• The final permutation

A diagram of how these stages fit together with the key schedule is shown below.

Diagram of DES encryption with the three main stages (initial permutation, round function and final permutation) along with the key schedule

Of these, the initial permutation, final permutation, and permuted choice 1 algorithms are all permutation operations. That is, they simply output the input they received after applying a specific permutation.

The DES round function

The most interesting part is the DES round function. Each round of DES takes a 64-bit input (two 32-bit half-blocks) and a 56-bit secret key.

As in any Feistel cipher, the DES round function swaps the left and right side of the inputs, and applies the F function during one of the swaps. That is,

• L_i+1 = R_i
• R_i+1 = L_i ^ F(R_i)

For the particular case of DES, the F function consists of several steps:

1. The input half-block is expanded using an expansion function E
2. The expanded input is exclusive-ored with the round key
3. The result is broken into 8 6-bit pieces and each is passed through a unique substitution box or S-Box
4. The results pass through a permutation function P

The E function, S-Boxes, and P function are described in more detail as follows in the following sections. A diagram of the round function and a round of the key schedule is shown below.

One round of the DES: Round function and a round of the key schedule

The DES Key Schedule

The key schedule of DES consists of two main stages: the initial key permutation using the Permuted Choice 1 algorithm and the generation of the round keys using a shift operation and the Permuted Choice 2 algorithm. Each of these are described in more detail in the following sections.

Detailed description of encryption steps with examples

In this section we will describe the steps of encryption. This includes the initial permutation, E function, exclusive-or, S-Boxes, P function and final permutation. Of these, the E function, exclusive-or, S-Boxes and P function are part of each round, whereas the initial permutation is used only once at the beginning and the final permutation is used only once at the end.

The Initial Permutation

The initial permutation of the DES algorithm changes the order of the plaintext prior to the first round of encryption. The structure of the initial permutation is shown in the Table below.

As shown in the table, the initial permutation makes no attempt to randomize the data. The bits at odd positions in the plaintext fill out the last four output blocks (rows in the table) by filling the last bit of all in order, followed by the second-to-last bit and so on. The first four blocks are filled out using an identical scheme with the bits in the even positions within the plaintext.

As an example, let’s apply the initial permutation to the following plaintext: 00010000 10110111 01100111 11000011 10010101 10111000 01000100 00001011. The initial permutation goes as follows.

In: 00010000 10110111 01100111 11000011 10010101 10111000 01000100 00001011
P[58]=0, P[50]=1, P[42]=0, P[34]=0, P[26]=1, P[18]=1, P[10]=0, P[2]=0
P[60]=0, P[52]=0, P[44]=1, P[36]=1, P[28]=0, P[20]=0, P[12]=1, P[4]=1
P[62]=0, P[54]=1, P[46]=0, P[38]=1, P[30]=0, P[22]=1, P[14]=1, P[6]=0
P[64]=1, P[56]=0, P[48]=0, P[40]=1, P[32]=1, P[24]=1, P[16]=1, P[8]=0
P[57]=0, P[49]=0, P[41]=1, P[33]=1, P[25]=1, P[17]=0, P[ 9]=1, P[1]=0
P[59]=0, P[51]=0, P[43]=1, P[35]=0, P[27]=0, P[19]=1, P[11]=1, P[3]=0
P[61]=1, P[53]=0, P[45]=1, P[37]=0, P[29]=0, P[21]=0, P[13]=0, P[5]=0
P[63]=1, P[55]=0, P[47]=0, P[39]=0, P[31]=1, P[23]=1, P[15]=1, P[7]=0
Out: 01001100 00110011 01010110 10011110 00111010 00100110 10100000 10001110

After the initial permutation, we the round functions begin, consisting of E function, exclusive-or, S-boxes and P function.

The E Function (in round function)

The E function is used to expand the 32-bit input to a round’s F function into a 48-bit block. The E function is fairly straightforward and is implemented as shown in the Table below.

As shown in the Table, the first two bits of each eight-bit block are the same as the last two bits of the previous block (wrapping around to the last block in the case of the first row). The remaining 4 columns are the bits of the input in order starting with the second bit.

As an example, let’s expand the 32-bit string: 11010100 00000100 11010100 11110011. For the purposes of this example, we’ll break the steps into two parts: the left two columns repeated from the previous round and the right four columns which are unique. The symbol ’:’ is used to represent a range that is inclusive and wraps around, i.e. 30:2 is (30, 31, 1, 2).

In: 11010100 00000100 11010100 11110011 
Left        Right
P[32: 1]=11 P[ 2: 5]=1010
P[ 4: 5]=10 P[ 6: 9]=1000
P[ 8: 9]=00 P[10:13]=0000
P[12:13]=00 P[14:17]=1001
P[16:17]=01 P[18:21]=1010
P[20:21]=10 P[22:25]=1001
P[24:25]=01 P[26:29]=1110
P[28:29]=10 P[30: 1]=0111
Out: 111010 101000 000000 001001 011010 101001 011110 100111

Exclusive-or (in round function)

The 48-bit output from the E function is exclusive-or’ed with the 48-bit round key.

The DES S-Boxes (in round function)

For the S-Box stage of encryption, the input (output of exclusive-or) is broken into eight six-bit blocks (the rows in the Table in the previous section). Each of these blocks passes through a different Substitution Box or S-Box. An example of the first S-Box is shown in the table below.

To use the S-Box, the row and column are selected using the outer two and inner four bits of the binary representation of the input using the format shown in the Table. For example, an input of 101100 would use the third row (the outer two bits of 101100 are 10, which is 2 and we start counting at zero) and the seventh column (the inner four bits of 101100 are 0110, which is 6 and we start counting at zero). Therefore, the output of the first S-Box for an input of 101100 is 2. Since the S-Box downsizes the input from 6-bits to 4-bits (half-block inputs to rounds are thirty-two bits and we have eight S-Boxes), this is represented as 0010.

As an example, let’s use the output of the previous expansion example: 111010 101000 000000 001001 011010 101001 011110 100111. For this example, we’ll use the same S-Box for all of the input values but in actuality, each value would pass through a different S-Box. In the example, S(A,B) refers to the cell at the intersection of row A and column B in the S-Box Table.

In: 111010 101000 000000 001001 011010 101001 011110 100111
111010: S(10,1101)= 10= 1010
101000: S(10,0100)= 13= 1101
000000: S(00,0000)= 14= 1110
001001: S(01,0100)= 14= 1110
011010: S(00,1101)=  9= 1001
101001: S(11,0100)=  4= 0100
011110: S(00,1111)=  7= 0111
100111: S(11,0011)=  2= 0010
Out: 10101101 11101110 10010100 01110010

The P Function (in round function)

The P function in DES is another permutation function. It takes a thrity-two bit block as input and outputs a thirty-two bit block. The permutation is shown in the Table below.

As shown, the permutation for the P function is not as structured as other permutation functions in DES. However, the permutation is not random and is the same for all rounds of DES.

As an example, we’ll use the S-Box output from our example in the previous section: 10101101 11101110 10010100 01110010.

In: 10101101 11101110 10010100 01110010
P[16]=0, P[ 7]=0, P[20]=1, P[21]=0, P[29]=0, P[12]=0, P[28]=1, P[17]=1
P[ 1]=1, P[15]=1, P[23]=0, P[26]=1, P[ 5]=1, P[18]=0, P[31]=1, P[10]=1
P[ 2]=0, P[ 8]=1, P[24]=0, P[14]=1, P[32]=0, P[27]=1, P[ 3]=1, P[ 9]=1
P[19]=0, P[13]=1, P[30]=0, P[ 6]=1, P[22]=1, P[11]=1, P[ 4]=0, P[25]=0
Out: 00100011 11011011 01010111 01011100

The P function is the last step of the round function.

The Final Permutation

The final permutation occurs after the sixteen rounds of DES are completed. It is the inverse of the initial permutation and is shown in the Table below.

As an example, let’s undo the initial permutation. Its output was 01001100 00110011 01010110 10011110 00111010 00100110 10100000 10001110. The Final Permutation is applied as follows:

In: 01001100 00110011 01010110 10011110 00111010 00100110 10100000 10001110
P[40]=0, P[8]=0, P[48]=0, P[16]=1, P[56]=0, P[24]=0, P[64]=0, P[32]=0 
P[39]=1, P[7]=0, P[47]=1, P[15]=1, P[55]=0, P[23]=1, P[63]=1, P[31]=1
P[38]=0, P[6]=1, P[46]=1, P[14]=0, P[54]=0, P[22]=1, P[62]=1, P[30]=1
P[37]=1, P[5]=1, P[45]=0, P[13]=0, P[53]=0, P[21]=0, P[61]=1, P[29]=1
P[36]=1, P[4]=0, P[44]=0, P[12]=1, P[52]=0, P[20]=1, P[60]=0, P[28]=1
P[35]=1, P[3]=0, P[43]=1, P[11]=1, P[51]=1, P[19]=0, P[59]=0, P[27]=0
P[34]=0, P[2]=1, P[42]=0, P[10]=0, P[50]=0, P[18]=1, P[58]=0, P[26]=0
P[33]=0, P[1]=0, P[41]=0, P[ 9]=0, P[49]=1, P[17]=0, P[57]=1, P[25]=1
Out: 00010000 10110111 01100111 11000011 10010101 10111000 01000100 00001011

Looking back to the original input of the Initial Permutation function, we see that the output of the Final Permutation is identical. The Final permutation simply undoes the Initial Permutation.

Detailed description of key scheduling steps with examples

In this section we will describe the steps of the key schedule. This includes the Permuted Choice 1, the shift operation and Permuted Choice 2 steps. Of these, PC1 is only applied once initially, whereas the shift operation and PC2 are applied in each round.

Permuted Choice 1

The Permuted Choice 1 algorithm performs two functions in DES. Throughout this discussion, we’ve said that DES uses a 56-bit key, but technically it takes a 64-bit key as input. The eighth bit of each of the 8 8-bit blocks of the key is specified as a parity bit and the first purpose of Permuted Choice 1 is to drop these bits. The second purpose is to permute the key prior to key expansion. The Permuted Choice 1 algorithm is shown in the below Table.

As an example, we’ll execute the PC-1 algorithm on the following 64-bit key: 11010000 00100111 11000100 11111000 10101000 10101101 11011110 10111001.

In: 11010000 00100111 11000100 11111000 10101000 10101101 11011110 10111001 
K[57]=1, K[49]=1, K[41]=1, K[33]=1, K[25]=1, K[17]=1, K[ 9]=0,
K[63]=0, K[55]=1, K[47]=0, K[39]=0, K[31]=0, K[23]=0, K[15]=1
K[ 1]=1, K[58]=0, K[50]=1, K[42]=0, K[34]=0, K[26]=1, K[18]=1,
K[ 7]=0, K[62]=0, K[54]=1, K[46]=1, K[38]=0, K[30]=0, K[22]=1
K[10]=0, K[ 2]=1, K[59]=1, K[51]=0, K[43]=1, K[35]=1, K[27]=1,
K[14]=1, K[ 6]=0, K[61]=1, K[53]=1, K[45]=1, K[37]=1, K[29]=1
K[19]=0, K[11]=1, K[ 3]=0, K[60]=1, K[52]=1, K[44]=0, K[36]=0,
K[21]=0, K[13]=0, K[ 5]=0, K[28]=1, K[20]=0, K[12]=0, K[ 4]=1
Out: 1111110 0100001 1010011 0011001 0110111 1011111 0101100 0001001

After the PC-1 algorithm is completed, generation of DES’s round keys begins. For this, the key is split into two 28-bit subkeys (the left seven and right seven columns of the Table above) and remain split for the rest of the key schedule.

Shift operation

For each round, both subkeys are shifted to the left by a set amount. These shifts are cumulative and the shift amount for each round is shown in the Table below.

Permuted Choice 2

After the shift occurs, the round key is generated using the Permuted Choice 2 (PC-2) algorithm. This algorithm is shown in the Table below.

The PC-2 algorithm takes a 56-bit subkey as input and produces a 48-bit round key. Each bit of the initial 56-bit key is used in an average of 14 of 16 round keys.

As an example, we’ll use the output of the PC-1 algorithm as input: 1111110 0100001 1010011 0011001 0110111 1011111 0101100 0001001.

In: 1111110 0100001 1010011 0011001 0110111 1011111 0101100 0001001
K[14]=1, K[17]=1, K[11]=0, K[24]=1, K[ 1]=1, K[ 5]=1
K[ 3]=1, K[28]=1, K[15]=1, K[ 6]=1, K[21]=1, K[10]=0
K[23]=0, K[19]=0, K[12]=0, K[ 4]=1, K[26]=0, K[ 8]=0
K[16]=0, K[ 7]=0, K[27]=0, K[20]=1, K[13]=0, K[ 2]=1
K[41]=1, K[52]=0, K[31]=1, K[37]=0, K[47]=1, K[55]=0
K[30]=1, K[40]=1, K[51]=0, K[45]=0, K[33]=1, K[48]=0
K[44]=1, K[49]=0, K[39]=1, K[56]=1, K[34]=1, K[53]=1
K[46]=1, K[42]=1, K[50]=0, K[36]=1, K[29]=0, K[32]=0
Out: 110111 111110 000100 000101 101010 110010 101111 110100

Decryption with DES

Like all other Feistel ciphers, the process for decryption in DES follows the exact same steps as encryption, apart from the fact that the round keys need to be used in reverse order.

3DES: Triple DES

The DES algorithm is not currently in use in its original form due to the small size of its secret key. In 1999, it was demonstrated that DES could be broken using a brute force search of all possible keys in less than a day. A variant of DES called 3DES (pronounced “Triple DEZ”) is still in use where a DES is run three times in sequence using distinct keys (which triples the size of the secret key to be shared).

Advantages

DES is broken; however, 3DES is currently considered a secure cipher. DES does have the desirable properties of confusion and diffusion: each bit of ciphertext is based upon multiple bits of the key and changing a single bit of plaintext changes, on average, half of the bits of ciphertext.

Due to its Feistel structure and uncomplicated logic, DES is relatively easy to implement. However, it uses eight distinct S-Boxes, which increases its footprint (AES uses a single S-Box).

Disadvantages

The main disadvantage to DES is that it is broken using brute-force search. However, using 3DES mitigates this issue at the cost of increasing execution time.

DES is also vulnerable to attacks using linear cryptanalysis. However, it takes 2⁴⁷ known plaintexts to break DES in this manner.