CS-E4340 Cryptography: Exercise Sheet 4
—Message Authentication Codes (MACs) & Pseudorandom Functions (PRFs)—
Submission Deadline: October 11, 12:00 via MyCourses
Each exercise can give up to two participation points, 2 for a mostly correct solution and 1 point
for a good attempt. Overall, the exercise sheet gives at most 4 participation points.
Exercise Sheet 4 is intended to help…
(a) …understand the definition of a message authentication code (MAC).
(b) …understand the relation between PRFs and MACs.
(c) …understand and practice how to define the security for a cryptographic primitive via se-
curity notions.
Exercise 1 shows that a UNF-CMA-secure MAC might leak the message it authenticates.
Exercise 2 explores the differences/similarities between one-way functions and UNF-CMA-
secure MAC schemes.
Exercise 3 constructs variants of MAC schemes and the goal is to distinguish modifications
which harm security from modifications which don’t harm security.
Exercise 4 deepens understanding of the UNF-CMA game and provide some definitions in
which no scheme can be secure. In this case, we say that these are variants of the MAC
game which are trivial to break (trivial does not mean that the exercise is easy. Rather, it
means that the definitions are not meaningful.).
Exercise 5 is an advanced counterexample for showing that not every UNF-CMA-secure MAC
is a one-way function. (In fact, every UNF-CMA-secure MAC is a so-called distributional one-
way function. Ask Miikka Tiainen if you are curious on the definition and its implications.)
Hint: Lecture 4 and the beginning of Lecture 5 cover message authentication codes, so you can
have a look at both lecture videos to help with this exercise sheet.
Exercise 1 (MACs can leak the message). Let m1 be a UNF-CMA secure MAC scheme. Prove
that also m2 is a UNF-CMA secure MAC scheme, where
m2.mac(k, x) := m1.mac(k, x)||x
and
m2.ver(k, x, t)
assert t ∕= ⊥
t
′ ← t1…|t|−|x|
x
′ ← t|t|−|x|+1…|t|
if x′ ∕= x
return 0
return m1.ver(k, x, t′)
Hint: You need to provide a reduction in pseudo-code (main task) and show that the reduction
works. In order to show that the reduction works as it should (explain in your solution what
this means), you can either provide the main conceptual argument (in text) or an inlining proof
(in pseudocode) as in the lecture.
Exercise 2 (OWFs & MACs). Prove or disprove: For all one-way functions f , m is an UNF-
CMA secure MAC scheme, where m.mac(k, x) = f(k||x) and
m.ver(k, x, t)
t
′ ← f(k||x)
if t′ ∕= t
return 0
else
return 1
Hint: If you believe that this is an UNF-CMA secure MAC scheme, see hint for Exercise 1. If you
believe that this is not necessarily an UNF-CMA secure MAC scheme, define a counterexample
OWF f and provide an adversary in pseudocode. See lecture notes for Lecture 4 for an example
on how to write such adversary pseudocode.
Exercise 3 (Candidate MAC schemes). Let f be a secure (λ, λ)-PRF. Consider the four MAC
schemes m1, m2, m3, m4 given below.
1. Do you think, these MAC-schemes are UNF-CMA? Justify your intuition.
2. Choose one of the MAC schemes mi that you think is not UNF-CMA secure. Provide
an adversary A (in pseudocode) that can distinguish between the real and ideal games
Gunf-cmabm (see Chapter 3 in the Crypto Companion). An intuitive explanation for why the
adversary works suffices in this exercise.
Note: Below, the syntax x[i] refers to the value assigned to x during the ith loop. Moreover,
y[i] ← f(k, x[i]) is the output value of f during the ith loop.
2
m1.mac(k, x)
j ← λ − (|x| mod λ)
x
′ ← x||0j
for i = 0 until
|x′|
λ
− 1
ℓ ← λi + 1
r ← λi + λ
x[i] ← x′ℓ..r
y[i] ← f(k, x[i])
t ← (y[0], y[1], …, y[
!!x′
!! /λ − 1])
return t
m1.ver(k, x, t)
j ← λ − (|x| mod λ)
x
′ ← x||0j
(y[0], y[1], …, y[
!!x′
!! /λ − 1]) ← t
for i = 0 until
|x′|
λ
− 1
ℓ ← λi + 1
r ← λi + λ
x[i] ← x′ℓ..r
if y[i] ∕= f(k, x[i])
return 0
return return 1
m2.mac(k, x)
j ← λ − (|x| mod λ)
x
′ ← x||0j
y[−1] ← 0λ
for i = 0 until
|x′|
λ
− 1
ℓ ← λi + 1
r ← λi + λ
x[i] ← x′ℓ..r
y[i] ← f(k, x[i] ⊕ y[i − 1])
t ← (y[0], y[1], …, y[
!!x′
!! /λ − 1])
return t
m2.ver(k, x, t)
j ← λ − (|x| mod λ)
x
′ ← x||0j
y[−1] ← 0λ
(y[0], y[1], …, y[
!!x′
!! /λ − 1]) ← t
for i = 0 until
|x′|
λ
− 1
ℓ ← λi + 1
r ← λi + λ
x[i] ← x′ℓ..r
if y[i] ∕= f(k, x[i] ⊕ y[i − 1])
return 0
return return 1
3
m3.mac(k, x)
j ← λ − (|x| + 1) mod λ)
x
′ ← x||1||0j
y[−1] ← 0λ
for i = 0 until
|x′|
λ
− 1
ℓ ← λi + 1
r ← λi + λ
x[i] ← x′ℓ..r
y[i] ← f(k, x[i] ⊕ y[i − 1])
t ← (y[0], y[1], …, y[
!!x′
!! /λ − 1])
return t
m3.ver(k, x, t)
z ← λ − ((|x| + 1) mod λ)
x
′ ← x||1||0z
y[−1] ← 0λ
(y[0], …, y[
!!x′
!! /λ − 1]) ← t
for i = 0 until
|x′|
λ
− 1
ℓ ← λi + 1
r ← λi + λ
x[i] ← x′ℓ..r
if y[i] ∕= f(k, x[i] ⊕ y[i − 1])
return 0
return return 1
m4.mac(k, x)
j ← λ − ((|x| + 1) mod λ)
x
′ ← x||1||0j
y[−1] ← 0λ
for i = 0 until
|x′|
λ
− 1
ℓ ← λi + 1
r ← λi + λ
x[i] ← x′ℓ..r
y[i] ← f(k, x[i] ⊕ y[i − 1])
t ← y[
|x′|
λ
− 1]
return t
m4.ver(k, x, t)
z ← λ − (|x| + 1) mod λ)
x
′ ← x||1||0z
y[ − 1] ← 0
λ
for i = 0 until
|x′|
λ
− 1
ℓ ← λi + 1
r ← λi + λ
x[i] ← x′ℓ..r
y[i] ← f(k, x[i] ⊕ y[i − 1])
if y[
|x′|
λ
− 1] = t :
return 1
else return 0
Exercise 4. (Security Models, Weak Unforgeability) In this exercise, we aim to under-
stand what would be a good model for a weak unforgeability definition that captures that only
the message m is authenticated whereas the tag might be malleable. We capture weak unforge-
ability as computational indistinguishability between a real game Gwunf-cma0m and an ideal
game Gwunf-cma1m. We define the real game for weak unforgeability under chosen message at-
tacks (wUNF-CMA) as the real game for UNF-CMA security, i.e., Gwunf-cma0m := Gunf-cma0m,
where m is a message authentication scheme. Below, we give three candidates for the ideal game
Gwunf-cma1m. You need to choose one candidate such that weak unforgeability (integrity on the
message only) is best captured. Justify your choice.
4
Package Parameters
λ : security parameter
m : MAC scheme
Package State
k : k
L : list
Mac(x)
if k = ⊥
k ←$ {0, 1}λ
t ← m.mac(k, x)
L ← L ∪ {x}
return t
VERIFY(x, t)
assert x ∕= ⊥
if (x) ∈ L and if m.ver(k, x, t) = 1
return 1
else return 0
Package Parameters
λ : security parameter
m : MAC scheme
Package State
k : k
L : list
Mac(x)
if k = ⊥
k ←$ {0, 1}λ
t ← m.mac(k, x)
L ← L ∪ {x}
return t
VERIFY(x, t)
assert x ∕= ⊥
if (x) ∈ L
return 1
else return 0
Package Parameters
λ : security parameter
m : MAC scheme
Package State
k : k
L : list
MAC(x)
if k = ⊥
k ←$ {0, 1}λ
t ← m.mac(k, x)
L ← L ∪ {(x, t)}
return t
VERIFY(x, t)
assert x ∕= ⊥
if (x, t) ∈ L
return 1
else return 0
Exercise 5. (Advanced counterexamples) Assume the existence of secure (∗, λ)-PRFs.
Prove that there exists an UNF-CMA-secure MAC scheme m such that the function
fm : z #→ x||m.mac(k, x) where k = z1..ℓ and x = zℓ+1..|x| for ℓ =
”
|z|
2
#
is not a one-way function. Notation: k is the first half of the input of fm, and x is the second
half of the input of fm. When the input is of odd length, then x has one bit more than k.
Hint: Consult the counterexample theorems in the Crypto Companion.
5