Block Ciphers and the Data Encryption Standard

Chapter 3

BLOCK CIPHERS AND THE DATA  ENCRYPTION STANDARD

3.1                         Block Cipher Principles

Stream Ciphers and Block Ciphers

Motivation for the Feistel Cipher Structure

The Feistel Cipher

3.2                         The Data Encryption Standard

DES Encryption

DES Decryption

3.3                         A Des Example

Results

The Avalanche Effect

3.4                         The Strength of Des

The Use of 56-Bit Keys

The Nature of the DES Algorithm

Timing Attacks

3.5                         Differential and Linear Cryptanalysis

Differential Cryptanalysis

Linear Cryptanalysis

3.6                         Block Cipher Design Principles

DES Design Criteria

Number of Rounds

Design of Function F

Key Schedule Algorithm

All the afternoon Mungo had been working on Stern’s code, principally with the aid of the latest messages which he had copied down at the Nevin Square drop. Stern was very confident. He must be well aware London Central knew about that drop. It was obvious that they didn’t care how often Mungo read their messages, so confident were they in the impenetrability of the code.

—Talking to Strange Men, Ruth Rendell

KEY POINTS

◆              A block cipher is an encryption/decryption scheme in which a block of plaintext is treated as a whole and used to produce a ciphertext block of equal length.

◆              Many block ciphers have a Feistel structure. Such a structure consists of a number of identical rounds of processing. In each round, a substitution is performed on one half of the data being processed, followed by a permu-tation that interchanges the two halves. The original key is expanded so that a different key is used for each round.

◆              The Data Encryption Standard (DES) has been the most widely used encryption algorithm until recently. It exhibits the classic Feistel structure. DES uses a 64-bit block and a 56-bit key.

◆              Two important methods of cryptanalysis are differential cryptanalysis and linear cryptanalysis. DES has been shown to be highly resistant to these two types of attack.

The objective of this chapter is to illustrate the principles of modern symmetric ciphers. For this purpose, we focus on the most widely used symmetric cipher: the Data Encryption Standard (DES). Although numerous symmetric ciphers have been developed since the introduction of DES, and although it is destined to be replaced by the Advanced Encryption Standard (AES), DES remains the most important such algorithm. Furthermore, a detailed study of DES provides an understanding of the principles used in other symmetric ciphers.

This chapter begins with a discussion of the general principles of symmetric block ciphers, which are the type of symmetric ciphers studied in this book (with the exception of the stream cipher RC4 in Chapter 7). Next, we cover full DES. Following this look at a specific algorithm, we return to a more general discussion of block cipher design.

Compared to public-key ciphers, such as RSA, the structure of DES and most symmetric ciphers is very complex and cannot be explained as easily as RSA and simi-lar algorithms. Accordingly, the reader may wish to begin with a simplified version of DES, which is described in Appendix G. This version allows the reader to perform encryption and decryption by hand and gain a good understanding of the working of the algorithm details. Classroom experience indicates that a study of this simplified version enhances understanding of DES.