立方攻击研究进展

2020-10-28王明兴朱玉倩苗三立

网络安全与数据管理 2020年10期

王明兴，朱玉倩，苗三立

(1.中国电子信息产业集团有限公司第六研究所，北京102209；2.密码科学技术国家重点实验室，北京100878)

0 引言

DINUR I 和 SHAMIR A 在 2009 年的欧密会上提出了一种新型的攻击手段[1]，称为立方攻击(Cube Attack)。立方攻击是一种选择明文攻击，其攻击思想是：密码算法被看成是一个未知的复杂的多元多项式，输入变量(明文或者初始向量)称为公开变量，密钥变量称为秘密变量；输出变量可以表示为公开变量和秘密变量的某种多项式的形式。只要至少有一位输出变量可以表示为秘密变量和公开变量的低次多项式，通过赋值一些公开变量，即可访问密码算法获取输出结果，得到秘密变量的简单的方程式，恢复密钥比特。

TODO Y 等人[2]在 2015 年提出了多重集合的可分性(Division Property)的概念，它是分析分组密码积分特征的有力工具。在之后的一年，TODO Y 等人[3]又提出了基于比特的多重集合的可分性。向泽军等人[4]在2016 年的亚密会上提出了可分路径的概念，将可分路径的计算转化为求解混合整数线性规划 (Mixed Integer Linear Programming，MILP)问题，提高了积分攻击的准确性和运算效率。在 2017 年的美密会上，TODO Y 等人[5]提出了可分性的可分路径和立方攻击的超级多项式之间的联系，给出了求解超级多项式中的变量的算法。

王庆菊等人[6]进一步提升了MILP 模型的计算准确性，提出了超级多项式的最高次项的求解算法，降低了立方攻击的复杂度。王森鹏等人[7]采用了三子集可分性的概念，发展了求超级多项式的算法，降低了算法的时间复杂度。HAO Y L 等人[8]提出了基于完善的三子集的多重集合的可分性的定义，更进一步提升了MILP 模型计算超级多项式的准确性。

本文的主要目的是全面回顾立方攻击的技术演进历程，介绍最新的立方攻击技术，展望未来立方攻击的发展方向和应用价值。

1 立方攻击的原理和过程

1.1 立方攻击的定义

立方攻击利用了多元布尔多项式的高阶差分的性质，即布尔多项式都可以表示成一种带余除法的形式，其中余式是不能包含除式的全部变量的多项式。

定义 1[1]设布尔多项式 f(x1，x2，…，xn-1)的代数正规型表示为：

设 I={i1，i2，…，i|I|}是集合{1，2，…，n}的一个子集，I 中元素的个数记为|I|，I 被称为是一个立方指数，称为一个立方(cube)，设于是：

其中PS(I)是与tI没有相同变量的多项式，被称为立方 I 的超级多项式(Superpoly)；r(x1，x2，…，xn-1)中的每一项至少缺失tI中的一个变量。当 CI中的变量取遍所有的可能值，对式(2)的左端取连加和，得到PS(I)，即∑CIf=PS(I)。

对攻击者而言，密码算法是一个关于秘密变量和公开变量的复杂的多元多项式，表示为 f(v1，v2，…，vm-1，x1，x2，…，xn-1)，其中 xi是秘密变量，vi是公开变量。立方攻击是把多元布尔多项式表示成一种类似于式(2)的分解式，除式是某些公开变量的乘积，超级多项式是秘密变量的简单的多项式，然后通过下面的攻击过程恢复密钥。

1.2 立方攻击的攻击过程

攻击过程分为两个阶段：离线阶段和在线阶段。

离线阶段：攻击者可以选择秘密变量和公开变量，随机选择立方变量，执行密码算法，计算PS(I)，使用一次或者二次超级多项式的判定准则(见第2 节)，得到很多立方变量和相应的简单超级多项式，为在线阶段做准备。

在线阶段：秘密变量是固定的且是未知的，不允许选择，敌手利用离线阶段获得的立方变量，对其进行0/1 赋值，去访问加密算法，得到输出比特；对所有输出比特进行连加求和，获得超级多项式的值，最后求解得到的代数方程组，可以恢复某些密钥比特；猜测剩余的密钥变量，完成密钥恢复攻击。

2 低次超级多项式的判别方法

文献[1，9-10]中的超级多项式的次数是一次或二次的，判别方法也较为简单，下面分别叙述。

2.1 一次超级多项式判别方法

独立均匀随机地选择 x，y∈{0，1}n，验证 PS(I)[0]+PS(I)[x]+PS(I)[y]=PS(I)[x+y]是否成立。如果PS(I)是线性的，则测试总是成功的；如果 PS(I)不是线性的，则测试以很高的概率失败，测试进行足够多次，敌手就可以确定PS(I)是非常接近线性的了。

2.2 二次超级多项式的判别方法

随机选择 x1，x2，x3∈{0，1}n，验证 PS(I)[0]+PS(I)[x1]+PS(I)[x2]+PS(I)[x3]+PS(I)[x1+x2]+PS(I)[x1+x3]+PS(I)[x2+x3]+PS(I)[x1+x2+x3]=0 是否成立。如果 PS(I)是二次的，则测试总是成功的；如果PS(I)不是二次的(是更高次的)，则测试以很高的概率失败，测试多次就可以排除非二次的PS(I)。

2.3 非线性超级多项式的判别方法

在非线性超级多项式情形下，为确定超级多项式的项和系数，引入一种扩展的立方攻击理论(Extended Cube Attack)。

定义2(扩展立方体)[10]在立方攻击中，对任意立方 CI，如果存在另一个立方 CH，且 I∩H=φ，则CI与 CH可以得到一个扩展的立方 CI∪H。

下面的引理 1 和引理 2，判断哪些密钥变量存在于PS(I)中以及以怎样的单项式形式存在。

引理 1[10]设 f(x1，x2，…，xn)是一个多项式，设I={i0，…，il} 是集合 {1 ，2 ，…，n}的一个子集，则 tI以子项式或子项的一部分存在于 f 中，当且仅当至少存在一个向量 x ∈{0，1}n-|I|，使得。

引理2[10]单项式是 PS(I)中的一个子项，当且仅当令所有xi=0(xi∉I∪H)，有

3 立方攻击的前沿研究及主要结论

上节介绍了求解低次超级多项式的判别方法，求解更高次的超级多项式的方法是本节要介绍的内容。

3.1 基于比特的多重集合的可分性

基于比特的可分性定义如下：

定义3[2]设是一个多重集合是一个n 维向量的集合，称多重集 X 有可分性，如果满足下面的条件：

这里 u≥K 是指如果对于任意的 i，都有 ui≥ki，其中。

定义4[4](可分路径) 假设可分性质的传播为{K}≜Y0→Y1→…→Yr，进一步地，对任何向量Yi+1必然存在一个向量可由可分性的传播规则传播到，更进一步地，(K0，K1，…，Kr)∈(Y0×Y1×…×Yr)，如果 Ki可以传播到Ki+1，i ∈{0，1，…，r-1}，就把(K0，K1，…，Kr)称为一条 r 轮的可分路径。

为了计算出所有的可分路径，需要先把密码算法中的复制运算(Copy)、异或运算(XOR)和且运算(AND)转化成MILP 模型，再把整个密码算法建模成MILP 模型，这样就可以使用最优化数学软件Gurobi来计算所有的可分路径。

3.2 基于可分路径寻找超级多项式

由第2 节可知，立方攻击成功的关键在于找到简单的超级多项式，例如超级多项式中的变量的个数少，同时次数又是一次的或者二次的。下面的性质是利用可分路径求出超级多项式中所有的变量的依据。

性质 1[5]设 f(X，V)是一个多元多项式，X=(x0，x1，…，xn-1)是秘密变量，V=(v0，v1，…，vm-1)是公开变量，设一个立方索引 I={i0，i1，…，i|I|-1}，KI是一个m 维的向量，使得即如果 i∈I，则 ki=1，否则 ki=0；n 维向量 ej=(0，…，0，1，0，…，0)，即在第 j 分量上取值为 1，而其他分量是 0；假设没有可分路径(ej，KI)→f1，那么 xj不是超级多项式中的变量。

性质 1 说明，存在可分路径(ej，KI)→f1，则 xj是超级多项式中的变量，那么可以得到超级多项式中的所有的变量，进而求出超级多项式的表达式。

离线阶段：设J 是超级多项式中的变量下标的集合，集合J 遍历所有可能的值组成的集合记为 CJ，集合 J 之外的变量赋值为 0，对于给定的值Xs=(xs，0，0，…，0)，xs∈CJ，敌手可以设定公开变量中除了立方变量之外的变量为某些常数，计算∑CIf(Xs，V)=PS(I)，得到超级多项式的真值表。值得注意的是，敌手可以多次选择除了立方变量以外的公开变量的值使得超级多项式是一次的。

这里时间复杂度为 2|I|+|J|，如果|I|+|J|小于密钥长度，那么立方攻击就是有效的。

在文献[6]中，王庆菊等人注意到常数值0 在运算中会消去多项式这一现象，提出了Flag 技术，即定义了初始向量的常数值与变量的运算法则，修正了复制、异或、且运算的 MILP 模型，提高了可分路径的计算准确性，提出了超级多项式的最高次项的判断方法，使得立方攻击可以求出更高次数的超级多项式。

性质 2设 f(X，V)是一个多元多项式，X=(x0，x1，…，xn-1)是秘密变量，V=(v0，v1，…，vm-1)是公开变量，设一个立方索引 I={i0，i1，…，i|I|-1}，KI是一个m 维向量，使得即如果i ∈I，则ki=1，否则 ki=0；KΛ是一个 n 维向量，假设没有可分路径(KΛ，KI)→1，那么 XKΛ不在超级多项式中。

性质 2 说明，如果存在可分路径(KΛ，KI)→1，那么XKΛ在超级多项式中，于是，在线性整数规划模型中可以求得超级多项式中的最高次项；再由性质1，得到超级多项式中的所有的变量，就可以降低恢复超级多项式的复杂度。

3.3 基于三子集可分性

定义 5[7](基于三子集可分性) 设 X 是一个多重集合是由 n 维比特向量组成的集合，当多重集 X 具有可分性是指下列的条件成立：

基于三子集可分性修改了复制运算、异或运算、与运算的 MILP 建模，王森鹏等人[7]提出了该可分性的修剪性质(Pruning Properties)，去掉无用的可分路径，并提出了可分路径的加速传播和停止准则，来提高可分路径的计算效率；最后提出了相似多项式(Similar Polynomial)的概念来计算超级多项式。但是这一概念与文献[10]中的引理2 本质上是一致的。对密码算法 Trivium[11]的立方攻击的轮数是 839 轮，但时间复杂度为常数，攻击实际可行。

3.4 完善的三子集可分性

HAO Y L 等人[8]发现王森鹏等人的立方攻击的计算方法并非总是有效的，在求841 轮的Trivium的超级多项式时，由于 L 的规模过大，在合理的时间内是无法求解的。于是，提出了完善三子集可分性的概念。

定义 6[8](完善三子集可分性) 设 X 是一个多重集合，其元素，设 L 也是一个多重集合，其元素有完善的三子集可分性是指满足下面的条件：

HAO Y L 等人进一步完善了复制运算、异或运算、与运算的MILP 建模，提出了更有效的计算超级多项式的算法，对轮数是 841 轮的 Trivium，完全确定了其超级多项式的表达式，展示了立方攻击的强大的分析能力。

4 立方攻击技术比较

密码算法Trivium 是基于非线性反馈移位寄存器的序列密码，迭代关系式是两次的，密钥长度是80 bit，初始化向量是80 bit，初始化轮数是1 152 轮。表1 以立方攻击分析 Trivium 算法为例，清晰地展示了立方攻击技术的分析能力。

通过表1 可以发现，基于一次或者二次超级多项式判定方法的立方攻击，求得的超级多项式表达式简单，攻击轮数低，时间复杂度也低；而基于多重集合可分性的立方攻击，可以求得的超级多项式表达式复杂，攻击轮数高，但是时间复杂度不一定高。

究其原因，密码算法 Trivium 的迭代关系式是二次的，在初始化轮数较低时(小于 767 轮)，局部出现线性多项式的可能性较大，但是随着初始化轮数的增加(大于 832 轮)，输出比特的关系式的非线性程度将急剧增加，无论是代数次数还是项数都会增加很快，局部出现线性多项式的可能性较小，输出比特的关系式会非常复杂。这是两种立方攻击的分析效果截然不同的根本原因。这就是说，基于一次或者二次超级多项式的判定方法的立方攻击不可能分析到更高的轮数，即基于一次或者二次超级多项式的判定方法的立方攻击，不可能取得大的突破性进展，这是由密码算法自身的迭代关系式和轮数决定的。但是基于可分性，立方攻击可能分析到更高的轮数。这是因为后者有清晰的数学模型、扎实的数学理论支撑，而且计算过程使用了数学软件工具，能够求解的超级多项式从理论上讲是不限制次数和项数的，能否计算出超级多项式只取决于计算机的计算能力，所以后者方法可以求出更高轮数的超级多项式的表达式。

由此可知，未来的研究方向主要是要完善基于可分性的立方攻击的技术，提升其计算能力。亟待解决的研究问题有两个：一是进一步提高数学模型计算的准确性，因为有研究指出，针对 Trivium 的某些轮数，立方攻击不是密钥恢复攻击而是区分攻击；二是优化实现立方攻击的算法，降低其时间复杂度，提高其计算效率，因为目前的攻击算法在普通计算机上的运行时间需要几天或者时间复杂度更大，还有进一步优化的必要。