🔓
Cryptography
  • What's this
  • Chapter 1 - Introduction
    • Exercise 1.1
  • Chapter 3 - Private-Key Encryption
    • Exercise 3.1
  • Chapter 4 - Message Authentication Codes
    • Exercise 4.7
    • Exercise 4.8
    • Exercise 4.14
    • Exercise 4.15
    • Extra: Authenticated Encryption CBC-XOR
  • Chapter 5 - Hash Functions and Applications
    • Exercise 5.3
  • Chapter 8 - Number Theory and Cryptographic Hardness Assumptions
    • (Unresolved) Exercise 8.15
Powered by GitBook
On this page
  • Problem
  • Solution

Was this helpful?

  1. Chapter 4 - Message Authentication Codes

Exercise 4.7

Problem

Let FFF be a pseudorandom function. Show that each of the following MACs is insecure, even if used to authenticate fixed-length messages. (In each case Gen outputs a uniform k∈{0,1}nk \in \{0, 1\}^nk∈{0,1}n. Let ⟨i⟩\langle i \rangle⟨i⟩ denote an n/2n/2n/2-bit encoding of the integer iii.)

  1. To authenticate a message m=m1,…,ml m = m_1, \ldots ,m_l m=m1​,…,ml​ where mi∈{0,1}nm_i \in \{0, 1\}^nmi​∈{0,1}n, compute t:=Fk(m1)⊕⋯⊕Fk(ml)t := F_k(m_1) \oplus \cdots \oplus F_k(m_l)t:=Fk​(m1​)⊕⋯⊕Fk​(ml​).

  2. To authenticate a message m=m1,…,ml m = m_1, \ldots ,m_l m=m1​,…,ml​ where mi∈{0,1}n/2m_i \in \{0, 1\}^{n/2}mi​∈{0,1}n/2, compute t:=Fk(⟨1⟩∣∣m1)⊕⋯⊕Fk(⟨l⟩∣∣ml)t := F_k(\langle 1 \rangle || m_1) \oplus \cdots \oplus F_k(\langle l \rangle || m_l)t:=Fk​(⟨1⟩∣∣m1​)⊕⋯⊕Fk​(⟨l⟩∣∣ml​).

  3. To authenticate a message m=m1,…,ml m = m_1, \ldots ,m_l m=m1​,…,ml​ where mi∈{0,1}n/2m_i \in \{0, 1\}^{n/2}mi​∈{0,1}n/2, choose uniform r←{0,1}nr \leftarrow \{0, 1\}^nr←{0,1}n, compute t:=Fk(r)⊕Fk(⟨1⟩∣∣m1)⊕⋯⊕Fk(⟨l⟩∣∣ml)t := F_k(r) \oplus F_k(\langle 1 \rangle || m_1) \oplus \cdots \oplus F_k(\langle l \rangle || m_l)t:=Fk​(r)⊕Fk​(⟨1⟩∣∣m1​)⊕⋯⊕Fk​(⟨l⟩∣∣ml​), and let the tag be ⟨r,t⟩\langle r, t \rangle ⟨r,t⟩

Solution

Part 1

Reorder the blocks in mmm and the tag doesn't change.

Part 2

Query

  • m1=m1∣∣m2m^1 = m_1 || m_2m1=m1​∣∣m2​, tag t1=Fk(⟨1⟩∣∣m1)⊕Fk(⟨2⟩∣∣m2)t_1 = F_k(\langle 1 \rangle || m_1) \oplus F_k(\langle 2 \rangle || m_2) t1​=Fk​(⟨1⟩∣∣m1​)⊕Fk​(⟨2⟩∣∣m2​)

  • m2=m3∣∣m2m^2 = m_3 || m_2m2=m3​∣∣m2​, tag t2=Fk(⟨1⟩∣∣m3)⊕Fk(⟨2⟩∣∣m2)t_2 = F_k(\langle 1 \rangle || m_3) \oplus F_k(\langle 2 \rangle || m_2) t2​=Fk​(⟨1⟩∣∣m3​)⊕Fk​(⟨2⟩∣∣m2​)

  • m3=m3∣∣m4m^3 = m_3 || m_4m3=m3​∣∣m4​, tag t3=Fk(⟨1⟩∣∣m3)⊕Fk(⟨2⟩∣∣m4)t_3 = F_k(\langle 1 \rangle || m_3) \oplus F_k(\langle 2 \rangle || m_4) t3​=Fk​(⟨1⟩∣∣m3​)⊕Fk​(⟨2⟩∣∣m4​)

Thus m∗=m1⊕m2⊕m3=m1∣∣m4 m^* = m^1 \oplus m^2 \oplus m^3 = m_1 || m_4m∗=m1⊕m2⊕m3=m1​∣∣m4​, tag t=t1⊕t2⊕t3=Fk(⟨1⟩∣∣m1)⊕Fk(⟨2⟩∣∣m4)t = t_1 \oplus t_2 \oplus t_3 = F_k(\langle 1 \rangle || m_1) \oplus F_k(\langle 2 \rangle || m_4) t=t1​⊕t2​⊕t3​=Fk​(⟨1⟩∣∣m1​)⊕Fk​(⟨2⟩∣∣m4​).

Part 3

Let m∈{0,1}n/2m \in \{0, 1\}^{n/2}m∈{0,1}n/2. When choosing r=⟨1⟩∣∣mr = \langle 1 \rangle || mr=⟨1⟩∣∣m, t=Fk(r)⊕Fk(⟨1⟩∣∣m)=0nt = F_k(r) \oplus F_k(\langle 1 \rangle || m) = 0^nt=Fk​(r)⊕Fk​(⟨1⟩∣∣m)=0n.

Thus t=⟨⟨1⟩∣∣m,0n⟩ t = \left\langle \langle 1 \rangle || m, 0^n \right\rangle t=⟨⟨1⟩∣∣m,0n⟩ will be a valid tag for mmm.

Last updated 5 years ago

Was this helpful?