密码学中立方攻击的另类应用

什么是立方攻击？

   立方攻击(Cube Attack)是由密码学家Itai Dinur和Adi Shamir在2009年欧密会(EUROCRYPT)上首次提出的一种新型密码分析方法。这种攻击方法属于代数攻击与高阶差分攻击的交叉领域，主要针对基于非线性反馈移位寄存器的密码算法。立方攻击的核心思想源于一个关键观察：任何密码算法都可以被看作一个多元多项式，其中输入变量包含公开变量(明文或初始向量)和秘密变量(密钥)。当密码算法中存在某些输出位可以表示为秘密变量和公开变量的低次多项式时，通过精心选择并固定部分公开变量的值，攻击者能够推导出关于密钥比特的简单线性或非线性方程，最终恢复出完整密钥。立方攻击的实施过程通常包括两个阶段：预处理阶段和在线阶段。在预处理阶段，攻击者随机选择公开变量的子集作为候选立方，通过线性测试、二次测试和常数测试等方法验证其是否为合适的立方变量。在线阶段则利用找到的立方变量进行密钥恢复。

   立方攻击是一种新型的代数攻击方法，旨在寻找密码算法的低次方程以恢复密钥或进行区分攻击。它吸收了饱和攻击及高阶差分分析的思想，该攻击方法主要基于下述定理：

   立方攻击为选择IV攻击，攻击者把密码算法看作一个黑盒子，它是关于n个未知变量和m个公开变量的未知多项式，输出1个比特。对密码算法的立方攻击分为两个阶段：预处理阶段和密钥恢复阶段。在预处理阶段，攻击者可以改变公开变量及未知变量的值，并可以模拟算法的执行，目的是找到尽量多的关于未知变量的线性方程(超级多项式)，预处理过程只进行1次。在密钥恢复阶段，攻击者只改变公开变量的值，通过在预处理阶段找到的超级多项式来恢复某些密钥比特。对分组密码来讲，在选择明文攻击的条件下，明文为公开变量，密钥为未知变量;对序列密码来讲，在选择 IV 攻击的条件下，IV 为公开变量，密钥为未知变量。

   立方攻击的发展经历了几个重要阶段：

2009年：基础立方攻击概念提出，初期效果有限

2011年：动态立方攻击(Dynamic Cube Attack)出现，利用代数特性构建区分器

2017年：条件立方攻击(Conditional Cube Attack)被提出，引入比特条件控制机制

2020年：新型条件立方攻击放松了限制条件，获得更高自由度

   立方攻击的适用目标十分广泛，包括序列密码、分组密码和哈希函数等。在序列密码方面，它成功应用于分析Trivium、Grain等算法；在分组密码领域，则主要针对轻量级密码如SIMON、LED等。特别值得一提的是，当Todo等人引入多重集合可分性(Division Property)概念后，立方攻击的分析能力得到质的飞跃。通过将攻击过程转化为混合整数线性规划(Mixed Integer Linear Programming, MILP)问题，并利用数学软件求解，攻击效率大幅提升。

传播安全知识、拓宽行业人脉——看雪讲师团队等你加入！