Message Authentication Code

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

Define: MAC $I=(S, V)$ defined over $(\mathcal{K, M, T})$:

• $S(k, m)$ outputs $t$ in $\mathcal{T}$.
• $V(k, m, t)$ output ‘yes’ or ‘no’

S stands for signing, V stands for verification.

Secure MACs

Attacker can give Alice $m_1, ... m_q$, to get $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:

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

Secure PRF -> Secure MAC

The error bound of PRF is $Adv_{MAC}[A, I_F] \leq Adv_{PRF}[B, F] + 1/|Y|$ The $I_F$ is secure as long as $|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.

CBC-MAC and NMAC

It is important to use independent $k_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, t\oplus m)$ , the MAC is t!

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

We need to rotate keys for after $|X|^{1/2}$ messages with ECBC-MAC or $|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 $k_1$ for padding block, and $k_2$ for no-padding block to resolve the ambiguity. It is as safe as CBC-MAC, and standardized by NIST.

PMAC

Parallel MAC

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

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) \in \{1, ... q\} ^2$ where q is a large prime number such as ($q = 2^{128} + 51$), and break the message to blocks, $(m[1], ..., m[L])$:

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

Many-time MAC

Cater-Wegman MAC:

for F be a secure PRF, for r is random chosen: $r \leftarrow \{0, 1\}^n$. The verification is: $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 $\mathcal{(K, M, T)}$, Let H: $M^{big} \to M$

Def: $I^{big} = (S^{big}, V^{big})$ over $(K, M^{big}, T)$ as:

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

Birthday Attack

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

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

Merkle-Damgard Paradigm

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

Davies-Meyer compression

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

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

Miyaguchi-Preneel:

Other natural variants are insecure:

SHA256:

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

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

HMAC

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