Transcript a(x) - University of South Carolina

CSCE 715:
Network Systems Security
Chin-Tser Huang
[email protected]
University of South Carolina
After DES…

More symmetric encryption algorithms


Triple-DES
Advanced Encryption Standards
01/28/2009
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
01/28/2009
3
Why Triple-DES?

Double-DES may suffer from meet-in-themiddle attack





works whenever use a cipher twice
assume C = EK2[EK1[P]], so X = EK1[P] =
DK2[C]
given a known pair (P, C), attack by encrypting P
with all keys and store
then decrypt C with keys and match X value
can be shown that this attack takes O(256) steps
01/28/2009
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
01/28/2009
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
01/28/2009
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
01/28/2009
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
01/28/2009
8
AES Evaluation Criteria

Initial criteria




security – effort to practically cryptanalyze
cost – computational
algorithm & implementation characteristics
Final criteria




general security
software & hardware implementation ease
implementation attacks
flexibility (in en/decrypt, keying, other factors)
01/28/2009
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


few complex rounds verses many simple rounds
refined existing ciphers verses new proposals
01/28/2009
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
01/28/2009
11
Abstract Algebra Background



Group
Ring
Field
01/28/2009
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
01/28/2009
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
01/28/2009
14
Field



A set of numbers with two operations
 integral domain
 multiplicative inverse: aa-1 = a-1a= 1
Infinite field if infinite number of
elements
Finite field if finite number of
elements
01/28/2009
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


01/28/2009
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


01/28/2009
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


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
01/28/2009
18
Modulo 8 Example
01/28/2009
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
Two numbers are called relatively prime if
they have no common factors (except 1)

e.g. 8 and 15 relatively prime as GCD(8,15) = 1
01/28/2009
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



R = A mod B
A = B, B = R
return A
01/28/2009
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


GF(p)
GF(2n)
01/28/2009
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


have multiplicative inverses
Hence arithmetic is “well-behaved” and can
do addition, subtraction, multiplication, and
division without leaving the field GF(p)
01/28/2009
23
Arithmetic in GF(7)
01/28/2009
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
01/28/2009
25
Polynomial Arithmetic

Can compute using polynomials

Several alternatives available



ordinary polynomial arithmetic
poly arithmetic with coords mod p
poly arithmetic with coords mod p and
polynomials mod M(x)
01/28/2009
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
01/28/2009
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

01/28/2009
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
01/28/2009
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
01/28/2009
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

can extend Euclid’s Inverse algorithm to find
01/28/2009
31
Arithmetic in GF(23)
01/28/2009
32
AES Cipher – 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
01/28/2009
33
AES Encryption and Decryption
01/28/2009
34
AES Data Structure
01/28/2009
35
AES Encryption Round
01/28/2009
36
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)
01/28/2009
37
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
01/28/2009
38
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
01/28/2009
39
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
01/28/2009
40
AES Key Expansion



Take 128/192/256-bit 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
01/28/2009
41
AES Decryption


AES decryption is not identical to encryption
because steps are 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


swap byte substitution & shift rows
swap mix columns and add (tweaked) round key
01/28/2009
42
Implementation Aspects

Can efficiently implement on 8-bit CPU




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
01/28/2009
43
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
01/28/2009
44
Next Class


Confidentiality of symmetric encryption
Read Chapters 7, 8, 9
01/28/2009
45