Fast Correlation Attack Revisited -Cryptanalysis on Full Grain-128a, Grain-128, and Grain-v1
Fast Correlation Attack Revisited -Cryptanalysis on Full Grain-128a, Grain-128, and Grain-v1
复制标题
DOI：
10.1007/978-3-319-96881-0_5
复制
发表时间：
2018-08
期刊：
影响因子：
--
通讯作者：
Yosuke Todo;Takanori Isobe;W. Meier;Kazumaro Aoki;Bin Zhang
中科院分区：
文献类型：
--
作者：
Yosuke Todo;Takanori Isobe;W. Meier;Kazumaro Aoki;Bin Zhang
快速相关攻击(FCA)是基于LFSR的流密码的一种著名的密码分析技术。利用LFSR的初始状态与对应密钥流之间的相关性，恢复LFSR的初始状态。本文从一个新的角度对有限域上的FCA进行了重新审视，给出了FCA在多重线性逼近时的一个新的性质。此外，我们基于新的性质提出了一种新的算法，这使得我们能够同时降低时间和数据的复杂性。最后，我们将这一技术应用于Grain家族，这是一类分析得很好的流密码。Grain系列中有三种流密码：Grain-128a、Grain-128和Grain-v1，Grain-v1位于eSTREAM产品组合中，Grain-128a由ISO/IEC标准化。因此，我们破解了它们，特别是对于Grain-128a，首次报道了对其完整版本的密码分析。
A fast correlation attack (FCA) is a well-known cryptanalysis technique for LFSR-based stream ciphers. The correlation between the initial state of an LFSR and corresponding key stream is exploited, and the goal is to recover the initial state of the LFSR. In this paper, we revisit the FCA from a new point of view based on a finite field, and it brings a new property for the FCA when there are multiple linear approximations. Moreover, we propose a novel algorithm based on the new property, which enables us to reduce both time and data complexities. We finally apply this technique to the Grain family, which is a well-analyzed class of stream ciphers. There are three stream ciphers, Grain-128a, Grain-128, and Grain-v1 in the Grain family, and Grain-v1 is in the eSTREAM portfolio and Grain-128a is standardized by ISO/IEC. As a result, we break them all, and especially for Grain-128a, the cryptanalysis on its full version is reported for the first time.