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

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

针对LEX算法的密码分析，学术界已发展出多种攻击方法。这些方法从不同角度切入，揭示了算法的潜在弱点。以下是对这些方法的全面盘点。

滑动攻击 (Slide Attack)

滑动攻击最早由Wu和Preneel发现。其核心在于，LEX算法中每组AES加密都使用相同的加密密钥。若一个密钥被用于约2^60.8个不同的随机初始向量(IV)，且每个IV生成20,000字节密钥流，则可通过滑动攻击轻松恢复密钥。

为应对此威胁，后续研究提出了改进方案，例如利用AES的密钥扩展算法来改变密钥使用方式，使改进后的算法能有效抵抗滑动攻击。

相关密钥攻击 (Related-Key Attack)

相关密钥攻击假设攻击者知道或能选择两个具有某种数学关系的密钥。此类攻击对LEX造成了严重威胁。

• Mondal和Mukhopadhyay的攻击：利用两个相关密钥，基于AES密钥调度中一个5轮差分路径进行分析。该攻击使用2^54.3个密钥流，以2^102次运算即可恢复完整的轮密钥。不过，该论文曾因技术错误被撤回。
• 王秋艳和金晨辉的攻击：结合了猜测决定方法与差分分析。在已知一对相关密钥各自产生的239.5字节密钥流条件下，通过穷举2字节密钥值和中间状态的8字节差分来恢复所有候选密钥。此攻击的成功率为1，计算复杂度为2^100.3轮AES加密。

差分故障攻击 (Differential Fault Attack)

差分故障攻击通过诱导加密设备产生错误，并分析正确与错误输出的差异来获取密钥信息。

• 张中亚和关杰的攻击：基于面向比特的随机故障模型。分析表明，约需96对（正误输出密钥流）和2^32次计算，或120对和2^16次计算，即可完全恢复128比特的初始密钥。结论是LEX对此类攻击不安全。
• 李佳雨等人的分析：进一步指出，仅需40次诱导故障和2^16次计算，就能恢复出一轮AES的轮密钥，进而破解整个LEX算法。

为增强抗攻击能力，有研究提出将每组轮密钥异或一个128比特随机序列的改进方案。

代数攻击 (Algebraic Attack)

代数攻击试图将密码算法表示为复杂的多元方程组，并通过求解方程组来还原密钥。

• Z'aba等人的代数分析：利用LEX每轮泄漏的字节，构建了一个包含21个方程、17个变量的方程组。该攻击仅需36字节的密钥流。其安全性依赖于该小规模方程组难以被快速求解。
• 对LEX小型版本的代数分析：针对一个16比特状态和16比特密钥的LEX小型版本，攻击者将其表示为374个二次布尔方程组成的系统（含208个未知数）。通过Gröbner基方法求解，可在不到2分钟内恢复密钥。

密钥恢复攻击 (Key Recovery Attack)

这是由Dunkelman和Keller提出的针对“改进版LEX”的攻击。

该攻击需要约2^36.3字节（约240字节）由同一密钥（可能在不同IV下）产生的密钥流，恢复密钥的时间复杂度约为2^112次AES加密。此攻击是导致LEX最终未能入选eSTREAM项目最终组合的关键原因之一。

重同步攻击 (Resynchronization Attack)

重同步攻击利用了LEX在重新同步（即使用新IV初始化）过程中的弱点。

LEX的重同步机制容易受到滑动攻击。若一个密钥配合约2^60.8个随机IV使用，且每个IV生成20,000字节密钥流，则可通过滑动攻击轻松恢复密钥。

截断滑动攻击 (Truncated Slide Attack)

尤加勇和李超曾针对LEX算法提出过截断滑动攻击。这是滑动攻击的一种变体，旨在进一步利用算法的结构弱点。

总结

下表汇总了上述各类攻击方法的核心信息：

总结

总而言之，LEX算法尽管设计精巧、速度卓越，但其基于AES“泄漏提取”的构造方式引入了多种可利用的结构性弱点。从早期的滑动攻击、重同步攻击，到更强大的相关密钥攻击、差分故障攻击和代数攻击，一系列密码分析手段揭示了其安全边界。特别是Dunkelman和Keller的密钥恢复攻击，直接导致了它未能进入eSTREAM项目的最终候选名单。

这些攻击也催生了如TweLEX等一系列改进方案，旨在修补原有漏洞并探索“泄漏提取”这一设计理念的更多可能性。