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
09/05/2013
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
09/05/2013
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
09/05/2013
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 is compatible with single DES
Standardized in ANSI X9.17 & ISO8732
No current known practical attacks
09/05/2013
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
09/05/2013
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
09/05/2013
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
09/05/2013
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)
09/05/2013
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
09/05/2013
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 on an entire block in every round
resistant against known attacks
speed and code compactness on many CPUs
design simplicity
Use finite field
09/05/2013
11
Abstract Algebra Background



Group
Ring
Field
09/05/2013
12
Group



A set of elements or “numbers”
With a binary operation whose result is also
in the set (closure)
Obey the 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
09/05/2013
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
09/05/2013
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
09/05/2013
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


09/05/2013
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


09/05/2013
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
09/05/2013
18
Modulo 8 Example
09/05/2013
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
09/05/2013
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
09/05/2013
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)
09/05/2013
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)
09/05/2013
23
Arithmetic in GF(7)
09/05/2013
24
Finding Multiplicative Inverses

By extending Euclid’s algorithm
gcd(a, b) = d = ax + by
a = q1b + r1
r1 = ax1 + by1
b = q2r1 + r2
r2 = ax2 + by2
r1 = q3r2 + r3
r3 = ax3 + by3
……
rn-2 = qnrn-1 + rn
Can derive
ri = ri-2 – ri-1qi
And
xi = xi-2 – qixi-1
09/05/2013
rn = axn + byn
yi = yi-2 – qiyi-1
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)
09/05/2013
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
09/05/2013
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

09/05/2013
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
Polynomial arithmetic modulo an irreducible
polynomial forms a field
09/05/2013
29
Polynomial GCD

Can find greatest common divisor for polynomials
 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
09/05/2013
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
09/05/2013
31
Arithmetic in GF(23)
09/05/2013
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
09/05/2013
33
AES Encryption and Decryption
09/05/2013
34
AES Data Structure
09/05/2013
35
AES Encryption Round
09/05/2013
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)
09/05/2013
37
Byte Substitution Rationale



S-box is designed to be resistant to known
cryptanalytic attacks
The Rijndael developers sought a design that
has a low correlation between input bits and
output bits and the property that the output
is not a linear mathematical function of the
input
Nonlinearity is due to the use of the
multiplicative inverse
09/05/2013
38
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
09/05/2013
39
Shift Row Transformation
09/05/2013
40
Shift Row Rationale
 More substantial than it may first appear
 The State, as well as the cipher input and output,
is treated as an array of four 4-byte columns
 On encryption, the first 4 bytes of the plaintext
are copied to the first column of State, and so on
 The round key is applied to State column by
column
 Thus, a row shift moves an individual byte from one
column to another, which is a linear distance of a
multiple of 4 bytes
 Shift row ensures that the 4 bytes of one column
are spread out to four different columns
09/05/2013
41
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
09/05/2013
42
MixColumn Transformation
09/05/2013
43
Mix Columns Rationale


Coefficients of a matrix based on a linear
code with maximal distance between code
words ensures a good mixing among the
bytes of each column
The mix column transformation combined
with the shift row transformation ensures that
after a few rounds all output bits depend on
all input bits
09/05/2013
44
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
but ensured to affect every bit of State
09/05/2013
45
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
09/05/2013
46
AES Key Expansion
09/05/2013
47
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



use inverses of each step
But with a different key schedule
Works since result is unchanged when


swap byte substitution & shift rows
swap mix columns and add (tweaked) round key
09/05/2013
48
AES Example
09/05/2013
49
Avalanche Effect of AES
09/05/2013
50
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
09/05/2013
51
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
09/05/2013
52
Next Class


Confidentiality of symmetric encryption
Read Chapter 14
09/05/2013
53