CM30173: Cryptography\reserved@d =[@let@token art II
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
Part II
Private-key cryptography: block ciphers
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
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
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
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
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
Early timeline
Early 1970’s: IBM starts to develop a system for
encrypting ATM data.
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
Early timeline
Early 1970’s: IBM starts to develop a system for
encrypting ATM data.
1973: National Bureau of Standards (NBS) puts
out a call for submissions for cryptosystems. 1974:
NBS repeats call for submissions. IBM submits the
Feistel cipher Lucifer.
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
Early timeline
Early 1970’s: IBM starts to develop a system for
encrypting ATM data.
1973: National Bureau of Standards (NBS) puts
out a call for submissions for cryptosystems. 1974:
NBS repeats call for submissions. IBM submits the
Feistel cipher Lucifer.
1974/75: The National Security Agency (NSA)
provides technical advice to IBM and changes are
made to the algorithm.
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
Early timeline
Early 1970’s: IBM starts to develop a system for
encrypting ATM data.
1973: National Bureau of Standards (NBS) puts
out a call for submissions for cryptosystems. 1974:
NBS repeats call for submissions. IBM submits the
Feistel cipher Lucifer.
1974/75: The National Security Agency (NSA)
provides technical advice to IBM and changes are
made to the algorithm.
1975: NBS publishes the algorithm for comment.
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
Early timeline
Early 1970’s: IBM starts to develop a system for
encrypting ATM data.
1973: National Bureau of Standards (NBS) puts
out a call for submissions for cryptosystems. 1974:
NBS repeats call for submissions. IBM submits the
Feistel cipher Lucifer.
1974/75: The National Security Agency (NSA)
provides technical advice to IBM and changes are
made to the algorithm.
1975: NBS publishes the algorithm for comment.
1977: The Data Encryption Standard (DES)
adopted for “unclassified” applications.
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
Definition of a Feistel cipher:
Definition (Feistel cipher)
A Feistel cipher is an iterated cipher in which the
state on round i is divided into two halves of equal
length: Li and Ri.
The round function g has the form
g(Li!1, Ri!1, ki) = (Li, Ri) and is computed:
Li = Ri!1
Ri = Li!1 ! f(Ri!1, ki)
for some function f .
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
Diagram of a Feistel cipher
Plaintext
Ciphertext
L0 R0
L1 R1
LNr!1 RNr!1
LNrRNr
f
f
f
k1
k2
kNr
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
Encryption in a Feistel cipher:
Algorithm
Inputs: plaintext block (length m), (k1, . . . , kNr)
Output: ciphertext block
Initialise state:
L0 = left m/2 bits of plaintext block
R0 = right m/2 bits of plaintext block
for round i = 1 to Nr do
Call the round function:
Li = Ri!1
Ri = Li!1 ! f(Ri!1, ki)
end do
Notice the output order of the state pair:
ciphertext block = RNrLNr
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
DES the Feistel cipher
Cryptosystem (DES)
DES is a 16 round Feistel cipher where:
m = 64, Li and Ri are bitstrings of length 32.
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
DES the Feistel cipher
Cryptosystem (DES)
DES is a 16 round Feistel cipher where:
m = 64, Li and Ri are bitstrings of length 32.
k is 56 bits long, from this sixteen 48 bit round
keys are produced consisting of a selection of bits
of k, permuted.
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
DES the Feistel cipher
Cryptosystem (DES)
DES is a 16 round Feistel cipher where:
m = 64, Li and Ri are bitstrings of length 32.
k is 56 bits long, from this sixteen 48 bit round
keys are produced consisting of a selection of bits
of k, permuted.
There is a fixed initial permutation
L0R0 = IP (x) before the first round.
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
DES the Feistel cipher
Cryptosystem (DES)
DES is a 16 round Feistel cipher where:
m = 64, Li and Ri are bitstrings of length 32.
k is 56 bits long, from this sixteen 48 bit round
keys are produced consisting of a selection of bits
of k, permuted.
There is a fixed initial permutation
L0R0 = IP (x) before the first round.
The inverse permutation IP!1(R16L16) is applied
after the last round.
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
DES the Feistel cipher
Cryptosystem (DES)
DES is a 16 round Feistel cipher where:
m = 64, Li and Ri are bitstrings of length 32.
k is 56 bits long, from this sixteen 48 bit round
keys are produced consisting of a selection of bits
of k, permuted.
There is a fixed initial permutation
L0R0 = IP (x) before the first round.
The inverse permutation IP!1(R16L16) is applied
after the last round.
f : {0, 1}32 ” {0, 1}48 # {0, 1}32.
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
DES the Feistel cipher
Cryptosystem (DES)
DES is a 16 round Feistel cipher where:
m = 64, Li and Ri are bitstrings of length 32.
k is 56 bits long, from this sixteen 48 bit round
keys are produced consisting of a selection of bits
of k, permuted.
There is a fixed initial permutation
L0R0 = IP (x) before the first round.
The inverse permutation IP!1(R16L16) is applied
after the last round.
f : {0, 1}32 ” {0, 1}48 # {0, 1}32.
f consists of a substitution (S-box) followed by a
fixed permutation.
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
DES f function
Expand Ri!1 to 48 bits and x-or with ki:
state = E(Ri!1) ! ki
Apply substitutions to state: map 6-bit substrings
to 4-bit substrings
Permute state: state = P (state)
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
Diagram of DES f function
Ri!1 E k
i
32
32
32
48
4848
8 ” 6 bits
8 ” 4 bits
P
S1 S2 S3 S4 S5 S6 S7 S8
Permutation
Substitutions
f(Ri!1, ki)
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
Expansion, permutation and S-boxes
Expansion: E
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
Permutation: P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
Example S-box:
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
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)
Private-key cryptography: block ciphers
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