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

• 作者: 史丹萍 孙思维 张英杰 王鹏 胡磊 魏荣
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: Grain-v1 基于LFSR的流密码 快速相关攻击 基于MILP的线性分析
• 年，卷（期）: 2020,（6）
• 页码范围: 812-825
• 页数: 14页
• 分类号: TP309.7
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000408

摘要

快速相关攻击(FCA)是对基于LFSR结构的流密码算法的主流攻击方法之一.Todo等人在2018年美密会提出了基于LFSR结构的流密码算法的一种新性质,并进一步指出基于Grain结构的流密码算法存在多个高相关度的线性逼近.利用这两个发现,他们从线性分析的角度改进了对基于Grain结构的流密码算法的快速相关攻击,并成功地攻击了Grain-128a,Grain-128以及Grain-v1.本文首先以一种便于理解的方式回顾了Todo等人提出的快速相关攻击方法.之后,我们基于NFSR的状态更新函数改进了基于混合整数线性规划(MILP)搜索校验等式的方法.我们利用改进后的方法搜到了Grain-v1的新的检验等式,与Todo等人的结果相比,新的检验等式对应更多高相关度掩码,可将FCA的时间和数据复杂度由276:6935 和275:1085 降低为275:6724 和274:0875.