· one of the most significant recent (public) advances in cryptanalysis
· known by NSA in 70's cf DES design
· Murphy, Biham & Shamir published in 90’s
· powerful method to analyse block ciphers
· used to analyse most current block ciphers with varying degrees of success
· DES reasonably resistant to it, cf Lucifer
Linear Cryptanalysis
· another recent development
· also a statistical method
· must be iterated over rounds, with decreasing probabilities
· developed by Matsui et al in early 90's
· based on finding linear approximations
· can attack DES with 243 known plaintexts, easier but still in practise infeasible
Group
· a set of elements or “numbers”
· with some operation whose result is also in the set (closure)
Cyclic Groupa group is cyclic if every element is a power of some fixed element
Ringa set of “numbers” with two operations (addition and multiplication) which form: an abelian group with addition operation
if multiplication operation is commutative, it forms a commutative ring
if multiplication operation has an identity and no zero divisors, it forms an integral domain
Field a set of numbers with two operations which form: abelian group for addition abelian group for multiplication (ignoring 0) ring; have hierarchy with more axioms/laws group -> ring -> field
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 & b have same remainder eg. 100 = 34 mod 11
· is 'clock arithmetic'
· uses a finite number of values, and loops back from either end
· modular arithmetic is when do addition & multiplication and modulo reduce answer
· can do reduction at any point, ie
o a+b mod n = [a mod n + b mod n] mod n
Euclidean Algorithm
an efficient way to find the GCD(a,b)
uses theorem that:
GCD(a,b) = GCD(b, a mod b)
Euclidean Algorithm to compute GCD(a,b) is:
EUCLID(a,b)
1. A = a; B = b 2. if B = 0 return A = gcd(a, b)
3. R = A mod B 4. A = B 5. B = R 6. goto 2
Galois Fields
finite fields play a key role in cryptography
can show 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 fields: GF(p) GF(2n)
Polynomial Arithmetic with Modulo Coefficients
when computing value of each coefficient do calculation modulo some value
forms a polynomial ring
could be modulo any prime
but we are most interested in mod 2
ie all coefficients are 0 or 1
eg. let f(x) = x3 + x2 and g(x) = x2 + x + 1
f(x) + g(x) = x3 + x + 1
f(x) x g(x) = x5 + x2
Origins
clear a replacement for DES was needed
have theoretical attacks that can break it
have demonstrated exhaustive key search
attacks
can use Triple-DES – but slow, has small blocks
US NIST issued call for ciphers in 1997
15 candidates accepted in Jun 98
5 were shortlisted in Aug-99
Triple-DES with Two-Keys
hence must use 3 encryptions
l would seem to need 3 distinct keys
but can use 2 keys with E-D-E sequence
l C = EK1(DK2(EK1(P)))
l nb encrypt & decrypt equivalent in sec.
l if K1=K2 then can work with single DES
standardized in ANSI X9.17 & ISO8732
no current known practical attacks
Triple-DES with Three-Keys
although are no practical attacks on two-key Triple-DES have some indications
can use Triple-DES with Three-Keys to avoid even these C = EK3(DK2(EK1(P)))
has been adopted by some Internet applications, eg PGP, S/MIME
Modes of Operation
· block ciphers encrypt fixed size blocks
o eg. DES encrypts 64-bit blocks with 56-bit key
· need some way to en/decrypt arbitrary amounts of data in practise
· ANSI X3.106-1983 Modes of Use(now FIPS 81)defines 4 possible modes