An Improved Framework of Massive Superpoly Recovery in Cube Attacks Against NFSR-Based Stream Ciphers

针对立方攻击中大规模超多项式恢复技术的改进

A critical problem in the cube attack is how to recover superpolies efficiently.As the targeting number of rounds of an iterative stream cipher increases,the scale of its superpolies becomes larger and larger.Recently,to recover massive superpolies,the nested monomial prediction technique,the algorithm based on the divide-and-conquer strategy,and stretching cube attacks were proposed,which have been used to recover a superpoly with over ten million monomials for the NFSR-based stream ciphers such as Trivium and Grain-128AEAD.Nevertheless,when these methods are used to recover superpolies,many invalid calculations are performed,which makes recovering superpolies more difficult.This study finds an interesting observation that can be used to improve the above methods.Based on the observation,a new method is proposed to avoid a part of invalid calculations during the process of recovering superpolies.Then,the new method is applied to the nested monomial prediction technique and an improved superpoly recovery framework is presented.To verify the effectiveness of the proposed scheme,the improved framework is applied to 844-and 846-round Trivium and the exact ANFs of the superpolies is obtained with over one hundred million monomials,showing the improved superpoly recovery technique is powerful.Besides,extensive experiments on other scaled-down variants of NFSR-based stream ciphers show that the proposed scheme indeed could be more efficient on the superpoly recovery against NFSR-based stream ciphers.

立方攻击的一个关键问题是如何有效地恢复超多项式.随着序列密码算法目标轮数的增长,其超多项式的规模也变的越来越大.近年来,为了恢复大规模超多项式,一系列新的技术被提出,包括嵌套单项预测技术、基于分治策略的恢复算法以及延展立方攻击.针对基于NFSR的序列密码算法,这些新技术能够用来恢复项数达到千万级别的超多项式.然而,利用这些新技术恢复超多项式的过程中,许多无效计算的存在使得超多项式的恢复变得更加困难.本文观察到一些有趣的实验现象能够用于改进上述方法.基于这一观察,提出了一种新的方法来避免超多项式恢复过程中存在的部分无效计算,将该方法与嵌套单项预测技术相结合,得到了改进的超多项式恢复框架.将其应用于844和846轮的Trivium算法,成功恢复了具有项数达到亿级的超多项式的准确的代数正规型,证明了改进的恢复超多项式的技术是有效的.此外,在其他减轮的基于NFSR的序列密码算法上的广泛实验表明,所提出的改进确实能够更加有效地恢复其超多项式.