CM30173: Cryptography\reserved@d =[@let@token art II
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Part II
Private-key cryptography: block ciphers
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
Double-DES?
Security of double-DES
Triple-DES?
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
After DES: Triple DES
Double-DES?
Security of double-DES
Triple-DES?
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES
CM30173:
Cryptography
Part II
The Data
Encryption
Standard (DES)
Feistel ciphers
DES
Security of DES
Modes of operation
Electronic codebook
mode (ECB)
Cipher block chaining
mode (CBC)
Output feedback mode
(OFB)
Cipher feedback mode
(CFB)
Further reading
Cost of attacks
Attack method Data complexity Storage Processing
Known Chosen complexity complexity
Exhaustive precomputation – 1 256 1
Exhaustive search 1 – small 255
Linear cryptanalysis 243 – texts 243
Di!erential cryptanalysis – 247 texts 247
(From Handbook of Applied Cryptography)
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Product cipher
Recall:
Definition (Product)
A product cipher combines two or more components
with the intention of producing a cipher that is more
secure than the basic parts of which it is made.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Some facts
For a key k in the DES keyspace DES encryption
defines a permutation of 64 bits.
There are 256 possible keys and hence up to 256
di!erent permutations.
Given k1, k2 can I find a third key k3 such that
eDESk3 (x) = e
DES
k2
(eDESk1 (x)) ?
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Some facts
For a key k in the DES keyspace DES encryption
defines a permutation of 64 bits.
There are 256 possible keys and hence up to 256
di!erent permutations.
Given k1, k2 can I find a third key k3 such that
eDESk3 (x) = e
DES
k2
(eDESk1 (x)) ?
Theorem (DES is not a group)
The set of 256 permutations defined by the 256 DES
keys is not closed under function composition.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Definition of double-DES
Cryptosystem (Double DES)
Double-DES is a product cipher. Let k1, k2 be DES
keys of length 56 bits, define double DES encryption by:
e(k1,k2)(x) = e
DES
k2
(eDESk1 (x)),
and decryption by:
d(k1,k2)(y) = d
DES
k1
(dDESk2 (y)),
where x, y are of length 64.
The combined key length of (k1, k2) is 112 bits.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Better than DES?
Attack model: known plaintext
Naive exhaustive key search would then take 2112
operations.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Better than DES?
Attack model: known plaintext
Naive exhaustive key search would then take 2112
operations.
However, we can attack the structure of a product
cipher.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
Inputs: x, y = e(k1,k2)(x) = e
DES
k2
(eDESk1 (x))
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
Inputs: x, y = e(k1,k2)(x) = e
DES
k2
(eDESk1 (x))
1 For each key k1 in the DES keyspace calculate
z = eDESk1 (x) and store (z, k1) in table 1, ordered by
z value.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
Inputs: x, y = e(k1,k2)(x) = e
DES
k2
(eDESk1 (x))
1 For each key k1 in the DES keyspace calculate
z = eDESk1 (x) and store (z, k1) in table 1, ordered by
z value.
2 For each key k2 in the DES keyspace calculate
z = dDESk2 (y) and store (z, k2) in table 2, ordered by
z value.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
Inputs: x, y = e(k1,k2)(x) = e
DES
k2
(eDESk1 (x))
1 For each key k1 in the DES keyspace calculate
z = eDESk1 (x) and store (z, k1) in table 1, ordered by
z value.
2 For each key k2 in the DES keyspace calculate
z = dDESk2 (y) and store (z, k2) in table 2, ordered by
z value.
3 Two table entries, (z, k1) and (z, k2), match if they
are
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
Inputs: x, y = e(k1,k2)(x) = e
DES
k2
(eDESk1 (x))
1 For each key k1 in the DES keyspace calculate
z = eDESk1 (x) and store (z, k1) in table 1, ordered by
z value.
2 For each key k2 in the DES keyspace calculate
z = dDESk2 (y) and store (z, k2) in table 2, ordered by
z value.
3 Two table entries, (z, k1) and (z, k2), match if they
are
1 in di!erent tables and
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
Inputs: x, y = e(k1,k2)(x) = e
DES
k2
(eDESk1 (x))
1 For each key k1 in the DES keyspace calculate
z = eDESk1 (x) and store (z, k1) in table 1, ordered by
z value.
2 For each key k2 in the DES keyspace calculate
z = dDESk2 (y) and store (z, k2) in table 2, ordered by
z value.
3 Two table entries, (z, k1) and (z, k2), match if they
are
1 in di!erent tables and
2 have equal z values.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
Inputs: x, y = e(k1,k2)(x) = e
DES
k2
(eDESk1 (x))
1 For each key k1 in the DES keyspace calculate
z = eDESk1 (x) and store (z, k1) in table 1, ordered by
z value.
2 For each key k2 in the DES keyspace calculate
z = dDESk2 (y) and store (z, k2) in table 2, ordered by
z value.
3 Two table entries, (z, k1) and (z, k2), match if they
are
1 in di!erent tables and
2 have equal z values.
4 For each matching pair save the key pair (k1, k2) in
the set of candidate keys.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
5 The candidate keys are all those for which
y = e(k1,k2)(x). You should prove this!
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
5 The candidate keys are all those for which
y = e(k1,k2)(x). You should prove this!
6 In an ideal cipher, with block size 64 bits, if we
select a key (k1, k2) at random we expect to find
that y = e(k1,k2)(x) with probability 1/2
64. Why?
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
5 The candidate keys are all those for which
y = e(k1,k2)(x). You should prove this!
6 In an ideal cipher, with block size 64 bits, if we
select a key (k1, k2) at random we expect to find
that y = e(k1,k2)(x) with probability 1/2
64. Why?
7 The number of candidate key pairs will therefore be
about 2112/264 = 248.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Meet in the middle attack
5 The candidate keys are all those for which
y = e(k1,k2)(x). You should prove this!
6 In an ideal cipher, with block size 64 bits, if we
select a key (k1, k2) at random we expect to find
that y = e(k1,k2)(x) with probability 1/2
64. Why?
7 The number of candidate key pairs will therefore be
about 2112/264 = 248.
8 With high (how high?) probability we find the
correct key by testing each candidate key with a
second plaintext-ciphertext pair.
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Complexity of “meet in the middle attack”
On the problem sheet I ask you to put together the
whole argument and estimate the
data complexity,
processing complexity and
storage complexity,
and hence the cost of the attack. You should conclude
that:
CM30173:
Cryptography
Part II
After DES: Triple
DES
Double-DES?
Security of
double-DES
Triple-DES?
After DES: The
Advanced
Encryption
Standard
A new competition
Rijndael: The chosen
cipher
Security of AES
Complexity of “meet in the middle attack”
On the problem sheet I ask you to put together the
whole argument and estimate the
data complexity,
processing complexity and
storage complexity,
and hence the cost of the attack. You should conclude
that:
Double-DES is essentially no more secure than
DES itself.
Private-key cryptography: block ciphers
After DES: Triple DES
Double-DES?
Triple-DES?
After DES: The Advanced Encryption Standard
A new competition
Rijndael: The chosen cipher
Security of AES