Block Cipher And Des

Ch 3: Block Ciphers and Data Encryption Standard (DES) Fourth Edition by William Stallings Lecture slides by Lawrie Brown (modified by Prof. M. Singhal, U of Kentucky) 1

Modern Block Ciphers • look at modern block ciphers • one of the most widely used types of cryptographic algorithms • provide secrecy /authentication services • focus on DES (Data Encryption Standard) to illustrate block cipher design principles

2

Block vs Stream Ciphers • block ciphers process messages in blocks, each of which is then en/decrypted • like a substitution on very big characters – 64-bits or more

• stream ciphers process messages a bit or byte at a time when en/decrypting • many current ciphers are block ciphers • broader range of applications 3

Block Cipher Principles • most symmetric block ciphers are based on a Feistel Cipher Structure • block ciphers look like an extremely large substitution • would need table of 264 entries for a 64-bit block • instead create from smaller building blocks • using idea of a product cipher

4

Ideal Block Cipher

5

Claude Shannon and SubstitutionPermutation Ciphers • Claude Shannon introduced idea of substitutionpermutation (S-P) networks in 1949 • form basis of modern block ciphers • S-P nets are based on the two primitive cryptographic operations: – substitution (S-box) – permutation (P-box)

• provide confusion & diffusion of message & key

6

Diffusion and Confusion… • Diffusion: “The statistical structure of the plaintext is spread (dissipated) into long-range statistics of the ciphertext.” • Achieved by having each plaintext digit affect the value of many ciphertext digits. • Objective is to globalize the local affects. 7

Diffusion and Confusion… • Confusion: “Attempts to make the relationship between the ciphertext and the encryption key as complex as possible.” • Achieved by using a complex substitution algorithm. • Even if an attacker can have some handle on the statistics of the ciphertext, it is very difficult to deduce the key. 8

Feistel Cipher Structure • Horst Feistel devised the feistel cipher – based on concept of invertible product cipher

• partitions input block into two halves – process through multiple rounds which – perform a substitution on left data half – based on round function of right half & subkey – then have permutation swapping halves

• implements Shannon’s S-P net concept 9

Feistel Cipher Structure

10

Feistel Cipher Design Elements • • • • • •

block size key size number of rounds subkey generation algorithm round function fast software en/decryption

11

Feistel Cipher Decryption

12

Data Encryption Standard (DES) • • • • •

most widely used block cipher in world adopted in 1977 by NBS (now NIST) encrypts 64-bit data using 56-bit key has widespread use has been considerable controversy over its security

13

DES History • IBM developed Lucifer cipher – by team led by Feistel in late 60’s – used 64-bit data blocks with 128-bit key

• then redeveloped as a commercial cipher with input from NSA and others • in 1973 NBS issued request for proposals for a national cipher standard • IBM submitted their revised Lucifer which was eventually accepted as the DES 14

DES Design Controversy • although DES standard is public • was considerable controversy over design – in choice of 56-bit key (vs Lucifer 128-bit) – and because design criteria were classified

• subsequent events and public analysis show in fact design was appropriate • use of DES has flourished – especially in financial applications – still standardised for legacy application use 15

16

DES… • Initial Permutation (IP): The plaintext block undergoes an intial permutation. > 64 bits of the block are permuted. • A Complex Transformation: 64 bit permuted block undergoes 16 rounds of complex transformation. (Using subkeys) 17

DES… • 32-bit swap: 32 bit left and right halves of the output of the 16th round are swapped. • Inverse Initial Permutation (IP-1): The 64 bit output undergoes a permutation that is inverse of the intial permutation. >The 64 bit output is the ciphertext. 18

19

DES • The complex processing at each iteration/round: – Li = Ri-1 – Ri = Li-1 ⊗ F(Ri-1, Ki)

• Details of function F: It takes 32 bits input and produces a 32 bit output. 20

DES • Details of function F: >32 bit input is expanded into 48 bits. -This is done by permuting and duplicating some bits of 32 bits. >Exclusive OR operation is performed between these 48 bits and 48 bit subkey. 21

DES • Details of function F:... > 48 bit output of the Exclusive OR operation is grouped into 8 groups of 6 bits each. > Each 6 bit group is fed into a 6to-4 substitution box that transforms 6 bits to 4 bits. 22

DES • Details of function F:... > 32 bit output of 8 substitution boxes is fed into a permutation box. > The 32 bit output of the permutation box is F(Ri-1, Ki). 23

DES • Concerns about: – The key length (56-bits) > 56 bit key was adequate in 70s. > With faster processors, this encryption method is no longer safe.

24

Time to break a code (106 decryptions/µs)

25

Triple DEA • Use three keys and three executions of the DES algorithm (encrypt-decryptencrypt) • • • •

C = EK3[DK2[EK1[P]]]

C = ciphertext P = Plaintext EK[X] = encryption of X using key K DK[Y] = decryption of Y using key K

• Effective key length of 168 bits 26

Triple DEA

27

Cipher Block Modes of Operation • Cipher Block Chaining Mode (CBC) - A method to increase the security of DES or any block cipher. – The input to the encryption algorithm is the XOR of the current plaintext block and the preceding ciphertext block.

- Processing of a sequence of plaintext blocks is chained together. 28

29

Basis of Cipher Block Chaining…

Ci = E k [Ci −1 ⊕ Pi ] D K [Ci ] = D K [E K (Ci −1 ⊕ Pi )] D K [Ci ] = (Ci −1 ⊕ Pi ) Ci −1 ⊕ D K [Ci ] = Ci −1 ⊕ Ci −1 ⊕ Pi = Pi 30