IA174: Symmetric Key Encryption and Secrecy IV
Modes of Block Ciphers
1/30
Recall: ECB mode insecure
E.g. in early stages of the pandemic (spring 2020), many security vulnerabilities were discovered
in the Zoom conference call system. This included the use of ECB mode for encryption:
(Marczak & Scott-Railton: “Move Fast and Roll Your Own Crypto” )
• “Zoom documentation claims that the app uses “AES-256” encryption for meetings where
possible. However, we find that in each Zoom meeting, a single AES-128 key is used in
ECB mode by all participants to encrypt and decrypt audio and video. The use of ECB
mode is not recommended because patterns present in the plaintext are preserved during
encryption.”
2/30
Lesson Plan
• Introduce two modes that turn secure block ciphers into semantically secure ciphers: CBC
and CTR.
• Generalize semantic security to cover many-time encryption under chosen plaintext
attacks: CPA security.
• No deterministic cipher can provide CPA security: we will introduce randomized and
nonce-based approaches to overcome this.
• Show that CBC and CTR with randomness and nonce usage do provide CPA security.
3/30
CBC (Cipher Block Chaining) mode: in picture
4/30
CBC mode: in picture II
5/30
CBC mode: in picture II
5/30
Deterministic CBC mode: pseudocode
In the following, E = (E, D) is a block cipher over (K, X).
Algorithm 1: Encryption ECBC of the CBC mode of E.
Input: Message m = x1 || x2 || · · · || xj ∈ X≤n
, key k ∈ K, IV ∈ X.
Output: c = ECBC(IV )(k, m)
y0 ← IV ;
for i ∈ {1, . . . , j} do
yi = E(k, yi−1 ⊕ xi )
return y1 || y1 || y2 || · · · || yj
Algorithm 2: Decryption DCBC of the CBC mode of E.
Input: ciphertext c = y1 || y2 || · · · || yj ∈ X≤n
, key k ∈ K, IV ∈ X.
Output: m = DCBC(IV )(k, c)
y0 ← IV ;
for i ∈ {1, . . . , j} do
xi = D(k, yj ) ⊕ yj−1
return x1 || x2 || · · · || xj
6/30
CTR (Counter) mode: in picture (with IV=0, only good for Semantic security)
Key idea: turn a block cipher into a PRG (and thus, into a stream cipher). In the following we
denote by [i]X the representation of number i ≥ 0 as a binary vector of the same length as
blocks in X.
7/30
CTR mode: in picture (with arbitrary IV)
8/30
Deterministic CTR mode: pseudocode
Let E = (E, D) be a block cipher over (K, X) = {0, 1}ℓ
. The CTR mode of E is a stream
cipher ECTR defined by the pseudorandom generator in the following pseudocode:
Algorithm 3: Keystream generation for the counter mode.
Input: Key k ∈ K, IV ∈ X, n ≥ 1.
Output: A keystream consisting of n blocks.
for i ∈ {0, . . . , n − 1} do
zi = E(k, IV ⊞ℓ [i]X )
return z1 || z2 || · · · || zn
9/30
Notes on CBC and CTR modes
• CTR mode is (unlike CBC), easy to parallelize.
• CTR mode does not require padding the message to a multiple of block length.
• CBC mode can use several types of padding, most common the one specified in PKCS #7.
• CTR mode has less stringent requirements on the IV for CPA security (see later).
10/30
Notes on CBC and CTR modes
• CTR mode is (unlike CBC), easy to parallelize.
• CTR mode does not require padding the message to a multiple of block length.
• CBC mode can use several types of padding, most common the one specified in PKCS #7.
• CTR mode has less stringent requirements on the IV for CPA security (see later).
“CTR is all that you should be doing with AES...”
Dan Bernstein1
... as long as you only care about confidentiality.
• E.g. CBC a building block for some MACs (see in 2 lectures).
1
According to P. Rogaway: Evaluation of Some Blockcipher Modes of Operation (2011)
10/30
Security theorems for CBC and CTR.
Theorem 1
Let E be a block cipher over (K, X) that is ε-secure for some negligible ε. Then for any
fixed IV , the cipher ECBC is δ-semantically secure for some negligible δ.
Theorem 2
Let E be a block cipher over (K, X) that is ε-secure for some negligible ε. Then for any
fixed IV , the cipher ECTR is δ-semantically secure for
δ = 2ε +
n2
2|X|
,
where n is the maximal number of blocks per message (i.e. M = X≤n
).
11/30
Security of CTR mode: proof
12/30
PRP-PRF switching lemma in CTR security proof
13/30
Beyond Semantic Security: Many-Time Keys and Chosen Plaintext Attacks
• A communication session often involves exchange of multiple messages, with a single key
used for all exchanges. Also, multi-message view might be more suitable due to practical
aspects of network communication.
• Moreover, the adversary can often recover encryptions of plaintext of his choice:
chosen-plaintext attacks. Examples:
• staged local manouvers in WWII;
• attacker sending an e-mail and recovering its encryption;
• attacker paying for online ads and intercepting encryption of the search traffic.
The notion of semantic security is insufficient for these scenarios, as the semantic security
attack game consists of encryption of a single message.
14/30
CPA security attack game (picture)
15/30
CPA security attack game
Let (E, D) be a cipher over (K, M, C). The CPA attack game against (E, D) is played as
follows:
Stage 1:
• The challenger samples a key k ∈ K and a bit i ∈ {0, 1}, both uniformly at random.
Neither is revealed to the adversary.
• The adversary announces a number of rounds q for which the game will be played.
16/30
CPA security attack game
Let (E, D) be a cipher over (K, M, C). The CPA attack game against (E, D) is played as
follows:
Stage 2:
• In each round 1 ≤ j ≤ q:
• The adversary computes (possibly in a randomized way) two messages, mj
0 and mj
1 of the
same length and sends them to the challenger.
• The challenger takes the message mj
i and encrypts it using the sampled key k. The resulting
ciphertext cj
= E(k, mj
i ) is sent to the adversary.
Stage 3:
• Finally, adversary outputs a guess g ∈ {0, 1}.
The adversary wins the game if g = i, otherwise it loses.
16/30
CPA security: definition
We define the CPA advantage of A against E as the quantity
ADVCPA(E, A) = P(A wins) −
1
2
.
We say that E is an ε-CPA secure cipher (where ε > 0) if for every efficient adversary it holds
ADVCPA(E, A) ≤ ε.
17/30
Deterministic vs. randomized ciphers
Fact 1
No deterministic cipher can be CPA secure.
18/30
Deterministic vs. randomized ciphers
Fact 1
No deterministic cipher can be CPA secure.
Imagine a the following 2-round CPA attack game:
1st round: m1,0 = m1,1 = arbitrary message m
2nd round: m2,0 = . . . , m2,1 = . . .
.
18/30
Deterministic vs. randomized ciphers
Fact 1
No deterministic cipher can be CPA secure.
Imagine a the following 2-round CPA attack game:
1st round: m1,0 = m1,1 = arbitrary message m
2nd round: m2,0 = m, m2,1 = m′
, where m′
is an arbitrary message different from m but
having the same length.
Then b = 0 if and only if c1 = c2.
18/30
Deterministic vs. randomized ciphers
Fact 1
No deterministic cipher can be CPA secure.
Imagine a the following 2-round CPA attack game:
1st round: m1,0 = m1,1 = arbitrary message m
2nd round: m2,0 = m, m2,1 = m′
, where m′
is an arbitrary message different from m but
having the same length.
Then b = 0 if and only if c1 = c2.
Solution: expand our notion of a cipher. Two principal approaches:
• Probabilistic encryption.
• Nonce-based encryption.
18/30
Probabilistic encryption
For a cipher E = (E, D) over (K, M, C):
• Standard definition: E : K × M → C a computable function (deterministic algorithm)
• Probabilistic definition: E : K × M → D(C) a computable function (randomized
algorithm) – D(S) is the set of probability distributions over the set S.
The remaining definitions are the same as for the standard notion of a cipher.
19/30
Probabilistic CBC and CTR modes
For a block cipher E = (E, D) over (K, X) and for M ∈ {CBC, CTR}, the probabilistic
M-mode is the cipher EP
M = (EP
M , DP
M ), where EP
M (k, m):
• First randomly samples IV ∈ X. (High-quality random sampling, in particular for the CBC
mode! E.g. /dev/random).
• Then computes e = EM(IV )(k, m) using the sampled IV .
• Outputs the ciphertext c = IV || e;
while DP
M (k, c):
• Interprets the first block of c as the IV to use, and the remaining part of c as the message
e to decrypt.
• Computes m = DM(IV )(k, e).
For CBC, it is vital that IV is unpredictable at the time of forging the chosen plaintext!
20/30
CBC with predictable IV is insecure
21/30
CPA security of randomized CBC mode
Definition 1
An adversary is q-bounded if he always plays the attack game for at most q rounds (i.e.
makes at most q queries to the challenger).
Theorem 3
Let E be an ε-secure block cipher over (K, X) for ε negligible, with n being the maximal
number of blocks per message. Then the cipher EP
CBC is δ-secure against all q-bounded
adversaries, where
δ = 2ε + 2
q2
n2
|X|
22/30
CPA security of randomized CTR mode
Definition 2
An adversary is q-bounded if he always plays the attack game for at most q rounds (i.e.
makes at most q queries to the challenger).
Theorem 4
Let E be an ε-secure block cipher over (K, X), with n being the maximal number of
blocks per message. Then the cipher EP
CTR is δ-secure against all q-bounded adversaries,
where
δ = 2ε +
q2
n
|X|
+
qn2
|X|
.
23/30
CPA security of randomized CTR mode: Proof idea
24/30
Nonce-based encryption
Nonce = number only used once (during the lifetime of a key).
Can either be randomly selected (similar to randomized encryption) or even come from a
known public sequence of numbers, in which case there is no need to send it along the message
(but it requires Alice and Bob to synchronize on the messages). Can be predictable.
25/30
Nonce-based encryption
Nonce = number only used once (during the lifetime of a key).
Can either be randomly selected (similar to randomized encryption) or even come from a
known public sequence of numbers, in which case there is no need to send it along the message
(but it requires Alice and Bob to synchronize on the messages). Can be predictable.
Formally, a nonce-based cipher over (K, N, X) is a tuple E = (E, D) where:
• E : K × N × M → C is an encryption algorithm, and
• D : K × N × C → M is a decryption algorithm such that for all
k ∈ K, ν ∈ N, m ∈ M : D(k, ν, E(k, ν, m)) = m.
We also have a special notion of security for nonce-based ciphers.
25/30
CPA security for nonce-based ciphers
Let (E, D) be a nonce-based cipher over (K, N, X). The nonce-based CPA attack game
between the challenger and the adversary A consists of two sub-experiments, experiment 0 and
experiment 1:. At the start of the game, the challenger samples b ∈ {0, 1} uniformly at
random, the choice is kept secret from the adversary. The experiment b is then performed as
follows:
• The challenger samples a key k ∈ K uniformly at random.
• A selects a number N of rounds for which the game will be played.
• In each round i:
• A computes two messages, mi,0 and mi,1 of the same length and a nonce
νi ∈ N \ {ν1, ν2, . . . , νi−1}, and sends these to the challenger. This process is adaptive, i.e.
the challenger may compute the messages based on what happened in the previous rounds.
• The challenger computes ci = E(k, νi , mi,b) and sends c to A.
• After the final round, A outputs his guess for the value of b.
The rest (including the definition of A’s NCPA advantage) is the same as for CPA security.
26/30
Nonce-based CBC mode (in picture)
27/30
Nonce-based CBC mode (pseudocode)
Algorithm 4: Encryption EN
CBC of the nonce-based CBC mode of E.
Input: Message m = x1 || x2 || · · · || xj ∈ X≤n
, a pair of keys (k, k′
) ∈ K2
, nonce ν ∈ X.
Output: c = EN
CBC (k, ν, m)
y0 ← E(k′
, ν);
for i ∈ {1, . . . , j} do
yi = E(k, yi−1 ⊕ xi )
return y1 || y1 || y2 || · · · || yj
Algorithm 5: Decryption DN
CBC of the nonce-based CBC mode of E.
Input: ciphertext c = y1 || y2 || · · · || yj ∈ X≤n
, a pair of keys (k, k′
) ∈ K, nonce ν ∈ X.
Output: m = DN
CBC (k, ν, , c)
y0 ← E(k′
, ν);
for i ∈ {1, . . . , j} do
xi = D(k, yj ) ⊕ yj−1
return x1 || x2 || · · · || xj
28/30
Nonce-based CTR mode
Recall: ℓ – block length, |X| = 2ℓ
, n – max no. of blocks in message
The nonce-based CTR mode is identical to “vanilla” CTR (with nonce used as IV), but with
N = {0, n, 2n, . . . , |X|/n}
29/30
CPA security of nonce-based modes
Theorem 5
Let E be an ε-secure block cipher over (K, X). Then the cipher EN
CBC is δ-secure against
all q-bounded adversaries, where
δ = 4 ·

ε +
q2
· n2
|X|

.
Theorem 6
Let E be an ε-secure block cipher over (K, X). Then the cipher EN
CTR is (ε + n2
|X| )-secure
against all adversaries.
30/30