Modern Block Ciphers

Modern Block Ciphers CSE 651: Introduction to Network Security

---

Summary • Block Ciphers (Chapter 3) • Feistel Cipher Structure (Chapter 3) • DES: Data Encryption Standard (Ch. 3) • 3DES (Ch 6.1) • AES: Advanced Encryption Standard (Ch. 5.2) 2

---

Monoalphabetic Substitution Cipher • Shuffle the letters and map each plaintext letter to a different random ciphertext letter: Plain letters: abcdefghijklmnopqrstuvwxyzCipher letters: DKVQFIBJWPESCXHTMYAUOLRGZN Plaintext: ifwewishtoreplacelettersCiphertext: WIRFRWAJUHYFTSDVFSFUUFYA • What does a key look like? 3

---

Playfair Key Matrix • Use a 5 x 5 matrix.• Fill in letters of the key (w/o duplicates). • Fill the rest of matrix with other letters.• E.g., key = MONARCHY. M O N A R C H Y B D E F G I/J K L P Q S T U V W X Z 4

---

Vigenère Cipher • Simplest polyalphabetic substitution cipher• Consider the set of all Caesar ciphers: { C , C , C , …, C } a b c z • Key: e.g. security• Encrypt each letter using C , C , C , C , C , s e c u r C , C , C in turn. i t y • Repeat from start after C . y • Decryption simply works in reverse. 5

---

Basic idea of modern block ciphers • From classical ciphers, we learn two techniques that may improve security: – Encrypt multiple letters at a time– Use multiple ciphertext alphabets (Polyalphabetic ciphers) • Combining these two techniques – encrypt eight (or more) letters at a time • called a block cipher – and use an extremely large number of ciphertext alphabets • wil be called modes of operation 1

---

Block Ciphers • In general, a block cipher replaces a block of N plaintext bits with a block of N ciphertext bits. (E.g., N = 64 or 128.) • A block cipher is a monoalphabetic cipher.• Each block may be viewed as a gigantic character.• The “alphabet” consists of 2N gigantic characters.• Each particular cipher is a one-to-one mapping from the plaintext “alphabet” to the ciphertext “alphabet”. • There are 2N! such mappings.• A secret key indicates which mapping to use. 7

---

Ideal Block Cipher • An ideal block cipher would allow us to use any of these 2N! mappings. – The key space would be extremely large. • But this would require a key of log (2N!) bits. 2 • If N = 64, log (2N!) ≈ N x 2N ≈ 1021 bits ≈ 1011 GB. 2 • Infeasible! 8

---

Practical Block Ciphers • Modern block ciphers use a key of K bits to specify a random subset of 2K mappings. • If K ≈ N, – 2K is much smaller than 2N!– But is still very large. • If the selection of the 2K mappings is random, the resulting cipher wil be a good approximation of the ideal block cipher. • Horst Feistel, in1970s, proposed a method to achieve this. 9

---

The Feistel Cipher Structure • Input: a data block and a key• Partition the data block into two halves L and R. • Go through a number of rounds.• In each round, – R does not change. – L goes through an operation that depends on R and a round key derived from the key. 10

---

The Feistel Cipher Structure φi µ

---

Round i L R i-1 i-1 f ki + L R i i

---

Mathematical Description of Round i ﾷ Let L and R be the input of round i, and i 1 − i 1 − L and R the output. i i ﾷ We have L := R i i 1 − R := L ￅ F(R , K ) i i 1 − i 1 − i ﾷ Or, ( L , R ) := µ oφ (L , R ), where i i i i 1 − i 1 − φ : (x, y) ﾮ (x ￅ F( y, k ), y). i i µ : (x, y) ﾮ ( y, x). 1 − 1 ﾷ Note that φ = φ and µ− = µ. i i 13

---

Feistel Cipher ﾷ Goes through a number of rounds, say 16 rounds. ﾷ A Feistel cipher encrypts a plaintext block m as: c := E (m) := µ o µ oφ oLo µ oφ o µ oφ (m) k 16 2 1 ﾷ The decryption will be: 1 − −1 −1 −1 D (c) = φ o µ oφ oLo µ oφ 1 − 1 − 1 o µ o µ− (c) k 1 2 16 = µ o µ oφ o µ oφ oLo µ oφ (c) 1 2 16 ﾷ The descryption algorithm is the same as the encryption algorithm, but uses round keys in the reverse order. 14

---

DES: The Data Encryption Standard • Most widely used block cipher in the world. • Adopted by NIST in 1977.• Based on the Feistel cipher structure with 16 rounds of processing. • Block = 64 bits• Key = 56 bits • What is specific to DES is the design of the F function and how round keys are derived from the main key. 15

---

Design Principles of DES • To achieve high degree of diffusion and confusion. • Diffusion: making each plaintext bit affect as many ciphertext bits as possible. • Confusion: making the relationship between the encryption key and the ciphertext as complex as possible. 1

---

DES Encryption Overview

---

Round Keys Generation • Main key: 64 bits.• 56-bits are selected and permuted using Permuted Choice One (PC1); and then divided into two 28-bit halves. • In each round: – Left-rotate each half separately by either 1 or 2 bits according to a rotation schedule. – Select 24-bits from each half, and permute the combined 48 bits. – This forms a round key.

---

Permuted Choice One (PC1) 57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36 63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4 19

---

Initial Permutation IP • IP: the first step of the encryption.• It reorders the input data bits. • The last step of encryption is the inverse of IP.• IP and IP-1 are specified by tables (see Stal ings book, Table 3.2) or http://en.wikipedia.org/wiki/DES_supplementary_material

---

Round i L R i-1 i-1 32 F ki 48 32 32 + L R i i

---

The F function of DES ﾷ The L and R each have 32 bits, and the round key K 48 bits. ﾷ The F function, on input R and K, produces 32 bits: F( , R K) = P( S ( E(R) ￅ K ) ) where E : expands 32 bits o t 48 bits; S : shrinks it back to 32 bits; P : permutes the 32 bits. 22

---

The F function of DES

---

The Expansion Permutation E

---

The S-Boxes • Eight S-boxes each map 6 to 4 bits • Each S-box is specified as a 4 x 16 table – each row is a permutation of 0-15– outer bits 1 & 6 of input are used to select one of the four rows – inner 4 bits of input are used to select a column • All the eight boxes are different.

---

Box S1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 0 15 7 4 14 2 13 1 10 6 12 11 6 5 3 8 1 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 2 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 3 • For example, S (101010) = 6 = 0110. 1 26

---

Permutation Function P P 16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10 2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25 1

---

Avalanche Effect • Avalanche effect: – A smal change in the plaintext or in the key results in a significant change in the ciphertext. – an evidence of high degree of diffusion and confusion– a desirable property of any encryption algorithm • DES exhibits a strong avalanche effect – Changing 1 bit in the plaintext affects 34 bits in the ciphertext on average. – 1-bit change in the key affects 35 bits in the ciphertext on average.

---

Attacks on DES • Brute-force key search – Needs only two plaintext-ciphertext samples – Trying 1 key per microsecond would take 1000+ years on average, due to the large key space size, 256 ≈ 7.2×1016. • Differential cryptanalysis – Possible to find a key with 247 plaintext-ciphertext samples– Known-plaintext attack • Liner cryptanalysis: – Possible to find a key with 243 plaintext-ciphertext samples– Known-plaintext attack 29

---

DES Cracker • DES Cracker: – A DES key search machine – contains 1536 chips– Cost: $250,000. – could search 88 billion keys per second – won RSA Laboratory’s “DES Challenge II-2” by successful y finding a DES key in 56 hours. • DES is feeling its age. A more secure cipher is needed. 30

---

Multiple Encryption with DES • In 2001, NIST published the Advanced Encryption Standard (AES) to replace DES. • But users in commerce and finance are not ready to give up on DES. • As a temporary solution to DES’s security problem, one may encrypt a message (with DES) multiple times using multiple keys: – 2DES is not much securer than the regular DES– So, 3DES with either 2 or 3 keys is used 31

---

2DES • Consider 2DES with two keys: C = E (E (P)) K2 K1 • Decryption: P = D (D (C)) K1 K2 • Key length: 56 x 2 = 112 bits • This should have thwarted brute-force attacks? • Wrong! 32

---

Meet-in-the-Middle Attack on 2DES • 2-DES: C = E (E (P)) K2 K1 E P E K 1 K 2 C • Given a known pair (P, C), attack as fol ows: – Encrypt P with al 256 possible keys for K1. – Decrypt C with al 256 possible keys for K2. – If E (P) = D (C), try the keys on another (P’, C’). K1’ K2’ – If works, (K1’, K2’) = (K1, K2) with high probability. – Takes O(256) steps; not much more than attacking 1-DES. 33

---

3DES with 2 keys ﾷ A straightforward implementation would be : c := E E E ( ) m 1 k ( k2 ( 1 k ) ﾷ In practice : c := E D E ( ) m 1 k ( k2 ( 1 k ) g Also referred to as EDE encryption ﾷ Reason : if k = k , then 3DES =1DES. 1 2 Thus, a 3DES software can be used as a single-DES. ﾷ Standardized in ANSI X9.17 & ISO 8732. ﾷ No practical attacks are known. 34

---

3DES with 3 keys ﾷ Encryption: c := E D E ( ) m . 3 k ( k2 ( 1 k ) ﾷ If k = k , it becomes 3DES with 2 keys. 1 3 ﾷ If k = k = k , it becomes the regular DES. 1 2 3 ﾷ So, it is backward compatible with both 3DES with 2 keys and the regular DES. ﾷ Some internet applications adopt 3DES with three keys; e.g. PGP and S / MIME. 35

---

AES: Advanced Encryption Standard

---

AES: Advanced Encryption Standard • In1997, NIST began the process of choosing a replacement for DES and cal ed it the Advanced Encryption Standard. • Requirements: block length of 128 bits, key lengths of 128, 192, and 256 bits. • In 2000, Rijndael cipher (by Rijmen and Daemen) was selected. • An iterated cipher, with 10, 12, or 14 rounds. • Rijndael al ows various block lengths. • But AES al ows only one block size: 128 bits. 37

---

Modulo-2 Arithmetic ﾷ There are only two numbers : 0 and 1. ﾷ Addition, substraction and multiplication are as below: + 0 1 − 0 1 ﾴ 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 1 0 1 0 1 ﾷ Note: addition = substraction = XOR.

---

Byte-oriented operations g Each byte is viewed as a polynomial of degree ﾣ 7. 7 3 g Example: a = 10001001 = x + x +1 = ( A x). 7 b = 100010 = x + x = B(x). g Addition and substraction are simply bitwise XOR: a + b = 10001001 1 � 00010 = 00001011 = ( A x) + B(x). a − b = 10001001 1 � 00010 = 00001011 = ( A x) + B( x). 39

---

Byte-oriented operations g Multiplication ( )ￗ: "regular" polynomial multiplication (ﾴ) modulo a fixed modulus P(x), where 8 4 3 P(x) = x + x + x + x +1 = 100011011. a b �= ( A x) ﾴ B(x) mod P(x) 14 10 8 7 4 = x + x + x + x + x + x mod P(x) 6 5 4 3 2 = x + x + x + x + x + x +1 a b �= 10001001 1 �00010 mod 100011011 = 100010110010010 mod 100011011 = 0111 40

---

Byte-oriented operations g For any byte a (viewed as a polynomial), there is a unique byte b (also viewed as a polynomial) such that a b � = 1. g This element b is called the inverse of a, and is 1 denoted by a− . g Mathematically, the set of all polynomials of degrees ﾣ 7 8 forms a field, GF(2 ), under the operation of addition and multiplication mod P(x), where P(x) is a fixed modulus. 41

---

Structure of Rijndael g N : block size (number of words). For AES, N = 4. b b g N : key length (number of words). k g N : number of rounds, depending on N , N . r b k A g ssume: N = 4, N = 4, N = 10. b k r g stat :e a variable of 4 words, holding the data block, viewed as a 4 ﾴ 4 matrix of bytes; each column is a word. K g ey schedule: 11 round keys key , key , K, key 0 1 10 computed from the main key k. 42

---

Rijndael algorithm ( input: plaintext m, key k) 1 state ﾬ m 2 AddKey(state,key ) 0 3 for i ﾬ 1 to N −1 do r 4 SubBytes(state) 5 ShiftRows(state) 6 Mixcolumns(state) 7 AddKey(state,key ) i 8 SubBytes(state) 9 ShiftRows(state) 10 AddKey(state,key ) Nr 11 return(state) 43

---

Figure 5.1 AES Encryption and Decryption 44

---

AddKey(stat , e keyi) state ﾬ state ￅ keyi 45

---

SubBytes(stat ) e g Each byte z in the state matrix is substituted with 1 another byte S (z) = Az− + b. RD 1 g The substitution S (z) = Az− + b, called Rijndael’s RD S-box, is based on some mathematics in finite fields, and can be specified as a table (Table 5.4 of Stallings). 46

---

8 g That is, treat z as an element in GF(2 ). 1 − 8 g Find its multiplicative inverse z in GF(2 ). 1 g Now treat z− as a vector of 0/1. 1 g Multiply A with z− , and add the result to . b 10 � 001111 � 1 �� 11 � 000111 � 1 �� 11 � 100011 � 0 �� � � �� A = 11110001 0 � a � nd b = �� 111000 0 � � �� 011100 1 � � �� 0 �01110� 1 �� 0 �00111� 0 �� � � �� 47

---

ShiftRows(state) g Left-shift row i circularly by i bytes, 0 ﾣ i ﾣ 3. a � b c d � a � b c d � � � � � e f g h f g h e � � � � ﾮ i � j k l � k � l i j � � � � � m n o p p m n o � � � � 48

---

MixColumns(state) g Operate on each column of the state matrix. g Each column a = (a , a , a , a ) is substituted with 0 1 2 3 (b , b , b , b ), where 0 1 2 3 b � � 0 �2 03 01 01� a � � 0 0 b � � 0 �1 02 03 01� a � � 1 � �= 1 � � � � b � � 0 �1 01 02 03� a � � 2 � � 2 � � � � b 03 01 01 02 a 3 � � � ��3 � g Using finite-field multiplication and addition. 49

---

Math behind MixColumns(state) g Operate on each column of the state matrix. g Each column a = (a , a , a , a ) is viewed as a 0 1 2 3 polynomial : 3 2 a(x) = a x + a x +a x + a 3 2 1 0 g A fixed polynomial: c( 3 2 x) = 03x + 01x +01x + 02. 3 2 g Compute b(x) = b x + b x +b x + b 3 2 1 0 4 = a(x) c( � x) mod (x +1) g (a , a , a , a ) is substituted with (b , b , b , b ) 0 1 2 3 0 1 2 3 50

---

Rijndael Decryption g Each step of Rijndael encryption is invertible. 51

---

A Rijndael Animation by Enrique Zabala 52

---