symetric : - stream ciphor - block ciphor –> AES
plan : today: AES, next lecture: Digital Signature, Hashing, MAC, last lecture: black box and white box fuzzing.
Symmetric key cryptographer
- stream ciphers: handles one bit at a time.
x_i(input) -->key(eg. XOR)-->y_i(output)
- block cipher: divide the message into fixed size blocks
[ / / ] 128bits input--->key(AES)----->[ / /]128bit output
AES(advanced encryption standard)
Why are we even looking at AES? - it is the most widely used encryption algorithm in the world.
History of AES:
DES - Data Encryption standard is proposed by IBM.
1997- contest generated the next generation of symmetric key algorthrm NIST
1999- selected 5 finalists.
2000 - ‘Rijndael’ two belgian cryptographer(Joan daemen, vincent Rijmen) was choosen by NIST. 2001 - standarized
AES was developed in collaboration with researchers and was analysed by thousands of researchers and users.
128 bits == 16 bytes
padding scheme, PKCS
prcess: key addition->block substitution->shift rows->mix cols -> key addition(k rounds) last round: ->key addition->byte substitution->shift rows->key addition
key addition: data state XOR key data state(data after some rounds)
the number of rounds depends on the key.
AES-256 bit encryption is considered to be “solid”
Byte substitutio: A0 ,…..A15 16 8-bit data blok | | | | s-box [ byte substitution layer ] | | | | B0 B15
B_i = S(A_i)
byte substitution used proper finite fields—Galor’s Fields
shift rows: mix cols: provides diffusiong which ensures that change in single bit in the state influence all the text
To understand S-boxes and overall AES, we have to revisit finite fields
Finite fields(galois Field): is a finite set of elements , it has 2 operations: +,*
for +, 0 is identity for *, 1 is identity
it forms an additve group with ‘+’ with identity element 0.
it forms an multiplicative group(excluding 0) with ‘*’ with indentity elelment 1.
when two group operations are mixed, distributivity holds. : $a(b+c) = ab+ac$
R - field (+,*), Cryptography - finite fields ( has finite number of elements)
finite fields only exists if they have p^m elements where m is a positive integer and p is a prime number.
order of a froup
Example: There is a finite field with 11 element GF(11^1) There is a finite field with 27 element GF(3^3) There is a finite field with 11 element GF(11^1)
two type of finite fields Gf(p^m):
- m=1 ,GF(P) , prime fields
- m>1, GF(p^m), extention fields
prime fields, GF(P),
how do you compute in extension fields?
elements of GF(2^m) are polynomials of the form $a_{m-1}x^{m-1}+a_{m-2}x^{m-2}+…..+a_0x^0$
Interesting thing about the polynomials are their coefficient.
$a_i \in GF(2) = {0,1}$
Ex: GF(2^3) , what is the order of GF(2^3).
Enumerate all the polynomial we are going to have: A(x) (a2,a1,a0) GF(2^3)={
0, (0,0,0)
1, (0,0,1)
x, (0,1,0)
x+1, (0,1,1)
x^2, (1,0,0)
x^2+1, (1,0,1)
X^2+x, (1,1,0)
X^2+x+1,(1,1,1) } --- addition: in GF(2) ,addition and subtraction are identical. a_i \in GF(2), addtion/subtraction of co-effiennt mean the same in GF(2) A(x)+B(x) = C(x)
ci=ai+bi mod 2
multiplication:
\[A(x)B(x) =(X^2+x+1)(X^2+1)\]\(= X^4+x^3+x^2+X^2+x+1 mod2\) \(= x^4+x^3+x+1 = C(x)\)
C(x) is not in the finite field.
GF(7): 3*4 = 12 mod 7 = 5 mod 7
solution: Reduce C(x) modulo a polynomial that behave like a prime. “irreducible polynomials” P(x) = amx^m +……a_0x_0 (one degree higher than GF(2^m))
E.g : $GF(2^3)$: P(x) = $x^3+x+1$ : p(x) = $
c(x) = c’(x) mod P(x)
"AES irreducible polynomial"
key addition <--
| |
byte substitution |
| |
shift rows |
| |
mix cols |
| |
-----------------------
|
Byte substitution
|
shift row
|
key addition
|
output
Byte substitute layer of AES S(Ai) = Bi s_box is the non-linear element 8 AES
size of Ai = 8bit 2^8 = 256 distinct element.
s-box:
| | |
Ai--> | GF(2^8) inverse | Affine mapping | Bi
| | |
S-box Ai = 0xC2 (1100 0010) A(x)=x^7 +x^6 +x A-1(x) in GF(2^8) = (2F) = (0010 1111) = x^5 +x^3+x^2+x+1
multiply A(x)*A-1(x) =1 mod p(x)
P(x) for AES = X^8 +X^4+x+1
