消息认证码的安全性分析概述
消息认证码概述
消息认证码由密钥生成、标签生成和验证三个算法组成：
正确性要求合法生成的标签能够通过验证。安全性则要求不知道密钥的攻击者难以为新消息产生合法标签。
MAC 提供消息完整性和共享密钥范围内的来源认证，不提供消息机密性，也不提供数字签名意义上的不可否认性。双方都知道密钥，因此双方都能生成标签。
普通无密钥杂凑 \(H(M)\) 不能替代 MAC：攻击者修改消息后可以自行重新计算摘要。
伪造攻击
在选择消息攻击模型下，攻击者可查询若干消息的标签，最后输出 \((M^*,T^*)\)。若 \(M^*\) 从未查询过，且验证通过，就构成存在性伪造。
存在性表示攻击者只需找到某条新消息，不必提前固定其内容。这已经足以破坏通常要求的不可伪造性。
对理想的 \(t\) 比特标签，单次盲猜成功概率为 \(2^{-t}\)。允许 \(v\) 次在线验证时，成功概率至多按 \(v/2^t\) 的联合界估计，直到该界失去意义。因此截短标签的安全性必须结合在线尝试次数评估。
重放已获得的合法消息—标签对通常不属于这个“新消息伪造”实验，但现实协议仍需防重放。做法是把序号、会话标识等一并认证，并维护相应状态。
R 型区分攻击与存在性伪造
R 型区分攻击比较真实 MAC 与相同输入输出空间上的随机函数。它利用的是标签的非随机关系，而不一定恢复密钥。
密钥前缀杂凑的长度扩展
考虑不安全的直接构造
其中 \(H\) 是完整摘要暴露链接状态的 MD 型杂凑。
给定标签 \(T\)，若知道或猜测 \(|K|\)，便能构造
攻击者从状态 \(T\) 出发，设置正确的已处理长度，继续压缩 \(X\) 及最终填充，就能计算 \(M'\) 的合法标签。全过程不需要知道 \(K\) 或恢复 \(M\)。
消息格式必须允许插入这些字节；若格式不允许，具体攻击可能被限制，但这种限制不是该 MAC 构造的一般安全证明。
碰撞扩展区分
教材还利用生日碰撞说明区分与伪造的关系。选择两条等长消息，使其标签满足
在正确处理填充与长度的条件下，把相同后缀接到相应链接状态之后，碰撞继续保持。随机函数在两个不同新输入上的输出却只有约 \(2^{-t}\) 的概率相等。
因此，可查询其中一条扩展消息的标签，把它移用于未查询的另一条扩展消息，形成存在性伪造。
不要把这一结论原样套到 HMAC。HMAC 的外层摘要不直接暴露内层链接状态，不能从公开标签直接完成上述长度扩展。底层杂凑存在普通碰撞，也不自动意味着能够伪造 HMAC。
选择性伪造
选择性伪造要求攻击者在与标签接口交互前，已经固定要伪造的目标消息。它比“最后找到任意一条新消息”有更强的目标限制。
以未进行长度处理、输出完整分组的 CBC-MAC 为例。固定零 IV，递推为
这种基本构造在固定分组数的消息域上可以安全，但不能不加处理地混用不同消息长度。
例：预先固定两块目标消息 \(A\Vert B\)。
1) 查询一块消息 \(A\)，得到 \(t_A=E_K(A)\)。
2) 选择 \(X\ne A\)，查询 \(X\)，得到 \(t_X=E_K(X)\)。
3) 查询两块消息 \(X\Vert(B\oplus t_A\oplus t_X)\)，得到标签 \(t\)。
则
目标消息从未查询，因为第三步的首块为 \(X\ne A\)。攻击利用了同一密钥接口同时接受一块、两块消息，以及标签暴露完整链值。
若只输出截断标签，上述步骤不能直接得到完整的 \(t_A,t_X\)，不能照搬相同复杂度。标准 CMAC 通过末块子密钥和完整/非完整块的区分解决这类可变长问题，而不是简单保留原始 CBC-MAC。
通用性伪造
通用性伪造意味着攻击者获得了对任意目标消息生成有效标签的能力，未必恢复原始密钥。
例如，对某些迭代 MAC，若能恢复处理秘密前缀后的完整内部状态，同时知道已处理长度与后续规则，就得到一种等价认证能力：可以从该状态继续处理任意合法消息。
这里的等价状态不能笼统写成 \(H(K)\)。实际需要的可能是“密钥块之后、尚未完成最终填充的链接状态”，还需保留字节计数等辅助信息；完成填充后的摘要未必是同一个对象。
存在性、选择性与通用性描述的是不同伪造能力。评价攻击时应直接说明目标消息何时选定、哪些标签可以查询，以及是否能对任意消息工作。
密钥恢复攻击
MAC 也可能遭受主密钥恢复或等价密钥恢复。最直接的穷举攻击枚举 \(\kappa\) 比特密钥，并用消息—标签对验证。
在理想独立近似下，每组 \(t\) 比特标签筛去约 \(1-2^{-t}\) 比例的错误密钥，\(r\) 组数据后剩余错误候选期望约为
这说明短标签可能需要更多验证数据，但不表示穷举计算量自动减少为 \(2^t\)。
条件立方与减轮 Keccak-MAC
教材使用减轮 Keccak-MAC 展示条件立方攻击：通过设置输入比特关系，控制非线性层中不同立方变量是否相乘，从而限制输出的代数次数。
若正确的部分密钥猜测使输出关于 \(d\) 个立方变量的次数低于 \(d\)，则其立方和必为零；错误猜测可能破坏这些条件，产生不同结果。
算法框架为：
1) 选择可控制的消息变量，确定需满足的比特条件。
2) 枚举条件中涉及的少量密钥比特。
3) 按该猜测设置输入，进行立方求和。
4) 用多个结构筛选候选，再用独立消息—标签对验证。
如果一个立方有 \(d\) 个变量，猜测 \(s\) 比特，则朴素成本约为 \(2^{d+s}\) 次对应计算。这个数只描述所恢复的那部分密钥，不能自动作为全密钥恢复的成本。
这些结果针对明确定义的减轮 Keccak-MAC，不能直接表述为标准 SHA-3、KMAC 或完整轮数构造已被破解。
实现与协议要求
标签比较应避免按首个不同字节提前返回造成时序泄露。消息编码应无歧义，并认证算法标识、上下文和必要的长度信息；不同用途使用独立密钥或规范的域分离。
MAC 验证通过只说明认证条件成立，不自动说明消息新鲜、授权合理或数据格式安全，这些仍由上层协议负责。
本章总结
MAC 的核心目标是阻止新消息伪造，而不是隐藏消息或密钥本身。长度扩展、可变长 CBC-MAC 拼接以及实现泄露，都可能绕开主密钥恢复。
安全分析需要区分：区分器与伪造、存在性与选择性目标、等价状态与原始密钥、减轮构造与标准完整算法。
参考：王美琴主编，《密码分析学》，第 14 章。立方和的推导见第 12 章。
完
评论