【作者】 张海纳；

【导师】 王小云； 蔡吉人；

【作者基本信息】 山东大学 ， 信息安全， 2009， 博士

【摘要】 2004年,为加强信息安全特别是密码与数字水印方面的合作研究,欧洲启动了ECRYPT（European Network of Excellence for Cryptology）研究计划。eSTREAM为ECRYPT计划的工程项目之一,主要任务是征集新的可以广泛使用的序列密码算法,以改变2003年NESSIE工程6个参赛序列密码算法全部落选的状况。该工程于2004年11月开始算法征集,至2005年4月,共收到34个候选算法。经过3轮为期4年的评估,2008年4月eSTREAM工程结束,共有8个参赛算法获选。自第二评估阶段至今,共有12个算法（第二阶段8个,第三阶段3个,获选算法1个）被破解。在导师的精心指导下,本论文主要对eSTREAM工程的四个候选密码算法ABC v3（第二阶段）、TSC-4（第二阶段）、CryptMT v3（第三阶段）和Grainv1（最终获选）进行了安全性分析:在弱密钥条件下,破解了ABC v3和TSC-4;发现CryptMT v3密钥初始化过程存在概率为1的差分特征:对Grain v1进行了弱Key-Ⅳ攻击。1.弱密钥条件下破解ABC v3ABC v3的密钥长度为128比特,是34个参赛算法中运行速度最快的算法之一。ABC v1和v2为ABC v3之前的两个版本。2005年,Berbain、Gilbert和Khazaei同时发现ABC v1的线性移位寄存器（LFSR）长度过短,通过分别征服攻击破解了ABC v1。ABC v2加大LFSR的长度以弥补ABC v1的缺陷。但在SAC 2006上,Wu和Preneel发现ABC v2存在一类弱密钥,并且在弱密钥条件下,ABC v2可被破解。通过修改密钥初始化过程,消除Wu-Preneel弱密钥,ABCv3可抵抗以前所有攻击。ABC系列算法结构主要由LFSR、T-函数和基于背包问题构造的S-盒三部分组成。LFSR的最低权位32比特字与S-盒的输出进行模2³²加运算后作为密钥流输出字。LFSR反馈多项式的项数为3,虽然可以提高运行速度,但同时也降低了安全性,易受快速相关攻击。为此,算法设计者采用了T-函数、S-盒和模加运算等大量非线性组件来掩藏LFSR的线性。特别是基于背包问题构造的S-盒,加大了分析的难度。本文采取以恢复LFSR的内部状态为首要目标、以寻找算法核心部件S-盒的弱点为关键、以非线性模加运算的线性逼近为突破口的技术路线,发现ABC v3存在新型弱密钥,其发生的概率为2^-24.29。最终,在弱密钥条件下破解了ABC v3。（1）证明两类线性逼近式的概率优势从ABC v3最外层模加运算出发,首先研究二元非线性运算模加的线性逼近问题。本文发现了一类具有高概率优势的线性逼近式,通过分类和数学归纳,给出了此类线性逼近式的概率优势:其中,y,c和x为n比特整数,y=c+x（mod 2ⁿ）,F（y,m）=（?）=,1≤m≤n,δ_i（y）为整数y的第i低权位比特。另外一类线性逼近式反映了给定条件下三组模加运算进位比特之间的线性关系。由于各组运算的相关性导致研究的复杂化,Wu与Preneel通过计算机实验发现了该类逼近式的概率优势但没有给出严格的数学证明。通过分类归纳,本文证明了该线性逼近式的概率优势,并对其进行了推广,结果之一如下:这里,a_i,b_i和c_i为3个n比特整数,c_i,n=δ_n（a_i+b_i）,1≤i≤3,n≥2。这两类具有概率优势的线性表达式反映了非线性模加运算的线性逼近关系,利用它们可以得到大量序列密码ABC的弱密钥。由于模加运算与异或运算在对称密码算法的设计中使用广泛,这两类具有概率优势的线性表达式不仅能用来分析其它对称密码算法,而且是设计安全的对称密码算法时需要重点考虑的因素之一。（2）发现新型弱密钥首先,严格证明了产生ABC v2弱密钥的条件对于ABC v3不再存在,从而ABC v3可以抵抗先前所有攻击。因此,寻找ABC v3的新型弱密钥是本文研究的重点和难点。基于背包问题的S-盒是ABC v3的核心部件,具有很高的非线性度。由于背包问题是一个NP-C问题,目前没有很好的理论求解方法;而且由于新型弱密钥出现的概率很低,限于存储和计算能力,直接搜索的难度很大。通过大量分析研究,本文发现一类弱S-盒。在弱S-盒条件下,S-盒的输出在某些位置能够暴露LFSR的线性关系。本文提炼出一种快速搜索弱S-盒的算法,其核心是构造一个具有特殊性质的非线性变换,把全空间搜索简化到子空间搜索,提高速度近2^13.8倍。将产生弱S-盒的密钥定义为新型弱密钥,利用已提出的搜索算法,可得ABC v3在2¹²⁸个密钥中存在约2^103.71个新型弱密钥。（3）区分和恢复新型弱密钥新型弱密钥的区分攻击:利用模加运算的具有概率优势的线性逼近式和LFSR的线性特性,以正态分布逼近二项分布,建立ABC v3新型弱密钥的区分器,区分一个弱密钥与一个强密钥的计算复杂度约为2^41.48次异或运算。新型弱密钥的恢复攻击:首先,利用LFSR的内部状态与密钥流输出间的强相关性,运用快速相关攻击,可以恢复弱密钥条件下LFSR的所有内部状态。其次,利用T-函数的特性恢复T-函数的内部状态。第三,运用分别征服攻击逐步恢复背包函数的所有参数。最后可得,在弱密钥条件下恢复ABC v3的所有内部状态所需密钥流输出为2^36.05个32比特字,计算复杂度约为2^50.56次异或运算。ABC v1和v2除了密钥初始化过程外,在结构上与ABC v3基本相同,所以ABC v3的攻击方法可以平移到ABC v1和v2。经过分析,弱密钥条件下,恢复ABC v1和v2所有内部状态所需要的数据量和计算复杂度与ABC v3相同,但弱密钥的个数只有2⁹⁷+2^95.19个,反而小于ABC v3弱密钥的个数2^103.71。因此,经过改进的ABC v3安全性有所降低。2.弱密钥条件下破解TSC-4自Klimov和Shamir把T-函数引入密码学以来,出现了很多基于T-函数设计的序列密码算法,如Klimov-Shamir系列算法、TSC-1、TSC-2和TSC-3等。但所有算法均被破解。在总结已有攻击的基础上,Moon等密码学家设计了TSC-4。TSC-4进入eSTREAM第二评估阶段,密钥长度为80比特。在Indocrypt2006上,Fischer、Meier和Berbain等发现TSC-4的密钥初始化过程存在一定非随机性,但无法通过密钥流区分,不能形成真正的攻击。TSC-4算法结构主要由三部分组成:两个对称的T-函数部件X和Y以及一个以X和Y的部分状态为输入以密钥流为输出的非线性滤波函数。其中,T-函数采用了多种非线性逻辑运算、选择控制、S-盒等技术手段,具有很强的雪崩和扩散效应。由于很难建立数学模型,TSC-4一直没有被破解。本文将差分分析与分别征服攻击相结合,以计算机模拟实验为基础,从所得实验数据中挖掘数学规律,归纳弱密钥的特征,在弱密钥条件下破解了TSC-4。（1）构造密钥初始化过程的两个特殊差分特征TSC-4的密钥初始过程首先把密钥K和初始向量IV载入X和Y,然后进行8圈算法体的迭代。其中,每圈迭代包括三步:第一步通过非线性滤波函数把结构X和Y的信息混合后输出一个字节;第二步,X和Y各自按行循环移位:第三步是把第一步的输出字节混合到X和Y中。由此可见,X和Y主要是通过第一和第三步发生联系。使部件Y差分非零,部件X差分为零,如果初始化过程中每一圈的第一步输出差分为零,那么Y的差分就不可能扩散到X中,即X的差分可以始终保持为零。这样就可以“切断”部件X和Y的联系,达到控制雪崩的目的。利用此特点,构造出两个特殊差分特征Ω_X和Ω_Y,当差分特征Ω_Y成立时,差分特征Ω_X成立的概率为1。（2）发现弱密钥首先,随机选取密钥K和初始向量IV,运行密钥初始化过程,如果差分特征Ω_Y成立,则保留K和IV以及相对应的X和Y状态。第二,以状态Y的列为单位进行χ²检验,检测出非随机分布。第三,以检测出的非随机分布为研究对象,运用卡诺图技术,归纳总结出高概率线性表达式。第四,按照K和IV的载入方式代换关于X和Y的高概率线性表达式,得到关于K和IV的表达式。第五,合并各关于K和IV的线性表达式,定义产生高概率Ω_Y的弱密钥空间E_K和特殊IV空间E_IV。第六,按照空间E_K和E_IV重新运行密钥初始化过程,得到Ω_Y产生的概率。最后,可得对于80比特的密钥,TSC-4弱密钥的个数约为2⁷²个。当选择的IV对属于空间E_IV时,如果K是弱密钥,则Ω_Y出现的概率为2^-15.40;如果K为强密钥,则Ω_Y出现的概率为2^-24.74。（3）区分并恢复弱密钥尽管确定了密钥初始化过程的两个特殊差分特征和弱密钥,但除密钥流已知外,X和Y的内部状态未知。因此,需要构造一个能够把X和Y的差分不平衡性传递到密钥流的区分器。通过实验,本文成功构造出此区分器。通过理论计算可得,对于每个弱密钥,恢复出8比特密钥约需要2^40.53个选择IV对,剩余72比特密钥可通过搜索攻击恢复。通过分析可知,TSC-4是不安全的。另外,本文指出TSC-4还存在其它类型的弱密钥和攻击方法,如相关密钥攻击等。3.发现CryptMT v3密钥初始化过程存在概率为1的差分特征CryptMT v3为进入eSTREAM工程第三评估阶段的序列密码,密钥长度为128比特。由于采用乘法运算等独特技术,目前无任何攻击。设密钥初始化过程为以密钥K为参数的函数生成器:F={f_K:{0,1}¹²⁸→{0,1}¹⁹⁹⁶⁸}。通过差分分析,本文构造出区分器A^f_K,可以把f_K与随机函数以概率1区分出来,因而f_K不是随机函数。分析结果表明,CryptMT v3的密钥初始化过程存在一定的弱点,可能被攻击。4.弱Key-Ⅳ条件下破解Grain v1Grain v1是eSTREAM最终获选算法之一,其最初版本为Grain v0,密钥加长版本为Grain-128。2005年,Khazaei、Hassanzadeh和Kiaei对Grain v0进行了区分攻击。在FSE 2006上,Berbain、Gilbert和Maximov通过恢复密钥攻击,破解了Grain v0。Grain v1为Grain v0的修改版本,可抵抗以前攻击。在（?）.K（?）k提出的针对Grain v1/128的再同步滑动攻击基础上,（?）.K（?）k和Preneel等对Grainv1/128的密钥初始化过程进行了分析,Lee等进行了相关密钥选择Ⅳ攻击。以上关于Grain v1/128的攻击本质上均为相关密钥攻击。Afzal和Masood提出对Grain v1/128进行代数攻击,但计算复杂度超过了搜索攻击。2008年,eSTREAM最终评估报告认为Grain v1/128是很安全的,但指出密钥初始化过程需要修改。Grain系列算法体主要由LFSR、NFSR和非线性滤波函数三部分组成。Grainv0/v1/128的密钥长度分别为80/80/128比特,初始向量长度分别为64/64/96比特。设Grain系列密码算法密钥Key的长度为k比特,初始向量Ⅳ的长度为l比特,则不同的密钥和初始向量对Key-Ⅳ产生不同的密钥流输出,共可产生2^k+l条序列。对于一个安全的序列密码算法,保证2^k+1条序列中的每一条序列都具有很高的随机性是必要的。本文以Key-Ⅳ产生的序列为研究对象,对Grain v1进行弱Key-Ⅳ攻击。（1）弱Key-Ⅳ的存在性当LFSR的内部状态为全’0’时,算法只有NFSR起作用。因此,将能够产生LFSR为全’0’状态的密钥Key和初始向量Ⅳ定义为一个弱Key-Ⅳ。本文给出了求取弱Key-Ⅳ的算法和弱Key-Ⅳ实例。设密钥初始化过程后,所有内部状态均匀分布,则在2^k+l个Key-Ⅳ中有2^l个弱Key-Ⅳ。（2）区分弱Key-Ⅳ运用循环Walsh谱理论得到NFSR的非线性反馈函数的最佳线性逼近后,由线性逼近引理,本文构造出Grain系列算法的区分器,对弱Key-Ⅳ进行区分攻击,结果如下:从Grain v0/v1/128的2⁸⁰/2⁸⁰/2¹²⁸个Key-Ⅳ中以99.977%的成功率区分出1个弱Key-Ⅳ各需要2^17.8/2^49.4/2^91.8个密钥流比特和2^21.1/2^52.7/2¹¹⁰次运算。（3）恢复弱Key-ⅣGrain v1产生密钥流输出时,LFSR独立作用,NFSR的内部状态由自身和LFSR的内部状态决定,密钥流输出由LFSR和NFSR的内部状态决定。所以,密钥流输出可以表示为LFSR和NFSR内部状态的非线性函数,可得到相应的代数方程。对于弱Key-Ⅳ,LFSR不起作用,利用Afzal和Masood的代数攻击结果可得:在已知弱Key-Ⅳ条件下,只需150比特密钥流输出和2^30.7次异或运算即可破解Grain v1;在已知弱Key-Ⅳ条件下,破解Grain-128的复杂度为2^93.8次异或运算;Grain v0的结果类似于Grain v1。综上所述,Grain v1和Grain-128都存在弱Key-Ⅳ。破解Gran v0/v1/128的弱Key-Ⅳ分别需要2^17.8/2^49.4/2^91.8个密钥流比特和2^30.7/2^52.7/2¹¹⁰次异或运算。虽然弱Key-Ⅳ出现的概率很低,但可以说明这两个算法的密钥初始化过程存在安全问题,有必要进行修改。更多还原

【Abstract】 In 2004, ECRYPT （European Network of Excellence for Cryptology）, a 4-year European research initiative, was launched. It’s main purpose is to intensify the collaboration of European researchers in information security, especially in cryptology and digital watermarking. eSTREAM （ECRYPT Stream Cipher Project） is a project of ECRYPT to identify new stream ciphers that might suitable for widespread adoption. It was set up because none of six stream ciphers submitted to NESSIE project had been selected as the portfolio. The call for primitives was first issued in November 2004, and 34 primitives were submitted until April 2005. After three evaluation phases in four years, the project was completed with 8 primitives being the finalist portfolios in April 2008. Since the second evaluation phase, 8 algorithms in phase 2, 3 algorithms in phase 3, and 1 portfolio have been broken.Under the guidance of my supervisors, we mainly analyzes 4 candidate algorithms to eSTREAM Project ABC v3 （Phase 2）, TSC-4 （Phase 2）, CryptMT v3 （Phase 3）, Grain v1 （portfolio）: break ABC v3 and TSC-4 with weak keys, find a differential characteristic in the key initialization process of CryptMT v3 with probability 1, and break Grain vl with weak Key-Ⅳs.1. Break ABC v3 with weak keysABC v3 is a synchronous stream cipher with two previous versions v1 and v2. Its key length is 128 bits, and it is one of the fastest algorithms among 34 candidates. In 2005, Berbain, Gilbert and Khazaei found that the size of LFSR is so short that ABC v1 could be broken by divide-and-conquer attack. The weakness of ABC v1 was eliminated by increasing the size of LFSR in ABC v2. However, at SAC 2006, Wu and Preneel found that there exists weak keys in ABC v2, which result in a key recovery attack on ABC v2. After twisting the key initialization process and eliminating Wu-Preneel weak keys, ABC v3 can resist all previous attacks.The cipher body of ABC family consists of three components: a LFSR （component A）, a T-function （component B） and a 32×32 S-box （component C） constructed by knapsack function. The keystream byte is the Modular Addition result of the least 32-bit word of component A and the output of component C. The number of terms in the feedback polyonmial of LFSR is 3, which improve the performance, however incurs fast correlation attack. In order to mask the linearity of the LFSR, the designers employ several nonlinear operations such as T-function, S-box, and Modular Addition, etc. Especially, the S-box constructed by knapsack function enhances the difficulty to cryptanalyze ABC v3. In order to break ABC v3 with weak keys, we find the linear approximations of the non-linear Modular Addition first, and then employ it to find the weakness of the kernel component S-box, which leads to recovery of the LFSR internal state.（1） Prove the probability advantage of two linear approximationsFrom the Modular Addition of ABC v3, we explore one linear approximation of Modular Addition with two integers. We find a type of linear approximation with high probability, and derive its concrete value by classification and mathematical induction. The probability is as follows:where, y, c, x are n-bit integers, y = c + x （mod 2ⁿ）, F（y, m） =（?）,δ_i（y） denote the ith least significant bit of integer y, and 1≤m≤n. That is the first type of linear expression.There exists another linear expression which reflects the linearity among the carry bits in three Modular Addition equations. The correlation among equations makes the problem more complex so that Wu and Preneel found the probability advantage of the second linear expression by experiment, and don’t present strict mathematical proof. We prove the probability by classification and mathematical induction, and presented a generalized version. One of the results is as follows:where, a_i,b_i,c_i are three n-bit integers, c_i,n=δ_n（a_i+b_i）, 1≤i≤3, and n≥2. Two linear expressions with probability advantage reflect the linearity of the nonlinear operation Modular Addition. Taking advantage of the two linear expressions, we derive a large amount （?）f weak keys and retrieve all the ABC main keys successively. Because Modular Addition and XOR operations are widely used in the design of symmetric ciphers, we believe that these types of linear expressions with probability advantages not only can be used to analyze some other symmetric ciphers, but also are important factors in the design of secure symmetric ciphers.（2） Find new type of weak keysFirstly, We prove that there is almost no bias which can be utilized to apply a fast correlation attack on ABC v3, and the weak keys defined by Wu and Preneel are eliminated. Consequently, ABC v3 can resist against all the previous attacks. Then, the difficulty and emphasis is to find new type of weak keys. The core component of ABC v3 is a 32×32 S-box based on a high non-linear knapsack function. Theoretically, the knapsack problem is NP problem which is hard to solve by known theories. Moreover, because of the limitation of the memory and computation, it is hard to search directly for weak keys with higher probability bias. After deep investigations, we find a type of weak S-box with which the output of S-box can leak the linearity of LFSR in component A, and provide a fast searching algorithm to find such weak S-boxes. The core of the searching algorithm is to construct a non-linear transformation with specific characteristic, which reduces the search space. As a result, the size of search space decreases by about 14263 times. We define the keys result in weak S-boxes as new type of weak keys. By experiments, we show that the total number of weak keys is about 2^103.71 for ABC v3.（3） Distinguish and recover weak keys The first step is to distinguish weak keys. Utilizing linear expressions with probability advantages and the linearity property of LFSR, and approximating the bi-nomial distribution with the normal distribution, we establish a distinguisher to identify the weak keys of ABC v3, and conclude that the weak keys can be successfully identified. Since one weak key exists among 2^24.29 keys, the complexity is about 2^36.62 keystream outputs and 2^41.48 XOR operations. The second step is to recover weak keys. Firstly, the initial value of component A （LFSR） is recovered by exploiting the strong correlation between the LFSR and the keystream. Secondly, the internal state of component B can be recovered from the property of T-functions. Thirdly, by a divide-and-conquer attack, we obtain the internal state of component C step by step. The total complexity of recovery all the internal states （three components A, B, and C） of ABC v3 is about 2^36.05 keystream words and 2^50.56 XOR operations.To sum up, the number of new type of weak keys is up to 2^103.71 in ABC v3. Recovering the internal state under a weak key requires 2^36.05 keystream words and 2^50.56 operations. The attack can be applied to ABC v1 and v2 with the same complexities as that of ABC v3. However, the number of weak keys for ABC v1 and ABC v2 decreases to 2⁹⁷+2^95.19. It revealed that ABC v3 incurs more weak keys than that of ABC v1 and v2. Hence, ABC v3 is still insecure.3. Break TSC-4 with weak keysSince T-function is introduced into cryptology by Klimov and Shamir, numbers of stream ciphers based on T-function have appeared, such as Klimov-Shamir algorithms, TSC-1, TSC-2 and TSC-3, etc. However, all of them were broken. TSC-4 is a T-function based stream cipher with 80-bit key, designed by Moon et al., and enters the second eSTREAM evaluation phase. At Indocrypt 2006, Fischer, Meier and Berbain et al. found that there exists some non-randomness in the key initialization process of TSC-4. Because the bias can not be found in the keystream output, the non-randomness could not be applied to attack TSC-4.TSC-4 consists of three components: two symmetric T-function structures X and Y, and a filter non-linear function whose input is obtained from X and Y and output is the keystream. Because the T-function employs several non-linear logical operations, chosen control operation and S-box, etc, its avalanche and diffusion effect are very strong, which is difficult to construct mathematical model. We combine the differential attack and divide-and-conquer attack, take experiments as basement, explore mathematical model from experiment data, and conclude the characteristic of weak keys with which break TSC-4 finally.（1） Construct two special differential characteristics in the key initializationThe key initialization of TSC-4 proceed as: Key and IV is loaded into X and Y first, and then 8 rounds iteration are performed. Each iterative round consists of three steps: step 1 mixes the information of X and Y into an output byte, step 2 is to rotation shift X and Y by one line, and step 3 confuse the output byte obtained in the first step with X and Y. We observe that the interaction of X and Y is caused by step 1 and step 3. If the differential of Y is non-zero, and both the differential of X and the output byte in step 1 are zeroes, the non-zero differential of Y can not be diffused to X, i.e., the differential of X will always be zero. Consequently, we can cut off the connection between X and Y in this way. Based on that, we can construct two special differential characteristicsΩ_X andΩ_Y If the differential characteristicΩ_Y holds, then the differential characteristicΩ_X holds with probability 1. The following is to find in which caseΩ_Y occurs with high probability.（2） Find weak keysFirstly, select K and IV randomly and perform the key initialization process. IfΩ_Y holds, reserve K and IV and corresponding X and Y. Secondly, employχ² test to Y by each column, and put non-random distributions. Thirdly, find linear expression about X and Y with high probability advantage based on the obtained non-random distributions. Fourthly, according to the Key/IV loading process, get the linear expression about K and IV by substitution of linear expression about X and Y. Fifthly, summarize linear expressions, define E_k as weak keys space which results inΩ_Y occurring with high probability and E_IV as special IV space. Sixthly, randomly select K and IV from spaces E_K and E_IV respectively, perform the key initialization process over again, and calculate the occurrence probabilityΩ_Y Finally, we conclude that there are 2⁷² weak keys among 2⁸⁰ keys. If chosen IV pair falls into E_IV, the occurrence probability ofΩ_Y is about 2^-15.40 for wgak keys and about 2^-24.74 for strong keys.（3） Identify and recover weak keysAlthough two special differential characteristics in the state initialization are constructed and weak keys are defined, the internal states are unknown except for the keystream output bits. Consequently, we need to construct a distinguisher which transfers the differential bias of the internal states to the keystream output bits. By experiments, we obtain the distinguisher successfully. At last, we conclude that there are about 2⁷² weak keys among the total 2⁸⁰ keys, and to recover 8 bits of a weak key needs about 2^40.53 chosen IV pairs. After that, we can recover the other 72 key bits by an exhaustive attack.As a result, TSC-4 is insecure. We reveal that there exists other types of weak keys and other attacks, such as related key attack, etc.3. Find a differential characteristic in the key initialization process of CryptMT v3 with probability 1CryptMT v3 is a stream cipher submitted to eSTREAM Project, and enters the third evaluation phase with 128-bit key. Because of employing multiplication operation etc, no attack has been published until now. Consider the key initialization process of CryptMT v3 as a function generator, i.e., a function family F={f_K:{0,1}¹²⁸→{0,1}^m} indexed by a key K randomly chosen from {0,1}^k. By differential attack, we construct a distinguisher A^f_K, which allows to distinguish f_K from a random function with probability 1. The result indicates that for each key K, f_K is not a PRF, and maybe result in potential attacks on CryptMT v3.4. Break Grain v1 with weak Key-IVsGrain v1 is one of the seven portfolios, Grain vO is its previous version, and Grain-128 is its variant version. In 2005, Khazaei, Hassanzadeh and Kiaei presented a distinguishing attack on Grain v0. At FSE 2006, Berbain, Gilbert and Maximov broken Grain v0 by a key recovery attack. Based on the slide resynchronization attack, （?）. K（?）k presented a related key attack on Grain v1. Then two research groups extended the attack and proposed related-key chosen IV attacks on Grain-v1 and Grain-128. All the attacks on Grain-v1 and Grain-128 are in the related-key settings. The algebraic attacks on two algorithms were proposed by Afzal and Masood, however, the total time complexity exceeds the exhaustive attack. The final eSTREAM evaluation report considers that Grain v1/128 is secure, but the key initialization should be modified.The cipher body of Grain family consists of three parts, a LFSR, a NFSR, and a nonlinear filter. For Grain v0/v1/128, the secret key is 80/80/128 bits, and the IV is specified to be 64/64/96 bits, respectively. Denote the size of key K as k bits, and the size of IV as / bits. There are 2^k+l different keystream sequences totally corresponding to all different （K,IV） pairs. It is necessary to guarantee that each sequence possesses perfect random characteristic among 2^k+l sequences for secure stream ciphers. We break Grain v1 with weak Key-IVs.（1） The existence of weak Key-IVsIt is obvious that if the initial states of the LFSR are all zeros after the initialization process, NFSR is the only active component of the cipher body. Consequently, if the （K,IV） pair results in the all zero LFSR state, we define the （K,IV） pair as a weak Key-IV. We present an algorithm to search for the weak Key-IVs, and an example is illustrated for each version. Suppose that the internal state with 2k bits of the NFSR and LFSR is uniformly distributed after the key initialization, there are 2^l weak Key-IVs among total 2^k+l Key-IVs for each Grain version.（2） Distinguish weak Key-IVsWe apply the second Walsh spectra to the nonlinear feedback function of NFSR, and obtain its best linear approximation. Utilizing the linear approximation lemma, we construct one distinguisher to distinguish the weak Key-IVs for each Grain version. We can distinguish a weak Key-IV from 2⁸⁰/2⁸⁰/2¹²⁸ Key-IVs with successful probability 99.977%, the data complexity is about 2^17.8/2^49.4/2^91.8 keystream bits, and the computational complexity is about 2^21.1/2^52.7/2¹¹⁰ XOR operations for Grain v0/ v1/128, respectively. （3） Recover weak Key-IVsThe internal state of Grain family consists of k bits from LFSR and NFSR, re-spectively. When the cipher generates keystream bits, LFSR works indepen-dently, NFSR is driven by its nonlinear feedback polynomial and the output of LFSR, and the keystream bits are generated by both LFSR and NFSR. Thus, the nonlinear equations could be obtained from the keystream bits and the internal state bits of LFSR and NFSR. For weak Key-IVs, utilizing the algebraic attack presented by Afzal and Masood, we conclude that the known weak Key-IVs of Grain v1 can be broken with 2^30.7 operations and 150 keystream bits, and the known weak Key-IVs of Grain-128 can be broken with 2^93.8 operations and 100 keystream bits. The result of Grain v0 is similar to that of Grain v1.As a result, to break a weak Key-IV of Grain v0/v1/128,2^17.8/2^49.4/2^91.8 keystream bits and 2^30.7/2^52.7/2¹¹⁰ XOR operations are required, respectively. Our results show that there exists a weakness in the key initialization process of Grain vl and Grain-128, and the key initialization process should be modified.更多还原