Trivium-like算法中可滑动Cube的研究

On Slidable Cubes in Trivium-like Ciphers

对于Trivium-like算法,cube攻击是最有效的攻击手段之一.在传统cube攻击中,攻击者主要利用线性检测等方法来寻找具有低次超多项式的cube.实验结果表明存在IV变元子集I1=(vi1,vi2,…,vid)和I2=(vi1-1,vi2-1,…,vid-1)满足pI2(k0,k1,…,kn-2)=σ(pI1(k1,k2,…,kn-1)),其中ki表示密钥变元,pI1是Cube CI1对于t时刻输出比特zt的超多项式,pI2是Cube CI2对于t+1时刻的输出比特zt+1的超多项式,并且变换\sigma将ki映射到ki-1.在本文中,称这种性质为cube的可滑动性.我们研究了Trivium-like算法的攻击中cube的可滑动性.特别地,我们给出了cube具有可滑动性的一个充分条件.此外,我们将充分条件的判断,转化到求解混合整数线性规划(MILP)模型,在实际中能够快速判断出具有滑动性的cube.最后,我们将充分条件应用到实验cube攻击、基于分离性质的cube攻击和相关cube攻击的已有结果,验证了方法的正确性并在实验cube攻击中得到了一个803-轮Trivium的新结果.

The cube attack is one of the most powerful cryptanalysis techniques on Trivium-like ciphers.In the traditional cube attack,a cube with the low-degree superpoly is found by performing a large number of experimental tests such as linearity tests.Observing previous experimental results,it is easy to find that there exist two subsets of IV variables I1=(vi1,vi2,…,vid)and I2=(vi1-1,vi2-1,…,vid-1)such that pI2(k0,k1,…,kn-2)=σ(pI1(k1,k2,…,kn-1)),where ki is a secrete variable,pI1is the superpoly of CI1in the output bit zt after t rounds,pI2is the superpoly of CI2in the output bit zt+1after t+1 rounds,and\sigma maps ki to ki-1.Such kind of cubes are called slidable cubes in this paper.Slidable cubes in cube attacks against Trivium-like ciphers are studied,and a sufficient condition for cubes to be slidable is given.Moreover,by converting the verification of the sufficient condition into solving an MILP model,it can quickly determine whether a cube is slidable or not.Finally,by applying the proposed method to experimental cube attacks,to cube attacks based on the division property,and to correlation cube attacks,the correctness of the proposed method is verified and a new result is obtained for 803-round Trivium.