IA174: Symmetric Key Encryption and Secrecy III
Block Ciphers: Basics
1/32
Block ciphers: Idea
2/32
Block ciphers: Definition
Definition 1: Block cipher (standard confusing definition)
A block cipher is a symmetric cipher (E, D) defined over the space (K, M, C) in which
M = C. For a block cipher, we denote X = M = C, in which case we say that the
cipher is defined over (K, X).
Typically, for block ciphers we imagine that M (and thus also C) are of the form {0, 1}ℓ
where
ℓ is relatively “small.” (Hundreds of bits.)
3/32
Block ciphers: Definition
Definition 1: Block cipher (standard confusing definition)
A block cipher is a symmetric cipher (E, D) defined over the space (K, M, C) in which
M = C. For a block cipher, we denote X = M = C, in which case we say that the
cipher is defined over (K, X).
Typically, for block ciphers we imagine that M (and thus also C) are of the form {0, 1}ℓ
where
ℓ is relatively “small.” (Hundreds of bits.)
Definition 2: Block cipher (without saying that it is a cipher)
A block cipher (or pseudorandom permutation (PRP)) over a keyspace K and blockspace
X is a tuple (E, D) such that:
• E : K × X → X is a block encryption function, and
• D : K × X → X is a block decryption function,
such that for every key k ∈ K, the function E(k, ·): X → X is a permutation of X
whose inversion is D(k, ·). 3/32
Confusing terminology
Despite the definiton, it is not good to view block ciphers as a special class of ciphers. Rather,
we should view them as a standalone cryptographic primitive from which actual ciphers are
constructed. Analogy with stream ciphers:
basic primitive actual cipher
PRG → stream cipher
block cipher (PRP) → block cipher mode of operation
4/32
Pseudorandom permutations: Idea
5/32
Secure pseudorandom permutations: the attack game
Let E = (E, D) be a block cipher over (K, X). Let Π(X) denote the set of all permutations of
the set X.
An attack game against block cipher (PRP) (E, D) is played as follows:
Stage 1:
• The challenger samples i ∈ {rand, fake}, both uniformly at random. She then proceeds as
follows: According to the outcome, she proceeds as follows:
• If i = rand, the challenger samples f ∈ Π(X) uniformly at random.
• If i = fake,, the challenger samples k ∈ K uniformly at random sets f = E(k, ·).
• Neither i, k or f are revealed to the adversary.
• The adversary computes (possibly in a randomized way) a number or rounds N ∈ N and
sends N to the challenger.
6/32
Secure pseudorandom permutations: the attack game
Let E = (E, D) be a block cipher over (K, X). Let Π(X) denote the set of all permutations of
the set X.
An attack game against block cipher (PRP) (E, D) is played as follows:
Stage 2: For each 1 ≤ i ≤ N:
• The adversary computes a block xi ∈ X. The computation might depend on the whole
past history of the game (i.e. adversary’s queries x1, . . . , xi−1 and challenger’s responses
y1, . . . , yi−1 – the adversary’s analysis is adaptive). It then sends xi to the challenger.
• The challenger computes a response yi = f (xi ) and sends it to the adversary.
Stage 3:
• The adversary outputs a guess g ∈ {rand, fake}.
The adversary wins the game if g = i, otherwise it loses.
6/32
Secure pseudorandom permutations: Formal definition
Definition 3: Advantage against block cipher
The advantage of a PRP adversary A against PRP (block cipher) (E, D) is the quantity
ADVSem((E, D), A) = P(A wins the PRP attack game against (E, D)) −
1
2
.
Definition 4: Secure PRP
We say that a PRP (block cipher) (E, D) is ε-secure (where ε > 0) if for every efficient
PRP adversary it holds ADVSem((E, D), A) ≤ ε.
We say that (E, D) is secure if it is ε-secure secure for a negligible value of ε.
7/32
Pseudorandom permutations: attack game picture
8/32
“OTP” is not a good PRP
9/32
From block ciphers to ciphers: teaser
• How to encode messages longer than a single block?
• To turn a block cipher E into a true cipher, we need to apply E using an appropriate mode.
• Ideally, the mode should be such that we can prove implications of the form
“E is a secure block cipher ⇒ the mode M of E is a secure cipher.”
• Mode of a block cipher will encode many blocks but uses a single key. Hence, block cipher
modes have to be designed so as to remain secure even if the adversary intercepts many
blocks encoded with the same key, or even many plaintext-ciphertext pairs (more on
chosen-plaintext security in the next lesson).
• More on block cipher modes in the next lesson, now just an example of how not to use
BCs.
10/32
ECB mode
11/32
ECB mode
Definition 5: ECB mode
Let E = (E, D) be a block cipher over (K, X), where X = {0, 1}ℓ
. Furthermore, let
n be a number capping the number of blocks a message can consist of. An electronic
codebook (ECB) mode of E is the cipher EECB = (EECB , DECB ) over ({0, 1}≤n·ℓ
, X≤n
, K)
defined as follows:
Given m ∈ {0, 1}≤n·ℓ
and k ∈ K, we compute EECB (k, m) by
• first checking whether len(m) is a multiple of ℓ; if not, we pad m make len(m) is a
multiple of ℓ;
• we then split m into individual blocks of length ℓ (i.e. m = m1 || m2 || · · · || mj ,
where j · ℓ = len(m)), and compute
EECB (k, m) = E(k, m1) || E(k, m2) || · · · || E(k, mj ).
(continuation on the next slide) 11/32
ECB mode
Definition 5: ECB mode
Given c ∈ X≤n
and k ∈ K, we compute DECB (k, c) by splitting c into blocks of length
ℓ (i.e. c = c1 || c2 || · · · || cj , where j · ℓ = len(c)) and compute
DECB (k, c) = D(k, c1) || D(k, c2) || · · · || D(k, cj ).
11/32
How secure is the ECB mode?
Ideally we would like to have:
E is an ε-secure block cipher, for ε negligible
⇓
EECB is a δ-semantically secure cipher, for δ negligible
12/32
ECB mode in pictures
13/32
ECB mode in pictures
Encrypted using the AES block cipher (widely believed to be secure) in ECB mode.
13/32
Design of block ciphers
• Theoretical:
• From secure pseudo-random generators, one can construct, using a rather straightforward
tree-construction secure pseudo-random functions. From these, one can construct, via the
Luby-Rackoff construction secure pseudo-random permutations, aka block ciphers. Details in
(Boneh & Shoup).
• Hence, there exist provably secure block ciphers (assuming certain computational problems
are hard.) However, they are not used in practice (slowness).
• Practical:
• Iterative (round) constructions.
14/32
Iterative block ciphers: general structure
15/32
Iterative block ciphers: design principles
A good block cipher should achieve a high degree of confusion and diffusion (Shannon):
• Confusion: any arithmetic relationships between the plaintext, the ciphertext, and the key
should be as complex as possible. In particular, linearities should be avoided.
16/32
Iterative block ciphers: design principles
A good block cipher should achieve a high degree of confusion and diffusion (Shannon):
• Confusion: any arithmetic relationships between the plaintext, the ciphertext, and the key
should be as complex as possible. In particular, linearities should be avoided.
• Diffusion: statistical regularities of the plaintext should be “uniformly” dissipated over the
ciphertext (and well-mixed with the entropy present in the key). E.g. when a single
plaintext bit changes, about half of the ciphertext bits should change.
16/32
DES: a historical block cipher
• Data Encryption Standard
• A block cipher developed in 1975 at IBM, at the request of the U.S. National Bureau of
Standards (today’s NIST: National Institute of Standards and Technology). The first
standardized and massively used block cipher, though nowadays completely broken.
• A 16-round Feistel network with 56-bit key length and 64-bit block length.
• The design of certain components was kept secret: sepculation about inclusion of
backdoors. Published in 1994. The original design aimed at frustrating differential
cryptanalysis, a technique published only in early 90s.
17/32
DES: a historical block cipher
• Data Encryption Standard
• A block cipher developed in 1975 at IBM, at the request of the U.S. National Bureau of
Standards (today’s NIST: National Institute of Standards and Technology). The first
standardized and massively used block cipher, though nowadays completely broken.
• A 16-round Feistel network with 56-bit key length and 64-bit block length.
• The design of certain components was kept secret: sepculation about inclusion of
backdoors. Published in 1994. The original design aimed at frustrating differential
cryptanalysis, a technique published only in early 90s.
• The greatest weakness of DES: small keyspace. Criticized already at DES publication.
Bruteforceable by a consumer-level hardware since late 1990’s (DES challenge: $250,000
hardware in 1998, $10,000 hardware in 2007).
17/32
DES: a historical block cipher
• Data Encryption Standard
• A block cipher developed in 1975 at IBM, at the request of the U.S. National Bureau of
Standards (today’s NIST: National Institute of Standards and Technology). The first
standardized and massively used block cipher, though nowadays completely broken.
• A 16-round Feistel network with 56-bit key length and 64-bit block length.
• The design of certain components was kept secret: sepculation about inclusion of
backdoors. Published in 1994. The original design aimed at frustrating differential
cryptanalysis, a technique published only in early 90s.
• The greatest weakness of DES: small keyspace. Criticized already at DES publication.
Bruteforceable by a consumer-level hardware since late 1990’s (DES challenge: $250,000
hardware in 1998, $10,000 hardware in 2007).
• Usability of DES infrastructure extended by employing 3-DES:
E3−DES (k, m) = EDES (k3, DDES (k2, EDES (k1, m))), where k = k1 || k2 || k3 is the 168-bit
3-DES key. 3-DES is a respected cipher (requires 2112
steps to bruteforce), but too slow.
In late 1990’s it became obvious that a new standard for block ciphers is needed. NIST
opened a competition for the Advanced Encryption Standard (AES).
17/32
AES: History
• IN 1997, NIST published a call for a new block cipher to become standardized under the
name Advanced Encryption Standard.
• originally 15 submissions, narrowed down to 5 in 1999 following a series of professional
open symposia
• the 5 finalists: MARS, RC6, Rijndael, Serpent, Twofish
• evaluation criteria: both security (the ability to withstand a rigorous cryptanalysis) and
performance
• in 2000, Rijndael (authors: Vincent Rijmen and Joan Daemen) was selected as a winner
18/32
AES: Basics
Three versions with differing keysizes: AES-128, AES-192, AES-256
version key size (bits) block size (bits) no. of rounds
AES-128 128 128 10
AES-192 192 128 12
AES-256 256 128 14
19/32
AES Encryption: Structure
20/32
AES Encryption: Structure (pseudocode)
Algorithm 1: AES-128.
Input: x ∈ {0, 1}128
, k ∈ {0, 1}128
Output: x′
∈ {0, 1}128
.
rk1, rk2, . . . , rk10 ← AES-128-key-schedule(k)
for i ∈ {1, . . . , 10} do
x ← x ⊕ rki ;
x ← SubBytes(x);
x ← ShiftRows(x);
if i < 10 then
x ← MixColumns(x)
return x
All the steps easily invertible (if round keys known) ⇒ decryption.
21/32
AES: representation of x
It is again (cf. ChaCha) convenient to represent the 128-bit vector x passed through AES as a
4x4 matrix of bytes:
x =





x1 x2 x3 x4
x5 x6 x7 x8
x9 x10 x11 x12
x13 x14 x15 x16





,
where each xi ∈ {0, 1}8
.
22/32
AES SubBytes
AES standard defines a non-linear permutation SAES : {0, 1}8
→ {0, 1}8
represented as a
look-up table of 256 entries (analogue of S-boxes in DES). Additional properties of SAES : no
fixed points (SAES (b) ̸= b for all b ∈ {0, 1}8
) and no inverse fixed points (SAES (b) ̸= ¬b for all
b ∈ {0, 1}8
).
x =





x1 x2 x3 x4
x5 x6 x7 x8
x9 x10 x11 x12
x13 x14 x15 x16





⇒ SubBytes(x) =





SAES (x1) SAES (x2) SAES (x3) SAES (x4)
SAES (x5) SAES (x6) SAES (x7) SAES (x8)
SAES (x9) SAES (x10) SAES (x11) SAES (x12)
SAES (x13) SAES (x14) SAES (x15) SAES (x16)





Note that SAES and thus SubBytes() are easily invertible.
23/32
AES SubBytes Table (Dworkin et al., AE standard, NIST FIPS)
24/32
AES ShiftRows
x =





x1 x2 x3 x4
x5 x6 x7 x8
x9 x10 x11 x12
x13 x14 x15 x16





⇒ ShiftRows(x) =





x1 x2 x3 x4
x6 x7 x8 x5
x11 x12 x9 x10
x16 x13 x14 x15





(A linear operation, easily invertible.)
25/32
AES MixColumns
tl;dr: Mixing bits of x in a linear but relatively complex way (provides diffusion).
MixColumns is essentialy a matrix multiplication over the field of bytes: a Galois field of
order 28
.
Let [n] denote a byte (8-bit) representation of number n, e.g. [3] = ”00000011”. Then
MixColumns(x) =





[2] [3] [1] [1]
[1] [2] [3] [1]
[1] [1] [2] [3]
[3] [1] [1] [2]





·





x1 x2 x3 x4
x5 x6 x7 x8
x9 x10 x11 x12
x13 x14 x15 x16





26/32
AES MixColumns
tl;dr: Mixing bits of x in a linear but relatively complex way (provides diffusion).
MixColumns is essentialy a matrix multiplication over the field of bytes: a Galois field of
order 28
.
Let [n] denote a byte (8-bit) representation of number n, e.g. [3] = ”00000011”. Then
MixColumns(x) =





[2] [3] [1] [1]
[1] [2] [3] [1]
[1] [1] [2] [3]
[3] [1] [1] [2]





·





x1 x2 x3 x4
x5 x6 x7 x8
x9 x10 x11 x12
x13 x14 x15 x16





We want to define a notion of summing and multiplication of bytes so that they obey similar
algebraic laws as summing and multiplication of integers. 26/32
Polynomials
A polynomial of degree n is an expression
an · xn
+ an−1 · xn−1
+ · · · a1 · x + a0,
where x is a variable and an, . . . , a0 are constant coefficients.
27/32
Polynomials
A polynomial of degree n is an expression
an · xn
+ an−1 · xn−1
+ · · · a1 · x + a0,
where x is a variable and an, . . . , a0 are constant coefficients.
Polynomials can be summed:
. . . multiplied:
and divided:
27/32
Polynomials over Z2
Consider the case where the coefficients are not integers, but integers modulo 2, i.e. bits with
addition = xor and multiplication = and.
Such polynomials can be again summed:
. . . multiplied:
and divided:
Given polynomials p(x), q(x), there exist unique polynomials h(x), r(x) s.t.
p(x) = q(x) · h(x) + r(x) and r(x) has smaller degree than q(x).
28/32
Galois Field: Polynomials over Z2 are bitvectors
A degree-7 polynomial a7 · x7
+ · · · + a1 · x + a0 over Z2 can be interpreted as a byte
a7a6 . . . a1a0. Moreover, in this interpretation, polynomial summation is the same as
bitwise xor ⊕.
29/32
Galois Field: Polynomials over Z2 are bitvectors
A degree-7 polynomial a7 · x7
+ · · · + a1 · x + a0 over Z2 can be interpreted as a byte
a7a6 . . . a1a0. Moreover, in this interpretation, polynomial summation is the same as
bitwise xor ⊕.
Idea: Let multiplication of bytes = multiplication of polynomials over Z2.
29/32
Galois Field: Polynomials over Z2 are bitvectors
A degree-7 polynomial a7 · x7
+ · · · + a1 · x + a0 over Z2 can be interpreted as a byte
a7a6 . . . a1a0. Moreover, in this interpretation, polynomial summation is the same as
bitwise xor ⊕.
Idea: Let multiplication of bytes = multiplication of polynomials over Z2. Does not quite work,
since the result might exceed the length of a byte:
29/32
Galois Field: Polynomials over Z2 are bitvectors
A degree-7 polynomial a7 · x7
+ · · · + a1 · x + a0 over Z2 can be interpreted as a byte
a7a6 . . . a1a0. Moreover, in this interpretation, polynomial summation is the same as
bitwise xor ⊕.
Idea: Let multiplication of bytes = multiplication of polynomials over Z2. Does not quite work,
since the result might exceed the length of a byte:
Better idea: Fix some polynomial q(x) of degree 8 irreducible over Z2. Then, to multiply bytes
b1 and b2, let p1(x) and p2(x) be the corresponding polynomials over Z2 and let b1 • b2 be the
byte corresponding to the remainder of p1(x) · p2(x) divided (over Z2) by q(x). AES uses
q(x) = x8
+ x4
+ x3
+ x + 1.
29/32
Galois Field: Polynomials over Z2 are bitvectors
A degree-7 polynomial a7 · x7
+ · · · + a1 · x + a0 over Z2 can be interpreted as a byte
a7a6 . . . a1a0. Moreover, in this interpretation, polynomial summation is the same as
bitwise xor ⊕.
Idea: Let multiplication of bytes = multiplication of polynomials over Z2. Does not quite work,
since the result might exceed the length of a byte:
Better idea: Fix some polynomial q(x) of degree 8 irreducible over Z2. Then, to multiply bytes
b1 and b2, let p1(x) and p2(x) be the corresponding polynomials over Z2 and let b1 • b2 be the
byte corresponding to the remainder of p1(x) · p2(x) divided (over Z2) by q(x). AES uses
q(x) = x8
+ x4
+ x3
+ x + 1.
The set of all bytes equipped with ⊕ as addition and • as multiplication is called a Galois field
of order 28
, i.e. GF(28
).
29/32
AES MixColumns
MixColumns is essentialy a matrix multiplication over the field of bytes: a Galois field of
order 28
.
Let [n] denote a byte (bitvector) representing number n, e.g. [3] = ”00000011”. Then
MixColumns(x) =





[2] [3] [1] [1]
[1] [2] [3] [1]
[1] [1] [2] [3]
[3] [1] [1] [2]





·





x1 x2 x3 x4
x5 x6 x7 x8
x9 x10 x11 x12
x13 x14 x15 x16





The •-multiplication by 2 and 3 can be implemented purely via bit-level XORs. The
multiplication matrix is invertible over GF(28
).
30/32
AES Key Schedule
31/32
Security of AES
• Best known key-recovery attacks against variants of AES:
variant bruteforce attack best known attack
AES-128 2128
2126.1
AES-192 2192
2189.74
AES-256 2256
2254.42
• AES-256 can fall prey to the related key attack in time 299.95
(easily avoidable using
proper key establishment protocols)
• The most practical attacks on AES do not attack the mathematical construction, but the
implementation (side-channel attacks: timing, energy consumption, etc.). More in the
practical crypto courses.
32/32