天津网站制作哪家好薇,做课件最好的素材网站,WordPress实现文章分类筛选,有口碑的唐山网站建设【现代密码学】笔记4--消息认证码与抗碰撞哈希函数《introduction to modern cryphtography》 写在最前面4 消息认证码与抗碰撞哈希函数MAC概念回顾#xff08;是的#xff0c;我忘记这些缩写是什么了。。#xff09;MAC的定义适应性CMA#xff08;Chosen Message Attack是的我忘记这些缩写是什么了。。MAC的定义适应性CMAChosen Message AttackPPT攻击者不可忽略的概率negl(n)总结 案例 构建安全MACCBC-MACCBC概念回顾构造固定长度的CBC-MAC CRHF哈希函数Hash Function、 定义抗碰撞Collision ResistanceHMAC信息论上MAC 写在最前面
主要在 哈工大密码学课程 张宇老师课件 的基础上学习记录笔记。
内容补充骆婷老师的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 k k, 标签(tag) t t t, 一个比特 b b b 为有效的 (valid}) 如果 b 1 b1 b1; 或 无效的 (invalid}) 如果 b 0 b0 b0.密钥生成 Key-generation 算法 k ← G e n ( 1 n ) , ∣ k ∣ ≥ n k \gets \mathsf{Gen}(1^n), |k| \ge n k←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)) 1 Vrfyk(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 \iff MacforgeA,Π(n)1⟺ V r f y k ( m , t ) 1 \mathsf{Vrfy}_k(m,t)1 Vrfyk(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的定义
MACMAC代表“消息认证码”Message Authentication Code它是一种用于验证消息完整性和来源真实性的加密工具。存在性不可伪造一个MAC系统被称为“存在性不可伪造”的意味着没有攻击者可以成功地伪造一个有效的MAC即使是一个新的、以前未见过的MAC除非通过微不足道的概率。
适应性CMAChosen 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 m m并得到对应的标签 t t t然后输出另一个与所查询消息 m m m具有相同CRC32值的新消息 m ′ m m′以及查到的标签 t t t。二是敌手可以查询一个消息 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 m m以及标签 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 cookieWeb服务器在发给浏览器的cookie中包含自己生成的MAC标签来阻止攻击者伪造其他用户的cookieTCP SYN cookie在TCP三次握手中服务器在其发给客户端的初始序列号中包含一个服务器生成的MAC标签来避免保留握手状态从而防御SYN Flooding DDoS攻击临时一次口令用户发送给服务器的临时登录口令为一个MAC标签 p M a c k ( T ) p\mathsf{Mac}_k(T) pMack(T)其中 k k k为原始口令 T T T为当前时间按半分钟取整敌手窃听了之前的临时口令也无法伪造未来的临时口令
构建安全MAC 构造安全MAC 基于PRF构造安全MAC F F F 是 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\}^n k←{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 F F 是一个PRF那么上述构造是安全的固定长度 MAC。引理如果 F F F 是一个 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 D D规约到伪造标签的敌手算法 A \mathcal{A} A。 D D D作为 A \mathcal{A} A的挑战者用 D D D要区分的预言机作为 A \mathcal{A} A的标签生成预言机当 A \mathcal{A} A伪造标签成功时 D D D输出1。 证明基于PRF的安全MAC续 如果是真随机 f f f 被使用 t f ( m ) tf(m) tf(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_k Fk 被使用那么就是在执行实验 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-MACCipher Block Chaining Message Authentication Code是一种基于块加密算法的消息认证码MAC构造方法。它使用的是密码块链接Cipher Block ChainingCBC模式这是一种常用的块加密操作模式。
构造固定长度的CBC-MAC 构造固定长度的CBC-MAC 为了构造用于变长消息的MAC先学习固定长度的CBC-MAC其与CBC结构类似做了两处改变改动1将初始向量IV改为0如果不这样改动则敌手查询 m 1 m_1 m1 并获得 ( 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_i mi 并得到 t i t_i ti然后输出 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_i ti′ti一个有效的标签。 构造固定长度的CBC-MAC续 定理如果 F F F是一个PRF那么上面的构造就是一个安全的固定长度MAC。这个构造不能用于变长消息因为对于一个块的消息 m m m和标签 t t t敌手可以在其后添加一个块 m ⊕ t m\oplus t m⊕t并且输出标签 t t t。 安全变长MAC 有三种方法可以将CBC-MAC改造为用于变长消息的MAC都可以防御上面在结尾添加新块的攻击。输入长度密钥分离 k ℓ : F k ( ℓ ) k_{\ell} : F_k(\ell) kℓ:Fk(ℓ), 用 k ℓ k_{\ell} kℓ 作为 CBC-MAC 的密钥。不同长度下采用不同密钥追加新块后长度变化之前的标签无法利用。在开头添加长度在CBC-MAC的明文 m m m前添加一个长度块 ∣ m ∣ |m| ∣m∣。不同长度下消息有不同的初始块追加新块后长度变化之前的标签无法利用。加密末块输出ECBC-MAC采用两个密钥 k 1 , k 2 k_1, k_2 k1,k2。用 k 1 k_1 k1和CBC-MAC计算出 t t t然后输出 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). m0m1⇒pad(m0)pad(m1).ISO的填充标准用“100…00”填充并按需填充哑块。如果不填充哑块则会导致什么CMACCipher-based MAC不填充哑块不加密最后一块的输出密钥包括三个 k , k 1 , k 2 k, k_1, k_2 k,k1,k2 k k k用于CBC-MAC k 1 k_1 k1 和 k 2 k_2 k2 与最后一块消息异或来阻止利用最后一块输出用 k 1 k_1 k1 和 k 2 k_2 k2 来区分是否添加了哑块。
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 s s 不保密. 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^s Hs 只在 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 xx′ 并且 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 s s 输出 x , x ′ x, x x,x′. 注敌手有 s s s意味着可以访问哈希函数 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⟺xx′∧Hs(x)Hs(x′). 哈希函数 Π \Pi Π ( G e n \mathsf{Gen} Gen, H s H^s Hs) 是抗碰撞的如果 ∀ \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 s s 和 x x x, 难以发现 x ′ ≠ x x \ne x x′x 使得 H s ( x ′ ) H s ( x ) H^s(x) H^s(x) Hs(x′)Hs(x).抗原像 Pre-image resistance: 给定 s s s 和 y H s ( x ) y H^s(x) yHs(x), 难以发现 x ′ x x′ 使得 H s ( x ′ ) y H^s(x)y Hs(x′)y.攻击越难反过来可以防范这种攻击的安全性就越弱。 关于CRHF的问题 如果认为不是那么请给出一个碰撞如果认为是则用反证法证明找到了 H ′ H H′的碰撞意味着 H H H的碰撞。 哈希函数的应用 文件指纹和去重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-Damgård Transform 从定长哈希函数 ( G e n , h ) (\mathsf{Gen}, h) (Gen,h) ( 2 ℓ 2\ell 2ℓ 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 H H: 密钥 s s s 与串 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} \rceil B:⌈ℓL⌉ (块数)。 用0填充。 ℓ \ell ℓ-位的块 x 1 , … , x B x_1,\dotsc,x_B x1,…,xB。最后一块是长度 x B 1 : L x_{B1} : L xB1:L L L L 以 ℓ \ell ℓ 位编码这是必要的因为只用0填充会导致不同消息的输入是一样的。 z 0 : I V 0 ℓ z_0 : IV 0^\ell z0:IV0ℓ。 对于 i 1 , … , B 1 i1,\dotsc,B1 i1,…,B1 计算 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 h h是定长CRHF那么 H H H也是CRHF。证明思路是 H H H上的碰撞意味着 h h h上的碰撞而 h h h是不会被找到碰撞的。两个消息 x ≠ x ′ x \ne x xx′ 长度分别为 L L L 和 L ′ L L′ 块数分别为 B B B 和 B ′ B B′使得 H s ( x ) H s ( x ′ ) H^s(x) H^s(x) Hs(x)Hs(x′)。 有两种情况 L ≠ L ′ L \ne L LL′: z B ∥ L ≠ z B ′ ∥ L ′ z_B\| L \ne z_{B}\| L zB∥LzB′∥L′长度不同意味着最后一个哈希函数 h h h的输入不同但输出相同发现碰撞。 L L ′ L L LL′: 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 xx′ 使得 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} hiFmi(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 m hiFhi−1(mi)⊕hi−1⊕m。定理如果 F F F是一个理想的加密方案那么Davies-Meyer构造得到一个CRHF。注理想的加密方案参考后面要学习的随机预言机模型。目前没有找到 F F F是强伪随机排列下该方法是CRHF的证明。对于这个定理不做严格证明而是回答两个问题 如果 h i F m i ( h i − 1 ) h_{i} F_{m_{i}}(h_{i-1}) hiFmi(hi−1) 不与 h i − 1 h_{i-1} hi−1 异或会如何敌手尝试以相同的 h i h_i hi和不同的 m i m_i mi对 F F F求逆。如果 F F F 不是理想的而是 ∃ x , F k ( x ) x \exists x, F_k(x)x ∃x,Fk(x)x会如何敌手输入不同 m i m_i mi但都得到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 使用CRHFMD变换来构造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\}^n s←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_2 G(k)defhs(IV∥(k⊕opad))∥hs(IV∥(k⊕ipad))k1∥k2 。其中 h h h是CRHF。如果 G G G是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 t t和 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的改进是工业标准RFC2104HMAC比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 \iff MacforgeA,Π1−time1⟺ V r f y k ( m , t ) 1 \mathsf{Vrfy}_k(m,t)1 Vrfyk(m,t)1 ∧ \land ∧ m ≠ m ′ m \neq m mm′. 定义一个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−time1]≤ε.这里 ε \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 k k的所有可能集合 K ( t ′ ) \mathcal{K}(t) K(t′)从中选择一个 k ∗ k^* k∗3选择输出 m m m是固定的根据 k ∗ k^* k∗计算 t t t并输出。 问题 K ( t ′ ) \mathcal{K}(t) K(t′)太大或太小会如何设想如果根据第一次消息和标签能够唯一确定密钥 k k k那么敌手一定可以成功伪造反之如果不能唯一确定密钥并且密钥可能的范围 K ( t ′ ) \mathcal{K}(t) K(t′)充分大那么敌手就难以成功伪造。从另一个角度需要第一次查询获得的一个对消息和标签与敌手伪造另一个新消息的标签这两个事件之间是充分独立的。密钥空间太大也不安全因为令 ( m , t ) (m, t) (m,t)是有效标签密钥集合也更大其概率也增大。 信息论上MAC的构造 一个函数 h h h: 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}|^2 Pr[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 h h: 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\}^n k←{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 P P函数 h h h 是一个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⋅mbmodp]证明 h a , b ( m ) t h_{a,b}(m) t ha,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 p a⋅mbtmodp 且 a ⋅ m ′ b t ′ m o d p a \cdot m b t \mod p a⋅m′bt′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 h h 是一个 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 2n 2n长度。证明直觉上每对消息和标签成立需要 2 n 2^n 2n个密钥才能保证 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 m m的有效标签的概率是至少 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 2n 2n。 总结 认证意味着存在不可伪造用PRF来实现安全MAC用带密钥的CRHF来实现安全MAC信息论MAC安全需要非常、非常长的密钥
