非线性反馈移存器型序列密码的完全性通用算法

Universal Algorithm of Full Diffusion of Stream Cipher Based on Nonlinear Feedback Shift Register

非线性反馈移存器型序列密码被使用于智能卡、射频识别标签(RFID)和无线传感器等硬件资源受限设备的信息加密中,其典型代表为Trivium算法、Grain v1算法和Mickey算法,然而现有的完全性算法在应用于此类序列密码时存在分析轮数较少及对依赖关系区分不清楚等问题.本文提出了一种考察此类序列密码完全性的通用算法,将算法内部状态表示成线性集合和非线性集合,将序列密码每轮更新转化为集合的运算,通过迭代计算可给出算法达到非线性完全性所需轮数的下界,克服了现有完全性算法的不足.应用此通用算法给出Trivium算法更优的1比特差分区分器并完成对Trivium-B算法的实时攻击.本方法可为此类序列密码的设计提供一定的理论依据.

Stream ciphers based on nonlinear feedback shift register are used in information security of hardware restricted devices such as smart cards,radio frequency identification(RFID)and wireless sensor network.Typical examples of these ciphers are Trivium,Grain v1 and Mickey.Previous algorithms of full diffusion have disadvantages such as few analyzing rounds and indistinct dependent relationship.This paper proposes an algorithm for full diffusion of stream cipher based on nonlinear feedback shift register.The internal states of cipher are represented as linear sets and nonlinear sets.Then round functions of stream cipher are converted to operations of sets.So we can estimate the lower bound of rounds which a stream cipher needs to reach full nonlinear diffusion.Using this algorithm,this paper presents an improved one bit differential distinguisher of Trivium and a real-time attack on full rounds of Trivium-B.Moreover,this method can provide certain theory basis for the design of this kind of stream cipher.