Introduction to Modern Cryptography Reading Notes
4 Message Authentication Codes
MAC的定义
我们需要保证消息可靠性(message integrity)，以应对攻击者可能会注入或修改信息的情况，为此需要引入新的机制 message authentication code (MAC)。
A message authentication code (or MAC) consists of three probabilistic polynomial-time algorithms \((\text{Gen},\text{Mac},\text{Vrfy})\) such that:
- The key-generation algorithm \(\text{Gen}\) takes as input the security parameter \(1^n\) and outputs a key \(k\) with \(|k| \geq n\).
- The tag-generation algorithm \(\text{Mac}\) takes as input a key \(k\) and a message \(m \in \{0, 1\}^*\), and outputs a tag \(t\). Since this algorithm may be randomized, we write this as \(t \leftarrow \text{Mac}_k(m)\).
- The deterministic verification algorithm \(\text{Vrfy}\) takes as input a key \(k\), a message \(m\), and a tag \(t\). It outputs a bit \(b\), with \(b = 1\) meaning valid and \(b = 0\) meaning invalid. We write this as \(b := \text{Vrfy}_k(m, t)\).
It is required that for every \(n\), every key \(k\) output by \(\text{Gen}(1^n)\), and every \(m \in \{0, 1\}^∗\), it holds that \(\text{Vrfy}_k(m, \text{Mac}_k(m)) = 1\).
If there is a function \(\ell\) such that for every \(k\) output by \(\text{Gen}(1^n)\), algorithm \(\text{Mac}_k\) is only defined for messages \(m \in \{0, 1\}^{\ell(n)}\), then we call the scheme a fixed-length MAC for messages of length \(\ell(n)\).
接下来就是关于 MAC 的安全测试和安全定义。
The message authentication experiment \(\text{Mac-forge}_{\mathcal{A},\Pi(n)}\):
- A key \(k\) is generated by running \(\text{Gen}(1^n)\).
- The adversary \(\mathcal{A}\) is given input \(1^n\) and oracle access to \(\text{Mac}_k(\cdot)\).The adversary eventually outputs \((m, t)\). Let \(Q\) denote the set of all queries that \(\mathcal{A}\) submitted to its oracle.
- \(\mathcal{A}\) succeeds if and only if (1) \(\text{Vrfy}_k(m, t) = 1\) and (2) \(m \notin Q\).In that case the output of the experiment is defined to be \(1\).
也就是说，\(\mathcal{A}\) 能多次访问黑盒 \(\text{Mac}_k\)，如果构造出任意一组能通过 \(\text{Vrfy}\) 验证的，且自己没有把明文输入给 \(\text{Mac}_k\) 的 \((m,t)\)，就算 \(\mathcal{A}\) 成功。注意到，如果通过 \(t\) 构造出一个 \(m\)，使得 \((m,t)\) 通过验证，那么 \(\mathcal{A}\) 也是通过该测试的。
对于安全的定义和之前类似，即通过测试的概率可忽略，就不再抄一遍了。
上面的定义并没有预防 replay attacks，即攻击者可以重复发送一条信息（比如，转账请求）。这种问题一般在应用层面进行解决，比如在消息中添加编号或时间戳这类信息。
上面的定义也没有排除攻击者为已有的消息 \(m\) 生成一个新的 tag \(t'\) 的可能性。为此需要定义 Strong unforgeability，关于它的测试 \(\text{Mac-sforge}_{\mathcal{A},\Pi(n)}\) 和 \(\text{Mac-forge}_{\mathcal{A},\Pi(n)}\) 基本差不多，除了条件(2)改为 \((m,t)\notin Q\)。由此可以定义强安全(strong security)
一个安全的 MAC，如果使用规范验证(canonical verification)，即直接对比 \(\text{Mac}_k(m)\) 和 \(t\) 是否一致，那么它也是强安全的。
构造安全MAC
通过伪随机函数可以构造安全的 MAC (fixed-length)
Let \(F\) be a (length preserving) pseudorandom function. Define a fixed-length MAC for messages of length \(n\) as follows:
- \(\text{Mac}\): on input a key \(k \in \{0, 1\}^n\) and a message \(m \in \{0, 1\}^n\), output the tag \(t := F_k(m)\).
- \(\text{Vrfy}\): on input a key \(k \in \{0, 1\}^n\), a message \(m \in \{0, 1\}^n\), and a tag \(t \in \{0, 1\}^n\), output \(1\) if and only if \(t= F_k(m)\).
但是，这种构造方式是 fixed-length，且消息相当短的，并不实用，但是可以通过它来构造任意长度的 MAC。
Let \(\Pi'=(\text{Mac}',\text{Vrfy}')\) be a fixed-length MAC for messages of length \(n\).Define a MAC as follows:
- \(\text{Mac}\): on input a key \(k\in\{0,1\}^n\) and a message \(m\in\{0,1\}^∗\) of (nonzero) length \(\ell<2^{n/4}\), parse \(m\) as \(d\) blocks \(m_1,..., m_d\), each of length \(n/4\). (The final block is padded with \(0\)s if necessary.) Choose a uniform message identifier \(r\in\{0, 1\}^{n/4}\).
For \(i = 1,\dots,d\), compute \(t_i \leftarrow \text{Mac}'_k(r||\ell||i||m_i)\), where \(i\), \(\ell\) are encoded as strings of length \(n/4\). Output the tag \(t := \langle r,t_1,...,t_d\rangle\).- \(\text{Vrfy}\): on input a key \(k\in\{0, 1\}^n\), a message \(m\in\{0, 1\}^∗\) of nonzero length \(\ell < 2^{n/4}\), and a tag \(t=\langle r, t_1,...,t_{d'}\rangle\), parse \(m\) as d blocks \(m_1,...,m_d\), each of length \(n/4\). (The final block is padded with \(0\)s if necessary.) Output \(1\) if and only if \(d' = d\) and \(\text{Vrfy}'_k(r||\ell||i||m_i, t_i)=1\) for \(1\leq i\leq d\).
可以证明，这种构造是安全的。（证明太长了，有时间看一看）
CBC-MAC
上面的构造方式是非常低效的。
下面是一个基础版本的CBC-MAC，对于任意的固定长度的消息，它是安全的
Let \(F\) be a pseudorandom function, and fix a length function \(\ell(n) > 0\).The basic CBC-MAC construction is as follows:
- \(\text{Mac}\): on input a key \(k\in\{0, 1\}^n\) and a message \(m\) of length \(\ell(n)\cdot n\),do the following (set \(\ell=\ell(n)\) in what follows):
- Parse \(m\) as \(m = m_1,...,m_{\ell}\) where each \(m_i\) is of length \(n\).
- Set \(t_0 := 0^n\). Then, for \(i = 1\) to \(\ell\) , set \(t_i := F_k(t_{i−1} \oplus m_i)\). Output \(t_{\ell}\) as the tag.
- \(\text{Vrfy}\): on input a key \(k\in \{0, 1\}^n\), a message \(m\), and a tag \(t\), do: If \(m\) is not of length \(\ell(n)\cdot n\) then output \(0\). Otherwise, output \(1\) if and only if \(t\stackrel{?}{=}\text{Mac}_k(m)\).
当发送不同长度的消息时，它将不再安全；另外，如果将 tag 改为所有的 \(m_i\)，也不再安全。
对于任意长度的消息（假设是 \(n\) 的倍数），有两种安全的修改方式：
- 在所有消息的最前面加入一个 \(n\)-bits 的块，表示消息的长度 \(|m|\)，做basic CBC-MAC。注意，如果把消息长度加在消息的最后面，是不安全的。（FIGURE 4.2）
- 选两个 key \(k_1\) 和 \(k_2\)，用 \(k_1\) 做一次 basic CBC-MAC 得到 \(t\)，然后将 \(t'=F_{k_2}(t)\) 作为 tag。
（所以任意固定长度和任意长度的区别到底是什么啊）任意固定长度可以避免长度扩展攻击之类的。
这两种方式的安全性证明标了星号，先跳过（
GMAC 和 Poly1305
两种比 CBC-MAC 更高效的 MAC。
skip
Information-Theoretic MACs
标了星号，skip