Modern Block Cipher- Modern Symmetric-Key Cipher

Introduction to Modern Symmetric-Key Ciphers- This lecture will cover only "Modern Block Cipher".
Slide Credit: Maleka Khatun & Mahbubur Rahman
Dept. of CSE, JnU, BD.

1. Maleka Khatun B150305031 Mahbubur Rahman B150305042 Chapter-5 Introduction to Modern Symmetric-Key Cipher (Modern Block Cipher) Presented By

2. MODERN BLOCK CIPHERS A symmetric-key modern block cipher encrypts an n-bit block of plaintext or decrypts an n-bit block of cipher text. The encryption or decryption algorithm uses a k-bit key. Fig 5.1 A modern block cipher 2 Note: If the message is fewer than n bits, padding must be Added to make it an n-bit block; if more than n bits then it Should be divided into n-bit blocks and the appropriate padding Must be added. The common values for n are 64, 128, 256, or 512

3. Continue… Example 5.1: How many padding bits must be added to a message of 100 characters if 8-bit ASCII is used for encoding and the block cipher accepts blocks of 64 bits? Answer: Encoding 100 characters using 8-bit ASCII results in an 800-bit message. The plaintext must be divisible by 64. If | M | and |Pad| are the length of the message and the length of the padding, 3

4. substitution or Transposition A modern block cipher can be designed to act as a substitution cipher or a transposition cipher If the cipher is designed as substitution cipher, a 1-bit or a 0-bit can be replaced by either a 0 or a 1 bit. This means that the plain text and the cipher text can have different number of 1’s. If the cipher is designed as transposition cipher, the bits are only reordered (transposed), there is same number of 1’s in the plaintext or ciphertext. N-bit possible plaintext or cipher text is 2 n because each of the block can have one of the two values 0 or 1 To be resistant to exhaustive-search attack, a modern block cipher needs to be designed as a substitution cipher. Example 5.2: Suppose that we have a block cipher where n = 64. If there are 10 1’s in the cipher text, how many trial-and-error tests does Eve need to do to recover the plaintext from the intercepted cipher text in each of the following cases? a. The cipher is designed as a substitution cipher. b. The cipher is designed as a transposition cipher. 4

5. Continue… Answer: In the first case, Eve has no idea how many 1’s are in the plaintext. Eve needs to try all possible 2 64 64-bit blocks to find one that makes sense. If eve could try 1 billion blocks per second, it will take hundreds of years, on average, before she could be successful. In the second case, Eve knows that there are exactly 10 1’s in the plaintext because transposition does not change the number of 1’s or 0’s in the cipher text. Eve can launch an exhaustive-search attack using only those 64-bit blocks that have exactly 10 1’s. there are only (64!)/[(10!)(54!)]= 151, 473, 214, 816 out of 2 64 64 bit words. Eve can test all of them in less than 3 minutes if she could do 1 billion tests per second. 5

6. Block Ciphers as Permutation Groups Full-Size Key Transposition Block Ciphers In a full-size key transposition cipher We need to have n! possible keys, so the key should have log 2 n! bits. Example 5.3: Answer: The set of permutation tables has 3! = 6 elements. Key should be log 2 6! =3 bits long . key can select 2 3 = 8 mapping. we can use any 6 of them. Show the model and the set of permutation tables for a 3-bit block transposition cipher where the block size is 3 bits. Fig 5.2 a transposition block cipher modeled as permutation 6

7. Block Ciphers as Permutation Groups Full-Size Key Substitution Block Ciphers A full-size key substitution cipher does not transpose bits; it substitutes bits. We can model the substitution cipher as a permutation if we can decode the input and encode the output. Example 5.4: Answer: The three input plaintext can be an integer between 0 to 7.This can be decoded as 8 bit string with a single 1.For example 000 can be decode as 00000001.101 decode as 00100000.The number of elements of transposition cipher(8!=40,320). The key is also much longer, [log 2 40,320] = 16 bits. Although a 16 bit key can define 65,536 different mappings, only 40,320 are used. Show the model and the set of permutation tables for a 3-bit block substitution cipher. 7

8. Block Ciphers as Permutation Groups Note: A full-size key n -bit transposition cipher or a substitution block cipher can be modeled as a permutation, but their key sizes are different: Transposition: the key is [log 2 n! ] bits long. Substitution: the key is [log 2 (2 n )!] bits long. Note: Actual ciphers can not use full size keys because the size of the key becomes so large, especially when using substitution block cipher. If the designer of DES(next chapter) which uses 64 bit block cipher, had used a full size key, the key would have been log 2 (2 64 )! Long , so the key size for DES is only 56 bits, which is a very small fraction of the full size key, this means it only uses 2 56 mappings out of 2 2^70 possible mappings. partial-key cipher is a group under the composition operation if it is a subgroup of the corresponding full-size key cipher. 8

9. Components of a Modern Block Cipher Modern block ciphers normally are keyed substitution ciphers in which the key allows only partial mappings from the possible inputs to the possible outputs. However modern block ciphers normally are not designed as a single unit. To provide the required properties of a modern block cipher, such as diffusion and confusion, as a modern block cipher is made of a combination of transposition units for diffusion (called D-box) or Substitution units (called S-box), and some other units. D(diffusion)-box: A D-box parallels the traditional cipher for characters. It transposes bits. It is referred to as permutation. That’s why it is also called P-box. The system of output of the D-boxes are predetermined. There are three types of D-boxes. 1. Straight D -boxes 2. Compression D-boxes 3. Expansion D-boxes 9

10. Continue… Straight D-boxes: A straight D-box with n inputs and n outputs according to permutation. There are n! possible mapping. Compression D-boxes : A compression D-box with n inputs and m outputs where m < n. Expansion D-boxes : An expansion D-box with n inputs and m outputs where m > n. Fig 5.4 types of D-boxes 10

11. Components of a Modern Block Cipher Example 5.5 Shows all 6 possible mappings of a 3 × 3 D-box. Answer: The possible mappings of a 3 × 3 D-box(3!=6 permutation) Example 5.6 Design an 8 × 8 permutation table for a straight D-box that moves the two middle bits (bits 4 and 5) in the input word to the two ends (bits 1 and 8) in the output words. Relative positions of other bits should not be changed . Answer: We need a straight P-box with the table [4 1 2 3 6 7 8 5]. The relative positions of input bits 1, 2, 3, 6, 7, and 8 have not been changed, but the first output takes the fourth input and the eighth output takes the fifth input. 11

12. invertibility Example 5.7: shows how to invert a permutation table represented as a one-dimensional table. Answer: Fig 5.6 Inverting a permutation table 12

13. Continue.. So, Compression and expansion D-boxes are not invertible. A straight D-box is invertible. That’s why it is used in both encryption and decryption algorithm. 13

14. S - Box S(substitution)box: An S-box is an m x n substitution unit, where m and n are not necessarily the same. The number of input and output are not necessarily same. Modern block ciphers use Key-less S-boxes where the mapping from the inputs to the outputs is predetermined. Example 5.10: The following table defines the input/output relationship for an S-box of size 3 × 2. The leftmost bit of the input defines the row; the two rightmost bits of the input define the column. The two output bits are values on the cross section of the selected row and column. Answer: Based on the table, an input of 010 yields the output 01. An input of 101 yields the output of 00. 14

15. invertibility Example 5.1 For example, if the input to the left box is 001, the output is 101. The input 101 in the right table creates the output 001, which shows that the two tables are inverses of each other. Answer: 15 An S-box may or may not be invertible, In an invertible S-box, the number of input bits should be same as the number of output bits

16. exclusive - or Exclusive-Or An important component in most block ciphers is the exclusive-or operation. Properties: The five properties of exclusive-or operation in GF (2 n ) field makes this operation a very interesting component for use in a block cipher. Closure: This property guarantees that the result of exclusive- oring two n-bit words is another n-bit word. Associativity: This property allows us to use more than one exclusive- or operation in any order. X  (Y  Z)  (X  Y)  Z 16

17. Continue.. Commutativity: This property allows us to swap the inputs without affecting the output. X  Y  Y  X  Existence of identity: The identity element for the exclusive-or operation is an n-bit word that consists of all 0’s or (000…0). This implies that exclusive- oring of a word with the identity element does not change that word. X  (00…0) = X Existence of inverse: In the GF (2 n ) field, each word is the additive inverse of itself. This implies that exclusive – oring of a word with itself yields the identity element. X  X = (00…0) Complement: The complement operation is a unary operation (one input ant one output) that flips each bit in a word. A 0-bit is changed to a 1-bit; a 1- bit is changed to 0-bit. We are interested in the complement operation in relation to the exclusive-or operation. If  X is the complement of X, then the following two relations hold: X   X = (11…1) X  (11…1) =  X 17

18. Circular Shift Circular Shift Another component found in some modern block ciphers is the circular shift operation. Shifting can to the left or to the right. The circular left shift operation shifts each bit in an n bit word k positions to the left. The leftmost k bits are removed and Become the rightmost bits. Here, n=8, k=3 Circular shift an 8 bit word to left or right 18

19. Continue.. Swap The swap operation is a special case of the circular shift operation where k = n/2. This means swap operation is valid only if n is an Even number. Split and Combine Two other operations found in some block ciphers are split and combine. It split n bit word in the middle, create two equal length word. Fig 5.11Swap operation on an 8 bit word Fig 5.12 Split and combine on an 8 bit word 19

20. Product Cipher Product cipher is a combination of substitution, permutation and other components. As a result, the resulting cipher will be more secure than individual components. Claude Shannon introduced the concept of product cipher. Claude Shannon gave emphasis on the security of the plaintext. Thus no attacker can attacks on it. So, he added two new important properties : diffusion, confusion. Diffusion: Diffusion hides the relationship between plaintext and cipher text. The attacker who uses ciphertext approaches will be frustrated. Each symbol in the ciphertext will depend on some or all the elements of the plaintext. 20

21. Product Cipher continue… Confusion: Confusion hides the relationship between ciphertext and key. If a single bit in the key will be changed the most or all the bits in the ciphertext will be changed. So, it may be very difficult to identify the key by the attackers according to ciphertext. Diffusion and confusion can be achieved by iterated product cipher. Iterated product cipher is combination of S-box, D-box and other components. Each iteration considered as round. Here the mapping of output according to input for both S-box, D-box has to be predetermined. The product cipher used only the straight D-box. Because it is invertible. So, decryption can be done by it. 21

22. Continue… Modern block cipher use a round key generator for each round. Round-Key generator: Round key generator creates different keys in each round. If a cipher key is normally given as 64 bit then the round key generator creates sixteen 48 bit keys out of 56 bit. Extra 8 bit is given with the input key(64 bit).this 8 bits are parity bit which are dropped before key generation by parity drop table. 22

23. Algorithm

24. Continue.. 57 49 41 33 25 17 09 01 58 50 42 34 26 18 10 02 59 51 43 35 27 19 11 03 60 52 44 36 63 55 47 39 31 23 15 07 62 54 46 38 30 22 14 06 61 53 45 37 29 21 13 05 28 20 12 04 Parity bit drop table(56 bit) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 Input (64 bits) 24

25. Continue… 14 17 11 24 01 05 03 28 15 06 21 10 23 19 12 04 26 08 16 07 27 20 13 02 41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32 57 49 41 33 25 17 09 01 58 50 42 34 26 18 10 02 59 51 43 35 27 19 11 03 60 52 44 36 63 55 47 39 31 23 15 07 62 54 46 38 30 22 14 06 61 53 45 37 29 21 13 05 28 20 12 04 Result of parity bit drop table (56 bit) Compressed D-box(48 bit) 18 59 42 03 57 25 41 36 10 17 27 50 11 43 34 33 52 01 02 09 44 35 26 49 30 06 47 62 45 12 55 38 14 38 31 37 06 29 46 04 22 28 53 22 21 07 63 39 Output of D-box 25

26. Product Cipher Three transformations are happened in every round of the product cipher. The text is mixed with the key to whiten the text( hide the bits of plaintext using the key).It is normally done by the exclusive-or operation. The output of the whitener are organized by S-box. The values of bits will changed by the structure of S-box transformation. The output of the S-boxes passed through a straight D-box to transpose the bits. The predetermined D-box(straight) pos 1 2 3 4 5 6 7 8 In bit 1 2 3 4 5 6 7 8 Out bit 2 7 3 8 6 1 4 5 26

27. Now, we consider a simple product cipher with 2 rounds. The plaintext and key both are 8 bit. In an N round product cipher plaintext will encrypted N times, key will changed for N times and cipher text will decrypted N times. 5. 27

28. Continue.. Classes of modern cipher: All modern block ciphers are product cipher. The product ciphers are divided into two classes. Feistel Ciphers Non Feistel cipher Feistel cipher use both invertible and noninvertible components. This block cipher is DES. Non Feistel cipher use only invertible components. This type of block cipher is AES. 28

29. Feistel Cipher A Feistel cipher combines all noninvertible components in an unit and uses the same unit in encryption and decryption algorithm. The encryption and decryption algorithm are inverse of each other (using the same unit of noninvertible components). First thought: In encryption, a noninvertible Function f(k),accepts the key as input. Then the output of the function is exclusive- ored with the plaintext. This combination is called Mixer. The output of this combination becomes ciphertext. It is sent to the receiver. Fig 5.15 The first thought in Feistel cipher design 29

30. Continue.. The input of decryption is same as the output of encryption algorithm. And the key function is also same. That’s mean C1=C2. Encryption : C1=P1  f(k) Decryption : P2 = C2  f(k) = C1  f(K) [C1=C2] = P1  f(k)  f(k) [X  X=0] = P1  0 = P1 the plaintext are same. So, encryption and decryption algorithm are inverse. 30

31. Continue… Example 5.12 This is a trivial example. The plaintext and cipher text are each 4 bits long and the key is 3 bits long. Assume that the function takes the first and third bits of the key, interprets these two bits as a decimal number, squares the number, and interprets the result as a 4-bit binary pattern. Show the results of encryption and decryption if the original plaintext is 0111 and the key is 101. Answer: The function extracts the first and second bits to get 11 in binary or 3 in decimal. The result of squaring is 9,which is 1001 in binary. 31

32. Improvement of Feistel cipher Some improvements are done on the first thought of Feistel cipher to secure the text. In noninvertible function two inputs are considered. Function is to be a part of plaintext in encryption and ciphertext in decryption. And key can be the second input of the function. By doing this function can be a complex element. To achieve this goal, divide the plaintext into two equal length blocks as left and right. Left block is represented as L and right one is R. The inputs of the function must be same in both algorithm. 32

33. Continue.. In encryption the right section of the plaintext and key(k) goes to function as input. The output of this function exclusive- ored with left section of plaintext. And produce the left section of the cipher text. The right section same as the plaintext. In decryption algorithm reverse approach is used. The right section of the received cipher text goes to the function. Figure 5.16 Improvement of the previous Feistel design 33

34. Continue… The input of decryption is same as the output of encryption algorithm. And the key function is also same. That’s mean R2=R3,L2=L3. Rules: Li = L(i-1)  f( R(i-1) , k) Encryption : L2= L1  f(R1,k) ; R1=R2 ; Decryption : L4 = L3  f( R3,k ) = L2  f( R2,K ) =L2  f( R1,K ) [R3=R2=R1] = L1  f( R1,K)  f( R1,K ) = L1  0 = L1 And R4=R3, As L4=L1 and R1=R2=R3=R4 the plaintext are correctly decrypted. 34

35. Final design of Feistel cipher But the improvement has one problem. The right half section of the plaintext never changes. So, it is very easy for the attacker to identify the left half section of the plain text. The design needs more improvement. First increase the number of rounds. Add a new element to each round: swapper . It allows to swap the left and right halves in each other. Consider a two rounds Feistel cipher number of keys are K1,K2.Keys are used in reverse order in encryption and decryption. Between two rounds a middle text is created. This middle text has to be same in encryption and decryption. 35

36. Continue… The mixer and swapper are inverse. 36

37. Continue… Here L3=L4,R3=R4,L3=R2,L4=R5. Check the equality of middle text. Rules: 1.Ri= L(i-1)  f( R(i-1) , k n ) 2.Li= K(i-1)  f( L(i-1) , k n ) Now, middle text in decryption L5 = R4  f(L4,K2) = R3  f(L3,K2) [R3=R4,L3=L4] = R3  f(R2,K2) [L3=R2] = L2  f(R2,K2)  f(R2,K2) = L2  0 =L2, R5=L4=L3=R2; So, the middle text are( L5=L2,R5=R2 )equal. 37

38. Continue… Check the equity of plaintext … Here, L5=L2 ,R5=R2; R6=L5, L4=R5, L3=L4, R3=R4 ,L3=R2, L2=R1; The plaintext in decryption L6 = R5  F(L5,K1) = R2  F(L2,K1) [R5=R2 ,L5=L2] = L1  F(R1,K1)  F(L2,K1) [Rules 1] = L1  F(R1,K1)  F(R1,K1) [L2=R1] = L1  0 = L1 And R6 = L5=L2=R1. The plaintext are same (L6=L1,R6=R1). 38

39. Non Feistel cipher Non Feistel cipher only used invertible components. That means S-boxes, need to have equal number of input and output, Compression and expansion D boxes are not allowed. Only can use straight D-boxes. In non Feistel cipher ,there is no need to divide the plaintext into two equal parts. 39

40. 40