【现代密码学】笔记4--消息认证码与抗碰撞哈希函数《introduction to modern cryphtography》-阿里云开发者社区

写在最前面

主要在哈工大密码学课程张宇老师课件的基础上学习记录笔记。

内容补充：骆婷老师的PPT

《introduction to modern cryphtography》–Jonathan Katz, Yehuda Lindell（现代密码学——原理与协议）中相关章节

密码学复习笔记这个博主好有意思

初步笔记，如有错误请指正

快速补充一些密码相关的背景知识

4 消息认证码与抗碰撞哈希函数

本节学习用于保护信息的完整性和真实性的消息认证码（MAC）和抗碰撞的哈希函数（CRHF）。
目录：MAC、构建安全MAC、CBC-MAC、CRHF、HMAC、信息论上MAC。
完整性与真实性（Integrity and Authentication）

敌手篡改传输中的密文（或明文）是对完整性的攻击；
敌手伪装成Alice发送密文（或明文）是对真实性（认证）的攻击；
上述两种攻击可以归结为对真实性（认证）的攻击，消息是由敌手构造并发出的；
注意，这里的真实性是指消息的来源是来自接受者所预期的发送者，不是指内容的真假！

MAC

MAC的词法（Message Authentication Code）

密钥 k kk, 标签(tag) t tt, 一个比特 b bb 为有效的 (valid}) ，如果 b = 1 b=1b=1;
或无效的 (invalid}) ，如果 b = 0 b=0b=0.
密钥生成 Key-generation 算法 k ← G e n ( 1 n ) , ∣ k ∣ ≥ n k \gets \mathsf{Gen}(1^n), |k| \ge nk←Gen(1n),∣k∣≥n.
标签生成 Tag-generation 算法 t ← M a c k ( m ) t \gets \mathsf{Mac}_k(m)t←Mack(m).
验证 Verification 算法 b : = V r f y k ( m , t ) b:= \mathsf{Vrfy}_k(m,t)b:=Vrfyk(m,t).
消息认证码 Message authentication code: Π = ( G e n , M a c , V r f y ) \Pi = (\mathsf{Gen}, \mathsf{Mac}, \mathsf{Vrfy})Π=(Gen,Mac,Vrfy).
基本正确性需求 Basic correctness requirement : V r f y k ( m , M a c k ( m ) ) = 1 \mathsf{Vrfy}_k(m,\mathsf{Mac}_k(m)) = 1Vrfyk(m,Mack(m))=1.
注：不同于加密方案，MAC并不需要从标签得到密文。

MAC安全

直觉上，没有敌手能够伪造一个从未被发送过的新消息的有效标签。这里“新消息”是为了排除“重放攻击”。
重放攻击（Replay attack）：敌手记录并发送之前的消息和标签，从而发送了一个伪造的消息并带有有效的标签；为了避免重放攻击，可以通过两种非密码学的方法。

序列号：接收方需要记录之前的序列号，从而发现序列号较小（或曾经接收过的）的旧消息；
时间戳：双方维护时钟同步，从而发现晚与当前时钟的旧消息；
这两种方法都不依赖于密码学，因此，防御重放攻击不需要在密码学的范畴内考虑。

存在性不可伪造（Existential unforgeability）：不能伪造任何消息的标签，一个都不能伪造。

存在性伪造 Existential forgery: 至少伪造一个消息的标签。
选择性伪造 Selective forgery: 实施攻击前选择一个消息，并伪造该消息的标签。
全域性伪造 Universal forgery: 伪造任意给定的消息的标签。
最强的安全目标是阻止最弱的敌手造成的后果。

适应性选择消息攻击（Adaptive chosen-message attack (CMA)）：敌手在攻击过程中始终具有获得任意消息的有效标签的能力，即访问标签生成预言机；

定义MAC安全

消息认证实验M a c f o r g e A , Π ( n ) \mathsf{Macforge}_{\mathcal{A},\Pi }(n)MacforgeA,Π(n)在挑战者和敌手之间：

挑战者生成密钥 k ← G e n ( 1 n ) k \gets \mathsf{Gen}(1^n)k←Gen(1n).
敌手 A \mathcal{A}A 具有访问标签生成算法M a c k ( ⋅ ) \mathsf{Mac}_k(\cdot)Mack(⋅)的预言机的能力，并输出 ( m , t ) (m,t)(m,t). 对预言机查询的消息集合为 Q \mathcal{Q}Q 。
M a c f o r g e A , Π ( n ) = 1 ⟺ \mathsf{Macforge}_{\mathcal{A},\Pi }(n)=1 \iffMacforgeA,Π(n)=1⟺ V r f y k ( m , t ) = 1 \mathsf{Vrfy}_k(m,t)=1Vrfyk(m,t)=1 ∧ \land∧ m ∉ Q m \notin \mathcal{Q}m∈/Q. 敌手成功，如果输出的消息和标签通过了验证，并且输出的消息是从未向预言机查询过的新消息。

定义：一个 MAC Π \PiΠ 是在适应性CMA下的存在性不可伪造 (existentially unforgeable under an adaptive CMA)，如果 ∀ \forall∀ PPT A \mathcal{A}A, ∃ \exists∃ n e g l \mathsf{negl}negl 使得: Pr ⁡ [ M a c f o r g e A , Π ( n ) = 1 ] ≤ n e g l ( n ) . \Pr [\mathsf{Macforge}_{\mathcal{A},\Pi }(n)=1] \le \mathsf{negl}(n).Pr[MacforgeA,Π(n)=1]≤negl(n).
如果对名称不熟悉，可以参考下方的概念回顾。

概念回顾（是的，我忘记这些缩写是什么了。。）

PPT在密码学中代表“概率多项式时间”（Probabilistic Polynomial Time），这是一种衡量算法或攻击者能力的标准。在这个特定的上下文中，PPT是用来描述攻击者的计算能力。

让我们来详细解释这个定义：

MAC的定义

MAC：MAC代表“消息认证码”（Message Authentication Code），它是一种用于验证消息完整性和来源真实性的加密工具。
存在性不可伪造：一个MAC系统被称为“存在性不可伪造”的，意味着没有攻击者可以成功地伪造一个有效的MAC（即使是一个新的、以前未见过的MAC），除非通过微不足道的概率。

适应性CMA（Chosen Message Attack）

适应性CMA：适应性选择消息攻击（Adaptive Chosen Message Attack）是一种攻击模型，其中攻击者可以选择并获得先前消息的MAC值，然后尝试基于这些信息伪造新消息的MAC。
存在性不可伪造：在适应性CMA环境下，存在性不可伪造意味着攻击者在选择任意消息并获取其MAC后，仍然无法伪造其他任何消息的MAC。

PPT攻击者

PPT攻击者：概率多项式时间攻击者是指那些拥有多项式时间计算能力的攻击者。这意味着他们的计算资源是有限的，不能进行无限的尝试或拥有无限的计算能力。
重要性：在考虑密码系统的安全性时，通常假设攻击者是PPT的。这是一种现实的假设，因为实际中攻击者的资源是有限的。

不可忽略的概率（negl(n)）

n e g l ( n ) \mathsf{negl}(n)negl(n)：这是一个表示概率的术语，指的是某个函数随着输入大小的增长而增长得极其缓慢，以至于在实际中可以忽略不计。
应用：在这个定义中，如果对于所有的PPT攻击者A \mathcal{A}A，伪造MAC的概率 Pr ⁡ [ M a c f o r g e A , Π ( n ) = 1 ] \Pr [\mathsf{Macforge}_{\mathcal{A},\Pi }(n)=1]Pr[MacforgeA,Π(n)=1] 是可忽略的，那么就可以说这个MAC系统在适应性CMA下是存在性不可伪造的。

总结

所以，这个定义的含义是：一个MAC系统在适应性选择消息攻击下被认为是安全的，如果没有任何实际的、有限计算能力的攻击者能够以超过微不足道的概率成功伪造一个MAC。这个标准确保了即使在面对强大但现实的攻击者时，MAC系统也能保持其安全性和完整性。

案例

真实例子

WEP 802.11 MAC中的漏洞有两点
一是存在不同消息的CRC32可能是一样的情况，而且这种情况很容易给出。那么，敌手可以查询一个消息m mm并得到对应的标签t tt；然后，输出另一个与所查询消息m mm具有相同CRC32值的新消息m ′ m'm′，以及查到的标签t tt。
二是敌手可以查询一个消息m ′ m'm′并获得标签( r , t ′ ) (r, t')(r,t′)，由此计算得到F ( k , r ) = t ′ ⊕ C R C 32 ( m ′ ) F(k,r) = t'\oplus \mathsf{CRC32}(m')F(k,r)=t′⊕CRC32(m′)；输出一个新消息m mm以及标签t = ( r , F ( k , r ) ⊕ C R C 32 ( m ) ) t = (r, F(k,r)\oplus\mathsf{CRC32}(m))t=(r,F(k,r)⊕CRC32(m))。
上述漏洞展现了攻击MAC的两种常用手段：一是找到两个消息得到相同的中间结果，从而以一个消息的标签作为另一个新消息的标签；二是利用对一个/多个消息的标签来获得构造标签所需的信息，从而构造一个新消息的标签。

例题

如果认为是安全的，则要用反证法证明，若新方案不安全，则原方案也不安全；
如果认为是不安全的，则给出一个新消息和对应的标签；

MAC应用

Web cookie：Web服务器在发给浏览器的cookie中包含自己生成的MAC标签，来阻止攻击者伪造其他用户的cookie；
TCP SYN cookie：在TCP三次握手中，服务器在其发给客户端的初始序列号中包含一个服务器生成的MAC标签，来避免保留握手状态，从而防御SYN Flooding DDoS攻击；
临时一次口令：用户发送给服务器的临时登录口令为一个MAC标签p = M a c k ( T ) p=\mathsf{Mac}_k(T)p=Mack(T)，其中k kk为原始口令，T TT为当前时间（按半分钟取整）；敌手窃听了之前的临时口令也无法伪造未来的临时口令；

构建安全MAC

构造安全MAC

基于PRF构造安全MAC

F FF 是 PRF. ∣ m ∣ = n |m| = n∣m∣=n.
G e n ( 1 n ) \mathsf{Gen}(1^n)Gen(1n): k ← { 0 , 1 } n k \gets \{0,1\}^nk←{0,1}n .
M a c k ( m ) \mathsf{Mac}_k(m)Mack(m): t : = F k ( m ) t := F_k(m)t:=Fk(m).
V r f y k ( m , t ) \mathsf{Vrfy}_k(m,t)Vrfyk(m,t): 1 ⟺ t = ? F k ( m ) 1 \iff t \overset{?}{=} F_k(m)1⟺t=?Fk(m).

定理：如果 F FF 是一个PRF，那么上述构造是安全的固定长度 MAC。
引理：如果F FF是一个 PRF，那么F k t ( m ) = F k ( m ) [ 1 , … , t ] F^t_k(m) = F_k(m)[1,\dots,t]Fkt(m)=Fk(m)[1,…,t]也是一个PRF。

注：这个引理说明部分输出仍保留伪随机性。引理成立的原因在于，如果根据更短的输出可以区分出伪随机函数，那么根据原长度输出也可以区分出伪随机函数了。

证明基于PRF的安全MAC

证明思路是从PRF的区分器算法D DD规约到伪造标签的敌手算法A \mathcal{A}A。D DD作为A \mathcal{A}A的挑战者，用D DD要区分的预言机作为A \mathcal{A}A的标签生成预言机；当A \mathcal{A}A伪造标签成功时，D DD输出1。

证明基于PRF的安全MAC（续）

如果是真随机 f ff 被使用 t = f ( m ) t=f(m)t=f(m) 是均匀随机的.
Pr ⁡ [ D f ( ⋅ ) ( 1 n ) = 1 ] = Pr ⁡ [ M a c f o r g e A , Π ~ ( n ) = 1 ] ≤ 2 − n . \Pr[D^{f(\cdot)}(1^n)=1] = \Pr[\mathsf{Macforge}_{\mathcal{A},\tilde{\Pi}}(n) = 1] \le 2^{-n}.Pr[Df(⋅)(1n)=1]=Pr[MacforgeA,Π~(n)=1]≤2−n.
如果 F k F_kFk 被使用，那么就是在执行实验 M a c f o r g e A , Π ( n ) \mathsf{Macforge}_{\mathcal{A},\Pi}(n)MacforgeA,Π(n).
Pr ⁡ [ D F k ( ⋅ ) ( 1 n ) = 1 ] = Pr ⁡ [ M a c f o r g e A , Π ( n ) = 1 ] = ε ( n ) . \Pr[D^{F_k(\cdot)}(1^n)=1] = \Pr[\mathsf{Macforge}_{\mathcal{A},\Pi}(n) = 1] = \varepsilon(n).Pr[DFk(⋅)(1n)=1]=Pr[MacforgeA,Π(n)=1]=ε(n).
根据PRF的定义有，∣ Pr ⁡ [ D F k ( ⋅ ) ( 1 n ) = 1 ] − Pr ⁡ [ D f ( ⋅ ) ( 1 n ) = 1 ] ∣ ≥ ε ( n ) − 2 − n . \left| \Pr[D^{F_k(\cdot)}(1^n)=1] - \Pr[D^{f(\cdot)}(1^n)=1] \right| \ge \varepsilon(n) - 2^{-n}.∣∣Pr[DFk(⋅)(1n)=1]−Pr[Df(⋅)(1n)=1]∣∣≥ε(n)−2−n.

扩展到变长消息

对于变长消息，下面的建议是安全的吗？
建议1：将所有块异或后，对结果进行认证：t : = M a c k ′ ( ⊕ i m i ) t := \mathsf{Mac}_k'(\oplus_i m_i)t:=Mack′(⊕imi)；
建议2：对每个块分别认证，t i : = M a c k ′ ( m i ) t_i := \mathsf{Mac}_k'(m_i)ti:=Mack′(mi)；
建议3：对每个块连带一个序列号一起认证， t i : = M a c k ′ ( i ∥ m i ) t_i := \mathsf{Mac}_k'(i\| m_i)ti:=Mack′(i∥mi).

CBC-MAC

CBC概念回顾

CBC-MAC（Cipher Block Chaining Message Authentication Code）是一种基于块加密算法的消息认证码（MAC）构造方法。它使用的是密码块链接（Cipher Block Chaining，CBC）模式，这是一种常用的块加密操作模式。

构造固定长度的CBC-MAC

构造固定长度的CBC-MAC

为了构造用于变长消息的MAC，先学习固定长度的CBC-MAC，其与CBC结构类似，做了两处改变：
改动1：将初始向量IV改为0；如果不这样改动，则敌手查询 m 1 m_1m1 并获得 ( I V , t 1 ) (IV, t_1)(IV,t1)；然后，输出 m 1 ′ = I V ′ ⊕ I V ⊕ m 1 m_1' = IV' \oplus IV \oplus m_{1}m1′=IV′⊕IV⊕m1 并且 t ′ = ( I V ′ , t 1 ) t' = (IV',t_1)t′=(IV′,t1)，一个有效的标签。
改动2：标签只包括最后一个块的输出；如果不这样改动，则敌手查询 m i m_imi 并得到 t i t_iti；然后，输出 m i ′ = t i − 1 ′ ⊕ t i − 1 ⊕ m i m_i' = t_{i-1}' \oplus t_{i-1} \oplus m_{i}mi′=ti−1′⊕ti−1⊕mi 以及 t i ′ = t i t_{i}' = t_iti′=ti，一个有效的标签。

构造固定长度的CBC-MAC（续）

定理：如果F FF是一个PRF，那么上面的构造就是一个安全的固定长度MAC。
这个构造不能用于变长消息，因为对于一个块的消息m mm和标签t tt，敌手可以在其后添加一个块m ⊕ t m\oplus tm⊕t并且输出标签t tt。

安全变长MAC

有三种方法可以将CBC-MAC改造为用于变长消息的MAC，都可以防御上面在结尾添加新块的攻击。
输入长度密钥分离：k ℓ : = F k ( ℓ ) k_{\ell} := F_k(\ell)kℓ:=Fk(ℓ), 用 k ℓ k_{\ell}kℓ 作为 CBC-MAC 的密钥。不同长度下采用不同密钥，追加新块后长度变化，之前的标签无法利用。
在开头添加长度：在CBC-MAC的明文m mm前添加一个长度块∣ m ∣ |m|∣m∣。不同长度下消息有不同的初始块，追加新块后长度变化，之前的标签无法利用。
加密末块输出（ECBC-MAC）：采用两个密钥k 1 , k 2 k_1, k_2k1,k2。用k 1 k_1k1和CBC-MAC计算出 t tt，然后输出 t ^ : = F k 2 ( t ) \hat{t} := F_{k_2}(t)t^:=Fk2(t)。输出结果被加密，之前的标签无法利用。

MAC填充（Padding）

与加密类似，为了将消息长度与块长度对齐，MAC中也需要在消息中填充。为了安全性，需要保证填充是可逆的，即不同的消息在填充后也应该不同！
m 0 ≠ m 1 ⇒ p a d ( m 0 ) ≠ p a d ( m 1 ) . m_0\neq m_1 \Rightarrow \mathsf{pad}(m_0) \neq \mathsf{pad}(m_1).m0=m1⇒pad(m0)=pad(m1).
ISO的填充标准：用“100…00”填充，并按需填充哑块。
如果不填充哑块，则会导致什么？
CMAC（Cipher-based MAC）：不填充哑块，不加密最后一块的输出，密钥包括三个k , k 1 , k 2 k, k_1, k_2k,k1,k2

k kk用于CBC-MAC；
k 1 k_1k1 和 k 2 k_2k2 与最后一块消息异或来阻止利用最后一块输出；
用k 1 k_1k1 和 k 2 k_2k2 来区分是否添加了哑块。

CRHF：哈希函数Hash Function、定义抗碰撞Collision Resistance

定义哈希函数（Hash Function）

一个哈希函数 (压缩函数) 是一对PPT算法( G e n , H ) (\mathsf{Gen}, H)(Gen,H)满足以下条件:

一个密钥 s ← G e n ( 1 n ) s \gets \mathsf{Gen}(1^n)s←Gen(1n)， s ss 不保密.
H s ( x ) ∈ { 0 , 1 } ℓ ( n ) H^s(x) \in \{0,1\}^{\ell(n)}Hs(x)∈{0,1}ℓ(n)，其中 x ∈ { 0 , 1 } ∗ x \in \{0,1\}^*x∈{0,1}∗ 且 ℓ \ellℓ 为多项式。

若 H s H^sHs 只在 x ∈ { 0 , 1 } ℓ ′ ( n ) x \in \{0,1\}^{\ell'(n)}x∈{0,1}ℓ′(n) 上定义并且 ℓ ′ ( n ) > ℓ ( n ) \ell'(n) > \ell(n)ℓ′(n)>ℓ(n)，那么 ( G e n , H ) (\mathsf{Gen}, H)(Gen,H) 是固定长度的哈希函数。
上面的定义说明，哈希函数将长消息转变为短消息。

定义抗碰撞（Collision Resistance）

碰撞（Collision）：x ≠ x ′ x \neq x'x=x′ 并且 H ( x ) = H ( x ′ ) H(x) = H(x')H(x)=H(x′)。
抗碰撞（Collision Resistance）：对于任意PPT算法，找到碰撞是不可能的。
碰撞发现实验H a s h c o l l A , Π ( n ) \mathsf{Hashcoll}_{\mathcal{A},\Pi}(n)HashcollA,Π(n):

s ← G e n ( 1 n ) s \gets \mathsf{Gen}(1^n)s←Gen(1n).

敌手 A \mathcal{A}A 输入 s ss ，输出 x , x ′ x, x'x,x′. 注：敌手有s ss，意味着可以访问哈希函数

H a s h c o l l A , Π ( n ) = 1 ⟺ x ≠ x ′ ∧ H s ( x ) = H s ( x ′ ) \mathsf{Hashcoll}_{\mathcal{A},\Pi}(n) =1 \iff x\ne x' \land H^s(x) = H^s(x')HashcollA,Π(n)=1⟺x=x′∧Hs(x)=Hs(x′).
哈希函数 Π \PiΠ (G e n \mathsf{Gen}Gen, H s H^sHs) 是抗碰撞的，如果∀ \forall∀ ppt A \mathcal{A}A， ∃ n e g l \exists\;\mathsf{negl}∃negl 使得
Pr ⁡ [ H a s h c o l l A , Π ( n ) = 1 ] ≤ n e g l ( n ) . \Pr[\mathsf{Hashcoll}_{\mathcal{A},\Pi}(n)=1] \le \mathsf{negl}(n).Pr[HashcollA,Π(n)=1]≤negl(n).

哈希函数安全的更弱的概念

抗碰撞（Collision resistance）: 难以找到 ( x , x ′ ) , x ′ ≠ x (x, x'), x' \ne x(x,x′),x′=x 使得 H ( x ) = H ( x ′ ) H(x) = H(x')H(x)=H(x′).
抗二次原像（Second pre-image resistance）: 给定 s ss 和 x xx, 难以发现 x ′ ≠ x x' \ne xx′=x 使得 H s ( x ′ ) = H s ( x ) H^s(x') = H^s(x)Hs(x′)=Hs(x).
抗原像（Pre-image resistance）: 给定 s ss 和 y = H s ( x ) y = H^s(x)y=Hs(x), 难以发现 x ′ x'x′ 使得 H s ( x ′ ) = y H^s(x')=yHs(x′)=y.
攻击越难，反过来可以防范这种攻击的安全性就越弱。

关于CRHF的问题

如果认为不是，那么请给出一个碰撞；
如果认为是，则用反证法证明找到了H ′ H'H′的碰撞意味着H HH的碰撞。

哈希函数的应用

文件指纹和去重（Fingerprinting 和 Deduplication）：识别一个文件，用于病毒指纹识别，去重复，P2P文件共享；
默克尔树（Merkle Tree）：构造多个文件或一个文件多个部分的指纹，从而定位有问题的文件或者文件中的部分；
口令哈希（Password Hashing）：( s a l t , H ( s a l t , p w ) ) (salt, H(salt, pw))(salt,H(salt,pw))，缓解明文口令泄漏风险；
密钥派生（Key Derivation）：从一个高熵（但不必均匀随机）的共享秘密中派生一个密钥；
承诺方案（Commitment Scheme）：将一个承诺与一份信息绑定，隐藏承诺的信息；例如，互联网上掷硬币。

生日问题

生日问题：“如果一群人中有两个人的生日是同一天的概率有1/2，这群人数有多少？”。答案是23。这与我们平时的认知差异，也被称作“生日悖论”。具体计算见教材附件。
这个问题意味着哈希函数的输出需要足够长，否则敌手可能通过蛮力枚举来发现碰撞。
在现实攻击中，找到有意义的消息的碰撞对于攻击者来说更有价值。这对攻击者来说并不是难题，可以很容易的构造足够数量的、有意义的消息来实施攻击。对消息中一个单词的替换，所构造明文的数量翻番。

MD变换（Merkle-Damgård Transform）

从定长哈希函数( G e n , h ) (\mathsf{Gen}, h)(Gen,h)(2 ℓ 2\ell2ℓbits→ ℓ \to \ell→ℓbits,ℓ = ℓ ( n ) \ell = \ell(n)ℓ=ℓ(n))构造变长哈希函数 CRHF( G e n , H ) (\mathsf{Gen}, H)(Gen,H):

G e n \mathsf{Gen}Gen: 不变
H HH: 密钥s ss与串x ∈ { 0 , 1 } ∗ x \in \{0,1\}^*x∈{0,1}∗,L = ∣ x ∣ < 2 ℓ L=|x|< 2^{\ell}L=∣x∣<2ℓ:

B : = ⌈ L ℓ ⌉ B := \lceil \frac{L}{\ell} \rceilB:=⌈ℓL⌉ (块数)。用0填充。 ℓ \ellℓ-位的块 x 1 , … , x B x_1,\dotsc,x_Bx1,…,xB。最后一块是长度 x B + 1 : = L x_{B+1} := LxB+1:=L， L LL 以 ℓ \ellℓ 位编码，这是必要的，因为只用0填充会导致不同消息的输入是一样的。
z 0 : = I V = 0 ℓ z_0 := IV = 0^\ellz0:=IV=0ℓ。对于 i = 1 , … , B + 1 i=1,\dotsc,B+1i=1,…,B+1，计算 z i : = h s ( z i − 1 ∥ x i ) z_i := h^s(z_{i-1}\| x_i)zi:=hs(zi−1∥xi)。

MD变换的安全性

定理：如果h hh是定长CRHF，那么H HH也是CRHF。
证明：思路是H HH上的碰撞意味着h hh上的碰撞，而h hh是不会被找到碰撞的。两个消息x ≠ x ′ x \ne x'x=x′，长度分别为L LL和L ′ L'L′，块数分别为B BB和B ′ B'B′，使得H s ( x ) = H s ( x ′ ) H^s(x) = H^s(x')Hs(x)=Hs(x′)。有两种情况：

L ≠ L ′ L \ne L'L=L′: z B ∥ L ≠ z B ′ ∥ L ′ z_B\| L \ne z_{B'}\| L'zB∥L=zB′∥L′；长度不同，意味着最后一个哈希函数h hh的输入不同，但输出相同，发现碰撞。
L = L ′ L = L'L=L′: z i ∗ − 1 ∥ x i ∗ ≠ z i ∗ − 1 ′ ∥ x i ∗ ′ z_{i^*-1}\| x_{i^*} \ne z_{i^*-1}'\| x_{i^*}'zi∗−1∥xi∗=zi∗−1′∥xi∗′；长度相同，意味着中间某一块的输入不同，但输出相同，发现碰撞。
因此，必定有 x ≠ x ′ x \neq x'x=x′ 使得 h s ( x ) = h s ( x ′ ) h^s(x) = h^s(x')hs(x)=hs(x′)。

作业中有关于MD变换的变体的安全性分析问题。

从分组密码构造CRHF

可以从块密码来构造CRHF，例如Davies-Meyer方法 (SHA-1/2, MD5) h i = F m i ( h i − 1 ) ⊕ h i − 1 h_{i} = F_{m_{i}}(h_{i-1}) \oplus h_{i-1}hi=Fmi(hi−1)⊕hi−1，或者 Miyaguchi-Preneel 方法 (Whirlpool) h i = F h i − 1 ( m i ) ⊕ h i − 1 ⊕ m h_{i} = F_{h_{i-1}}(m_{i}) \oplus h_{i-1} \oplus mhi=Fhi−1(mi)⊕hi−1⊕m。
定理：如果F FF是一个理想的加密方案，那么Davies-Meyer构造得到一个CRHF。注：理想的加密方案参考后面要学习的随机预言机模型。目前，没有找到F FF是强伪随机排列下该方法是CRHF的证明。
对于这个定理不做严格证明，而是回答两个问题：

如果 h i = F m i ( h i − 1 ) h_{i} = F_{m_{i}}(h_{i-1})hi=Fmi(hi−1) ，不与 h i − 1 h_{i-1}hi−1 异或，会如何？敌手尝试以相同的h i h_ihi和不同的m i m_imi对F FF求逆。
如果 F FF 不是理想的，而是 ∃ x , F k ( x ) = x \exists x, F_k(x)=x∃x,Fk(x)=x，会如何？敌手输入不同m i m_imi，但都得到0；

SHA-1和MD5

曾将广泛采用的哈希函数SHA1和MD5都已经被破解。对于128位的MD5，找到碰撞需要2 20.96 2^{20.96}220.96；对于160位的SHA1，找到碰撞需要2 51 2^{51}251。

HMAC

Hash-and-MAC

有了CRHF，一个自然的想法是：先将任意长度消息哈希，然后通过PRF对哈希值做MAC，实现任意长度消息MAC。F k ( H ( m ) ) F_k(H(m))Fk(H(m))
这个方案的安全性分两种情况分析：当不同消息得到相同哈希值时，这意味着碰撞发生；否则，意味着MAC标签被伪造。

NMAC

使用CRHF（MD变换）来构造MAC，而不需要用PRF
之所以需要开头的密钥，是为了在哈希函数为弱抗碰撞性时也保障安全；如果哈希函数是CRHF，则不需要开头的密钥
缺点：需要修改哈希函数（MD变换中初始向量）

HMAC（基于哈希的MAC）

以MD变换为基础构造一个安全的MAC。在开头和结尾以两个不同密钥作为哈希函数输入。
不需要修改哈希函数。
G e n ( 1 n ) \mathsf{Gen}(1^n)Gen(1n): 输出 ( s , k ) (s, k)(s,k). s ← G e n ~ , k ← { 0 , 1 } n s \gets \widetilde{\mathsf{Gen}}, k \gets \{0,1\}^ns←Gen,k←{0,1}n u.a.r；
M a c s , k ( m ) \mathsf{Mac}_{s,k}(m)Macs,k(m): t : = H I V s ( ( k ⊕ o p a d ) ∥ H I V s ( ( k ⊕ i p a d ) ∥ m ) ) t := H_{IV}^s\Big((k \oplus \mathsf{opad}) \| H_{IV}^s\big((k \oplus \mathsf{ipad}) \| m\big)\Big)t:=HIVs((k⊕opad)∥HIVs((k⊕ipad)∥m))
V r f y s , k ( m , t ) \mathsf{Vrfy}_{s,k}(m,t)Vrfys,k(m,t): 1 ⟺ t = ? M a c s , k ( m ) 1 \iff t \overset{?}{=} \mathsf{Mac}_{s,k}(m)1⟺t=?Macs,k(m)

HMAC安全性

定理：G ( k ) = def h s ( I V ∥ ( k ⊕ o p a d ) ) ∥ h s ( I V ∥ ( k ⊕ i p a d ) ) = k 1 ∥ k 2 G(k) \overset{\text{def}}{=} h^s(IV\| (k\oplus \mathsf{opad})) \| h^s(IV\| (k\oplus \mathsf{ipad})) = k_1\| k_2G(k)=defhs(IV∥(k⊕opad))∥hs(IV∥(k⊕ipad))=k1∥k2 。其中，h hh是CRHF。如果G GG是PRG，那么HMAC是安全的。
在HMAC之前，其他不安全的方案包括：
H s ( k ∥ x ) H^s(k\| x)Hs(k∥x) 存在长度扩展攻击弱点。在获得H s ( k ∥ x ) H^s(k\| x)Hs(k∥x)和消息长度后，敌手能够获得新消息 x ∥ x ′ x \| x'x∥x′ 的有效标签 H s ( k ∥ x ∥ x ′ ) H^s(k\| x \| x')Hs(k∥x∥x′) 。因为H s ( k ∥ x ) H^s(k\| x)Hs(k∥x)的输出标签t tt和x ′ x'x′作为哈希函数的输入直接得到输出。
H s ( x ∥ k ) H^s(x\| k)Hs(x∥k): 在一个弱哈希函数上的碰撞会导致MAC上碰撞。回顾NMAC中需要开头的密钥来支持弱抗碰撞的情况。
H s ( k ∥ x ∥ k ) H^s(k\| x\| k)Hs(k∥x∥k): 也存在一些已知的弱点，即使使用两个不同的密钥。
H s ( k ∥ H s ( k ∥ x ) ) H^s(k \| H^s(k \| x))Hs(k∥Hs(k∥x))：这是NMAC和HMAC的情况

HMAC结语

HMAC是基于NMAC的改进，是工业标准（RFC2104），HMAC比CBC-MAC更快；
验证计时攻击：

Keyczar密码学库（Python）：
def Verify(key, msg, sig_bytes):
\qquad return HMAC(key, msg) == sig_bytes
存在问题是上述比较是按字节匹配，通过观察函数返回时间可以判断相同字节的数量，从而按字节猜测标签内容。
在Xbox 360中，相邻字节上被验证拒绝的时间差有2.2毫秒.

不要自己实现密码学！

信息论上MAC

信息论上MAC安全定义

不可能达到“完美的、不可伪造的”MAC，因为算力无限制的敌手可以至少以1 / 2 ∣ t ∣ 1/2^{|t|}1/2∣t∣ 的概率输出一个有效的标签。为此，对敌手查询MAC预言机的次数需要加以限制，下面分析只允许敌手查询一次MAC预言机的情况。
一次消息认证实验M a c f o r g e A , Π 1 − t i m e \mathsf{Macforge}^{\mathsf{1-time}}_{\mathcal{A},\Pi }MacforgeA,Π1−time: 敌手查询一次MAC预言机后输出消息和标签，

k ← G e n k \gets \mathsf{Gen}k←Gen.
A \mathcal{A}A 输出一个消息 m ′ m'm′并且获得一个标签 t ′ ← M a c k ( m ′ ) t' \gets \mathsf{Mac}_k(m')t′←Mack(m′), 然后输出 ( m , t ) (m,t)(m,t).
M a c f o r g e A , Π 1 − t i m e = 1 ⟺ \mathsf{Macforge}^{\mathsf{1-time}}_{\mathcal{A},\Pi }=1 \iffMacforgeA,Π1−time=1⟺ V r f y k ( m , t ) = 1 \mathsf{Vrfy}_k(m,t)=1Vrfyk(m,t)=1 ∧ \land∧ m ≠ m ′ m \neq m'm=m′.

定义：一个MAC Π \PiΠ 是一次ε \varepsilonε-安全的（one-time ε \varepsilonε-secure），如果 ∀ \forall∀ ppt A \mathcal{A}A: Pr ⁡ [ M a c f o r g e A , Π 1 − t i m e = 1 ] ≤ ε . \Pr [\mathsf{Macforge}^{\mathsf{1-time}}_{\mathcal{A},\Pi}=1] \le \varepsilon.Pr[MacforgeA,Π1−time=1]≤ε.
这里ε \varepsilonε应该为1 / 2 ∣ t ∣ 1/2^{|t|}1/2∣t∣，才能达到之前的信息论安全。信息论安全的MAC在允许敌手查询MAC预言机若干次之后，成功伪造MAC的概率应该不大于1 / 2 ∣ t ∣ 1/2^{|t|}1/2∣t∣。

理解信息论MAC安全

假设敌手算法是确定性的，其最合理的步骤如下：

（1）选择的m ′ m'm′是固定的，查询得到t ′ t't′；
（2）根据m ′ m'm′和t ′ t't′确定k kk的所有可能集合K ( t ′ ) \mathcal{K}(t')K(t′)，从中选择一个k ∗ k^*k∗；
（3）选择输出m mm是固定的，根据k ∗ k^*k∗计算t tt并输出。

问题：K ( t ′ ) \mathcal{K}(t')K(t′)太大或太小会如何？
设想如果根据第一次消息和标签能够唯一确定密钥k kk，那么敌手一定可以成功伪造；反之，如果不能唯一确定密钥，并且密钥可能的范围K ( t ′ ) \mathcal{K}(t')K(t′)充分大，那么敌手就难以成功伪造。从另一个角度，需要第一次查询获得的一个对消息和标签与敌手伪造另一个新消息的标签这两个事件之间是充分独立的。密钥空间太大也不安全，因为令( m , t ) (m, t)(m,t)是有效标签密钥集合也更大，其概率也增大。

信息论上MAC的构造

一个函数 h hh: K × M → T \mathcal{K} \times \mathcal{M} \to \mathcal{T}K×M→T 是一个强全域函数（Strongly Universal Function (SUF)），如果对于所有不同的 m , m ′ ∈ M m, m' \in \mathcal{M}m,m′∈M 以及所有 t , t ′ ∈ T t, t' \in \mathcal{T}t,t′∈T, 以下成立: Pr ⁡ [ h k ( m ) = t ∧ h k ( m ′ ) = t ′ ] = 1 / ∣ T ∣ 2 \Pr [h_k(m) = t \land h_k(m') = t'] = 1 / |\mathcal{T}|^2Pr[hk(m)=t∧hk(m′)=t′]=1/∣T∣2，其中概率来自均匀选择的 k ∈ K k \in \mathcal{K}k∈K.
为了实现一次1 / 2 ∣ t ∣ 1/2^{|t|}1/2∣t∣-安全的MAC，需要一个新的数学对象，不同输入会独立产生不同的输出，输入间任何差异都会导致输出之间是完全独立的。将函数的这种性质称为：“成对独立的，pairwise-independent” 或者 “成对不可预测，pairwise-unpredictable”。
SUF是具有上面性质的函数，下一页证明
信息论安全MAC构造：

令 h hh: K × M → T \mathcal{K} \times \mathcal{M} \to \mathcal{T}K×M→T 为一个SUF.
G e n \mathsf{Gen}Gen: k ← { 0 , 1 } n k \gets \{0,1\}^nk←{0,1}n u.a.r.
M a c k ( m ) \mathsf{Mac}_k(m)Mack(m): t : = h k ( m ) t := h_k(m)t:=hk(m).
V r f y k ( m , t ) \mathsf{Vrfy}_k(m,t)Vrfyk(m,t): 1 ⟺ t = ? h k ( m ) 1 \iff t \overset{?}{=} h_k(m)1⟺t=?hk(m). (如果 m ∉ M m \notin \mathcal{M}m∈/M，那么输出 0.)

构造一个SUF

定理：对于任意质数 P PP，函数 h hh 是一个SUF: h a , b ( m ) = d e f [ a ⋅ m + b m o d p ] h_{a,b}(m) \overset{\mathsf{def}}{=} [ a \cdot m + b \mod p]ha,b(m)=def[a⋅m+bmodp]
证明：h a , b ( m ) = t h_{a,b}(m) = tha,b(m)=t 且 h a , b ( m ′ ) = t ′ h_{a,b}(m') = t'ha,b(m′)=t′，只有当 a ⋅ m + b = t m o d p a \cdot m + b = t \mod pa⋅m+b=tmodp 且 a ⋅ m ′ + b = t ′ m o d p a \cdot m' + b = t' \mod pa⋅m′+b=t′modp. 我们有 a = [ ( t − t ′ ) ⋅ ( m − m ′ ) − 1 m o d p ] a = [(t-t') \cdot (m - m')^{-1} \mod p]a=[(t−t′)⋅(m−m′)−1modp] 且 b = [ t − a ⋅ m m o d p ] b = [t - a \cdot m \mod p]b=[t−a⋅mmodp]，这意味着存在一个唯一的密钥 ( a , b ) (a, b)(a,b)。由于存在 ∣ T ∣ 2 |\mathcal{T}|^2∣T∣2 个密钥，Pr ⁡ [ h k ( m ) = t ∧ h k ( m ′ ) = t ′ ] = 1 ∣ T ∣ 2 \Pr [h_k(m) = t \land h_k(m') = t'] = \frac{1}{|\mathcal{T}|^2}Pr[hk(m)=t∧hk(m′)=t′]=∣T∣21。

来自SUF的MAC的安全性

定理：如果 h hh 是一个 SUF，构造是一个 1 / ∣ T ∣ − 1/|\mathcal{T}|-1/∣T∣−安全MAC.
证明：假设敌手算法是确定性的，不失一般性可以固定m ′ m'm′并遍历所有可能的t ′ t't′，敌手以( m ′ , t ′ ) (m', t')(m′,t′)作为输入并输出( m , t ) (m, t)(m,t)。根据SUF的定义，可以得到敌手成功的概率为1 / ∣ T ∣ 1/|\mathcal{T}|1/∣T∣。

信息论MAC的局限性

任意 ℓ \ellℓ次 2 − n 2^{-n}2−n-安全 MAC 需要密钥长度至少为 ( ℓ + 1 ) ⋅ n (\ell +1) \cdot n(ℓ+1)⋅n.
定理：令 Π \PiΠ 为一次 2 − n 2^{-n}2−n-安全 MAC，其中所有密钥长度相同。那么，密钥必须具有2 n 2n2n长度。
证明：直觉上，每对消息和标签成立需要2 n 2^n2n个密钥，才能保证 2 − n 2^{-n}2−n-安全。一共2对，需要2 2 n 2^{2n}22n。
令 K ( t ′ ) = d e f { k ∣ V r f y k ( m ′ , t ′ ) = 1 } \mathcal{K}(t') \overset{\mathsf{def}}{=} \{ k | \mathsf{Vrfy}_k(m', t') = 1\}K(t′)=def{k∣Vrfyk(m′,t′)=1}，即所有由所查询消息得到标签的密钥集合。对于任意 t ′ t't′， ∣ K ( t ′ ) ∣ ≤ 2 − n ⋅ ∣ K ∣ |\mathcal{K}(t')| \leq 2^{-n} \cdot |\mathcal{K}|∣K(t′)∣≤2−n⋅∣K∣。否则，敌手A \mathcal{A}A从全体密钥集合中随机挑选一个密钥得到 ( m , t ) (m, t)(m,t) 是一个有效标签的概率至少为 ∣ K ( t ′ ) ∣ / ∣ K ∣ > 2 − n |\mathcal{K}(t')|/|\mathcal{K}|> 2^{-n}∣K(t′)∣/∣K∣>2−n，这与安全要求矛盾。 A \mathcal{A}A有无限算力可以根据从第一次查询中得到对应的密钥集合K ( t ′ ) \mathcal{K}(t')K(t′)，从中选择一个密钥k ∗ k^*k∗，并输出一个新消息m mm的有效标签的概率是至少 1 ∣ K ( t ′ ) ∣ \frac{1}{|\mathcal{K}(t')|}∣K(t′)∣1。固定m ′ m'm′遍历所有标签t ′ t't′计算敌手成功概率为： ∑ t ′ Pr ⁡ [ M a c k ( m ′ ) = t ′ ] ⋅ 1 ∣ K ( t ′ ) ∣ ≥ ∑ t ′ Pr ⁡ [ M a c k ( m ′ ) = t ′ ] ⋅ 2 n ∣ K ∣ = 2 n ∣ K ∣ \sum_{t'} \Pr [\mathsf{Mac}_k(m') = t'] \cdot \frac{1}{|\mathcal{K}(t')|} \geq \sum_{t'} \Pr [\mathsf{Mac}_k(m') = t'] \cdot \frac{2^n}{|\mathcal{K}|} = \frac{2^n}{|\mathcal{K}|}∑t′Pr[Mack(m′)=t′]⋅∣K(t′)∣1≥∑t′Pr[Mack(m′)=t′]⋅∣K∣2n=∣K∣2n 。由于概率至多 2 − n 2^{-n}2−n, ∣ K ∣ ≥ 2 2 n |\mathcal{K}| \geq 2^{2n}∣K∣≥22n。由于所有密钥具有相同长度，每个密钥的长度至少是 2 n 2n2n。

总结

认证意味着存在不可伪造
用PRF来实现安全MAC
用带密钥的CRHF来实现安全MAC
信息论MAC安全需要非常、非常长的密钥

【现代密码学】笔记4--消息认证码与抗碰撞哈希函数《introduction to modern cryphtography》

写在最前面

4 消息认证码与抗碰撞哈希函数