Near Collision Attack on the Grain v1 Stream Cipher
Near Collision Attack on the Grain v1 Stream Cipher
复制标题
DOI：
10.1007/978-3-662-43933-3_27
复制
发表时间：
2013-03
期刊：
影响因子：
--
通讯作者：
Bin Zhang;Zhenqi Li;D. Feng;D. Lin
中科院分区：
文献类型：
--
作者：
Bin Zhang;Zhenqi Li;D. Feng;D. Lin
Grain v1是eSTREAM项目最终产品组合中的入围产品之一。它具有优雅、紧凑的结构，特别适合于硬件受限的环境。虽然已经发现了一些潜在的弱点，但尚未发现对单密钥模型中原始设计的密钥恢复攻击。在本文中，我们提出了一个密钥恢复攻击，称为近碰撞攻击，在粮食v1。该攻击利用Grain v1的紧凑型NFSR-LFSR组合结构，即使所有先前识别的弱点都已被缝合，并且如果采用完美的密钥/IV初始化算法，也可以工作。我们的想法是识别内部状态在不同时刻的近碰撞，并相应地恢复状态。结合BSW采样和固定密钥流差异的内部状态差异的非均匀分布，我们的攻击已在Grain v1的简化版本上得到实验验证。在一定的假设条件下，对Grainv 1的攻击结果进行了外推，结果表明，Grainv 1在预先计算了节拍、给定的内存和密钥流位数后，对任何固定的IV初始节拍都可以进行攻击，这是迄今为止针对Grainv 1的最好的密钥恢复攻击。希望它能为此类紧凑流密码提供一些新的见解。
Grain v1 is one of thefinalists selected in the final portfolio by the eSTREAM project. It has an elegant and compact structure, especially suitable for a constrained hardware environment. Though a number of potential weaknesses have been identified, no key recovery attack on the original design in the single key model has been found yet. In this paper, we propose a key recovery attack, called near collision attack, on Grain v1. The attack utilizes the compact NFSR-LFSR combined structure of Grain v1 and works even if all of the previous identified weaknesses have been sewed and if a perfect key/IV initialization algorithm is adopted. Our idea is to identify near collisions of the internal states at different time instants and restore the states accordingly. Combined with the BSW sampling and the non-uniform distribution of internal state differences for a fixed keystream difference, our attack has been verified on a reduced version of Grain v1 in experiments. An extrapolation of the results under some assumption indicates an attack on Grain v1 for any fixed IV incipher ticks after the pre-computation ofticks, given-bit memory andkeystream bits, which is the best key recovery attack against Grain v1 so far. Hopefully, it provides some new insights on such compact stream ciphers.