Presentation on theme: "Chapter3: Block Ciphers and the Data Encryption Standard"— Presentation transcript:
1 Chapter3: Block Ciphers and the Data Encryption StandardNUIST School of Computer and Software Jian Shen, PhD, Professor
2 Introduction 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 permutation 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. is designed to detect, prevent, or recover from a security attack. Security services include authentication, access control, data confidentiality, data integrity, nonrepudiation, and availability.
3 3.1. Block Cipher PrinciplesStream Ciphers and Block Ciphers A stream cipher is one that encrypts a digital data stream one bit or one byte at a time. Motivation for the Feistel Cipher Structure A block cipher operates on a plaintext block of n bits to produce a ciphertext block of n bits.
4 3.1. Block Cipher PrinciplesFigure 3.1 illustrates the logic of a general substitution cipher for n = 4. A 4-bit input produces one of 16 possible input states, which is mapped by the substitution cipher into a unique one of 16 possible output states, each of which is represented by 4 ciphertext bits.
5 3.1. Block Cipher PrinciplesTable 3.1. This is the most general form of block cipher and can be used to define any reversible mapping between plaintext and ciphertext.
6 3.1. Block Cipher PrinciplesThe Feistel Cipher Threat Feistel proposed
7 3.1. Block Cipher PrinciplesDiffusion and Confusion Assume the attacker has some knowledge of the statistical characteristics of the plaintext. In diffusion, the statistical structure of the plaintext is dissipated into long-range statistics of the ciphertext. This is achieved by having each plaintext digit affect the value of many ciphertext digits; generally this is equivalent to having each ciphertext digit be affected by many plaintext digits.
8 3.1. Block Cipher PrinciplesFeistel Cipher Structure Figure 3.2 depicts the structure proposed by Feistel. The inputs to the encryption algorithm are a plaintext block of length 2w bits and a key K. The plaintext block is divided into two halves, L0 and R0. The two halves of the data pass through n rounds of processing and then combine to produce the ciphertext block. Each round i has as inputs Li-1 and Ri-1, derived from the previous round, as well as a subkey Ki, derived from the overall K. In general, the subkeys Ki are different from K and from each other.
9 3.1. Block Cipher PrinciplesThe exact realization of a Feistel network depends on the choice of the following parameters and design features: Block size: Larger block sizes mean greater security (all other things being equal) but reduced encryption/decryption speed for a given algorithm. Key size: Larger key size means greater security but may decrease encryption/decryption speed. Number of rounds: The essence of the Feistel cipher is that a single round offers inadequate security but that multiple rounds offer increasing security. Subkey generation algorithm: Greater complexity in this algorithm should lead to greater difficulty of cryptanalysis. Round function: Again, greater complexity generally means greater resistance to cryptanalysis.
10 3.1. Block Cipher PrinciplesThere are two other considerations in the design of a Feistel cipher: Fast software encryption/decryption Ease of analysis
11 3.1. Block Cipher PrinciplesFeistel Decryption Algorithm Figure 3.3 shows the encryption process going down the left-hand side and the decryption process going up the right-hand side for a 16-round algorithm.
12 3.2. The Data Encryption StandardFeistel Decryption Algorithm For DES, data are encrypted in 64-bit blocks using a 56-bit key. The algorithm transforms 64-bit input in a series of steps into a 64-bit output. The same steps, with the same key, are used to reverse the encryption. DES Encryption The overall scheme for DES encryption is illustrated in Figure 3.4. As with any encryption scheme, there are two inputs to the encryption function: the plaintext to be encrypted and the key. In this case, the plaintext must be 64 bits in length and the key is 56 bits in length.
13 3.2. The Data Encryption StandardInitial Permutation The initial permutation and its inverse are defined by tables, as shown in Tables 3.2a and 3.2b, respectively. .
14 3.2. The Data Encryption StandardInitial Permutation To see that these two permutation functions are indeed the inverse of each other, consider the following 64-bit input M:
15 3.2. The Data Encryption StandardInitial Permutation where Mi is a binary digit. Then the permutation X = IP(M) is as follows: If we then take the inverse permutation Y = IP-1(X) = IP-1(IP(M)), it can be seen that the original ordering of the bits is restored.
16 3.2. The Data Encryption StandardDetails of Single Round Figure 3.5 shows the internal structure of a single round.
17 3.2. The Data Encryption StandardDetails of Single Round The role of the S-boxes in the function F is illustrated in Figure 3.6.
18 3.2. The Data Encryption StandardDetails of Single Round These transformations are defined in Table 3.3, which is interpreted as follows: The first and last bits of the input to box Si form a 2-bit binary number to select one of four substitutions defined by the four rows in the table for Si. The middle four bits select one of the sixteen columns. The decimal value in the cell selected by the row and column is then onverted to its 4-bit representation to produce the output.
19 3.2. The Data Encryption StandardKey Generation
20 3.2. The Data Encryption StandardDES Decryption As with any Feistel cipher, decryption uses the same algorithm as encryption, except that the application of the subkeys is reversed.
21 3.2. The Data Encryption StandardThe Avalanche Effect A desirable property of any encryption algorithm is that a small change in either the plaintext or the key should produce a significant change in the ciphertext. DES exhibits a strong avalanche effect. Table 3.5 shows some results taken from
22 3.3. The Strength of Des The Use of 56-Bit KeysThe Nature of the DES Algorithm Timing Attacks
23 3.4. Differential and Linear CryptanalysisDifferential Cryptanalysis History Differential Cryptanalysis Attack Figure 3.7, based on a figure in
24 3.4. Differential and Linear CryptanalysisWe now give a brief summary of the principle on which linear cryptanalysis is based. For a cipher with n-bit plaintext and ciphertext blocks and an m-bit key, let the plaintext block be labeled P<1>, ... P
25 3.5. Block Cipher Design PrinciplesDES Design Criteria No output bit of any S-box should be too close a linear function of the input bits. Each row of an S-box (determined by a fixed value of the leftmost and rightmost input bits) should include all 16 possible output bit combinations. If two inputs to an S-box differ in exactly one bit, the outputs must differ in at least two bits. If two inputs to an S-box differ in the two middle bits exactly, the outputs must differ in at least two bits. If two inputs to an S-box differ in their first two bits and are identical in their last two bits, the two outputs must not be the same. For any nonzero 6-bit difference between inputs, no more than 8 of the 32 pairs of inputs exhibiting that difference may result in the same output differ This is a criterion similar to the previous one, but for the case of three S-boxes.ence.
26 3.5. Block Cipher Design PrinciplesDES Design Criteria The criteria for the permutation P are as follows: The four output bits from each S-box at round i are distributed so that two of them affect (provide input for) "middle bits" of round (i + 1) and the other two affect end bits. The two middle bits of input to an S-box are not shared with adjacent S-boxes. The end bits are the two left-hand bits and the two right-hand bits, which are shared with adjacent S-boxes. The four output bits from each S-box affect six different S-boxes on the next round, and no two affect the same S-box. For two S-boxes j, k, if an output bit from Sj affects a middle bit of Sk on the next round, then an output bit from Sk cannot affect a middle bit of Sj. This implies that for j = k, an output bit from Sj must not affect a middle bit of Sj.
27 3.5. Block Cipher Design PrinciplesNumber of Rounds The cryptographic strength of a Feistel cipher derives from three aspects of the design: the number of rounds, the function F, and the key schedule algorithm. Design of Function F Design Criteria for F S-Box Design For larger S-boxes, such as 8 x 32, the question arises as to the best method of selecting the S-box entries in order to meet the type of criteria we have been discussing. Nyberg, who has written a lot about the theory and practice of S-box design, suggests the following approaches: Random Random with testing Human-made Math-made
28 3.5. Block Cipher Design PrinciplesKey Schedule Algorithm A final area of block cipher design, and one that has received less attention than S-box design, is the key schedule algorithm. With any Feistel block cipher, the key is used to generate one subkey for each round. In general, we would like to select subkeys to maximize the difficulty of deducing individual subkeys and the difficulty of working back to the main key. No general principles for this have yet been promulgated.
You are watching: Why is it important to study the feistel cipher?
See more: Thread: How Many Times Does A Guinea Pig Poop A Day, Their Surprising Habits!
29 Review Questions 3.1 Why is it important to study the Feistel cipher?3.2 What is the difference between a block cipher and a stream cipher? 3.3 Why is it not practical to use an arbitrary reversible substitution cipher of the kind shown in Table 3.1? 3.4 What is a product cipher? 3.5 What is the difference between diffusion and confusion? 3.6 Which parameters and design choices determine the actual algorithm of a Feistel cipher? 3.7 What is the purpose of the S-boxes in DES? 3.8 Explain the avalanche effect. 3.9 What is the difference between differential and linear cryptanalysis?