密码学专题| 三、完整性保护和消息认证码

消息认证码 MAC

消息鉴别码 MAC 的定义如下：

1. Gen: 输入 \(1^n\) ，输出秘钥 k
2. Mac: 输入 k 和消息 \(m \in \{0,1\}^* \)，输出签名 t。
3. Verify: 输入秘钥 k 消息 \(m \in \{0,1\}^* \) 以及签名 t ，输出布尔值： \( b \leftarrow Verify_k(m, t)\)

考虑其攻击模型 \(Adv_A^{\Pi_M}\)：

1. 考虑一个多项式运行时间的敌手 A 运行 Gen 生成随机秘钥 k。
2. A 可以任意访问黑盒 \(Mac_k\)，并输出任意多 \( (m,t) \in Q \) 对。
3. A 最终构造一对 \( (m^,t^) \notin Q \) 满足 \( Verify_k(m, t) = 1 \)

如果其 \(Adv_A^{\Pi_M}\) 满足如下公式，则认为该消息认证方案 \(\Pi_M\) 是计算安全的： \[ Pr[Adv_A^{\Pi_M} = 1] \le negl(n) \]

注意，该攻击模型 \(Adv_A^{\Pi_M}\) 未考虑重放攻击的可能性，应对重放攻击的方案是在协议中引入状态信息，具体有如下两种解决方案：

1. 引入序列号
2. 引入时间戳

基于伪随机函数构造的消息认证码

构造定长的 MAC 方案

定长的 MAC 可以使用伪随机函数 \(F_k\) 来构造：

1. Gen: 输入 \(1^n\) ，随机选取秘钥 \(k \leftarrow\{0,1\}^n\)
2. Mac: 输入 \(k \in \{0,1\}^n\) 和消息 \(m \in \{0,1\}^n\)，输出签名 \(t = F_k(m) \)。
3. Verify: 输入秘钥 \(k \in \{0,1\}^n\) 消息 \(m \in \{0,1\}^n\) 以及签名 \(t \in \{0,1\}^n\) ，判断 t 是否等于 \(t = F_k(m) \)。

构造不定长的 MAC 方案

可以构造一种使用伪随机函数 \(F_k\) 来构造的计算安全的任意长度 MAC 方案。一种方式是使用 CBC-MAC 方案。构造方法如下：

考虑一个伪随机函数 \(F_k\) 以及一个从秘钥长度确定分组数的函数 l(m,n)。

1. Gen: 输入 \(1^n\) ，随机选取秘钥 \(k \leftarrow\{0,1\}^n\)
2. 输入 \(k \in \{0,1\}^n\) 和消息 \(m \in \{0,1\}^{l(m,n)n}\)，完成如下构造:

1. 将 m 分成 l 个长度为 n 的消息 \(m_1,m_2 … m_l\)，令 t = 0
2. 从 i = 1 到 l 计算 \(t_i = F_k(t_{i-1} \bigotimes m_i )\)
3. 输出 \(t_l\)

3. Verify: 输入秘钥 \(k \in \{0,1\}^n\) 消息 \(m \in \{0,1\}^{l(m,n)n}\) 以及签名 \(t \in \{0,1\}^n\)。当且仅当 t 等于 \(Mac_k(m) \)时，输出 1.

注意这个方案目前要求 m 的长度已知，因此对于任意未知长度消息，需要对 CBC-MAC 方案进行改造： 一种方案是首先使用 k1 进行 CBC-MAC 计算得到 \(t’ = Mac_{k_1}(m)\)，而后使用 \(t = F_{k_2}(t’)\)

但是使用伪随机函数并不是构造消息认证码 MAC 的最佳方案。下面介绍使用抗碰撞的哈希函数来构造 MAC 的方案。

基于抗碰撞的散列函数构造的消息认证码

抗碰撞的散列函数

散列函数是一种将不定长消息映射为定长字符串的算法，通常要求有良好的抗碰撞特性。形式化的定义如下：

散列函数 是一个多项式时间的概率算法 \(\Pi_H = \{Gen,Hash\}\)，满足：

1. Gen: 输入一进制参数 \(1^n\) 得到随机化种子 \(s \leftarrow \{0,1\}^n \)
2. hash: 输入种子 \(s \in \{0,1\}^n \) 和一个不定长消息 \(m \in \{0,1\}^* \)，输出一个定长字符串 \(h \in \{0,1\}^{l(n)}\)。长度 l 是 n 的一个确定性函数。

此时可以定义强碰撞攻击 \(Adv_{A,\Pi_H}^{strong}\)：

1. 一个多项式运行时间的敌手 A 通过 Gen 得到种子 s。
2. 敌手 A 通过 s 并输出两个消息 \(m\) 和 \(m’\)
3. 定义当且仅当 \(m \ne m’ \) 且 \( Hash(s, m) = Hash(s, m’) \) 时输出 1，否则为 0。

如果一个散列函数 \(\Pi_H \) 是对抗强碰撞攻击的，则： \[ Pr[Adv_{A,\Pi_H}^{strong} = 1] \le negl(n) \]

此外还有安全性假设更弱的弱碰撞攻击 \(Adv_{A,\Pi_H}^{weak}\)：

1. 一个多项式运行时间的敌手 A 通过 Gen 得到种子 s。
2. 敌手 A 输入 s 和一个指定的消息 \(m\) 输出另一个消息 \(m’\)
3. 定义当且仅当 \(m \ne m’ \) 且 \( Hash(s, m) = Hash(s, m’) \) 时输出 1，否则为 0。

如果一个散列函数 \(\Pi_H \) 是对抗弱碰撞攻击的，则： \[ Pr[Adv_{A,\Pi_H}^{weak} = 1] \le negl(n) \]

生日攻击的结论：

设进行 q 次碰撞，大约 \(O(2^{l/2})\) 次碰撞，可以有较大概率发现一个强碰撞。如果 l(n) 是超对数的，那么则存在一个正整数 N，使得 n>N 时，具有碰撞的计算安全。

Merkle-Damgrad 变换

该变换将一个定长的散列函数扩展成一个任意长度的散列函数，但是保持了前者的抗强碰撞特性。假设其输入消息长度为大于 2l(n) ，输出长度为 l(n)，则：

1. Gen： 输入 \(1^n\) ，随机选取秘钥 \(s \leftarrow\{0,1\}^n\)
2. Hash: 输入 s 和消息 \(m \in {0,1\}^* \)。此时：

1. 将 m 分组为 \(m_1,m_2 … m_I\)，并设 z_0 = 0
2. i 从 1 到 I遍历，\(z_i = H(s, z_{i-1}||m_i)\)
3. 输出 \(z_I\)

实际使用的散列函数

实际使用的哈希函数有：

1. md5， sha-1 这些分别是 128 bit 和 160 bit 的哈希函数。但是已经不再安全，可以有比生日攻击成本小的攻击手段。md5 碰撞约 \(2^{18}\),sha-1 约 \(2^{63}\)
2. sha-2 包括 SHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256 等等
3. sha-3 自 2015 年发布，包括：SHA3-224、SHA3-256、SHA3-384、SHA3-512、SHAKE128、SHAKE256

基于抗碰撞的散列函数构造的 NMAC 、CMAC 和 HMAC

NMAC 方案首先生成了种子 s 以及两个秘钥 k1 和 k2。而后计算 \(NMAC: t = hash_{s,k_1}(Hash_{s,k_2}(m)) \)。其中第一个 hash 是外部固定长度哈希函数，内部 Hash 是 Merkle-Damgrad 中的 Hash 函数。

现实中，通常使用无秘钥的哈希函数，也就是假设 s 是固定的。由 k1 和 k2 构成了 NMAC 的秘钥。

HMAC 方案是 NMAC 方案的一个特例：

假设 （Gen, hash) 是一个抗碰撞的定长散列函数，（Gen, Hash) 使其对应的 Merkle-Damgrad 变换。那么：

1. Gen: 输入 \(1^n\) ，得到 \(s \leftarrow Gen(1^n) \)。并选取一个秘钥 \(k \leftarrow {0,1}^n \)，输出（s,k)。
2. HMAC: 输入 (s,k) 和一个消息 \(m \in \{0,1\}^* \)。则 \( t = Hash_{s,IV}( ( k \bigotimes opad) || ( Hash_{s,IV}( (k \bigotimes ipad) || m ) )\)
3. Verify: 输入 (s,k)、消息 \(m \in \{0,1\}^* \) 和 t。验证 t 和 HMAC 是否相等。

其中 opad 是 0x36 根据需要重复 padding 而成， ipad 是 0x5c 根据需要 padding 而成。随机数种子通常由哈希算法 hash 固定。