CN 6122: Advanced Network Security

Lecture 3 – Modern Block

Ciphers: DES, AES, and Triple-
DES

Ketema Adere (PhD)

ketem2006@gmail.com
1
 Outline
• Block cipher design principles
• DES: details and strength
• the AES selection process
• the details of Rijndael – the AES cipher
• Some other modern symmetric block
ciphers: Triple-DES and Blowfish

2
 Modern Block Ciphers
 one of the most widely used types of
cryptographic algorithms
 provide secrecy /authentication services
 a cryptographic checksum to ensure the
contents have not been altered
 to illustrate block cipher design principles
–focus on DES (Data Encryption Standard)
–Advanced Encryption Standard (AES)

3
 Block vs Stream Ciphers
 block ciphers process messages in blocks
(word at a time), each of which is then
en/decrypted
 like a substitution on very big characters
– 64-bits or more
 many current ciphers are block ciphers
 broader range of applications
 stream ciphers process messages a bit or
byte at a time when en/decrypting
4
 Stream Ciphers
• process the message bit by bit (as a stream)
• typically have a (pseudo) random stream key
• combined (XOR) with plaintext bit by bit
• randomness of stream key completely
destroys any statistically properties in the
message
– Ci = Mi XOR StreamKeyi
• what could be simpler!!!!
• but must never reuse stream key
– otherwise can remove effect and recover
5
messages
 Stream Cipher Properties
• some design considerations are:
– long period with no repetitions
– statistically random
– depends on large enough key
– large linear complexity
– correlation immunity
– confusion
– diffusion
– use of highly non-linear boolean functions

6
 Block Cipher Characteristics
• features seen in modern block ciphers
are:
– variable key length / block size / no rounds
– mixed operators, data/key dependent
rotation
– key dependent S-boxes
– more complex key scheduling
– operation of full data in each round
– varying non-linear functions
7
Block Cipher Design Principles
• Most symmetric block ciphers are based on a
Feistel Cipher Structure of 1970’s
• number of rounds
– more is better, exhaustive search best
attack
• function f:
– provides “confusion”, is nonlinear,
avalanche
• key schedule
– complex subkey creation, key avalanche 8
 Block Cipher Principles
 needed since must be able to decrypt
ciphertext to recover messages efficiently
 block ciphers look like an extremely large
substitution
 would need table of 264 entries for a 64-bit
block
 instead create from smaller building blocks
 using idea of a product cipher

9
Ideal Block Cipher

10
 Confusion and Diffusion
 cipher needs to completely obscure
statistical properties of original message
– a one-time pad does this
 more practically Shannon suggested
combining elements to obtain:
– diffusion – dissipates statistical structure of
plaintext over bulk of ciphertext complex
– confusion – makes relationship between
ciphertext and key as complex as possible
 As a result, an attempt of thwart to discover
either ciphertext or key would fail.
11
Claude Shannon: Substitution-
Permutation Ciphers
• Claude Shannon introduced idea of substitution-
permutation (S-P) networks in 1949 paper
• form basis of modern block ciphers
• S-P nets are based on the two primitive
cryptographic operations seen before:
– substitution (S-box)
– permutation (P-box)
• provide confusion and diffusion of message & key

12
 Feistel Cipher Structure
• Horst Feistel devised the feistel cipher
– based on concept of invertible product cipher
• partitions input block into two halves
– process through multiple rounds which
– perform a substitution on left data half
– based on round function of right half & subkey
– then have permutation swapping halves
• implements Shannon’s S-P network concept in
an easily inverted structure.
• One layer of S-boxes and the following P-box are
used to form the round function. 13
 Feistel Network
• Used in DES, IDEA, RC5 (Rivest's Cipher
n. 5), and many other block ciphers.
• Not used in AES
• A Feistel Network is fully specified given
–the block size: n = 2w
–number of rounds: d
–d round functions f1, …, fd: {0,1}w {0,1}w

14
 Feistel Network
L0 R0
• Encryption:
f1(•)
– L1 = R0 R1 = L0 ⊕ f1(R0)
– L2 = R1 R2 = L1 ⊕ f2(R1)
L1 R1 …
– Ld = Rd-1 Rd = Ld-1 ⊕ fd(Rd-1)
f2(•)
• Decryption:
Ld-1 Rd-1 – Rd-1 = Ld Ld-1 = Rd ⊕ fd(Ld)
…
f1(•)
– R0 = L1; L0 = R1 ⊕ f1(L1)

Rd Ld
15
Feistel Cipher Design Principles
 block size
– increasing size improves security, but slows cipher
 key size
– increasing size improves security, makes exhaustive key
searching harder, but may slow cipher
 number of rounds
– increasing number improves security, but slows cipher
 subkey generation
– greater complexity can make analysis harder, but slows
cipher
 round function
– greater complexity can make analysis harder, but slows
cipher
 fast software en/decryption & ease of analysis
– are more recent concerns for practical use and testing 16
 Feistel Cipher Decryption
 The same h/w or s/w is used for both encryption and
decryption, with just a slight change in how the keys are
used

17
 Feistel Cipher Decryption
 The process of decryption with a Feistel cipher is
essentially the same as the encryption process.
 The rule is as follows:
– Use the ciphertext as input to the algorithm, but
use the subkeys Ki in reverse order.
– That is, use Kn in the first round, Kn–1 in the
second round, and so on until K1 is used in the
last round.
 This is a nice feature because it means we need
not implement two different algorithms, one for
encryption and one for decryption.
18
Data Encryption
Standard (DES)

Plaintext
64 bit
DES 64 bit
Ciphertext

Key 56 bit

19
 DES
 most widely used block cipher in world
 adopted in 1977 by NBS (now NIST)
 encrypts 64-bit data using 56-bit key
 has widespread use
 has been considerable controversy over its
security

20
 DES Design Controversy
 although DES standard is public
 was considerable controversy over design
– in choice of 56-bit key (vs Lucifer 128-bit)
– and because design criteria were classified
 subsequent events and public analysis show
in fact design was appropriate
 DES has become widely used, especially
in financial applications

21
 DES Encryption
• Basic process in enciphering a 64-bit data
block using the DES (shown on the left side):
– an initial permutation (IP)
– 16 rounds of a complex key dependent round function
involving substitution and permutation functions
– a final permutation, being the inverse of IP
• Right side shows the handling of the 56-bit
key:
– an initial permutation of the key (PC1) which selects 56-bits
in two 28-bit halves
– 16 stages to generate the subkeys using a left circular shift
and a permutation

22
 DES Features
• Features:
–Block size = 64 bits
–Key size = 56 bits (in reality, 64 bits, but
8 are used as parity-check bits for error
control, see next slide)
–Number of rounds = 16
–16 intermediary keys, each 48 bits

23
 Key length in DES
• In the DES specification, the key length is 64 bit: 8
bytes; in each byte, the 8th bit is a parity-check bit

1 2 3 4 5 6 7 ... 57 58 59 60 61 6263 64
8

first 7 bits 7 bits

Parity-check bits

Each parity-check bit is the XOR of the

9
previous 7 bits 24
 DES Rounds
 There are two inputs to the encryption function:
 plaintext (64 bits in length) and
 key (56 bits in length)

25
 DES: Details
• IP(x) = L0R0
• Li = Ri-1
• Ri = Li-1 ⊕ f(Ri-1, Ki)
……
• y = IP-1(R16L16)
Note: IP means Initial
Permutation
 first step of the data computation
 IP reorders the input data bits
 even bits to LH half, odd bits to RH
half
 quite regular in structure (easy in h/w) 26
 Initial Permutation (IP)
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

• Table specifies the input permutation on a 64-bit block.

• The meaning is as follows:
• The first bit of the output is taken from the 58th bit of the input;
the second bit from the 50th bit, and so on, with the last bit of the
output taken from the 7th bit of the input.
• This information is presented as a table for ease of presentation: it is a
12
vector, not a matrix. 27
 DES Rounds
• IP(x) = L0R0
• Li = Ri-1
• Ri = Li-1 ⊕ f(Ri-1, Ki)
• y = IP-1(R16L16)

• Note that, as usual:

– R16 = L15 ⊕ f(R15, K16)
– L16 = R15
• … but they are switched in the
pre-output IP-1 means Inverse
Initial Permutation
y
28
 Final Permutation (IP-1)
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
 The final permutation is the inverse of the initial
permutation; the table is interpreted similarly.
• That is, the output of the Final Permutation has bit 40 of
the preoutput block as its first bit, bit 8 as its second bit,
and so on, until bit 25 of the preoutput block is the last
bit of the output. 29
 DES Round Structure
• uses two 32-bit L & R halves, as for any Feistel cipher
can describe as:
Li = Ri–1 and Ri = Li–1 xor F(Ri–1, Ki)
• takes 32-bit R half and 48-bit subkey and:
– expands R to 48-bits using perm E
– adds to subkey
– passes through 8 S-boxes to get 32-bit result
– finally permutes this using 32-bit perm P

30
 DES Round i
32 bit 32 bit

• Li = Ri-1 Li-1 Ri-1

• Ri = Li-1 ⊕ f(Ri-1, Ki) 48 bit

f(•) Ki
32 bit

Li Ri
32 bit 32 bit

31
 DES “f(•)” Function
 E is an expansion function
which takes a block of 32
bits as input and produces a
block of 48 bits as output

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 C1 C2 C3 C4 C5 C6 C7 C8
24 25 26 27 28 29 Fixed permutation
28 29 30 31 32 1 function
16 bits appear twice, in the
expansion 32
 Substitution Boxes S
• have eight S-boxes which map 6 to 4 bits
• each S-box is actually 4 little 4 bit boxes
– outer bits 1 & 6 (row bits) select one rows
– inner bits 2-5 (col bits) are substituted
– result is 8 lots of 4 bits, or 32 bits
• row selection depends on both data & key
– feature known as autoclaving (autokeying)
• example:
S(18 09 12 3d 11 17 38 39) = 5fd25e03

33
 S-boxes (…)
• S-boxes are the only non-linear elements in DES design
 Each of the unique selection
functions S1,S2,...,S8, takes a 6- B (6 bit) S-Box C (4 bit)
bit block as input and yields a
4-bit block as output 8 S-Box

• S = matrix 4x16, values from 0 to 15

• B (6 bit long) = b1b2b3b4b5b6

– b1b6  r = row of the matrix (2 bits: 0,1,2,3)

– b2b3b4b5  c = column of the matrix (4 bits:0,1,…15)

• C (4 bit long) = Binary representation of S(r, c)

34
 Example (S1)

Row 1 3 7 15 Column
#
# 0
2 …
1

2
3

Example:

C=7=0111

Another example: B=011011, C=? 35

 DES Key Schedule
• forms subkeys used in each round
• consists of:
– initial permutation of the key (PC1) which
selects 56-bits in two 28-bit halves
– 16 stages consisting of:
• selecting 24-bits from each half
• permuting them by PC2 for use in function f,
• rotating each half separately either 1 or 2
places depending on the key rotation
schedule K
36
 DES Key Generation (K1 – K16)
64 bit key (including parity-
check bits)
28 bits
28 bits

Matrix PC-1 and PC-2 are

Ci=LSi(Ci-1) given by the standard (see
Di=LSi(Di-1) next slide)
Ki=PC-2(CiDi) 48 bits
LS=Left Shift
-shift one position if
i=1,2,9 or 16
-shift two positions
otherwise
37
DES Permuted Choice 1 and 2 (PC-1,
PC-2)

Left
57 49 41 33 25 17 9
Parity-check bits (namely,
1 58 50 42 34 26 18
bits 8,16, 4,32,40,48,56,64)
10 2 59 51 43 35 27
are not chosen, they do not
19 11 3 60 52 44 36
appear in PC-1
Right
63 55 47 39 31 23 15
7 62 54 46 38 30 22
14 6 61 53 45 37 29
14 17 11 24 1 5 3 28
21 13 5 28 20 12 4
15 6 21 10 23 19 12 4
26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40
PC-2 selects the 48-bit
51 45 33 48 44 49 39 56
subkey for each round from
34 53 46 42 50 36 29 32
the 56-bit key-schedule state
38
 DES Decryption
• decrypt must unwind steps of data computation
• with Feistel design, do encryption steps again
• Decryption uses the same algorithm as
encryption, except that the subkeys K1, K2,…K16
are applied in reversed order
• using subkeys in reverse order (K16 … K1)
• note that IP undoes final FP step of encryption
• 1st round with K16 undoes 16th encrypt round
• ….
• 16th round with K1 undoes 1st encrypt round
• then final FP undoes initial encryption IP
• thus recovering original data value 39
 Avalanche Effect
• key desirable property of encryption
algorithm
• where a change of one input or key
bit results in changing approx half
output bits
• making attempts to “home-in” by
guessing keys impossible
• DES exhibits strong avalanche
40
 Strength of DES – Key Size
• 56-bit keys have 256 = 7.2 x 1016 values
• brute force search looks hard
• recent advances have shown is possible
– in 1997 on Internet in a few months
– in 1998 on dedicated h/w (EFF) in a few days
– in 1999 above combined in 22hrs!
• still must be able to recognize plaintext
• now considering alternatives to DES

41
Strength of DES – Timing Attacks
• attacks actual implementation of cipher
• use knowledge of consequences of
implementation to derive knowledge of
some/all subkey bits
• specifically use fact that calculations can
take varying times depending on the value of
the inputs to it
• particularly problematic on smartcards

42
 Strength of DES – Analytic Attacks
• now have several analytic attacks on DES
• these utilise some deep structure of the
cipher
– by gathering information about encryptions
– can eventually recover some/all of the sub-key
bits
– if necessary then exhaustively search for the rest
• generally these are statistical attacks
• include
– differential cryptanalysis
– linear cryptanalysis
– related key attacks 43
 Advanced Encryption
Standard (AES)

 AES includes three block Ciphers: AES uses 128-, 192- or 256-bit
keys to encrypt and decrypt data. 44
 Origins: AES
• clear a replacement for DES was needed
– have theoretical attacks that can break it
– have demonstrated exhaustive key search
attacks
• can use Triple-DES – but slow with small
blocks
• US NIST issued call for ciphers in 1997
• 15 candidates accepted in Jun 98
• 5 were shortlisted in Aug-99
• Rijndael was selected as the AES in Oct-2000
• issued as FIPS PUB 197 standard in Nov-2001 45
 AES
• The AES candidates are the latest generation
of block ciphers, and now we see a significant
increase in the block size:
– from the old standard of 64-bits up to 128-bits;
and keys from 128 to 256-bits.
• In part this has been driven by the public
demonstrations of exhaustive key searches of DES.
• Whilst triple-DES is regarded as secure and well
understood, it is slow, especially in s/w.

46
 AES Requirements
• private key symmetric block cipher
• 128-bit data, 128/192/256-bit keys
• stronger & faster than Triple-DES
• active life of 20-30 years (+ archival use)
• provide full specification & design details
• both C & Java implementations
• NIST have released all submissions &
unclassified analyses

47
 AES Evaluation Criteria
• initial criteria:
– security – effort to practically cryptanalyse
– cost – computational
– algorithm & implementation
characteristics
• final criteria
– general security
– software & hardware implementation ease
– implementation attacks
– flexibility (in en/decrypt, keying, other
factors) 48
 AES Shortlist
• after testing and evaluation, shortlist in
Aug-99:
– MARS (IBM) - complex, fast, high security margin
– RC6 (USA) - v. simple, v. fast, low security margin
– Rijndael (Belgium) - clean, fast, good security
margin
– Serpent (Euro) - slow, clean, v. high security margin
– Twofish (USA) - complex, v. fast, high security margin
• then subject to further analysis & comment
• saw contrast between algorithms with
– few complex rounds verses many simple rounds
– which refined existing ciphers verses new 49
proposals
 The AES Cipher - Rijndael
• designed by Rijmen-Daemen in Belgium
• has 128/192/256 bit keys, 128 bit data
• an iterative rather than feistel cipher
– treats data in 4 groups of 4 bytes
– operates an entire block in every round
• designed to be:
– resistant against known attacks
– speed and code compactness on many CPUs
– design simplicity

50
 Rijndael
• processes data as 4 groups of 4 bytes (state)
• has 9/11/13 rounds in which state undergoes:
– byte substitution (1 S-box used on every byte)
– shift rows (permute bytes between groups/columns)
– mix columns (subs using matrix multipy of groups)
– add round key (XOR state with key material)
• initial XOR key material & incomplete last round
• all operations can be combined into XOR and
table lookups - hence very fast & efficient

51
Rijndael

52
 Byte Substitution
• a simple substitution of each byte
• uses one table of 16x16 bytes containing a
permutation of all 256 8-bit values
• each byte of state is replaced by byte in row (left 4-
bits) & column (right 4-bits)
– eg. byte {95} is replaced by row 9 col 5 byte
– which is the value {2A}
• S-box is constructed using a defined transformation
of the values in GF(28)
• designed to be resistant to all known attacks

53
 Shift Rows
• a circular byte shift in each each
– 1st row is unchanged
– 2nd row does 1 byte circular shift to left
– 3rd row does 2 byte circular shift to left
– 4th row does 3 byte circular shift to left
• decrypt does shifts to right
• since state is processed by columns,
this step permutes bytes between the
columns 54
 Mix Columns
• each column is processed separately
• each byte is replaced by a value dependent
on all 4 bytes in the column
• effectively a matrix multiplication in GF(28)
using prime poly m(x) =x8+x4+x3+x+1

55
 Add Round Key
• XOR state with 128-bits of the round key
• again processed by column (though
effectively a series of byte operations)
• inverse for decryption is identical since
XOR is own inverse, just with correct
round key
• designed to be as simple as possible

56
AES Round

57
 AES Key Expansion
• takes 128-bit (16-byte) key and expands
into array of 44/52/60 32-bit words
• start by copying key into first 4 words
• then loop creating words that depend on
values in previous & 4 places back
– in 3 of 4 cases just XOR these together
– every 4th has S-box + rotate + XOR constant
of previous before XOR together
• designed to resist known attacks

58
 AES Decryption
• AES decryption is not identical to
encryption since steps done in reverse
• but can define an equivalent inverse
cipher with steps as for encryption
– but using inverses of each step
– with a different key schedule
• works since result is unchanged when
– swap byte substitution & shift rows
– swap mix columns & add (tweaked) round key

59
 Implementation Aspects
• can efficiently implement on 8-bit
CPU
– byte substitution works on bytes using a table
of 256 entries
– shift rows is simple byte shifting
– add round key works on byte XORs
– mix columns requires matrix multiply in GF(28)
which works on byte values, can be simplified
to use a table lookup

60
 Implementation Aspects
• can efficiently implement on 32-bit
CPU
– redefine steps to use 32-bit words
– can precompute 4 tables of 256-words
– then each column in each round can be
computed using 4 table lookups + 4 XORs
– at a cost of 16Kb to store tables
• designers believe this very efficient
implementation was a key factor in its
selection as the AES cipher

61
 differences between DES and AES
encryption

DES AES
Developed 1977 2000
Key Length 56 bits 128, 192, or 256 bits
Symmetric block Symmetric block
Cipher Type
cipher cipher
Block Size 64 bits 128 bits
Security Proven inadequate Considered secure

62
 Contemporary
Symmetric Ciphers

63
 Triple DES
• Clear a replacement for DES was
needed
– theoretical attacks that can break it
– demonstrated exhaustive key search attacks
• AES is a new cipher alternative
• prior to this alternative was to use multiple
encryption with DES implementations
• Triple-DES is the chosen form
64
 Why Triple-DES?
• Why not Double-DES?
– NOT same as some other single-DES use, but
have
• meet-in-the-middle attack
– works whenever use a cipher twice
– since X = EK1[P] = DK2[C]
– attack by encrypting P with all keys and store
– then decrypt C with keys and match X value
– can show takes O(256) steps

65
 Triple DES (Triple Data Encryption
Algorithm)
• Use three different keys
– Encrypt: C = EK3 [ DK2 [ EK1 [P] ] ]
– Decrypt: P = DK1 [ EK2 [ DK3 [C] ] ]
• The standard specifies three keying options:
1) Keying option 1: All three keys are independent.
2) Keying option 2: K1 and K2 are independent, and K3 = K1.
3) Keying option 3: All three keys are identical, i.e. K1 = K2 = K3.
• Using keying option 1: the key space is 56 x 3 = 168 bits
• No known practical attack against it.
• Many protocols/applications use 3DES (example PGP)
– The electronic payment industry uses Triple DES and continues to
develop and promulgate standards based upon it (e.g. EMV,
Europay-Visa-Mastercard).
 Triple DES (…)
• Question: if we use three completely different keys K1 ≠ K2
≠ K3 …
– Encrypt: C = EK3 [ DK2 [ EK1 [P] ] ]
– Decrypt: P = DK1 [ EK2 [ DK3 [C] ] ]

• … will the effective strength be that of 56x3= 168 bits?

• Keying option 2 provides less security than option 1, with 2 × 56 =
112 key bits. However, this option is stronger than double DES (with
K1 and K2), because it protects against meet-in-the-middle attacks.
– Note that this option is susceptible to certain chosen-plaintext or
known-plaintext attacks, and thus it is designated by NIST to have
only 80 bits of real security
• Keying option 3 is equivalent to DES, with only 56 key
bits. This option provides backward compatibility with
DES.
 Triple-DES with Two-Keys
• hence must use 3 encryptions
– would seem to need 3 distinct keys
• but can use 2 keys with E-D-E sequence
– C = EK1[DK2[EK1[P]]]
– nb encrypt & decrypt equivalent in security
– if K1=K2 then can work with single DES
• standardized in ANSI X9.17 & ISO8732
• no current known practical attacks

68
 Triple-DES with Three-Keys
• although are no practical attacks on two-key Triple-
DES have some indications
• can use Triple-DES with Three-Keys to avoid even
these
– C = EK3[DK2[EK1[P]]]
• has been adopted by some Internet applications, eg PGP,
S/MIME
• Triple-DES with two keys is a popular alternative to single-
DES, but suffers from being 3 times slower to run.
• Although there are no practical attacks, have some
indications of attack approaches.
• Hence some are now adopting Triple-DES with three keys for
greater security.
69
 Blowfish
• a symmetric block cipher designed by
Bruce Schneier in 1993/94
• characteristics
– fast implementation on 32-bit CPUs
– compact in use of memory
– simple structure eases
analysis/implemention
– variable security by varying key size
• has been implemented in various products
70
 Blowfish Key Schedule
• uses a 32 to 448 bit key
• used to generate
– 18 32-bit subkeys stored in K-array Kj
– four 8x32 S-boxes stored in Si,j
• key schedule consists of:
– initialize P-array and then 4 S-boxes using pi
– XOR P-array with key bits (reuse as needed)
– loop repeatedly encrypting data using current P &
S and replace successive pairs of P then S values
– requires 521 encryptions, hence slow in rekeying
71
 Blowfish: Discussion
• key dependent S-boxes and subkeys,
generated using cipher itself, makes
analysis very difficult
• changing both halves in each round
increases security
• provided key is large enough, brute-
force key search is not practical,
especially given the high key
schedule cost
72
 Blowfish Encryption
• uses two primitives: addition & XOR
• data is divided into two 32-bit halves L0 &
R0
for i = 1 to 16 do
Ri = Li-1 XOR Pi;
Li = F[Ri] XOR Ri-1;
L17 = R16 XOR P18;
R17 = L16 XOR i17;
• where
F[a,b,c,d] = ((S1,a + S2,b) XOR S3,c) +
S4,a 73
Thank You!
74