基于NLFSR的序列密码算法的分析方法研究

  本文关键词：基于NLFSR的序列密码算法的分析方法研究，，由笔耕文化传播整理发布。

【摘要】：2004年启动的欧洲eSTREAM工程极大地推动了国际序列密码算法设计与分析的发展,NLFSR (Non-Linear Feedback Shift Register)作为一种新的驱动部件被用于序列密码算法的设计中,基于NLFSR的序列密码算法的设计与分析得到了国际密码学界的高度关注,成为近几年来序列密码研究领域的热点问题。以Grain、Trivium和MICKEY为代表的基于NLFSR的序列密码算法在eSTREAM工程中胜出,一方面说明基于NLFSR的序列密码算法具有很高的安全性,另一方面也说明对基于NLFSR的序列密码算法进行有效的攻击是非常困难的。总体而言,从eSTREAM工程开始至今,尽管国际密码学界对基于NLFSR的序列密码算法给予了很高的关注,但分析方法的相关研究成果寥寥无几,对代表密码算法的安全性分析也是进展缓慢。基于NLFSR的序列密码算法的分析方法研究已成为当前序列密码研究领域最困难的问题之一,也是亟待解决的问题之一。本文对基于NLFSR的序列密码算法的分析方法进行了深入研究,针对基于NLFSR的序列密码算法设计中的主要关键点,即基于NLFSR的序列密码算法中布尔函数的设计、算法模型的设计、初始化算法的设计、算法密钥规模以及密钥加载方式的设计,有针对性地、系统地研究了代数攻击、基于猜测的复合攻击、滑动攻击和时间存储数据折中攻击共四种重要的分析方法,对Grain、Trivium和MICKEY等具有代表性的基于NLFSR的序列密码算法及其模型进行了安全性分析,以方法分析为主体,以密码算法模型及代表算法的安全性分析为例子,深入研究了基于NLFSR的序列密码算法抵抗以上四种分析方法的能力,取得的创新性成果列举如下。一、针对基于NLFSR的序列密码算法中布尔函数的设计,提出了代数攻击的一种新的变型和基于条件非线性逼近的概率代数攻击。1.通过对代数攻击的深入研究,提出了代数攻击的一种新的变型,命名为划分攻击,其主要思想为通过猜测大部分的密钥比特,将整个序列密码算法划分为众多不同、相互独立且密钥规模很小的子密码,对于每个子密码,攻击者可以具体地给出每个密钥流比特关于子密码密钥的多项式表示,从而有效地降低密钥恢复过程的时间复杂度。将划分攻击应用于全轮的Trivium序列密码算法,给出了针对全轮Trivium的首个优于穷举攻击的密钥恢复攻击,是目前为止所有分析结果中最好的。2.对针对Grain序列密码算法的概率代数攻击进行了深入研究,指出并修正了已有的针对Grain序列密码算法的概率代数攻击中存在的错误,针对Grain为代表的级联模型,提出了基于条件非线性逼近的概率代数攻击,作为应用,针对Grain v1序列密码算法,给出了成立概率更高的非线性方程组,提出了更加有效的概率代数攻击。二、针对基于NLFSR的序列密码算法模型的设计,提出了两种新的基于猜测策略的复合攻击,分别为基于密钥流输出函数弱正规性的猜测-仿射化攻击和基于时空折中技术的猜测验证攻击。1.指出了Mihaljevic等人给出的基于密钥流输出函数正规性的状态恢复攻击中存在的错误,利用密钥流输出函数的弱正规性,通过猜测对该函数进行仿射化,结合时间存储数据折中攻击,提出了新的基于猜测策略的复合攻击,即猜测-仿射化攻击,并应用于Grainv1序列密码算法中,给出了时间复杂度优于穷举攻击的状态恢复攻击。2.结合时间存储数据折中攻击,通过在离线攻击阶段建立验证表和在在线攻击阶段对输出密钥流序列进行预处理,提出了一种新的基于猜测策略的复合攻击,命名为猜测验证攻击,应用于简化的MICKEY和Grain算法模型,给出了时间复杂度优于穷举攻击的状态恢复攻击,与代数攻击相比,该攻击的优势在于分析结果与算法中采用的NLFSR的非线性反馈函数无关。三、针对基于NLFSR的序列密码算法初始化算法的设计,提出了基于带隐藏信息的滑动特征的滑动攻击。1.对基于NLFSR的序列密码算法中内部状态的滑动特征所导致的信息泄漏进行了分析,指出该滑动特征所导致的信息泄漏存在关于内部状态的隐藏方程,利用时空折中技术,提出了攻击算法,并对攻击算法的复杂度和成功率等性能指标进行了分析,解决了如何利用滑动特征所导致的信息泄漏进行密钥恢复这一理论问题。2.首次发现了基于NLFSR的Grain-128a序列密码算法中存在的滑动特征,提出了针对该算法的滑动攻击,相关密钥条件下恢复全部128比特密钥的时间复杂度约为296.322,需要2103.613个密钥流比特,攻击成功的概率为0.632,这是针对Grain-128a的首个有效密钥恢复攻击,分析结果表明Grain-128a的设计者对算法的改进并不彻底,Grain-128a依然有安全性漏洞。3.首次发现了基于WG-NLFSR的WG-8序列密码算法中存在的滑动特征,利用该滑动特征,在相关密钥条件下,提出了针对WG-8的首个实时的密钥恢复攻击,攻击结果远优于穷举攻击。通过实验仿真,验证了以上攻击结果的正确性。随后,通过修改WG-8的密钥和IV加载方式,提出了改进的WG-8序列密码算法,改进方法既保持了原算法设计上的特色,又提高了算法抵抗滑动攻击的能力。四、针对基于NLFSR的序列密码算法密钥规模的设计,提出了基于BSW Sampling技术的新TMDTO攻击。针对MICKEY序列密码算法中密钥加载方式的设计,结合时空折中技术,提出了首个优于穷举攻击的密钥恢复攻击。1.将BSW Sampling技术与Babbage和Golic分别独立提出的TMDTO攻击(记为BG-TMDTO攻击)进行了有效地结合,提出了新的基于BSW Sampling技术的TMDTO攻击,该攻击可视为BG-TMDTO攻击的一般性推广,即使序列密码算法的内部状态规模不小于密钥规模的两倍时,该攻击仍能得到良好的折中选择,将该攻击应用于Grain和MICKEY等基于NLFSR的序列密码算法,分析结果优于已有的TMDTO攻击。2. MICKEY序列密码算法自提出至今已有近十年的时间,但已有的分析结果却屈指可数,目前为止仍没有优于穷举攻击的分析成果出现。通过对MICKEY序列密码算法的密钥加载方式的深入分析,首次发现其初始化算法具有可分割性,利用这一结构性弱点,结合时空折中技术,提出了针对MICKEY序列密码算法的新密钥恢复攻击,时间复杂度降为穷举攻击时间复杂度的一半,是目前为止首个优于穷举攻击的分析结果。这一成果表明MICKEY的密钥加载方式是有潜在的安全性弱点的。欧洲eSTREAM工程丰富了序列密码研究的“数据库”,极大地促进了序列密码的研究。目前,基于NLFSR的序列密码算法的分析已成为序列密码研究领域的热点与难点问题。本文的研究成果将有助于深化对序列密码分析方法的认识,对丰富序列密码算法的分析理论具有重要意义。

  本文关键词：基于NLFSR的序列密码算法的分析方法研究，由笔耕文化传播整理发布。