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