Transcript 4-More-on-Sym

3DES and Block Cipher Modes of
Operation
CSE 651: Introduction to Network
Security
Abstract
• We will discuss
– 2DES and 3DES
– AES (Advanced Encryption Standard)
– How to use block ciphers?
– RC4: a widely used stream cipher
– Problems with WEP’s use of RC4
2
Multiple Encryption with DES
• DES is not secure enough.
• The once large key space, 256, is now too small.
• In 2001, NIST published the Advanced Encryption
Standard (AES) as an alternative.
• But users in commerce and finance are not ready
to give up on DES.
• Solution: to use multiple DES with multiple keys
3
Double-DES
• Consider 2-DES with two keys:
C = EK2(EK1(P))
• Decryption:
P = DK1(DK2(C))
• Key length: 56 x 2 = 112 bits
• This should have thwarted brute-force attacks?
• Wrong!
4
Meet-in-the-Middle Attack on 2DES
• 2-DES:
• So,
C = EK2(EK1(P))
X = EK1(P) = DK2(C)
• Given a known pair (P, C), attack as follows:
– Encrypt P with all 256 possible keys for K1.
– Decrypt C with all 256 possible keys for K2.
– If EK1’(P) = DK2’(C), try the keys on another (P’, C’).
– If works, (K1’, K2’) = (K1, K2) with high probability.
– Takes O(256) steps; not much more than attacking 1-DES.
5
Triple DES with Two Keys
• A straightforward implementation would be:
C = EK1(EK2(EK1(P)))
• In practice: C = EK1(DK2(EK1(P)))
– Also referred to as EDE encryption
• Reason: if K1=K2, then 3DES = 1DES. Thus, a 3DES
software can be used as a single-DES.
• Standardized in ANSI X9.17 & ISO8732
• No current known practical attacks
– What about the meet-in-the-middle attack?
6
Meet-in-the-Middle Attack on 3DES
K1
P
E
K2
A
D
K1
B
E
C
1. For each possible key for K1, encrypt P to produce a
possible value for A.
2. Using this A, and C, attack the 2DES to obtain a pair of
keys (K2, K1’).
3. If K1’ = K1, try the key pair (K1, K2) on another (C’,P’).
4. If it works, (K1, K2) is the key pair with high probability.
5. It takes O(255 x 256) = O(2111) steps on average.
7
Triple DES with Three Keys
• Encryption: C = EK3(DK2(EK1(P))).
• If K1 = K3, we have 3DES with 2 keys.
• If K1 = K2 = K3, we have the regular DES.
• So, 3DES w/ 3keys is backward compatible with
3DES w/ 2 keys and with the regular DES
• Some internet applications have adopted 3DES
with three keys.
– E.g. PGP and S/MIME.
8
Finite Fields
Some mathematics used in AES
Group
 A group, denoted by (G, ), is a set G with a
binary operation : G  G  G such that
1. a (b c)  ( a b) c (associative)
2.  e  G s.t. x  G, e x  x e  x (identity)
3. x  G,  y  G s.t. x y  y x  e (inverse)
 A group (G, ) is abelian if x, y  G, x y  y x.
 Examples: ( Z ,  ), (Q,  ), (Q \ {0}, ), ( R, ),
( R \ {0}, ), ( Z n , ), ( Z n* , ), where n is a positive
integer.
The Group ( Z n , )
 Z n  0, 1, 2, ..., n  1
 For a, b  Z n , we define a  b  a  b mod n
 For example, in Z10 ,
5  8  3, 9  9  8.
0  a  a for every a  Z10 ; 0 is the identity element.
Every a  Z10 has an inverse, namely 10  a.
So, the inverse of 5 is 5, the inverse of 3 is 7.
We write the inverse of a as  a.
The Group ( Z n*, )
 Z n*   x  Z n : gcd( x, n )  1
 For a, b  Z n* , we define a  b  a  b mod n
 For example, in Z1*0  1,3,7,9
3  7  1, 9  9  1.
1  a  a for every a  Z10* ; 1 is the identity element.
Every a  Z10 has an inverse.
E.g., the inverse of 3 is 7, the inverse of 9 is 9.
We write the inverse of a as a 1.
Field
 A field, denoted by (F , , ), is a set F with two
binary operations,  and , such that
1. ( F ,  ) is an abelian group (with identity 0).
2. ( F \ {0}, ) is an abelian group (with identy 1).
3. For all elements a  F , 0  a  a  0  0.
3. x, y , z  F , x  ( y  z )  x  y  x  z (distributive).
 Example fields: (Q, , ), ( R, , ).
 ( Z , , ) is not a field.
 For any prime p, ( Z p , , ) is a field, often denoted as Fp .
The Field F2
 There are only two numbers : 0 and 1.
 Addition, substraction and multiplication are as below:
 0 1
0 0 1
1 1 0
 0 1
0 0 1
1 1 0
 Note: addition = substraction = XOR.
 Just call it modulo-2 arithmetic.
 0 1
0 0 0
1 0 1
Polynomials over a field
 Q[ x ]  set of all polynomials with coefficients in Q.
 F [ x ]  set of all polynomials with coefficients in F ,
where F is a field.
 Fp [ x ]  set of all polynomials with coefficients in Fp ,
where p is a prime.
 F2 [ x ]  set of all polynomials with coefficients in F2 .
Addition & multiplication of polynomials
 Consider F2 [ x].
 For A( x), B( x)  F2 [ x], define A( x)+B( x) and
A( x)  B( x) in a straightforward way.
 Example: A( x)  x 3  x  1, B ( x)  x 2  x
A( x)  B( x)  x 3  x 2  (1  1) x  1  x3  x 2  1.
A( x)  B( x)  x  x  x  (1  1) x  x
5
4
3
2
 x5  x 4  x3  x
 (F2 [ x], +, ) is not a field, because any polynomial of
degree  1 does not have a multiplicative inverse.
Finite fields (Galois fields)
 Let p ( x )  F2 [ x ] be a fixed irreducible polynomial.
 A( x ) mod p( x ) = remainder of A( x ) divided by p ( x ).
 Define F2 [ x ] p( x )   A( x ) mod p( x ) : A( x )  F2 [ x ]
 For A( x ), B( x )  F2 [ x ] p( x ), define
A( x )  B ( x ) = A( x )  B ( x ) mod p ( x )
A( x )  B ( x ) = A( x )  B ( x ) mod p ( x )
 ( F2 [ x ] p( x ), , ) is a field, denoted as GF(2 ),
n
where n is the degree of p ( x ).
Galois field GF(2n )
 GF(2n ) has 2n elements.
 Each element is a polynomial of degree  n,
with coefficients in F2  0,1.
 Think of each element/polynomial as a bit string of
length n, and vice versa.
 Thus, if n  8, then GF(28 ) consists of all ploynomials
of degree less than 8, or all bit strings of length 8.
e.g.,
x 6  x 5  x 2  1  01100101
AES: Advanced Encryption
Standard
AES: Advanced Encryption Standard
• In1997, NIST began the process of choosing a
replacement for DES and called 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 allows various block lengths.
• But AES allows only one block size: 128 bits.
20
Modulo-2 Arithmetic
 There are only two numbers : 0 and 1.
 Addition, substraction and multiplication are as below:
 0 1
0 0 1
1 1 0
 0 1
0 0 1
1 1 0
 Note: addition = substraction = XOR.
 0 1
0 0 0
1 0 1
Byte-oriented operations
Each byte is viewed as a polynomial of degree  7.
Suppose:
a  10001001  x 7  x 3  1  A( x).
b  10000010  x 7  x  B( x).
Addition and substraction are simply bitwise XOR:
a  b  10001001  10000010  00001011  A( x)  B( x).
a  b  10001001  10000010  00001011  A( x)  B( x).
22
Byte-oriented operations
Multiplication: "regular" polynomial multiplication
modulo a fixed modulus P( x), where
P( x)  x8  x 4  x3  x  1  100011011.
a  b  A( x)  B( x) mod P( x)
 x14  x10  x8  x 7  x 4  x mod P( x)
 x 6  x5  x 4  x3  x 2  x  1
a  b  10001001  10000010 mod 100011011
= 100010110010010 mod 100011011
 01111111
23
Byte-oriented operations
For any byte a (viewed as a polynomial), there is
a unique byte b (also viewed as a polynomial) such that
a  b  1.
This element b is called the inverse of a, and is
denoted by a 1.
Mathematically, the set of all polynomials of degrees  7
forms a field, GF(28 ), under the operation of addition and
multiplication mod P( x), where P( x) is a fixed modulus.
24
Structure of Rijndael
N b : block size (number of words). For AES, N b  4.
N k : key length (number of words).
N r : number of rounds, depending on N b , N k .
Assume: N b  4, N k  4, N r  10.
state: a variable of 4 words, holding the data block,
viewed as a 4  4 matrix of bytes; each column is a word.
Key schedule: 11 round keys key0 , key1 , , key10
computed from the main key k .
25
Rijndael algorithm  input: plaintext m,
1
2
3
4
5
6
7
8
9
10
11
key k 
state  m
AddKey( state, key0 )
for i  1 to N r  1 do
SubBytes(state)
ShiftRows(state)
Mixcolumns(state)
AddKey( state, keyi )
SubBytes(state)
ShiftRows(state)
AddKey( state, key N r )
return(state)
26
Figure 5.1 AES Encryption and Decryption
27
AddKey(state, keyi )
state  state  keyi
28
SubBytes(state)
For each byte z in the state matrix,
substitute z with SRD ( z )  Az 1  b, where
10001111 
11000111 
11100011 
11110001 
A  

11111000


 01111100 
 00111110 
 00011111 


and
1 
1 
0
0
b 
0
1 
1 
0
 
29
That is, treat z as an element in GF(28 ).
Find its multiplicative inverse z 1 in GF(28 ).
Now treat z 1 as a vector of 0/1.
Multiply A with z 1 , and add the result to b.
If z 1   z0 z1 z2 z3 z4 z5 z6 z7  , b   b0b1b2b3b4b5b6b7  , and
SRD ( z )   z0 z1z2 z3 z4 z5 z6 z7  , then
zi  zi  zi  4  zi  5  zi  6  zi  7  bi
The indices i  k shoud be interpreted as i  k mod8.
30
The function SRD ( z )  Az 1  b is Rijndael's S-box.
It can be specified as a table (Table 5.4 of Stallings).
31
ShiftRows(state)
Left-shift row i circularly by i bytes, 0  i  3.
a

e

i

m
b
f
j
c
g
k
n
o
d a b c d
 

h  f g h e

l  k l i j
 

p  p m n o 
32
MixColumns(state)
Operates on each column of the state matrix.
View each column a  (a0 , a1 , a2 , a3 ) as a
polynomial with coefficients in GF(28 ) :
a ( x )  a3 x 3  a2 x 2 +a1 x  a0
A fixed polynomial: c( x)  03 x 3  01x 2 +01x  02.
The MixColumns operation maps each column
a( x)
a( x)  c( x) mod (x 4  1)
33
Rijndael Decryption
Each step of Rijndael encryption is invertible.
34
Rijndael key schedule
Assume: N b  4, N k  4, N r  10.
The secret key key, having 4 words, is expanded to 44 words.
Every four words are used as a round key.
ExpKey[0..43] : an array of words.
Initialization: ExpKey[0..3]  key.
For 4  j  43, ExpKey[ j ]
 ExpKey[ j  4]  f j ( ExpKey[ j  1]) if j mod 4  0

else
 ExpKey[ j  4]  ExpKey[ j  1]
f j : (a0 , a1 , a2 , a3 ) (SRD (a1 )  RC[ j / 4],
SRD (a2 ), SRD ( a3 ), SRD ( a0 )).
Where SRD is as in SubBytes, and RC[i ]  x i 1 mod P ( x ).
35
Modes of Operations
How to use a block cipher?
• Block ciphers encrypt fixed size blocks
– E.g. DES encrypts 64-bit blocks
• We need some way to encrypt arbitrary
amounts of data
– E.g. a message of 1000 bytes
• NIST defines five ways to do it
– Called modes of operations
– Including block and stream modes
37
Five Modes of Operation
– Electronic codebook mode (ECB)
– Cipher block chaining mode (CBC) – most
popular
– Output feedback mode (OFB)
– Cipher feedback mode (CFB)
– Counter mode (CTR)
38
Electronic Code Book (ECB)
• The plaintext is broken into blocks, P1, P2, P3, ...
• Each block is encrypted independently of the other
blocks
Ci = EK(Pi)
• For a given key, this mode behaves like we have a
gigantic codebook, in which each plaintext block has
an entry, hence the name Electronic Code Book
39
Remarks on ECB
• Strength: it’s simple.
• Weakness:
– Repetitive information contained in the
plaintext may show in the ciphertext, if aligned
with blocks.
– If the same message (e.g., your SSN) is
encrypted (with the same key) and sent twice,
their ciphertexts are the same.
• Typical application: secure transmission of short
pieces of information (e.g. an encryption key)
40
Cipher Block Chaining (CBC)
 The plaintext is broken into blocks: P1 , P2 , P3 , ...
 Each plaintext block is XORed  chained  with the previous
ciphertext block before encryption (hence the name):
Ci  E K  Ci 1  Pi 
C0  IV
 Use an Initial Vector  IV  to start the process.
 Decryption : Pi  Ci 1  D K (Ci )
 Application : general block-oriented transmission.
41
Cipher Block Chaining (CBC)
42
Remarks on CBC
• The same key is used for all blocks.
• A ciphertext block depends on all blocks before it.
• So, repeated plaintext blocks are encrypted
differently.
• Initialization Vector (IV)
– Must be known to both the sender & receiver
– Typically, IV is either a fixed value
– Or is sent encrypted in ECB mode before the rest of
message.
43
Message Padding
• The last plaintext block may be short of a
whole block and needs padding:
• Possible padding:
–
–
–
–
Known non-data values (e.g. nulls)
Or a number indicating the size of the pad
Or a number indicating the size of the plaintext
The last two schemes may require an extra block.
44
Cipher feedback mode (basic version)
•
•
•
•
Plaintext blocks: p1, p2, …
Key: k
Basic idea: construct key stream k1, k2, k3, …
Encryption:
c0  IV

ki  Ek (ci 1 ), for i  1

ci  pi  ki , for i  1
45
Cipher Feedback (CFB) Mode
 The plaintext is divided into segments of s bits
(where s  block-size): P1, P2 , P3 , P4 , 
 Encryption is used to generate a sequence of keys,
each of s bits: K1 , K 2 , K3 , K 4 , 
 The ciphertext is C1 , C2 , C3 , C4 , , where
Ci  Pi  Ki
 How to generate the key stream?
46
Generating Key Stream for CFB
 The input to the block cipher is a shift register x;
its value at stage i is denoted as xi .
 Initially, x1  an initial vector (IV).
For i  1, xi  shift-left-s -bits(xi 1 ) Ci 1.
 Then, Ki  s-most-significant-bits(E K ( xi )).
47
Encryption in CFB Mode
48
Decryption in CFB Mode
 Generate key stream K1 , K 2 , K3 , K 4 , 
the same way as for encryption.
 Then decrypt each ciphertext segment as:
Pi  Ci  K i
49
Remark on CFB
•
•
•
•
The block cipher is used as a stream cipher.
Appropriate when data arrives in bits/bytes.
s can be any value; a common value is s = 8.
A ciphertext segment depends on the current and
all preceding plaintext segments.
• A corrupted ciphertext segment during
transmission will affect the current and next
several plaintext segments.
– How many plaintext segments will be affected?
50
Output Feedback (OFB) Mode
 Very similar to Cipher Feedback in structure.
 But K i 1 rather than Ci 1 is fed back to the next stage.
 As in CFB, the input to the block cipher is a shift
register x; its value at stage i is denoted as xi .
 Initially, x1  an initial vector (IV).
For i  1, xi  shift-left-s -bits(xi 1 ) K i 1.
 Then, K i  s -most-significant-bits(E K ( xi )).
51
Cipher Feedback
Output Feedback
52
Remark on OFB
• The block cipher is used as a stream cipher.
• Appropriate when data arrives in bits/bytes.
• Advantage:
– more resistant to transmission errors; a bit error in a ciphertext
segment affects only the decryption of that segment.
• Disadvantage:
– Cannot recover from lost ciphertext segments; if a ciphertext
segment is lost, all following segments will be decrypted
incorrectly.
• IV should be generated randomly each time and sent with
the ciphertext.
53
Counter Mode (CTR)
• A counter T is initialized to some IV and then
incremented by 1 for each subsequent plaintext
block.
• Encryption:
T1 = IV
Ti = Ti-1 + 1
Ci = Pi XOR EK(Ti)
54
Remark on CTR
• Strengthes:
– Needs only the encryption algorithm (so do CFB and
OFB)
– Fast encryption/decryption; blocks can be processed
(encrypted or decrypted) in parallel; good for high
speed links
– Random access to encrypted data blocks
• As in OFB, IV should not be reused.
55
Stream Ciphers
Stream Cipher Diagram
57
Stream Ciphers
 Typically, process the plaintext byte by byte.
 So, the plaintext is a stream of bytes: P1 , P2 , P3 , 
 Use a key K as the seed to generate a sequence of
pseudorandom bytes (keystream): K1 , K 2 , K 3 , 
 The ciphertext is C1 , C2 , C3 , C4 , , where
Ci  Pi  K i
 Various stream ciphers differ in the way they
generate keystreams.
58
Stream Ciphers
 For a stream cipher to be secure, the keystream
should have a large period, and
should be as random as possible, each of the 256
values appearing about equally often.
 The same keystream must not be reused. That is,
the input key K must be different for each plaintext.
59
The RC4 Stream Cipher
• Designed by Ron Rivest in 1987 for RSA
Security.
• Kept as a trade secret until leaked out in 1994.
• The most popular stream cipher.
• Simple and fast.
• With a 128 bits key, the period is > 10100 .
• Used in the SSL/TLS standards (for secure Web
communication), IEEE 802.11 wireless LAN
standard, Microsoft Point-to-Point Encryption,
and many others.
60
RC4
 Two vectors of bytes:
 S [0], S [1], S [2], , S[255]
 T [0], T [1], T [2], , T [255]
 Key: variable length, from 1 to 256 bytes
 Initialization:
1. S [i ]  i, for 0  i  255
2. T [i ]  K [i mod key-length], for 0  i  255
(i.e., fill up T [0..255] with the key K repeatedly.)
61
RC4: Initial Permutation
 Initial Permutation of S:
j0
for i  0 to 255 do
j  ( j  S[i]  T [i] ) mod 256
Swap S[i], S[ j ]
 This part of RC4 is generally known as the
Key Scheduling Algorithm (KSA).
 After KSA, the input key and the temporary
vector T will no longer be used.
62
RC4: Key Stream Generation
 Key stream generation:
i, j  0
while (true)
i  ( i  1 ) mod 256
j  ( j  S[i] ) mod 256
Swap S[i], S[ j ]
t  ( S[i]  S [ j ] ) mod 256
k  S[t ]
output k
63
Security of RC4
• The keystream generated by RC4 is biased.
– The second byte is biased toward zero with high
probability.
– The first few bytes are strongly non-random and leak
information about the input key.
• Defense: discard the initial n bytes of the keystream.
– Called “RC4-drop[n-bytes]”.
– Recommended values for n = 256, 768, or 3072 bytes.
• Efforts are underway (e.g. the eSTREAM project) to
develop more secure stream ciphers.
64
Problems with WEP’s
use of RC4
• WEP is a protocol using RC4 to encrypt packets for
transmission over IEEE 802.11 wireless LAN.
• WEP requires each packet to be encrypted with a
separate RC4 key.
• The RC4 key for each packet is a concatenation of a
24-bit IV (initialization vector) and a 40 or 104-bit longterm key.
RC4 key: IV (24) Long-term lkey (40 or 104 bits)
65
802.11 frames using WEP
Header IV
l
Packet
ICV
FCS
encrypted
• ICV: integrity check value
• FCS: frame check sequence
• Both use CRC32
66
• Fluhrer, Mantin, and Shamir showed that:
• If the same secret key is used with numerous IVs,
and the attacker can obtain the first word of RC4
output (keystream) corresponding to each IV, then
he can construct the secret key with little effort.
• The first word is known for many plaintext packets.
• Recall: Ciphertext = plaintext XOR keystream
• So, the first word of RC output (keystream) can be
obtained.
67
• Tews, Weinmann, and Pyshkin wrote an
article, “Breaking 104 bit WEP in less than
60 seconds,” discussing how to discover
the RC4 key by analyzing the easily
identified ARP packets.
• ARP: Address Resolution Protocol.
68