Message Authentication Code

This week we focuses on the data integrity, Message Authentication Codes.

Define: MAC I=(S, V) defined over (K, M, T):

  • S(k, m) outputs t in T
  • V(k, m, t) output ‘yes’ or ‘no’

S stands for signing, V stands for verification.

Secure MACs

Attacker can give Alice m1,...mqm_1, ... m_q, to get tiS(k,mi)t_i \leftarrow S(k, m_i). The goal is to produce some new valid message/tag pairs (m, t), aka existential forgery, such that:

(m,t){(m1,t1),...,(mq,tq)}(m, t) \notin \{(m_1, t_1), ..., (m_q, t_q)\}

The MAC is secure if attacker cannot generate new (m, t), even for existing message, mim_i. Or more formally: AdvMAC[A,I]=Pr[Chal.outputs1]Adv_{MAC}[A, I] = Pr[Chal. outputs 1] is negligible.

Secure PRF -> Secure MAC

The error bound of PRF is AdvMAC[A,IF]AdvPRF[B,F]+1/YAdv_{MAC}[A, I_F] \leq Adv_{PRF}[B, F] + 1/|Y| The IFI_F is secure as long as Y|Y| is large enough.

Extend AES(16 bytes) from Small-MAC to Big-MAC:

  • CBC-MAC, ANSI X9.9, FIPS 186-3
  • HMAC, SSL, IPSec, SSH.



It is important to use independent k1k_1 to encrypt the raw CBC output. For raw CBC, the attacker can

  • choose one block message m, to get t = F(k, m)
  • then for 2-block message (m,tm)(m, t\oplus m) , the MAC is t!


Also the independent k1k_1 encrypt the output of cascade MAC to make it secure.

AdvPRF[A,FECBC]AdvPRF[B,F]+2q2XAdvPRF[A,FNMAC]qLAdvPRF[B,F]+q22K\begin{align*} Adv_{PRF}[A, F_{ECBC}] & \leq Adv_{PRF}[B, F] + \frac{2q^2}{|X|} \\ Adv_{PRF}[A, F_{NMAC}] & \leq q \cdot L \cdot Adv_{PRF}[B, F] + \frac{q^2}{2|K|} \end{align*}

We need to rotate keys for after X1/2|X|^{1/2} messages with ECBC-MAC or K1/2|K|^{1/2} for NMAC.

Once we find a hash collision, we can extend any arbitrary block to mount forgery attack.

MAC padding

Padding MUST be invertible to prevent forgery.

ISO: padding with 10000, 1 indicates the beginning of the padding. In case message has a clear cut, just append a dummy block.

CMAC uses k1k_1 for padding block, and k2k_2 for no-padding block to resolve the ambiguity. It is as safe as CBC-MAC, and standardized by NIST.


Parallel MAC


The P(k,i)P(k, i) enforce the block order, such k×ik \times i. The padding use similar technical as CMAC.

AdvPRF[A,FPMAC]AdvPRF[B,F]+2q2L2XAdv_{PRF}[A, F_{PMAC}] \leq Adv_{PRF}[B, F] + \frac{2q^2L^2}{|X|}

It is easy to replace one specific block, and compute the MAC without recomputing everything.

One-time MAC

Kind of like OTP, pick key, (k,a){1,...q}2(k, a) \in \{1, ... q\} ^2 where q is a large prime number such as (q=2128+51q = 2^{128} + 51), and break the message to blocks, (m[1],...,m[L])(m[1], ..., m[L]):

S(key,msg)=(Pmsg(k)+a)modqS(key, msg) = (P_{msg}(k) + a)\mod q

where Pmsg(x)=m[L]xL+...+m[1]xP_{msg}(x) = m[L]\cdot x^L + ... + m[1]\cdot x, aka a polynomial of L.

Many-time MAC

Cater-Wegman MAC:

CW((k1,k2),m)=(r,F(k1,r)S(k2,m))CW((k_1, k_2), m) = (r, F(k_1, r)\oplus S(k_2, m))

for F be a secure PRF, for r is random chosen: r{0,1}nr \leftarrow \{0, 1\}^n. The verification is: V(k2,m,F(k1,r)t))V(k_2, m, F(k_1, r) \oplus t)).

Collision Resistance

A function H is collision resistant if for efficient algorithms, the chance to fine the same hash is negligible.

Let I=(S, V) be a MAC for short message over (K, M, T), Let H: MbigMM^{big} \to M

Def: Ibig=(Sbig,Vbig)I^{big} = (S^{big}, V^{big}) over (K,Mbig,T)(K, M^{big}, T) as:

Sbig(k,m)=S(k,H(m));Vbig(k,m,t)=V(k,H(m),t)S^{big}(k, m) = S(k, H(m)); V^{big}(k, m, t) = V(k, H(m), t)

Thm: If I is a secure MAC and H is collision resistant, then IbigI^{big} is a secure MAC.

Birthday Attack

Let H:M{0,1}nH:M \to \{0, 1\}^n be a hash function (M2n|M| \gg 2^n) We can find a collision in time O(2n/2)O(2^{n/2}) thanks to the birthday paradox:

Let r1,...,rn{1,..,B}r_1, ..., r_n \in \{1, .., B\} be independent uniformly distributed integers. when n=1.2×B1/2n = 1.2 \times B^{1/2} then Pr[ij:ri=rj]12Pr[\exists i \neq j: r_i = r_j] \ge \frac{1}{2}

Merkle-Damgard Paradigm

Merkle-Damgard Paradigm
Merkle-Damgard Paradigm

Given h:T×XTh: T \times X \to T, we obtain H:XLTH: X^{\le L} \to T. So we can build a collision resistant function for larger message.

Davies-Meyer compression

E:K×{0,1}n{0,1}nE: K \times \{0, 1\}^n \to \{0, 1\}^n a block cipher: h(H,m)=E(m,H)Hh(H, m)= E(m, H) \oplus H.

Davies-Meyer compression
Davies-Meyer compression
Suppose E is an ideal cipher, finding a collision of h(H,m)=h(H,m)h(H, m) = h(H', m') takes O(2n/2)O(2^{n/2}) evaluations of (E, D).


h(H,m)=E(m,H)Hmh(H,m)=E(Hm,m)m\begin{align*} h(H, m) & = E(m, H) \oplus H \oplus m \\ h(H, m) & = E(H \oplus m, m) \oplus m \end{align*}

Other natural variants are insecure:

h(H,m)=E(m,H)mh(H, m) = E(m, H) \oplus m


  • Merkle-Damgrad funciton
  • Daives-Meyer Comporession
  • SHACAL-2 block cipher.

Choose a random 2000-bit prime number, pp and random 1u,vp1 \le u, v \le p. For m,h{0,...p1}m, h \in \{0, ... p - 1\}, define h(H,m)=uHvm(modp)h(H, m) = u^H \cdot v^m (\mod p). is provable secure, but slow.


S(k,m)=H(kopad,H(kipadm))S(k,m) = H(k \oplus opad, H(k \oplus ipad || m))