第 9 章：消息认证码 MAC¶
目前讲到的所有加密方式都没有确保完整性。我们需要一种方式来维护消息的完整性。
消息认证码 Message Authentication Code¶
现在发送者和接收者都有同一个密钥。
- \(k \leftarrow Gen(1^n)\)，密钥生成。
- \(t \leftarrow Mac_k(m)\)，标签生成。
- \(b := Vrfy_k(m, t)\)，验证算法。其中 \(\forall k \forall m, Vrfy_k(m, Mac_k(m)) = 1\)。
MAC 的安全性¶
定义一个实验“Mac 伪造”\(\text{Mac-forge}_{A, \Pi}\)：
- \(k \leftarrow Gen(1^n)\)
- 对手有访问 \(Mac_k(\cdot)\) 的权限。
- 对手：输出 \((m, t)\)。在这之前向 \(Mac_k(\cdot)\) 询问任意值 \(x \in Q\)。
\(\text{Mac-forge}_{A, \Pi} = 1\) 如果有 \(Vrfy_k(m, t) = 1\) 并且 \(m \notin Q\)，否则 \(\text{Mac-forge}_{A, \Pi} = 0\)。
如果对于所有的 PPT 对手，\(\Pr[\text{Mac-forge}_{A, \Pi} = 1] \leq negl(n)\)，那么 MAC 是安全的。
伪造攻击¶
- 存在性伪造：攻击者在查询 MAC oracle 后选择要伪造的消息，就是上面那个 \(\text{Mac-forge}\)。
- 选择性伪造：对手在进行攻击前选择一条消息，但是在之后无法查询该消息。
- 通用伪造：攻击者可以在查询 MAC oracle 后为任何消息创建 MAC。
复用攻击¶
MAC 可以保证攻击者不能新建可以验证的信息，但是可没说过能防御以前用过的信息。
防御方式：
- 使用序列号。
- 使用时间戳。
- 使用随机数。
使用 PRF 的定长 MAC¶
F 是一个 PRF。定义一个定长 MAC：
- \(Gen(1^n) = \{0, 1\}^n \to k\)，随机而平均地生成的。
- \(Mac_k(m) = F_k(m) = t\)。
- \(Vrfy_k(m, t) = 1\) 当且仅当 \(t = F_k(m)\)。
如果 F 是 PRF，这个系统就是一个安全的定长 MAC 系统。
变长 MAC¶
有个明显的思路是分块，给块的末尾补上 0。对于第 i 个块，算出：
- 一个新鲜出炉的随机辨识符 \(r\)；
- 信息长度 \(l\)；
- 块的编号 \(i\)；
- 信息 \(m_i\)。
这四个部分每个最多 \(n / 4\) 比特长。
\(t_i \leftarrow Mac'_k(r || l || i || m_i)\)。
基本 CBC-MAC¶
现在有一个 PRF \(F\)。基本 CBC-MAC \(Mac_k(m)\)：
- 把 m 分割为 \(m_1, \cdots, m_l\)。
- \(t_0 := 0^n\)。
- 从 1 到 l：\(t_i := F_k(t_{i - 1} \oplus m_i)\)。
- 输出为 \(t_l\)。
\(Vrfy_k(m, t)\) 检查是否 \(t = Mac_k(m)\)。
哈希函数¶
哈希的安全要求¶
- 哈希函数应该是单向的。
- 很难找到另外一个值，它的哈希和一个已知值的哈希相同。
- 很难找到另外一个值，它的哈希和一个已知值相同。