Grain-v1快速相关攻击的改进  

Improved Fast Correlation Attack on Grain-v1

作　　者：张英杰 胡磊[1,2,3] 史丹萍[1,2,3] 王鹏[1,2,3] 孙思维 魏荣 ZHANG Ying-Jie;HU Lei;SHI Dan-Ping;WANG Peng;SUN Si-Wei;WEI Rong(State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;Data Assurance and Communication Security Research Center,Chinese Academy of Sciences,Beijing 100093,China;School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China;Beijing Institute of Satellite Information Engineering,Beijing 100086,China)

机构地区：[1]中国科学院信息工程研究所信息安全国家重点实验室,北京100093 [2]中国科学院数据与通信保护研究教育中心,北京100093 [3]中国科学院大学网络空间安全学院,北京100093 [4]北京卫星信息工程研究所,北京100086

出　　处：《密码学报》2020年第6期812-825,共14页Journal of Cryptologic Research

基　　金：国家重点研发计划(2018YFA0704704);国家自然科学基金重点项目(62032014);十三五国家密码发展基金(MMJJ20180102);国家自然科学基金(61772519,61732021,61802400,61802399)。

摘　　要：快速相关攻击(FCA)是对基于LFSR结构的流密码算法的主流攻击方法之一.Todo等人在2018年美密会提出了基于LFSR结构的流密码算法的一种新性质,并进一步指出基于Grain结构的流密码算法存在多个高相关度的线性逼近.利用这两个发现,他们从线性分析的角度改进了对基于Grain结构的流密码算法的快速相关攻击,并成功地攻击了Grain-128a,Grain-128以及Grain-v1.本文首先以一种便于理解的方式回顾了Todo等人提出的快速相关攻击方法.之后,我们基于NFSR的状态更新函数改进了基于混合整数线性规划(MILP)搜索校验等式的方法.我们利用改进后的方法搜到了Grain-v1的新的检验等式,与Todo等人的结果相比,新的检验等式对应更多高相关度掩码,可将FCA的时间和数据复杂度由2^76:6935和2^75:1085降低为2^75:6724和2^74:0875.Fast correlation attack is one of the most important attacks on LFSR based stream ciphers.At Crypto 2018,Todo et al.found that there is a new property of LFSR based stream ciphers,and pointed out that there are many linear approximations of the Grain-based structure,which were successfully applied to the fast correlation attack on Grain-128a,Grain-128,and Grain-v1 from the aspect of linear cryptanalysis.This paper revisits the fast correlation attack proposed by Todo et al.in an easily-understood way.Then based on the state update function of NFSR,the MILP-based method used for searching good parity-check equations is improved.Finally,the improved MILP-based method is used to analyze Grain-v1 and new parity-check equations with more high-correlation masks than the one found by Todo et al.The method can be used to reduce the time and data complexities of fast correlation attack on Grain-v1 from 2^76:6935 to 2^75:6724 and from 2^75:1085 to 2^74:0875 respectively.

关 键 词：Grain-v1 基于LFSR的流密码 快速相关攻击 基于MILP的线性分析 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]