Transcript After DES…

After DES…
Network Systems Security
Mort Anvari
After DES…

More symmetric encryption algorithms


9/9/2004
Triple-DES
Advanced Encryption Standards
2
Triple DES

Clearly a replacement for DES was
needed




theoretical attacks that can break it
demonstrated exhaustive key search
attacks
Use multiple encryptions with DES
implementations
Triple-DES is the chosen form
9/9/2004
3
Why Triple-DES?

Double-DES may suffer from meet-in-themiddle attack





9/9/2004
works whenever use a cipher twice
assume C = EK2[EK1[P]], so X = EK1[P] =
DK2[C]
attack by encrypting P with all keys and store
then decrypt C with keys and match X value
can show attack takes O(256) steps
4
Triple-DES with Two Keys

Must use 3 encryptions


But can use 2 keys with E-D-E sequence





would seem to need 3 distinct keys
encrypt & decrypt equivalent in security
C = EK1[DK2[EK1[P]]]
if K1=K2 then can work with single DES
Standardized in ANSI X9.17 & ISO8732
No current known practical attacks
9/9/2004
5
Triple-DES with Three Keys


Some proposed attacks on two-key
Triple-DES, although none of them
practical
Can use Triple-DES with Three-Keys to
avoid even these


C = EK3[DK2[EK1[P]]]
Has been adopted by some Internet
applications, e.g. PGP, S/MIME
9/9/2004
6
Origins of
Advanced Encryption Standard






Triple-DES is slow with small blocks
US NIST issued call for ciphers in 1997
15 candidates accepted in Jun 1998
5 were shortlisted in Aug 1999
Rijndael was selected as the AES in Oct 2000
Issued as FIPS PUB 197 standard in Nov 2001
9/9/2004
7
AES Requirements







Private key symmetric block cipher
128-bit data, 128/192/256-bit keys
Stronger and faster than Triple-DES
Active life of 20-30 years (+ archival use)
Provide full specification and design details
Both C and Java implementations
NIST has released all submissions and
unclassified analyses
9/9/2004
8
AES Evaluation Criteria

Initial criteria




security – effort to practically cryptanalyze
cost – computational
algorithm & implementation characteristics
Final criteria




9/9/2004
general security
software & hardware implementation ease
implementation attacks
flexibility (in en/decrypt, keying, other factors)
9
AES Shortlist

Shortlist in Aug 99 after testing and evaluation







MARS (IBM) - complex, fast, high security margin
RC6 (USA) - very simple, very fast, low security margin
Rijndael (Belgium) - clean, fast, good security margin
Serpent (Euro) - slow, clean, very high security margin
Twofish (USA) - complex, very fast, high security margin
Subject to further analysis and comment
Contrast between algorithms with


9/9/2004
few complex rounds verses many simple rounds
refined existing ciphers verses new proposals
10
The Winner - Rijndael



Designed by Rijmen-Daemen in Belgium
Has 128/192/256 bit keys, 128 bit data
An iterative rather than feistel cipher



Designed to be




treats data in 4 groups of 4 bytes
operates an entire block in every round
resistant against known attacks
speed and code compactness on many CPUs
design simplicity
Use finite field
9/9/2004
11
Abstract Algebra Background



Group
Ring
Field
9/9/2004
12
Group



A set of elements or “numbers”
With a binary operation whose result is also
in the set (closure)
Obey following axioms




associative law:
has identity e:
has inverses a-1:
(a.b).c = a.(b.c)
e.a = a.e = a
a.a-1 = e
Abelian group if commutative a.b = b.a
9/9/2004
13
Ring



A set of elements with two operations (addition and
multiplication) which are:
an abelian group with addition operation
multiplication





has closure
is associative
distributive over addition: a(b+c) = ab + ac
Commutative ring if multiplication operation is
commutative
Integral domain if multiplication operation has
identity and no zero divisors
9/9/2004
14
Field



A set of numbers with two operations
 abelian group for addition
 abelian group for multiplication (ignoring 0)
 integral domain
 multiplicative inverse: aa-1 = a-1a= 1
Infinite field if infinite number of elements
Finite field if finite number of elements
9/9/2004
15
Modular Arithmetic


Define modulo operator a mod n to be remainder
when a is divided by n
Use the term congruence for: a ≡ b mod n
when divided by n, a and b have same remainder
 e.g. 100  34 mod 11
b is called the residue of a mod n if 0  b  n-1
 with integers can write a = qn + b


9/9/2004
16
Divisor

A non-zero number b is a divisor of a
if for some m have a=mb (a,b,m all
integers)
That is, b divides a with no remainder
Denote as b|a

E.g. all of 1,2,3,4,6,8,12,24 divide 24


9/9/2004
17
Modular Arithmetic




Can do modular arithmetic with any group of
integers Zn = {0, 1, … , n-1}
Form a commutative ring for addition
With a multiplicative identity
Some peculiarities


9/9/2004
if (a+b)≡(a+c) mod n then b≡c mod n
but (ab)≡(ac) mod n then b≡c mod n only
if a is relatively prime to n
18
Modulo 8 Example
9/9/2004
19
Greatest Common Divisor (GCD)

GCD (a,b) of a and b is the largest number
that divides evenly into both a and b


e.g. GCD(60,24) = 12
It is often desirable to find numbers that are
relatively prime, namely they have no
common factors (except 1)

9/9/2004
e.g. 8 and 15 relatively prime as GCD(8,15) = 1
20
Euclid's GCD Algorithm

Use following theorem


GCD(a,b) = GCD(b, a mod b)
Euclid's Algorithm to compute GCD(a,b)


A=a, B=b
while B>0



9/9/2004
R = A mod B
A = B, B = R
return A
21
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
Known as Galois fields
Denoted GF(pn)
In particular often use the following forms


9/9/2004
GF(p)
GF(2n)
22
Galois Fields GF(p)


GF(p) is 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)
9/9/2004
23
Arithmetic in GF(7)
9/9/2004
24
Finding Multiplicative Inverses

By extending Euclid’s algorithm
1.(A1, A2, A3)=(1, 0, m);
(B1, B2, B3)=(0, 1, b)
2. if B3 = 0
return A3 = gcd(m, b); no inverse
3. if B3 = 1
return B3 = gcd(m, b); B2 = b–1 mod m
4. Q = A3 div B3
5. (T1, T2, T3)=(A1 – Q B1, A2 – Q B2, A3 – Q
B3)
6. (A1, A2, A3)=(B1, B2, B3)
7. (B1, B2, B3)=(T1, T2, T3)
8. goto 2
9/9/2004
25
Polynomial Arithmetic

Can compute using polynomials

Several alternatives available



9/9/2004
ordinary polynomial arithmetic
poly arithmetic with coords mod p
poly arithmetic with coords mod p and
polynomials mod M(x)
26
Ordinary Polynomial Arithmetic



Add or subtract corresponding
coefficients
Multiply all terms by each other
E.g.
let f(x) = x3 + x2 + 2 and g(x) = x2 – x + 1
f(x) + g(x) = x3 + 2x2 – x + 3
f(x) – g(x) = x3 + x + 1
f(x) x g(x) = x5 + 3x2 – 2x + 2
9/9/2004
27
Polynomial Arithmetic with
Modulo Coefficients



Compute value of each coefficient as
modulo some value
Could be modulo any prime
But we are most interested in mod 2
i.e. all coefficients are 0 or 1
3
2, g(x) = x2 + x + 1
 e.g. let f(x) = x + x
f(x) + g(x) = x3 + x + 1
f(x) x g(x) = x5 + x2

9/9/2004
28
Modular Polynomial Arithmetic

Can write any polynomial in the form






f(x) = q(x) g(x) + r(x)
can interpret r(x) as being a remainder
r(x) = f(x) mod g(x)
If no remainder say g(x) divides f(x)
If g(x) has no divisors other than itself and 1
say it is irreducible (or prime) polynomial
Arithmetic modulo an irreducible polynomial
forms a field
9/9/2004
29
Polynomial GCD

Can find greatest common divisor for polys
 c(x) = GCD(a(x), b(x)) if c(x) is the poly of
greatest degree which divides both a(x), b(x)
 can adapt Euclid’s Algorithm to find it:
 EUCLID[a(x), b(x)]
1. A(x) = a(x); B(x) = b(x)
2. if B(x) = 0 return A(x) = gcd[a(x), b(x)]
3. R(x) = A(x) mod B(x)
4. A(x)  B(x)
5. B(x)  R(x)
6. goto 2
9/9/2004
30
Modular Polynomial Arithmetic

Can compute in field GF(2n)





polynomials with coefficients modulo 2
whose degree is less than n
hence must reduce modulo an irreducible poly of
degree n (for multiplication only)
Form a finite field
Can always find an inverse

9/9/2004
can extend Euclid’s Inverse algorithm to find
31
Arithmetic in GF(23)
9/9/2004
32
Rijndael


Process data as 4 groups of 4 bytes (State)
Has 9/11/13 rounds in which state undergoes:






byte substitution (1 S-box used on every byte)
shift rows (permute bytes between groups/columns)
mix columns (subs using matrix multiply of groups)
add round key (XOR state with key material)
Initial XOR key material & incomplete last round
All operations can be combined into XOR and table
lookups, hence very fast and efficient
9/9/2004
33
Rijndael
9/9/2004
34
AES Round
9/9/2004
35
Byte Substitution



A simple substitution of each byte
Uses one table of 16x16 bytes containing a permutation of all
256 8-bit values
Each byte of state is replaced by byte in corresponding row
(left 4 bits) and column (right 4 bits)


eg. byte {95} is replaced by row 9 col 5 byte, which is {2A}
S-box is constructed using a defined transformation of the
values in GF(28)
9/9/2004
36
Shift Rows

Circular byte shift in each row






1st row is unchanged
2nd row does 1 byte circular shift to left
3rd row does 2 byte circular shift to left
4th row does 3 byte circular shift to left
Decryption does shifts to right
Since state is processed by columns, this step
permutes bytes between the columns
9/9/2004
37
Mix Columns



Each column is processed separately
Each byte is replaced by a value
dependent on all 4 bytes in the column
Effectively a matrix multiplication in
GF(28) using prime poly m(x)
=x8+x4+x3+x+1
9/9/2004
38
Add Round Key




XOR state with 128 bits of the round
key
Again processed by column (though
effectively a series of byte operations)
Inverse for decryption is identical since
XOR is own inverse, just with correct
round key
Designed to be as simple as possible
9/9/2004
39
AES Key Expansion



Take 128-bit (16-byte) key and expand into
array of 44/52/60 32-bit words
Start by copying key into first 4 words
Then loop creating words that depend on
values in previous and 4 places back



in 3 of 4 cases just XOR these together
every 4th has S-box + rotate + XOR constant of
previous before XOR together
Designed to resist known attacks
9/9/2004
40
AES Decryption


AES decryption is not identical to encryption
since steps done in reverse
But can define an equivalent inverse cipher
with steps as for encryption



but using inverses of each step
with a different key schedule
Works since result is unchanged when


9/9/2004
swap byte substitution & shift rows
swap mix columns and add (tweaked) round key
41
Implementation Aspects

Can efficiently implement on 8-bit CPU




9/9/2004
byte substitution works on bytes using a
table of 256 entries
shift rows is simple byte shifting
add round key works on byte XORs
mix columns requires matrix multiply in
GF(28) which works on byte values, can be
simplified to use a table lookup
42
Implementation Aspects

Can efficiently implement on 32-bit CPU





redefine steps to use 32-bit words
can precompute 4 tables of 256-words
then each column in each round can be computed
using 4 table lookups + 4 XORs
at a cost of 16Kb to store tables
Designers believe this very efficient
implementation was a key factor in its
selection as the AES cipher
9/9/2004
43
Next Class


Confidentiality of symmetric encryption
Asymmetric encryption: RSA
9/9/2004
44