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

Xoodyak作为NIST轻量级密码竞赛的决赛算法，其安全性受到了学界的广泛审查。目前，所有已发表的攻击都针对缩减轮数的版本，其完整的12轮核心置换Xoodoo尚未被任何攻击所突破。

以下是根据现有研究，对Xoodyak面临的各种密码分析方法的全面盘点：

1.差分分析与线性分析

这是最基础的密码分析方法，通过分析明文差异如何影响密文差异（差分），或寻找明文与密文之间的线性关系（线性分析）来破解密码。

• 核心防御：Xoodyak的设计者提供了Xoodoo置换在差分和线性传播上的下界证明。随着研究的深入，这些下界在4轮和5轮上还得到了持续改进和加强。
• 具体应用：在攻击方面，研究者利用S盒线性化技术，成功实现了对Xoodyak哈希模式2轮的实际碰撞攻击和3轮的实际半自由起始碰撞攻击。

2.差分-线性分析

该方法结合了差分分析和线性分析的优点。

• 攻击成果：这是对Xoodyak攻击效果最显著的方法之一。
  • 4轮攻击：多个研究团队独立提出了针对4轮Xoodyak的差分-线性区分器或攻击。
  • 5轮攻击：在相关密钥模型下，攻击可被扩展至5轮。通过结合划分技术和中立位技术，攻击者能够同时降低时间与数据复杂度。

3.碰撞攻击

主要针对Xoodyak的哈希模式，目标是找到两个不同的输入，使其产生相同的哈希值。

• 中间相遇攻击 (MitM)：这是一种经典的碰撞攻击方法。最新的研究通过提出“整体弱扩散结构搜索策略”，将针对3轮Xoodyak-Hash的MitM碰撞攻击的时间和内存复杂度均降低了一半。
• 基于差分的碰撞攻击：研究者利用Xoodoo轮函数中θ和χ操作的特性，手工设计了名为“循环路 (loop trails)”的特殊差分路径。基于此构建的SAT模型，成功实现了上述2轮和3轮的实际碰撞攻击。

4.代数与高阶差分分析

这类方法从更抽象的数学层面分析算法的结构。

• 立方攻击 (Cube Attacks) 及其变种：
  • 条件立方攻击：这是目前对Xoodyak轮数攻击最深的成果之一，可以在nonce复用场景下，分别用约2^42.58和2^76.00的时间复杂度，恢复6轮和7轮Xoodyak的128位密钥。
  • 普通立方攻击：也被用于分析Xoodoo初始化阶段，成功攻击了6轮版本。
• 零和区分器 (Zero-Sum Distinguishers) 与SymSum区分器：这些是高阶差分分析的工具，用于区分算法与随机排列。
  • 研究者成功对Xoodoo[12]（12轮）构建了零和区分器。
  • SymSum区分器被成功应用，可对5轮Xoodyak-Hash和7轮Xoodoo构建区分器。
  • 通过改进为“SymSum_Sim”方法，得到了优于已有结果的Xoodyak区分器。
• 函数式密码分析 (Functional Cryptanalysis)：作为差分、旋转等技术的广义化，研究者展示了针对3轮Xoodoo的函数区分器。
• 原像攻击 (Preimage Attacks)：基于代数策略，针对2轮和3轮Xoodyak-XOF的原像攻击复杂度被进一步降低。

5.侧信道分析与故障攻击

这类攻击不直接攻击算法本身，而是利用其物理实现时的信息泄漏。

• 能量分析攻击 (Power Side-Channel Analysis, SCA)：研究人员在FPGA上实现了Xoodyak，并对其认证加密模式的初始化阶段进行了深入的能量分析-。模板攻击 (Template Attack)的成功率可达99.2%。攻击者还为相关性功耗分析 (CPA)开发了新的攻击模型。
• 故障攻击 (Fault Attacks)：针对Xoodyak实现的故障攻击也是研究的一个方向。

6.针对模式的通用攻击

这类攻击不针对Xoodyak的内部置换，而是利用其工作模式（全状态密钥双工）的漏洞。

• 新的通用攻击：Gilbert等人发现了一种针对双工结构认证加密的新通用攻击。虽然其数据复杂度高达2^148，属于学术攻击范畴，但它促使设计者修正了原先的安全声明，并完善了其安全界限。

总结

下表总结了上述主要的攻击方法及其达到的轮数：

注：*“相关密钥模型”是比标准攻击模型假设更强的一种场景，攻击者假设能够知道或选择密钥之间的关系。

总体而言，Xoodyak展现了强大的安全裕度。所有已发表的攻击都未能突破其完整的12轮设计，这表明其设计是相当稳健的。