企业官网建设流程全解析

Cheetah算法的各种密码分析方法全面盘点

Cheetah是 NIST SHA-3 竞赛第一轮候选算法，其密码分析研究主要围绕其Merkle-Damgård结构和基于 AES 的压缩函数展开。以下是对其已知密码分析方法的全面盘点。

🕵️长度扩展攻击（Length-Extension Attack）

这是 Cheetah 最著名、也是导致其声誉受损的分析结果。

攻击原理：Cheetah 本通过在最后一块压缩函数前对链接值进行置换（permutation）来抵御长度扩展攻击。然而，其初始链接值（IV）是全零向量，而全零向量恰好是该置换的一个不动点，即πIV=IV。这意味着对于长度小于 959 比特的短消息，攻击者可以像对待标准 Merkle-Damgård 结构一样，在已知哈希值后附加数据并计算出有效的新哈希值，实现长度扩展攻击。

作者回应：设计者 Khovratovich 等人对此回应称，这并非压缩函数的安全性问题，只需更换 IV或在最后一轮置换中加入非零常数即可消除不动点，从而彻底避免该攻击，且不影响速度与压缩函数安全性。尽管如此，这一观察仍是 Cheetah 最广为人知的密码分析结果，并被 ECRYPT Hash Function Website 等权威资料收录。

🎯反弹攻击（Rebound Attack）与半自由起始碰撞

这是针对 Cheetah压缩函数最深入的密码分析工作，由 Wu 等人在 ICISC 2009 上提出。

攻击对象：12 轮 Cheetah-256（Cheetah-256 共 16 轮，该攻击覆盖了其中 12 轮）。

方法概要：

• 首先分析了轮消息块注入的自由度与伪碰撞攻击轮数之间的关系，指出对 8 轮 Cheetah-256 可直接套用原始反弹技术构造伪碰撞。
• 进而构造了一条反弹差分路径，用于实施半自由起始碰撞攻击（semi-free start collision），即攻击者可以自由选择初始链接值，但两个消息必须从同一链接值出发产生碰撞。
• 关键优化在于观察到中立字节（neutral bytes）对状态值的影响，从而将攻击复杂度降低至224次压缩函数调用。

意义：该攻击是针对 Cheetah 压缩函数最有效的分析结果，但仅覆盖 12/16 轮，并未对完整 16 轮的 Cheetah-256 构成实际威胁。

🐑牧群攻击（Herding Attack）

牧群攻击是针对 Merkle-Damgård 结构的一种通用攻击，允许攻击者在预先不知道消息的情况下承诺一个哈希值，随后找到能产生该哈希值的消息前缀。

Cheetah的应对：Cheetah 通过引入Salt（盐值）来抵御牧群攻击。盐值是一个随机参数，在哈希前固定并插入每个消息块中，使得攻击者无法预计算牧群结构。这是 Cheetah 在高层结构设计上的一项主动防御措施。

🧬伪原像攻击（Pseudo-Preimage Attack）

伪原像攻击的目标是在给定链接值的情况下，找到能产生特定输出的消息。

分析结论：Cheetah 的设计文档指出，其压缩函数本质上是一个基于 AES 的分组密码，在 Davies-Meyer 模式下工作。寻找压缩函数的伪原像等价于对该分组密码进行密钥恢复（key-recovery）。由于 AES 的密钥恢复在计算上被认为是困难的，设计者据此认为 Cheetah 对伪原像攻击具有与 AES 相当的安全强度。

🔗多碰撞攻击（Multicollision Attack）

多碰撞攻击旨在为同一哈希函数找到多个产生相同摘要的消息。

Cheetah的防御：设计文档明确指出，块计数器（block counter）是抵御快速多碰撞和快速第二原像攻击的核心机制。该计数器将消息块的位置信息纳入压缩过程，使得攻击者无法轻易构造可互换的“可扩展消息”（expandable messages），从而阻碍多碰撞和第二原像攻击的构造。

🧪其他分析方向与结论

💎总结

Cheetah的密码分析呈现出“高层结构存在缺陷，底层压缩函数较强”的鲜明特点。

• 最严重的分析结果是长度扩展攻击，根源在于 IV 为置换的不动点，属于高层结构的实现疏忽，但修复代价极低。
• 最深入的技术分析是 Wu 等人的反弹攻击，将半自由起始碰撞攻击推进到12轮（总 16 轮），复杂度仅为224，但未触及完整轮数。
• 设计层面的防御较为完善：Salt 抵御牧群攻击，块计数器抵御多碰撞与第二原像攻击，Davies-Meyer 模式提供伪原像抵抗性。

总体而言，Cheetah 虽因长度扩展问题在第一轮后被淘汰，但其基于 AES 的压缩函数在差分、反弹、伪原像等核心分析方向上表现出了较强的抵抗能力，公开文献中未出现对完整 16 轮 Cheetah-256 的有效攻击。