Cheetah算法的各种密码分析方法全面盘点Cheetah是 NIST SHA-3 竞赛第一轮候选算法其密码分析研究主要围绕其Merkle-Damgård结构和基于 AES 的压缩函数展开。以下是对其已知密码分析方法的全面盘点。️长度扩展攻击Length-Extension Attack这是 Cheetah 最著名、也是导致其声誉受损的分析结果。攻击原理Cheetah 本通过在最后一块压缩函数前对链接值进行置换permutation来抵御长度扩展攻击。然而其初始链接值IV是全零向量而全零向量恰好是该置换的一个不动点即πIVIV。这意味着对于长度小于 959 比特的短消息攻击者可以像对待标准 Merkle-Damgård 结构一样在已知哈希值后附加数据并计算出有效的新哈希值实现长度扩展攻击。作者回应设计者 Khovratovich 等人对此回应称这并非压缩函数的安全性问题只需更换 IV或在最后一轮置换中加入非零常数即可消除不动点从而彻底避免该攻击且不影响速度与压缩函数安全性。尽管如此这一观察仍是 Cheetah 最广为人知的密码分析结果并被 ECRYPT Hash Function Website 等权威资料收录。反弹攻击Rebound Attack与半自由起始碰撞这是针对 Cheetah压缩函数最深入的密码分析工作由 Wu 等人在 ICISC 2009 上提出。攻击对象12 轮 Cheetah-256Cheetah-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从而阻碍多碰撞和第二原像攻击的构造。其他分析方向与结论分析方法状态与结论关键限制/备注差分分析设计者给出了活性 S-box 数量的下界Cheetah-256 消息扩展中至少81个内部轮中至少17个认为截断差分权重很高足以抵抗差分攻击。这是设计层面的安全性论证而非实际的攻击结果。线性分析公开文献中未见针对 Cheetah 的专门线性分析攻击报道。由于核心组件来自 AES其线性特性继承自 AES被认为具有足够的抵抗力。缺乏专门研究但 AES 的线性分析结果可作为间接参考。代数分析未见公开的代数攻击结果。Cheetah 的代数结构较复杂且轮数较多代数攻击的可行性未被证实。---相关密钥攻击Cheetah 作为哈希函数无传统意义上的“密钥”概念但在 HMAC-PRF 模式下相关密钥场景下的安全性未被专门分析。设计者声称其可作为 PRF 使用但未提供相关密钥攻击的详细分析-。总结Cheetah的密码分析呈现出“高层结构存在缺陷底层压缩函数较强”的鲜明特点。最严重的分析结果是长度扩展攻击根源在于 IV 为置换的不动点属于高层结构的实现疏忽但修复代价极低。最深入的技术分析是 Wu 等人的反弹攻击将半自由起始碰撞攻击推进到12轮总 16 轮复杂度仅为224但未触及完整轮数。设计层面的防御较为完善Salt 抵御牧群攻击块计数器抵御多碰撞与第二原像攻击Davies-Meyer 模式提供伪原像抵抗性。总体而言Cheetah 虽因长度扩展问题在第一轮后被淘汰但其基于 AES 的压缩函数在差分、反弹、伪原像等核心分析方向上表现出了较强的抵抗能力公开文献中未出现对完整 16 轮 Cheetah-256 的有效攻击。