对Grain-v1算法的时空折中Cube攻击

A Space-time Tradeoff Cube Attack on Grain-v1

cube集合的选取是cube攻击中的关键问题,也是最耗时的阶段.本文采用时空折中思想,设计一种新的搜索算法.选择一个维度较大的指标集,进行一次标准cube攻击,同时存储该指标集每个向量对应的cube和,对指标集的每个子集求取cube和时,只需将相应向量对应值相加即可,这样通过对一个cube集合的运算,可以诱导出多个线性方程.将此方法应用到缩减轮数的Grain-v1算法,对于初始化轮数为70轮的Grain-v1算法,可直接恢复18比特密钥,并找到关于另外28比特密钥的5个线性表达式.对于初始化轮数为75轮的Grain-v1算法,可以直接恢复14比特密钥,并找到了关于另外28比特密钥的6个线性表达式.

How to select the cube set is the crucial point of the cube attack, and is also the time-consuming phase. We found a new search algorithm, which uses the method of space-time tradeoff. We selected a cube set which have larger dimension and conducted a standard cube attack, at the same time, we stored all the cube sum which corresponds to each vector of the cube set, Then we could get the cube sum of the each subset by adding the corresponding value. So we could get more linear equations by only one cube set. Applying it to a reduced version of Grain-v1 with 70 initialization rounds, the study finds that 18-bit secret key can be recovered and can find 5 linear equations on another 28 bits of the secret key. For the initialization of 75 rounds, the study finds that 14-bit secret key can be recovered and can find 6 linear equations on another 28 bits of the secret key.