CM30173: Cryptography\reserved@d =[@let@token art II
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Part II
Private-key cryptography: block ciphers
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
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
The S-box and the permutation
z 0 1 2 3 4 5 6 7
!S(z) 4 1 E 8 D 6 2 B
. . .
8 9 A B C D E F
F C 9 7 3 A 5 0
z 1 2 3 4 5 6 7 8
!P (z) 1 5 9 13 2 6 10 14
. . .
9 10 11 12 13 14 15 16
3 7 11 15 4 8 12 16
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Encryption
We will encrypt using the key
k = 1110 0111 0110 0111 1001 0000 0011 1101
First we define a very simple key schedule. Let kr be 16
consecutive bits of k starting at bit 4r # 3. That is:
k1 = 1110 0111 0110 0111
k2 = 0111 0110 0111 1001
k3 = 0110 0111 1001 0000
k4 = 0111 1001 0000 0011
k5 = 1001 0000 0011 1101
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Using the SPN
Exercise (hints available!): start to encrypt the
plaintext:
x = 0100 1110 1010 0001
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 1
Plaintext: state = 0100 1110 1010 0001
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 1
Plaintext: state = 0100 1110 1010 0001
k1 = 1110 0111 0110 0111
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 1
Plaintext: state = 0100 1110 1010 0001
k1 = 1110 0111 0110 0111
X-or: state = 1010 1001 1100 0110
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 1
Plaintext: state = 0100 1110 1010 0001
k1 = 1110 0111 0110 0111
X-or: state = 1010 1001 1100 0110
Substitutions: state = 1001 1100 0011 0010
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 1
Plaintext: state = 0100 1110 1010 0001
k1 = 1110 0111 0110 0111
X-or: state = 1010 1001 1100 0110
Substitutions: state = 1001 1100 0011 0010
Permutation: state = 1100 0100 0011 1010
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 2
state = 1100 0100 0011 1010
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 2
state = 1100 0100 0011 1010
k1 = 0111 0110 0111 1001
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 2
state = 1100 0100 0011 1010
k1 = 0111 0110 0111 1001
X-or: state = 1011 0010 0100 0011
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 2
state = 1100 0100 0011 1010
k1 = 0111 0110 0111 1001
X-or: state = 1011 0010 0100 0011
Substitutions: state = 0111 1110 1101 1000
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 2
state = 1100 0100 0011 1010
k1 = 0111 0110 0111 1001
X-or: state = 1011 0010 0100 0011
Substitutions: state = 0111 1110 1101 1000
Permutation: state = 0111 1110 1100 1010
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 3
state = 0111 1110 1100 1010
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 3
state = 0111 1110 1100 1010
k1 = 0110 0111 1001 0000
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 3
state = 0111 1110 1100 1010
k1 = 0110 0111 1001 0000
X-or: state = 0001 1001 0101 1010
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 3
state = 0111 1110 1100 1010
k1 = 0110 0111 1001 0000
X-or: state = 0001 1001 0101 1010
Substitutions: state = 0001 1100 0110 1001
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 3
state = 0111 1110 1100 1010
k1 = 0110 0111 1001 0000
X-or: state = 0001 1001 0101 1010
Substitutions: state = 0001 1100 0110 1001
Permutation: state = 0101 0110 0010 1001
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 4
state = 0101 0110 0010 1001
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 4
state = 0101 0110 0010 1001
k1 = 0111 1001 0000 0011
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 4
state = 0101 0110 0010 1001
k1 = 0111 1001 0000 0011
X-or: state = 0010 1111 0010 1010
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Round 4
state = 0101 0110 0010 1001
k1 = 0111 1001 0000 0011
X-or: state = 0010 1111 0010 1010
Substitutions: state = 1110 0000 1110 1001
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Output
state = 1110 0000 1110 1001
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Output
state = 1110 0000 1110 1001
k1 = 1001 0000 0011 1101
CM30173:
Cryptography
Part II
Outline
Combining basic
building blocks
Substitution-
permutation
networks
Example SPN
Attacks on SPNs
Output
state = 1110 0000 1110 1001
k1 = 1001 0000 0011 1101
Ciphertext: state = 0111 0000 1101 0100
Private-key cryptography: block ciphers
Outline
Combining basic building blocks
Substitution-permutation networks
Example SPN
Attacks on SPNs