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

2020-05-28 cryptography 密码学 消息认证码

消息认证码 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\)
  1. 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 固定。

本人保留对侵权者及其全家发动因果律武器的权利

版权提醒

如无特殊申明,本站所有文章均是本人原创。转载请务必附上原文链接:https://www.laytonchen.com/post/crypto/crypto-mac/

如有其它需要,请邮件联系!版权所有,违者必究!