基于NLFSR的流密码算法的安全性分析

The eSTREAM (ECRYPT Stream Cipher Project), launched at 2004, greatly promoted the development of design and analysis of stream ciphers. Some representative NLFSR (Non-Linear Feedback Shift Register)-based stream ciphers, e.g., Grain v1, Trivium and MICKEY 2.0, had been three of the seven finalists in the final eSTREAM portfolio, and design and analysis of NLFSR-based stream ciphers attracted so much attention all over the world. However, so far the progress of cryptanalysis of representative NLFSR-based stream ciphers had been slow, and the research on the cryptanalysis of NLFSR-based stream ciphers has become one of the most difficult works in the current field of stream cipher. This project will study on the resistance of representative NLFSR-based stream ciphers (e.g., Grain v1, Trivium and MICKEY 2.0) and their models against these all known attacks, take the research on cryptanalytic methods, e.g., higher order differential cryptanalysis, propose new effective attack variants and improve the existing cryptanalytic results. The study will provide scientific basis and direction for the design of NLFSR-based stream ciphers, and be of great significance contributes to enrich the design and cryptanalytic theories of stream ciphers.

2004年启动的欧洲eSTREAM工程极大地推动了国际流密码算法设计与分析的发展，以Grain v1、Trivium和MICKEY 2.0为代表的基于非线性反馈移位寄存器（Non-Linear Feedback Shift Register，NLFSR）的流密码算法在eSTREAM工程中胜出，使得基于NLFSR的流密码算法的设计与分析得到了国际密码学界的高度关注。然而，到目前为止对这类流密码算法的安全性分析研究却是进展缓慢，已成为当前流密码研究领域的难点问题之一。本项目拟研究Grain v1、Trivium和MICKEY 2.0等基于NLFSR的典型流密码算法及模型抵抗各种已知密码分析方法的能力，对高阶差分分析等流密码分析方法进行研究，提出更加有效的攻击变型，改进现有的密码分析结果，为基于NLFSR的流密码算法的设计提供理论依据和指导，对丰富流密码算法的设计和分析理论具有重要意义。

以Trivium、MICKEY 2.0和Grain v1流密码算法在欧洲eSTREAM工程中及ACORN v3在CAESAR竞赛中胜出为标志，基于NLFSR的新型流密码算法已经获得了非常广泛的认可，在近几年的流密码研究领域非常活跃，是非常重要的研究领域和方向。本项目对基于NLFSR的新型流密码算法的代数次数评估方法进行了深入研究，取得的主要成果简述如下：.1．利用数字映射技术，结合ACORN v3认证加密算法的设计特点，对该密码算法进行了代数次数评估，利用评估结果建立了有效的区分器，改进了已有的针对该密码算法的区分攻击。.2．提出了复合数字映射技术并且证明了复合数字映射的评估效果要优于已有的数字映射技术，基于复合数字映射，提出了一个评估基于NLFSR的密码算法的代数次数的新的一般性框架，针对类Trivium流密码算法，改进了现有的区分攻击。.3．基于数字映射技术，提出了一个新的搜索立方的一般性方法—迭代步技术，给出了增量迭代步技术和减量迭代步技术两种搜索策略，提出了针对基于NLFSR的密码算法的搜索立方的算法，改进了现有的针对ACORN v3认证加密算法的区分攻击。.4．发现了MICKEY流密码算法的初始化算法中存在的可分割性，利用这一结构性弱点，结合时空折中技术，提出了针对MICKEY流密码算法的新TMDTO攻击，时间复杂度降为穷举攻击时间复杂度的一半，是目前为止首个优于穷举攻击的分析结果。.5．发现了WG-16流密码算法中存在的滑动特征，利用该特征提出了相关密钥条件下的密钥恢复攻击，攻击结果远优于穷举攻击，结果表明WG-16在多相关密钥条件下可以被实时破解，并没有达到设计者声称的安全强度。