CM30173: Cryptography\reserved@d =[@let@token art II
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Part II
Private-key cryptography: block ciphers
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Attacks on SPNs: Di!erential cryptanalysis
Example of di!erential cryptanalysis
Pseudo-code for example
Attacks on SPNs: Linear cryptanalysis
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Overview of method
For each tuple (x, x!, y, y!):
1 For each candidate round key kNr+1 partially
decrypt both ciphertexts producing state and
state!.
2 Find the state di!erence state” = state ! state!.
3 If state” = expected di!erence then increment the
counter for this candidate key.
The candidate key with the highest count should have
the correct values for the targeted key bits.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Finding a di!erential trail
How do we find the expected di!erence between state
and state! just before the final S-boxes?
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Finding a di!erential trail
How do we find the expected di!erence between state
and state! just before the final S-boxes?
1 For each S-box consider all possible di!erentials:
(a”, b”) = (input di!erence, output di!erence)
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Finding a di!erential trail
How do we find the expected di!erence between state
and state! just before the final S-boxes?
1 For each S-box consider all possible di!erentials:
(a”, b”) = (input di!erence, output di!erence)
2 Find the propagation ratio, the probability b”
occurs given a”.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Finding a di!erential trail
How do we find the expected di!erence between state
and state! just before the final S-boxes?
1 For each S-box consider all possible di!erentials:
(a”, b”) = (input di!erence, output di!erence)
2 Find the propagation ratio, the probability b”
occurs given a”.
3 Combine high probability di!erentials to make a
di!erential trail.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
An example input di!erence to !S
For example, consider the set of pairs with input
di!erence a! = 1111:
{(a, a ! a!)|a ” {0, 1}4}
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
An example input di!erence to !S
For example, consider the set of pairs with input
di!erence a! = 1111:
{(a, a ! a!)|a ” {0, 1}4}
What happens when we input a, a” to our S-box?
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Example for input di!erence 1111
a a
”
b b
”
b
!
0000 1111 0100 0000 0100
0001 1110 0001 0101 0100
0010 1101 1110 1010 0100
0011 1100 1000 0011 1011
0100 1011 1101 0111 1010
0101 1010 0110 1001 1111
0110 1001 0010 1100 1110
0111 1000 1011 1111 0100
1000 0111 1111 1011 0100
1001 0110 1100 0010 1110
1010 0101 1001 0110 1111
1011 0100 0111 1101 1010
1100 0011 0011 1000 1011
1101 0010 1010 1110 0100
1110 0001 0101 0001 0100
1111 0000 0000 0100 0100
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Example di!erence
0000 0001 0010 0011 0100 0101 0110 0111
0 0 0 0 8 0 0 0
1000 1001 1010 1011 1100 1101 1110 1111
0 0 2 2 0 0 2 2
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Example di!erence
0000 0001 0010 0011 0100 0101 0110 0111
0 0 0 0 8 0 0 0
1000 1001 1010 1011 1100 1101 1110 1111
0 0 2 2 0 0 2 2
The propagation ratio is
count
24
.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Example di!erence
0000 0001 0010 0011 0100 0101 0110 0111
0 0 0 0 8 0 0 0
1000 1001 1010 1011 1100 1101 1110 1111
0 0 2 2 0 0 2 2
The propagation ratio is
count
24
.
Output di!erence 0100 has propagation ratio 0.5
Output di!erences 1010, 1011, 1110, 1111 have
propagation ratio 0.125
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Di!erence distribution table
We can construct a di!erence distribution table
each row represents one of the possible 4 bit input
di!erences
each column one of the 4 bit output di!erences
an element of the table is the number of times the
output di!erence occurred given the input
di!erence
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Di!erence distribution table
We can construct a di!erence distribution table
each row represents one of the possible 4 bit input
di!erences
each column one of the 4 bit output di!erences
an element of the table is the number of times the
output di!erence occurred given the input
di!erence
We will use this to construct our di!erential trail.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Di!erence distribution table
a 0 1 2 3 4 5 6 7 8 9 A B C D E F
0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 2 0 4 2 0 0 4 0 2 0 0 2 0
2 0 0 0 0 0 0 4 0 0 2 4 2 0 2 0 2
3 0 0 0 2 2 2 2 0 2 0 0 0 2 0 0 4
4 0 0 0 2 0 0 2 4 0 2 0 0 6 0 0 0
5 0 0 4 0 0 4 0 0 0 2 2 0 2 0 0 2
6 0 0 0 2 0 0 2 0 0 0 6 0 2 2 2 0
7 0 0 0 4 2 2 0 0 2 2 0 0 0 0 0 4
8 0 0 0 0 0 0 0 4 0 0 0 4 2 2 2 2
9 0 2 2 0 0 2 0 2 2 2 0 0 0 0 4 0
A 0 6 0 0 2 0 4 0 2 0 0 0 0 2 0 0
B 0 0 2 4 0 0 0 2 6 0 0 0 0 2 0 0
C 0 0 2 0 0 0 0 2 2 0 2 6 2 0 0 0
D 0 2 4 0 0 2 0 0 0 2 0 0 0 2 4 0
E 0 6 2 0 2 0 0 2 0 0 0 0 0 4 0 0
F 0 0 0 0 8 0 0 0 0 0 2 2 0 0 2 2
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
But we don’t know the round keys…
Round r:
stater = stater#1 ! k
r
and then apply the substitutions to stater.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
But we don’t know the round keys…
Round r:
stater = stater#1 ! k
r
and then apply the substitutions to stater.
To make a di!erential trail we don’t need kr:
state! = stater ! state
”
r
= (stater#1 ! k
r) ! (state”
r#1 ! k
r)
= stater#1 ! state
”
r#1
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
But we don’t know the round keys…
Round r:
stater = stater#1 ! k
r
and then apply the substitutions to stater.
To make a di!erential trail we don’t need kr:
state! = stater ! state
”
r
= (stater#1 ! k
r) ! (state”
r#1 ! k
r)
= stater#1 ! state
”
r#1
S-box input di!erences on round r
= permuted S-box output di!erences from round r#1
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Example di!erential trail
We can now form a di!erential trail…
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Probability the trail occurs
We used
PR(1111, 0100) =
1
2
once and
PR(0100, 1100) =
3
8
three times hence the propagation ratio of the entire
trail is assumed to be
1
2
!
3
8
“3
=
27
1024
.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Candidate keys
Which bitstrings are candidate keys in this example?
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Candidate keys
Which bitstrings are candidate keys in this example?
Targeted bits: first 8 bits of the final round key.
Candidate keys: partial keys that vary the bits
interacting with the di!erential trail.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Filtering
Not all tuples (x, x”, y, y”) will be useful for this
particular di!erence trail.
We filter our input tuples…
Tuples that survive the filter are called right pairs.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Algorithm (Sketch of di!erential cryptanalysis)
for each tuple (x, x”, y, y”) perform filtering
for each right pair do
for each candidate key k do
x-or: state = y ! k, state” = y” ! k
substitutions: apply !#1
S
to state and state”
compute di!erence: state! = state ! state”
if state! == expected di!erence then
increment counter for k
end if
end do
end do
output candidate key with maximum counter
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Attacks on SPNs: Di!erential cryptanalysis
Example of di!erential cryptanalysis
Pseudo-code for example
Attacks on SPNs: Linear cryptanalysis
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
A related attack is linear cryptanalysis
Objective: Find targeted key bits.
Known plaintext attack: attacker has a set of
plaintext-ciphertext pairs encrypted with the same
key k.
Using probabilistic analysis we find biased linear
approximations for the S-boxes. We construct a
linear approximation, with a large bias, of the SPN
(excepting the final round) in terms of plaintext
bits and state bits.
For each candidate key we partially decrypt each
ciphertext and see if the linear approximation holds
for state, incrementing a counter for the key if it
does.
The candidate key with largest bias (from
|input pairs|/2) should contain the targeted key
bits.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Cost of di!erential cryptanalysis
If p is the propagation ratio of the di!erential trail then
the attack is often successful if the number of tuples
(x, x”, y, y”) is approximately c/p where c is some small
constant.
Cost of linear cryptanalysis
If p is the “bias” of the linear approximation then the
attack is often successful if the number of
plaintext-ciphertext pairs is approximately c/p2 where c
is some small constant.
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Can we protect against these attacks?
It is possible to design S-boxes to reduce the
e!ectiveness of these attacks.
DES was protected against di!erential cryptanalysis
but not linear cryptanalysis.
AES was protected against both attacks.
The attacks are still theoretically possible but
require infeasible quantities of input data.
In the next lecture we will introduce DES which was
designed to withstand di!erential cryptanalysis and is
also one of the most important examples of block
ciphers.
Private-key cryptography: block ciphers
Attacks on SPNs: Differential cryptanalysis
Example of differential cryptanalysis
Pseudo-code for example
Attacks on SPNs: Linear cryptanalysis