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
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Substitution-permutation network
Cryptosystem (SPN)
Let l, m, Nr be positive integers.
!S : {0, 1}
l ! {0, 1}l is an S-box
!P : {1, . . . , lm} ! {1, . . . , lm} is a permutation
P = C = {0, 1}lm
K ” ({0, 1}lm)Nr+1 is the set of all key schedules
that can be derived from an initial key k
For a key schedule (k1, . . . , kNr+1) we encrypt
using an iterated cipher composed of substitution,
permutation and x-or operations.
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Encryption
Algorithm (SPN)
Inputs: plaintext block, !S, !P , (k
1, . . . , kNr+1)
Output: ciphertext block
state = plaintext block
for round r = 1 to Nr ! 1 do
x-or: state = state ” kr
substitutions: apply !S to m strings of l bits of state
permutation: apply !P to lm bits of state
end do
x-or: state = state ” kNr
substitutions: apply !S to m strings of l bits of state
ciphertext block = state ” kNr+1
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Outline
Combining basic building blocks
Substitution-permutation networks
Example SPN
Attacks on SPNs
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Evaluating security of block ciphers
Key size
Block size
Estimated security level
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Computational security against exhaustive
key search
A fixed key size defines an upper bound on the
security of the cipher.
If the key k is a bitstring of length lk then there are
2lk keys.
Given a small number of plaintext-ciphertext pairs
the attack has complexity of 2lk!1 operations.
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Computational security against exhaustive
data analysis
Text dictionary attack: For block size m, if an
attacker has collected 2m plaintext-ciphertext pairs
then they have a complete dictionary of the cipher.
Matching ciphertext attack: If you have
collected 2m/2 blocks you expect to find matching
ciphertext blocks within them.
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
Set up
Chosen plaintext attack
CM30173:
Cryptography
Part II
Attacks on SPNs:
Di!erential
cryptanalysis
Example of di!erential
cryptanalysis
Pseudo-code for
example
Attacks on SPNs:
Linear cryptanalysis
Set up
Chosen plaintext attack
Plaintexts chosen in pairs x, x! such that
x ! x! = x”, a particular plaintext 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
Set up
Chosen plaintext attack
Plaintexts chosen in pairs x, x! such that
x ! x! = x”, a particular plaintext di!erence.
x” is chosen such that, with high probability,
during encryption, a particular state di!erence will
occur at the input to the last round of 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
What are we trying to do?
Objective
Find targeted key bits.
Basic idea
Exploit a situation whereby a particular di!erence
between ciphertexts y” occurs, given a particular
di!erence between plaintexts x”, with a very much
higher probability than is ideal.
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.
Private-key cryptography: block ciphers
Attacks on SPNs: Differential cryptanalysis
Example of differential cryptanalysis
Pseudo-code for example
Attacks on SPNs: Linear cryptanalysis