Optimizing Fast Near Collision Attack on Grain Using Linear Programming
Optimizing Fast Near Collision Attack on Grain Using Linear Programming
复制标题
使用线性规划优化谷物的快速近碰撞攻击
DOI：
10.1109/access.2019.2959334
复制
发表时间：
2019
期刊：
影响因子：
3.9
通讯作者：
LIANGMIN WANG
中科院分区：
文献类型：
--
作者：
SENSHAN PAN;YUEPING WU;LIANGMIN WANG
2018年，一种名为快速近碰撞攻击（FNCA）的攻击被提出，这是对eSTREAM项目三个面向硬件的决赛选手之一Grain-v1的近碰撞攻击（NCA）的改进版本。FNCA是一种密钥恢复攻击，采用分而治之的策略，需要一个合并阶段。我们提出了一种改进的FNCA的合并阶段进行优化的线性规划为基础的战略。它减少了合并的每一步中的内部状态向量（ISV）的候选，并具有整体的时间复杂度降低。由于合并阶段是分而治之的策略，其中的大部分位的完整的内部状态被恢复是至关重要的，其他分析与FNCA的粮食家庭可以得到不同程度的优化，我们的方法。本文提供了一个实验上的减少粮食和理论分析的粮食-v1证实的结果。在80位内部状态的减少的Grain的情况下，时间复杂度为237.1096，其具有27.8%的减少。对于Grain-v1，其理论时间复杂度约为273.4，与原始时间复杂度相比降低了79.4%。
In 2018, an attack named fast-near-collision attack (FNCA) was proposed, which is an improved version of near-collision attack (NCA) on Grain-v1, one of the three hardware-oriented finalists of the eSTREAM project. FNCA is designed as a key recovery attack and takes a divide-and-conquer strategy that needs a merging phase. We propose an improved FNCA where the merging phase is optimized by a linear programming based strategy. It decreases the candidates of the internal state vectors (ISVs) in each step of merging and has a reduction in the overall time complexity. Since the merging phase is vital for a divide-and-conquer strategy, where the most of bits of the full internal state are recovered, other analyses on Grain family with FNCA can get optimized by our method in varying degrees. This paper offers an experiment on a reduced Grain and a theoretical analysis on Grain-v1 to confirm the results. In the case of the reduced Grain of an 80-bit internal state, the time complexity is 237.1096, which has a 27.8% reduction. For Grain-v1, its theoretical time complexity is around 273.4, which is reduced by 79.4% compared with the original one.
登录
查看更多内容
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
DOI：
10.1007/978-3-319-96881-0_5
发表时间：
2018-08
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Yosuke Todo;Takanori Isobe;W. Meier;Kazumaro Aoki;Bin Zhang
通讯作者：
Yosuke Todo;Takanori Isobe;W. Meier;Kazumaro Aoki;Bin Zhang
DOI：
10.1007/11799313_2
发表时间：
2006-03
期刊：
--
影响因子：
--
作者：
C. Berbain;H. Gilbert;A. Maximov
通讯作者：
C. Berbain;H. Gilbert;A. Maximov
DOI：
--
发表时间：
2016
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Vahid Aminghafari;Honggang Hu
通讯作者：
Vahid Aminghafari;Honggang Hu
DOI：
10.1007/3-540-45708-9_19
发表时间：
2002-08
期刊：
--
影响因子：
--
作者：
D. Wagner
通讯作者：
D. Wagner