BINF-KT-CNS-S12

Communication Network Security

AOT
Agententechnologien in betrieblichen Anwendungen und der Telekommunikation

Symmetric Cryptography: Block Ciphers Lecture 4 (May 7th, 2012)

Dr. Seyit Ahmet Camtepe
Director of Competence Center Security at DAI-Labor Office: TEL 1409 Phone: 030 314 74117 E-Mail: [email protected], [email protected]

Acknowledgements
This presentation is in part based on:
Cryptography and Network Security by W. Stallings Cryptography: Theory and Practice by D.R. Stinson Lecture slides prepared under my TA-ship for the Network Security Lecture of Prof. B. Yener at RPI, New York.

AOT

Week 4: Theoretical Background

Perfect Secrecy
For (P, C, K, E, D) cryptosystem where |K|=|C|=|P|: (1) every key should be used with equal probability, (2) Every (p, c) pair should have a unique key

Entropy, Redundancy, Spurious Key, Unicity Distance

Number of Spurious Keys approaches 0 exponentially as block size n increases (using Redundancy and Entropy of the language) Substitution Cipher requires ciphertext of size 25 so that number of Spurious Keys will be 0 ..

Product Cryptosystem
Product of non-idenpotent cryptosystems increase security (e.g., product of substitution with permutation ciphers) Modern Block Ciphers

AOT

Week 4: Feistel Cipher

Invertible product cipher Partitions input block into two halves Process through multiple rounds
Perform a substitution on left data half based on round function of right half & subkey Have permutation swapping halves

Implements substitutionpermutation network concept

AOT

Week 5: Block Ciphers

Data Encryption Standard (DES) Triple-DES (3-DES) Modes of Operation Advanced Encryption Standards (AES)

AOT

Data Encryption Standard (DES)

Most widely used block cipher 1977 by NBS (now NIST)
FIPS PUB 46

Encrypts 64-bit data using 56-bit key

AOT

Block Cipher Design Principles

Similar to Feistel: Number of rounds
More rounds against exhaustive search-based attacks

Function F:
Provides confusion, is nonlinear, avalanche

Key Schedule
Complex subkey creation, key avalanche

AOT

DES History
IBM developed Lucifer cipher
a team led by Feistel 64-bit data blocks with 128-bit key

Redeveloped as a commercial cipher with input from NSA and others IBM revised Lucifer which was eventually accepted as the national cipher standard

AOT

DES Encryption

AOT

DES Encryption: Initial Permutation (IP)

Reorders the input data bits
Even bits to LH half, Odd bits to RH half

Example:
IP(675a6967 5e5a6b5a) = (ffb2194d 004df6fb)

AOT

DES Encryption: Initial Permutation (IP)

AOT

DES Encryption: DES Round Structure (1)

Two 32-bit Left and Right halves
Similar to Feistel cipher: Li = Ri1 Ri = Li1 XOR F(Ri1, Ki)

F(R, K)
Takes 32-bit Right half and 48-bit Subkey Expands Right half to 48-bits using Perm E XORs with Subkey Passes through 8 S-boxes to get 32-bit result Finally permutes this using 32-bit Perm P

AOT

DES Encryption: DES Round Structure (2)

AOT

DES Encryption: DES Round Structure (3)

AOT

DES Encryption: DES Round Structure (4)

AOT

DES Encryption: Substitution Boxes S

Eight S-boxes which map 6 to 4 bits

48 bits is divide into 8 times 6 bits For each 6 bits, one S box Outer bits 1 & 6 (row bits) select one rows Inner bits 2 - 5 (col bits) are substituted Result is 8 times 4 bits = 32 bits

Example:
S(18 09 12 3d 11 17 38 39) = 5fd25e03

AOT

DES Encryption: DES Round Structure (4)

Example 011001 1100 0 1

Column Address
Row Address

AOT

DES Encryption: DES Key Schedule

16 subkeys for 16 rounds
Initial Permutation of the Key (PC1)
Every 8th bit is dropped selects 56-bits in two 28-bit halves

Each stage consisting of:

Selecting 24-bits from each half Rotating each half separately either 1 or 2 places depending on the key rotation schedule K Permuting them by PC2 to produce 48 bit subkey

AOT

DES Encryption: DES Key Schedule

AOT

DES Encryption: DES Key Schedule

AOT

DES Decryption
Encryption steps using subkeys in reverse order (SK16 SK1) IP undoes final FP step of encryption 1st round with SK16 undoes 16th encrypt round 16th round with SK1 undoes 1st encrypt round Final FP undoes initial encryption IP Recovers original data value

AOT

DES Avalanche Effect

Key desirable property of encryption algorithm A change of one input or key bit results in changing approx half output bits DES exhibits strong avalanche

AOT

Strength of DES: Key Size

56-bit keys have 256 = 7.2 x 1016 values Brute force search looks hard, but possible
in 1997 on Internet in a few months in 1998 on dedicated h/w (EFF) in a few days in 1999 above combined in 22hrs! Attempts to reduce search space
Differential Cryptanalysis, Complexity is 255 [BIHA93], Complexity is 247 (chosen plaintext attack) Linear Cryptanalysis, Complexity is 243 (known plaintext attack)

Need to be able to recognize plaintext

What if compressed before encrypted!

AOT

Simplified DES
Educational purpose Works on 8-bit blocks and uses 10-bit key for rounds Consider that plaintext and ciphertext are known:
Plaintext : p1, p2, , p8 Ciphertext: c1, c2, , c8 Key: k1, k2, , k10

Simplified encryption algorithm will produce 8 non-linear equations (combination of linear and non-linear equations) with 10 unknowns. Note that:
Permutations (P10, P8, P4) are linear xor additions are linear Substitution boxes (S0 and S1) are non-linear!

AOT

Initial Permutation of bit positions

2
8-bit plain text

Initial Key: 10-bit

Initial Permutation 4-bit 4-bit

P10

8-bit K1
+ F

P10: Permutation of 10-bit 3 5 2 7 4 10 1 9 8 6

5-bit

5-bit

Left Shift Left Shift

8-bit K2 + F P8 K1
Left Shift Left Shift Inverse Initial Perm. 8-bit cipher text

P8 K2

P8: 8 Permutation of 10-bit 6 3 7 4 8 5 10 9

AOT

Inverse Permutation of bit pos.

4-bit

F function

1 2 3 4 4-bit

8-bit + 4-bit 8-bit Key 4-bit

4-bit
Bit-2 and Bit-3 Column Add. 0,1, 2, 3 0 1 0 1
1 3 0 3 0 2 2 1

Expansion / Permutation 4 1 2 3 2 3 4 1 8-bit

S0 2-bit P4 4-bit

S1

Bit-1 and Bit-4 Row Add. 0,1, 2, 3 2 3

3 1 1 3 2 0 3 2

0 0 1 2 3
0 2 3 2

1
1 0 0 1

2
2 1 1 0

3
3 3 0 3

2-bit

2 3

S0 Substitution Matrix

S1 Substitution Matrix

AOT

P4 2 4 3 1

Initial Key: 10 bits P10 8-bit plain text Initial Permutation 4-bit 4-bit 5-bit 5-bit 8-bit cipher text Initial Permutation 4-bit 4-bit

Left Shift Left Shift

8-bit K1 + F

P8 8-bit K1
Left Shift Left Shift

8-bit K2 + F

8-bit K2 +

P8 8-bit K2

8-bit K1 +

Inverse Initial Perm. 8-bit cipher text

Inverse Initial Perm. 8-bit plain text

AOT

Week 5: Block Ciphers

Data Encryption Standard (DES) Triple-DES (3-DES) Modes of Operation Advanced Encryption Standards (AES)

AOT

Multiple Encryption with DES: Double DES

Clear a replacement for DES was needed Double DES
C=EK2(EK1(P)) P=DK1(DK2(C))

Needs to be Non-idenpotent
No K3 such that C = EK2(EK1(P)) = EK3(P)

Subject to meet-in-the-middle attack

Given (P,C) Find X = EK1(P) for all possible K1 Find Y = DK2(C) for all possible K2 X=Y means K1 and K2 are the keys Complexity is 256 = 2 x 255

AOT

Multiple Encryption with DES: Triple-DES with Two-Keys

2 keys with E-D-E sequence

C = EK1(DK2(EK1(P))) If K1=K2 then can work with single DES
Attack Complexity 2112

3 keys with E-D-E

C = EK3(DK2(EK1(P))) PGP, S/MIME

Standardized in ANSI X9.17 & ISO8732 AOT

Modes of Operation
Block ciphers encrypt fixed size blocks
DES encrypts 64-bit blocks, with 56-bit key What if arbitrary amount of information needs to encrypted

ANSI X3.106-1983 Modes of Operation

Electronic Codebook Book (ECB) Cipher Block Chaining (CBC) Cipher Feed Back (CFB) Output Feed Back (OFB) Counter (CTR)

AOT

Modes of Operation: Electronic Codebook Book (ECB)

AOT

Modes of Operation: Electronic Codebook Book (ECB)

Message is broken into independent blocks
Each block is encrypted independently Each block is a value which is substituted by Ci Ci = DESK1 (Pi)

Usage: secure transmission of single block of info needs to be sent (e.g., a session key) Repetitions in message may show in ciphertext
E.g., graphics or messages that change very little

AOT

Modes of Operation: Cipher Block Chaining (CBC)

AOT

Modes of Operation: Cipher Block Chaining (CBC)

Idea: make the ciphertext dependent on all blocks before it
Message is broken into blocks Each previous cipher blocks is chained with current plaintext block, hence name Ci = DESK1(Pi XOR Ci-1) C-1 = IV (use Initial Vector (IV) to start process)

Uses: Bulk data encryption, authentication (email, FTP, web etc)

AOT

Modes of Operation: Cipher Block Chaining (CBC)

Each ciphertext block depends on all message blocks (to provide an avalanche effect)
Change in the message affects all consecutive ciphertext blocks

Need Initial Value (IV) known to sender & receiver

If IV is sent in the clear, an attacker can change bits of the first block, and change IV to compensate IV may be a fixed value (as in EFTPOS) IV may be sent encrypted in ECB mode before rest of message

Last short block

Padding with known non-data value (eg nulls) Pad last block with count of pad size
eg. [ b1 b2 b3 0 0 0 0 5] 3 data bytes, then 5 bytes pad+count

AOT

Modes of Operation Cipher Feed Back (CFB)

AOT

Modes of Operation Cipher Feed Back (CFB)

Idea here is to use the block cipher essentially as a pseudo-random number generator
Message is treated as a stream of bits Added to the output of the block cipher Result is feed back for next stage Ci = Pi XOR DESK1(Ci-1) C-1 = IV

Uses: stream data encryption, authentication Limitations

Errors propagate for several blocks after the error Must use over a reliable network transport layer

AOT

Modes of Operation Output Feed Back (OFB)

AOT

Modes of Operation Output Feed Back (OFB)

When error feedback a problem or where need to encryptions before message is available Generation of the "random" bits is independent of the message being encrypted
Output of cipher is added to message Output is then feedback, feedback is independent of message Ci = Pi XOR Oi Oi= DESK1(Oi-1) O-1 = IV

Uses: stream encryption over noisy channels, bursty traffic Must never reuse the same sequence (Key+IV)

AOT

Modes of Operation Counter (CTR)

AOT

Modes of Operation Counter (CTR)

Similar to OFB but encrypts counter value rather than any feedback value
Can do parallel encryptions Random access to encrypted data blocks Ci = Pi XOR Oi Oi = DESK1(i)

Uses: high-speed network encryptions

Good for bursty high speed links

Must never reuse key/counter values AOT

Block Ciphers
Data Encryption Standard (DES) Triple-DES (3-DES) Modes of Operation

AOT

Next: Block and Stream Ciphers

AES Stream Ciphers PRNG Key Management

AOT

Advanced Encryption Standards (AES)

A replacement for DES was needed
have theoretical attacks that can break it have demonstrated exhaustive key search attacks

Triple-DES slow with small blocks US NIST issued call for ciphers in 1997
15 candidates accepted in June 1998 5 were short-listed in August 1999 Rijndael was selected as the AES in October 2000 Issued as FIPS PUB 197 standard in November 2001

AOT

Simplified AES
16-bit Plaintext 16-bit key 3 round with initial add key

AOT

Simplified AES

Nibble Representation

K0 = k0 ..k15 K1 = k16 ..k31 K2 = k32 ..k47

AOT

Simplified AES: Nibble Substitution

AOT

Simplified AES: Shift Row

AOT

Simplified AES: Mix Column

Operations in GF(24)

AOT

Simplified AES: Add Key

AOT

Simplified AES: Key Expansion

Operations are in GF(24)
mod (x4+x+1)

Round Constant RC[i]=xi+2 RC[1]=x3 mod (x4+x+1) =1000 RC[2] = x4 mod (x4+x+1)= RC[2] = x+1 = 0011
0000

AOT

Example Z8
a b mod 8 1, 3, 5, 7 has inverses Unbalanced occurances in multiplication table
Therefore we need GF(23)

Integer 1 2 3 4 5 Ocurrances in Multiplication 4 8 4 12 4

6 7 8 4

AOT

Galois Fields
Finite fields play a key role in cryptography Number of elements in a finite field must be a power of a prime pn Denoted GF(pn)

GF(p) is the set of integers {0,1, , p-1} with arithmetic operations modulo prime p
Form a finite field, since have multiplicative inverses

Hence arithmetic is well-behaved and can do addition, subtraction, multiplication, and division without leaving the field GF(p)

AOT

Example GF(7)
a b mod 7 Inverses Balanced occurrences

AOT

GF(8) = GF(23)
0 000 0 1 001 1 2 010 x 3 011 x+1 4 100 x2 5 101 x2+1 6 110 x2+x 7 111 x2+x+1

23 = 8 elements Polynomial representations What about inverses and occurrances?

AOT

Example GF(23)

AOT

Block Ciphers
Data Encryption Standard (DES) Triple-DES (3-DES) Modes of Operation Advanced Encryption Standards (AES)
Simplified AES

AOT