Symmetric Encryption – Block Ciphers

CYB 215: Fundamentals of Information Assurance By: Saleh Almowuena

Block Ciphers
 Encrypt data one block at a time
 Used in broader range of applications
 Typical block size 64 – 128 bits
 Most algorithms based on a structure
referred to as Feistel block cipher

2
Block Ciphers
 Input: a plaintext block of n bits
 Output: a ciphertext block of n bits
 2n possible plaintext blocks
 2n! possible mapping between plaintext
and ciphertext
 Reversible/nonsingular encryption
 Each has unique ciphertext
 Irreversible/singular
 More than one plaintext  same ciphertext
3
Reversible VS Irreversible
Reversible Mapping Irreversible Mapping
Plaintext Ciphertext Plaintext Ciphertext
00 11 00 11
01 10 01 10
10 00 10 01
11 01 11 01

4
Ideal Block Cipher

5
Ideal Block Cipher
Encryption Table Decryption Table

6
Key Length for the Ideal
Block Cipher
 In previous example, key is mapping
 Key length 16 × 4 bits = 64 bits
 i.e. concatenate all bits of ciphertext table
 In general, key length is 2n × n
 Actual block size is at least 64 bits
 Key length will be 264 × 64 ≈ 1021 bits

7
Feistel Cipher
 Build strong cipher that alternates
substitutions & permutations
 Key length k, block length n
 2k possible transformations,
rather than 2n!
 Practical application of a product cipher
that alternates confusion and diffusion
functions

8
Substitution vs. Permutation
 Substitution: Each plaintext element is
uniquely replaced by a corresponding
ciphertext element.
 Permutation: a sequence of plaintext
elements is replaced by a permutation of
that sequence. That is, no elements are
added or deleted or replaced.

9
Diffusion
 Each plaintext digit affects the value of
many ciphertext digits
 Ciphertext has nearly equal letter
frequency compared to plaintext
 Achieved by multiple permutations
followed by applying a function

10
Confusion
 Maximize complexity of the relation
between key and ciphertext statistics
 Achieved by using complex substitution
algorithms

11
Feistel Cipher Structure
 Input
 plaintext block of length 2w
 key K
 Plaintext block divided to LE0, RE0
 Pass thru n rounds of processing
 Each round i has
 LEi-1,
REi-1 derived from previous round
 subkey Ki derived from overall K
12
 Output (plaintext)

RD17 = LE0 LD17 = RE0

Input (plaintext)
LE0 RE0 LD16 = RE0 RD16 = LE0

Round 16
Round 1
F K1

F K1

LE1 RE1 LD15 = RE1 RD15 = LE1

Round 15
Round 2
F K2

F K2
Feistel Cipher Structure
LE2 RE2 LD14 = RE2 RD14 = LE2

LE14 RE14 LD2 = RE14 RD2 = LE14

Round 15

Round 2
F K15

F K15

Round 16 LE15 RE15 LD1 = RE15 RD1 = LE15

Round 1
F K16

F K16

LE16 RE16 LD0 = RE16 RD0 = LE16

Input (ciphertext)

LE17 RE17
Output (ciphertext)

Figure 3.3 Feistel Encryption and Decryption (16 rounds)

Feistel Cipher Structure
 Substitution performed to left half
 apply round function F to right half
 take XOR of output with left half
 F is parameterized by round subkey Ki

 Permutation of left and right halves

 interchange left and right halves

14
Feistel Decryption Algorithm
 Ciphertext is used as input
 Use subkeys Ki in reverse order
 Same algorithm is used
 Notation
 LEi : left half in encryption algorithm
 REi : right half in encryption algorithm
 LDi : left half in decryption algorithm
 RDi : right half in decryption algorithm
15
 Feistel Example
Encryption round Decryption round

F(03A6, 12DE52)
[F(03A6, 12DE52) DE7F]
DE7F 03A6 03A6 = DE7F
Round 15

Round 2
F 12DE52

F 12DE52

03A6 F(03A6, 12DE52) DE7F F(03A6, 12DE52) DE7F 03A6

Figure 3.4 Feistel Example

Design Parameters
 Block size
 larger: greater security (diffusion)
 smaller: faster encryption, decryption
 typical: 64 bit, 128 bit AES

 Key size
 larger: greater security (brute-force resist)
 smaller: faster encryption, decryption
 typical: 128 bit
17
Design Parameters
 Number of rounds
 multiple rounds increase security
 typical: 16

 Subkey generation algorithm

 complexity makes cryptanalysis difficult
 Round function
 complexity makes cryptanalysis difficult

18
Data Encryption Standard (DES)
 Issued in 1977 by the National Bureau of
Standards (now NIST)
 Was the most widely used encryption scheme
until the introduction of the Advanced
Encryption Standard (AES) in 2001
 Algorithm itself is referred to as the Data
Encryption Algorithm (DEA)
 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
 64-bit plaintext block
 56-bit key
 Exact structure as Feistel except
 initialpermutation of plaintext
 final permutation of last round’s output

20
DES Security
 1977
 estimated brute-force attack
 cost: ~ $20 million Must be able to
recognize plaintext!
 time: ~ 10 hours
 1998
 DES definitely proved insecure
 EFF designed “DES Cracker”
 cost: < $250,000
 time: < 3 days
21
Avalanche Effect
 Small change in P  large change in C
 1 bit change in P/K  many bit change in C
 Makes cryptanalysis more difficult
 DES exhibits strong avalanche effect

22
Avalanche Effect – Example
 Two plaintexts used, with 1 bit difference
 00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000

 10000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000
 Key
 0000001 1001011 0100100 1100010 0011100
0011000 0011100 0110010
 After 3 rounds, 21 bits differ
 On completion, 34 bits differ
23
Avalanche Effect – Example
 Single plaintext
 01101000 10000101 00101111 01111010
00010011 01110110 11101011 10100100
 Two keys, with 1 bit difference
 1110010 1111011 1101111 0011000
0011101 0000100 0110001 11011100

 0110010 1111011 1101111 0011000

0011101 0000100 0110001 11011100
 After 4 rounds, 32 bits differ
 On completion, 35 bits differ
24
Avalanche Effect – Example

25
AES General Structure
 Key length: 128, 192, or 256 bits
 AES-128, AES-192, or AES-256, accordingly
 Plaintext block: 128 bits (16 bytes)
 Depicted as 4×4 matrix of bytes (by
column)
 Copied into State array
 Modified at each stage encrypt / decrypt
 Copied to output matrix after final stage
26
27
AES General Structure
 AES Cipher consists of N-rounds
 10, 12, or 14, depending on key length
 Rounds 1 to N – 1 consist of four
transforms
 SubBytes
 ShiftRows
 MixColumns
 AddRoundKey
28
AES General Structure
 Each transform takes 4×4 or more matrix
in
 Produces 4×4 matrix out
 Output of final round is the ciphertext
 Key expansion generations N + 1 round
keys
 Each round key is 4×4 matrix (w)
 used in AddRoundKey transformation
29
AES Data Structures
AES Parameters

31
AES Transformation Functions
 Substitute Bytes
 Shift Rows
 Mix Columns
 Add Round Key

32
AES
Encryption
and
Decryption
Substitute Bytes Transformation
 Simple table lookup
 Uses AES S-box
 contains all possible 256 8-bit permutations
 Each byte in State maps to new byte
 leftmost4 bits used as row
 rightmost 4 bits used for column

34
Substitute Bytes Transformation

35
S-Box

36
Inverse S-Box

37
Example
EA 04 65 85 87 F2 4D 97
83 45 5D 96 EC 6E 4C 90
5C 33 98 B0 4A C3 46 E7
F0 2D AD C5 8C D8 95 A6

38
ShiftRows Transformation
 First row not altered
 Second row 1-byte circular left shift
 Third row 2-byte circular left shift
 Fourth row 3-byte circular left shift
 In inverse transformation (InvShiftRows)
 circular shifts done in opposite direction
 Spread 4 bytes of one column to all
columns
39
ShiftRows Transformation

40
Example
87 F2 4D 97 87 F2 4D 97
EC 6E 4C 90 6E 4C 90 EC
4A C3 46 E7 46 E7 4A C3
8C D8 95 A6 A6 8C D8 95

41
MixColumns Transformation
 Operates on each column individually
 Each byte of a column mapped to new
value
 function
02 03 01 01of all bytes
  s0,0 s0,1
in
s0,2that
s0,3column
  s0,0  s0,2
s0,1   
s0,3
 01  s1,3   s1,0  
 02 03 01  s1,0 s1,1 s1,2  
s1,1 
s1,2 s1,3 

 01 01 02 03  s2,0 s2,1 s2,2 
s2,3   s2,0 
s2,1 
s2,2  
s2,3
   
  

 03 01 01 02   s3,0 s3,1 s3,2 s3,3   s3,0 s3,1 s3,2 s3, 3 

42
MixColumns Transformation

43
Multiplication in GF(28)
 Multiplication by x (00000010) is done as
 1-bit
left shift, then
 conditional bitwise XOR with (00011011)
 Summary (see Equation 5.6)

  b6 b5 b4 b3 b2 b1 b0  0 if b7  0

x f  x  
 b6  b5  b4  b3  b2  b1  b0  0  00011011 if b7 1
 Multiplication by higher power
 repeated application of (5.6)
44
Example
87 F2 4D 97 47 40 A3 4C
6E 4C 90 EC 37 D4 70 9F
46 E7 4A C3 94 E4 3A 42
A6 8C D8 95 ED A5 A6 BC

45
 Example Verification
02  87  03  6E  46  A6  47
87  02  6E  03  46  A6  37
87  6E  02  46  03  A6  94
03  87  6E  46  02  A6  ED

87 shifted left by 1 bit

02  87   0000 1110   00011011   0001 0101

Followed by XOR x8 + x4 + x3 + x + 1
because MSB of 87 is 1

03  6E  6E  02  6E   0110 1110   1101 1100   1011 0010 
6E left shifted by 1 bit
No XOR because MSB of 6E is 0
46
Example Verification
02  87  0001 0101
03  6E  1011 0010
46  0100 0110
A6  1010 0110
0100 0111  47

47
AddRoundKey Transformation
 128 bits of State XORed with round key
 Inverse AddRoundKey is the same
 Rationale
 as simple as possible
 affects all bits of State
 Complexity of round key expansion +
complexity of other stages of AES, ensures
security
48
Example
47 40 A3 4C AC 19 28 57
37 D4 70 9F 77 FA D1 5C
94 E4 3A 42 66 DC 29 00
ED A5 A6 BC F3 21 41 6A
EB 59 8B 1B
40 2E A1 C3
F2 38 13 42
1E 84 E7 D6
49
Single AES
Round

50
 AES Key Expansion
 Takes 4-word (16 bytes) as input and produces array of 44
words (176 bytes)
 Provide 4-word round keys for
 initial AddRoundKey stage
 other 10 rounds
 Key is copied into the first four words of the expanded key
 Each added word w[i] depends on the immediately preceding
word, w[i – 1], and the word four positions back, w[i – 4]
• In three out of four cases a simple XOR is used
• For a word whose position in the w array is a multiple of 4, a
more complex function is used

51
AES Key Expansion
 RotWord
 one-byte circular left shift on a word
 [B0, B1, B2, B3]  [B1, B2, B3, B0]

 SubWord
 byte substitution on each byte of a word
 using S-box

 Rcon[j] = (RC[j], 0, 0, 0)
Round j 1 2 3 4 5 6 7 8 9 10
RC[j] 01 02 04 08 10 20 40 80 1B 36
52
AES
Key
Expansion
Example
Key 0f 15 71 c9 47 d9 e8 59 0c b7 ad df af 7f 67 98

Key Words Auxiliary Function

w0 = 0f 15 71 c9 RotWord(w3) = 7f 67 98 af = x1
w1 = 47 d9 e8 59 SubWord(x1) = d2 85 46 79 = y1
w2 = 0c b7 ad df Rcon(1) = 01 00 00 00
w3 = af 7f 67 98 y1 ⊕ Rcon(1)= d3 85 46 79 = z1
w4 = w0 ⊕ z1 = dc 90 37 b0 RotWord(w7) = 81 15 a7 38 = x2
w5 = w4 ⊕ w1 = 9b 49 df e9 SubWord(x4) = 0c 59 5c 07 = y2
w6 = w5 ⊕ w2 = 97 fe 72 3f Rcon(2) = 02 00 00 00
w7 = w6 ⊕ w3 = 38 81 15 a7 y2 ⊕ Rcon(2)= 0e 59 5c 07 = z2
w8 = w4 ⊕ z2 = d2 c9 6b b7 RotWord(w11)= ff d3 c6 e6 = x3
w9 = w8 ⊕ w5 = 49 80 b4 5e SubWord(x2) = 16 66 b4 8e = y3
w10 = w9 ⊕ w6 = de 7e c6 61 Rcon(3) = 04 00 00 00
w11 = w10 ⊕ w7 = e6 ff d3 c6 y3 ⊕ Rcon(3)= 12 66 b4 8e = z3

54
AES Encryption Cipher Overview

 Youtube Example
 https://www.youtube.com/watch?v=H2LlHOw_ANg
 Symmetric Encryption – Block Ciphers

CYB 215: Fundamentals of Information Assurance By: Saleh Almowuena