Link to video on youtube

Accompanying Lecture Notes

Introduction

• DES is a block cipher and as the name suggests it works on blocks of bits or binary numbers--the 0s and the 1s common to digital world. It encrypts group of 64 plaintext bits(one block) and returns 64 ciphertext bits. To do the encryption, DES uses keys which are also 64 bits long. However, every 8th key bit is ignored in the DES algorithm, so that the effective key size is 56 bits.

Block Cipher Primitives

• Confusion : An encryption operation where the relationship between plaintext and ciphertext is obscured. Today, a common element for achieving confusion is substitution, which is found in both AES and DES.

• Diffusion : An encryption operation where the influence of one plaintext symbol is spread over many ciphertext symbols with the goal of hiding statistical properties of the plaintext. A simple diffusion element is the bit permutation, which is frequently used within DES.

Both operations by themselves cannot provide security. The idea is to concatenate confusion and diffusion elements to build a more secure cipher.

Overview of DES Algorithm

Fig 1: Overview of the DES Algorithm

• DES is a Symmetric cipher: uses same key for encryption and decryption
• Uses 16 rounds which all perform the identical operation
• Different subkey(48 bit) in each round derived from main key

Internal structure of DES

1. Initial Permutaion(IP) : This is the first thing that is seen in the expanded view of DES block in Fig 1.

• IP is a bitwise permutation or simple crosswiring in hardware.
• The corsswiring is done according to the table(left) given in Fig 2.
• The IP has no effect on the DES security at all.

Fig 2: Initial Permutation(left) and the Final Permutation(right) tables

2. DES Encryption Round - Feistel Networks

• DES structure is a Feistel network
• Advantage: encryption and decryption differ only in keyschedule( explained later )

Fig 3: Encryption block round 1 - Feistel Networks

• The encryption block for round 1 in Fig 3 takes an input of 64 bit data permuted in the IP
• Plaintext is split into 32-bit halves $ L_i $ and $ R_i $
• $ R_i $ is fed into the function f, the output of which is then XORed with $ L_i $
• Left and right half halves are swapped at the end of one encryption round
• Each encryption round can be expressed as :

$ L_i = R_{i-1} $

$ R_i = L_{i-1} \oplus f(R_{i-1},k_i) $

Fig 4: Encryption block final round - Feistel Networks

• And as seen in Fig 1, we have sixteen such rounds.
• And the Left and Right side bits are swapped again before the Final Permutation(FP) as shown in Fig 4.

3. The f-funtion(inside the feistel network)

Fig 5: The f-function block

• Main operation of DES
• Inputs to f function are $ R_{i-1} $ and round key $ k_i $
• It has 4 main steps in Fig 5 :

 **1. Expansion block E
 **2. XOR with round key
 **3. S-box substitution (eight of them)
 **4. Permutation

3.1 The Expansion fucntion E

• The main purpose of the expansion funtion is to increase diffusion in the input $ R_{i-1} $ bits.
• It is done using the table shown in Fig 6.

Fig 6: The expansion block

3.2 XOR with round key

• Bitwise XOR of the round key $ k_i $ and the output of the expansion function E
• We take a 48-bit expanded message bit and XOR with 48-bit key input and the output data is also 48-bit (Fig 5)

[Round keys are derived from the main key in the DES keyschedule later in the notes]

3.3 The DES S-Box substitution

• Eight substitution tables which form the core security of DES (Refer book)
• Take 6 bits of input and gives 4-bit output
• Non-linear and resistant to differential cryptanalysis

3.4 The Permutation P

• This is the last step in the f-fucntion in Fig 5.
• It is also bitiwse permutation, which introduces diffusion using the table in Fig 7.
• Output bits of one S-Box effect several S-Boxes in next round.
• Diffusion by E, S-Boxes and P guarantees that after Round 5 every bit is a function of each key bit and each plaintext bit.

Fig 7: The Permutation P

References

• C. Paar. Understanding Cryptography. Lecture Notes. Dept. of Electr. Eng. and In­for­ma­ti­on Sci­en­ces, Ruhr University.
• C. Paar and J. Pelzl. Understanding Cryptography. A textbook for Student and Practitioners. Springer 2010.

Questions and comments

If you have any questions, comments, etc. please post them here.

Back to 2015 Summer Paar