eSTREAM序列密码候选算法的安全性分析
|
摘要
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 v3
ABC 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~(32)加运算后作为密钥流输出字。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~n),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~(128)个密钥中存在约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~(97)+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的列为单位进行χ~2检验,检测出非随机分布。第三,以检测出的非随机分布为研究对象,运用卡诺图技术,归纳总结出高概率线性表达式。第四,按照K和IV的载入方式代换关于X和Y的高概率线性表达式,得到关于K和IV的表达式。第五,合并各关于K和IV的线性表达式,定义产生高概率Ω_Y的弱密钥空间E_K和特殊IV空间E_(IV)。第六,按照空间E_K和E_(IV)重新运行密钥初始化过程,得到Ω_Y产生的概率。最后,可得对于80比特的密钥,TSC-4弱密钥的个数约为2~(72)个。当选择的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}~(128)→{0,1}~(19968)}。通过差分分析,本文构造出区分器A~(f_K),可以把f_K与随机函数以概率1区分出来,因而f_K不是随机函数。分析结果表明,CryptMT v3的密钥初始化过程存在一定的弱点,可能被攻击。
4.弱Key-Ⅳ条件下破解Grain v1
Grain 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~(80)/2~(80)/2~(128)个Key-Ⅳ中以99.977%的成功率区分出1个弱Key-Ⅳ各需要2~(17.8)/2~(49.4)/2~(91.8)个密钥流比特和2~(21.1)/2~(52.7)/2~(110)次运算。
(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~(110)次异或运算。虽然弱Key-Ⅳ出现的概率很低,但可以说明这两个算法的密钥初始化过程存在安全问题,有必要进行修改。
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 keys
ABC 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 approximations
From 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~n), 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 keys
Firstly, 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~(97)+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 keys
Since 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 initialization
The 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 keys
Firstly, 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χ~2 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~(72) weak keys among 2~(80) 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 keys
Although 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~(72) weak keys among the total 2~(80) 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 1
CryptMT 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}~(128)→{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-IVs
Grain 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-IVs
It 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-IVs
We 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~(80)/2~(80)/2~(128) 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~(110) XOR operations for Grain v0/ v1/128, respectively.
(3) Recover weak Key-IVs
The 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~(110) 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.
在导师的精心指导下,本论文主要对eSTREAM工程的四个候选密码算法ABC v3(第二阶段)、TSC-4(第二阶段)、CryptMT v3(第三阶段)和Grainv1(最终获选)进行了安全性分析:在弱密钥条件下,破解了ABC v3和TSC-4;发现CryptMT v3密钥初始化过程存在概率为1的差分特征:对Grain v1进行了弱Key-Ⅳ攻击。
1.弱密钥条件下破解ABC v3
ABC 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~(32)加运算后作为密钥流输出字。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~n),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~(128)个密钥中存在约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~(97)+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的列为单位进行χ~2检验,检测出非随机分布。第三,以检测出的非随机分布为研究对象,运用卡诺图技术,归纳总结出高概率线性表达式。第四,按照K和IV的载入方式代换关于X和Y的高概率线性表达式,得到关于K和IV的表达式。第五,合并各关于K和IV的线性表达式,定义产生高概率Ω_Y的弱密钥空间E_K和特殊IV空间E_(IV)。第六,按照空间E_K和E_(IV)重新运行密钥初始化过程,得到Ω_Y产生的概率。最后,可得对于80比特的密钥,TSC-4弱密钥的个数约为2~(72)个。当选择的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}~(128)→{0,1}~(19968)}。通过差分分析,本文构造出区分器A~(f_K),可以把f_K与随机函数以概率1区分出来,因而f_K不是随机函数。分析结果表明,CryptMT v3的密钥初始化过程存在一定的弱点,可能被攻击。
4.弱Key-Ⅳ条件下破解Grain v1
Grain 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~(80)/2~(80)/2~(128)个Key-Ⅳ中以99.977%的成功率区分出1个弱Key-Ⅳ各需要2~(17.8)/2~(49.4)/2~(91.8)个密钥流比特和2~(21.1)/2~(52.7)/2~(110)次运算。
(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~(110)次异或运算。虽然弱Key-Ⅳ出现的概率很低,但可以说明这两个算法的密钥初始化过程存在安全问题,有必要进行修改。
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 keys
ABC 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 approximations
From 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~n), 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 keys
Firstly, 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~(97)+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 keys
Since 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 initialization
The 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 keys
Firstly, 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χ~2 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~(72) weak keys among 2~(80) 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 keys
Although 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~(72) weak keys among the total 2~(80) 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 1
CryptMT 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}~(128)→{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-IVs
Grain 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-IVs
It 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-IVs
We 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~(80)/2~(80)/2~(128) 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~(110) XOR operations for Grain v0/ v1/128, respectively.
(3) Recover weak Key-IVs
The 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~(110) 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.
引文
[1] V. Anashin, A. Bogdanov, I. Kizhvatov, S. Kumar, ABC: A New Fast Flexible Stream Cipher, Available at http://www.ecrypt.eu.org/stream/ciphers/abc/abc.pdf.
[2] V. Anashin, A. Bogdanov, I. Kizhvatov, and S. Kumar. ABC: a New Fast Flexible Stream Cipher Specification, Version 3. Available at http://www.ecrypt.eu.org/stream/abcp2.html.
[3] V. Anashin, A. Bogdanov, I. Kizhvatov, Increasing the ABC Stream Cipher Period, Available at http://www.ecrypt.eu.org/stream/papersdir/050.pdf, Also available at http://crypto.rsuh.ru/papers/abc-spec-v2.pdf.
[4] F. Arnault, T. P. Berger and C. Lauradoux. Update on F-FCSR Stream Cipher. Available at http://www.ecrypt.eu.org/stream/ffcsrp3.html.
[5] M. Afzal, and A. Masood. Algebraic Cryptanalysis of A NLFSR Based Stream Cipher.ICTTA 2008,2008.
[6] R. G. Brown. DieHarder: A Random Number Test Suite. Available at http://www.phy.duke.edu/rgb/General/dieharder.php.
[7] C. Berbain, O. Billet, A. Canteaut, N. Courtois, B. Debraize, H. Gilbert, L. Goubin, A.Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin and H. Sibert. Decim v2.Available at http://www.ecrypt.eu.org/stream/decimp3.html.
[8] C. Berbain, O. Billet, A. Canteaut, N. Courtois, H. Gilbert, L. Goubin, A. Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin and H. Sibert. Sosemanuk: a fast software-oriented stream cipher. http://www.ecrypt.eu.org/stream/sosemanukp3.html.
[9] D. Brumley and D. Boneh. Remote Timing Attacks are Practical. In Proceedings of the 12th USENIX Security Symposium, August 2003
[10] S. Babbage, C. Cid, N. Pramstaller and H. Raddum. An Analysis of the Hermes8 Stream Ciphers. ACISP 2007, LNCS 4586, pp. 1-10, Springer, 2007.
[11] S. Babbage and M. Dodd. The stream cipher MICKEY 2.0. Available at http://www.ecrypt.eu.org/stream/mickeyp3.html.
[12] C. Berbain, H. Gilbert, and A. Maximov. Cryptanalysis of Grain. In M. J. B. Robshaw Editor, FSE 2006, LNCS 4047, pp. 15-29,2006.
[13] C. Berbain and H. Gilbert. Cryptanalysis of ABC. Available at http://www.ecrypt.eu.org/stream/papersdir/2005/048.pdf.
[14] A. Braeken, J. Lano, N. Mentens, B. Preneel and I. Verbauwhede. Snksspecication and-sourcecode. Available at http://www.ecrypt.eu.org/stream/sfinks.html.
[15] Y. Borissov, S. Nikova, B. Preneel and J. Vandewalle. On a Resynchronization Weakness in a Class of Combiners with Memory. In Security in Communication Networks - SCN 2002,LNCS 2576, pp. 164-173, Springer, 2002.
[16] A. Biryukov and A. Shamir. Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers, Asiacrypt 2000, LNCS 1976, pp. 1-13, Springer, 2000.
[17] E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems. In Advances in Cryptology - CRYPTO'90, LNCS 537, pages 221. Springer, 1991.
[18] E. Biham and J. Seberry. Py: A fast and secure stream cipher using rolling arrays. Available at http://www.ecrypt.eu.org/stream/pyp2.html.
[19] M. Boesgaard, M. Vesterager, T. Christensen and E. Zenner. The Stream Cipher Rabbit. Available at http://www.ecrypt.eu.org/stream/rabbitp3.html.
[20] M. Boesgaard, M. Vesterager, T. Pedersen and O. Scavenius. Rabbit: A New High Performance Stream Cipher. Fast Software Encryption - FSE 2003, LNCS 2887, pages 226- 244,Springer, 2004.
[21] S. Babbage. A Space/Time Tradeoff in Exhaustive Search Attacks on Stream Ciphers. European Convention on Security and Detection, IEE Conference publication, No. 408, May 1995.
[23] D. Bernstein. Cache-Timing Attacks on AES (2005),http://cr.yp.to./antiforgery/cachetiming-20050414.pdf.
[23] D. J. Bernstein. Salsa20/8 and Salsa20/12. Available at http://www.ecrypt.eu.org/stream/salsa20p3.html.
[24] E. Biham. On Matsui's linear cryptanalysis. In Advances in Cryptology - EUROCRYPT'94,LNCS 950, pages 341-355. Springer-Verlag, 1995.
[25] A. Biryukov . A new 128 bit key stream cipher: LEX. Available at http://www.ecrypt.eu.org/stream/lexp3.html.
[26] T. Brigham. TRBDK3 YAEA: High Security, Synchronous Stream Cipher. Available at http://www.ecrypt.eu.org/stream/trbdk3.html.
[27] B. Buchberger, Grobner Base: An Algorithm Method in Polynomial Ideal Theory, Multi-deimension System Theory. Dordrecht, pp. 184-232,1985.
[28] C. Cid, H. Gilbert, and T. Johansson. Cryptanalysis of Pomaranch. IEE Information Security, 153(2):51-53, June 2006.
[29] C. Berbain and H. Gilbert. On the Security of IV Dependent Stream Ciphers. In A.Biryukov,editor, FSE 2007, LNCS 4593, pp.254-273. Springer, 2007.
[30] V. V. Chepyzhov, T. Johansson and B. Smeets. A Simple Algorithm for Fast Correlation Attacks on Stream Ciphers. In Fast Software Encryption - FSE 2000, LNCS 1978, pp. 181-195, Springer, 2000.
[31] C. D. Canniere, (?). K(?)k, and B. Preneel. Analysis of Grain' s Initialization Algorithm. In S. Vaudenay Editor, AFRICACRYPT 2008, LNCS 5023, pp. 276-289, 2008.
[32] N. Courtois, A. Klimov, J. Patarin, and A. Shamir. Efficient algorithms for solving overdeined systems of multivariate polynomial equations. In B. Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, LNCS 1807, pp. 392-407. Springer, 2000.
[33] C. Cid and G. Leurent. An analysis of the XSL algorithm. In B. Roy, editor, Advances in Cryptology - ASIACRYPT 2004, LNCS 3788 , pp. 333-352. Springer, 2005.
[34] J. Y. Cho and J. Pieprzyk. Crossword Puzzle Attack on NLS. Selected Areas in Cryptography - SAC 2006, LNCS 4356, pp. 249-265, Springer, 2007.
[35] C. D. Canne and B. Preneel. Trivium Specifications. Available at http://www.ecrypt.eu.org/stream/triviump3.html.
[36] N. Courtois and J. Pieprzyk. Cryptanalysis of block ciphers with overdefined systems of equations. In Y. Zheng, editor, Advances in Cryptology - ASIACRYPT 2002, LNCS 2501,pp. 267-287. Springer, 2002.
[37] A. Canteaut and M. Trabbia. Improved Fast Correlation Attacks Using Parity Check Equations of Weight 4 and 5." In Advances in Cryptology - EUROCRYPT 2000, LNCS 1807,pp. 573-588, Springer, 2000.
[38] N. T. Courtois. Cryptanalysis of Sfinks. Information Security and Cryptology - ICISC 2005,LNCS 3935, pp. 261-269, Springer, 2006.
[39] LAN Crypto. LAN Crypto Submission to the ECRYPT Stream Cipher Project (yamb).Available at http://www.ecrypt.eu.org/stream/yamb.html.
[40] E. Dawson, K. Chen, M. Henricksen, W. Millan, L. Simpson, H. Lee,S. Moon. Dragon: A Fast Word Based Stream Cipher. Available at http://www.ecrypt.eu.org/stream/dragonp3.html.
[41] D. Moon, D. Kwon, D. Han, etc., T-function Based Stream Cipher TSC-4, Available at http://www.ecrypt.eu.org/stream/p2ciphers/tsc4/tsc4_p2.pdf.
[42] J. Daemen, R. Govaerts and J. Vandewalle. Resynchronization Weakness in Synchronous Stream Ciphers. In Advances in Cryptology-EUROCRYPT' 93, LNCS 765, pp. 159-167,Springer, 1994.
[43] J. Daemen, R. Govaerts, and J. Vandewalle. Weak keys for IDEA, CRYPTO '93, pp. 224-231, 1993.
[44] O. Dunkelman, A. Hecht, C. Gressel, R. Granot and G. Vago. Zk-Crypt. Available at http://www.ecrypt.eu.org/stream/zkcryptp2.html.
[45] P. Delaunay and A. Joux. Yet Another Attack on Vest. Progress in Cryptology -AFRICACRYPT 2008, LNCS 5023, pp. 221-235, Springer, 2008.
[46] O. Dunkelman and N. Keller. A New Attack on the LEX Stream Cipher. Progress in Cryp-tology - AFRICACRYPT 2008, LNCS 5023, pp. 539-556, Springer, 2008.
[47] J. Daemen and P. Kitsos. The Self-synchronizing Stream Cipher Moustique. Available at http://www.ecrypt.eu.org/stream/mosquitop3.html.
[48] J. Daemen, J. Lano, B. Preneel. Chosen Ciphertext Attack on SSS. SASC 2006 - Stream Ciphers Revisited, 2006.
[49] C. Diem. The XL-algorithm and a conjecture from commutative algebra. In P. Lee, editor,Advances in Cryptology - ASIACRYPT 2004, LNCS 3329, pp. 323-337. Springer, 2004.
[50] ECRYPT. eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932. Available at http://www.ecrypt.eu.org/stream/.
[51] H. Englund, M. Hell and T. Johansson. Two General Attacks on Pomaranch-like Keystream Generators. Fast Software Encryption - FSE 2007, LNCS 4593, pp. 274-289, Springer,2007.
[52] eSTREAM. Call for Stream Cipher Primitives. Available at http://www.ecrypt.eu.org/stream/call/.
[53] eSTREAM. End of Phase 3 of the eSTREAM Projcet. Available at http://www.ecrypt.eu.org/stream/endofphase3.html.
[54] eSTREAM.The eSTREAM Portfolio.Available at http://www.ecrypt.eu.org/stream/portfolio.html.
[55] eSTREAM. Available at http://www.ecrypt.eu.org/stream/.
[56] J. C. Faugere, A New Efficient Algorithm for Computing Grobner Bases (F4), Journal of Pure and Applied Algebra. Vol.139, NO.1-3, pp. 61-88, June,1999.
[57] J. C. Faugere, A New Efficient Algorithm for Computing Grobner Bases without Reduction to Zero (F5), International Sysmposium on Symbolic and Algebraic Computation-ISSAC'02, pp. 75-83, ACM Press, 2002.
[58] FIPS, Guidelines for Implementing and Using the NBS Data Encryption Standard, F1PS-PUB 74, http://www.itl.nist.gov/fipspubs/fip74.html.
[59] S. Fluhere, I. Mantin and A. Shamir. Weaknesses in the Key Scheduling Algorithm of RC4.Eighth Annual Workshop on Selected Areas in Cryptography - SAC 2001, LNCS 2259, pp.1-24, Springer-Verlag, 2001.
[60] F. Muller and T. Peyrin, Linear Cryptanalysis of the TSC Family of Stream Ciphers, ASIACRYPT 2005, LNCS 3788, pp.373-394,2005.
[61] F. Muller and T. Peyrin, Linear Cryptanalysis of TSC Stream Ciphers - Applications to the ECRYPT Proposal TSC-3, Available at http://www.ecrypt.eu.org/stream/papersdir/042.ps.
[62] B. Gammel, R. Gottfert and O. Kniffler. Achterbahn-128/80. Available at http://www.ecrypt.eu.org/strearn/achterbahnp2.html.
[63] D. Gligoroski, S. Markovski, L. Kocarev and M. Gusev. Edon80. Available at http://www.ecrypt.eu.org/strearn/edon80p3.html.
[64] S. Goldwasser, S. Micali and C. Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Comput., Vol. 18, No. 1,1989.
[66] J. D. Golic, G. Morgari. On the Resynchronization Attack. In Fast Software Encryption -FSE 2003, LNCS 2887, pp. 100-110, Springer, 2003.
[66] S. Goldwasser and S. Micali. Probabilistic Enryption and How to Play Mental Poker Keeping Secret All Partial Information. 14th ACM STOC, pp. 365-377,1982.
[67] G. Gong and Y. Nawaz. The WG Stream Cipher. Available at http://www.ecrypt.eu.org/strearn/wgp2.html.
[68] J. D. Golic. Cryptanalysis of Alleged A5 Stream Cipher, Eurocrypt'97, LNCS 1233, pp.239-255, Springer, 1997.
[69] H. Wu and B. Preneel. Cryptanalysis of the stream cipher DECIM. In M. Robshaw, editor,FSE 2006, LNCS 4047, pages 30 - 40. Springer, 2006.
[70] H. Wu and B. Preneel. Resynchronization attacks on WG and LEX. In M. Robshaw, editor,FSE 2006, LNCS 4047, pages 422 - 432. Springer, 2006.
[71] M. Hell and T. Johansson. A Key Recovery Attack on Edon80. Advances in Cryptology -ASIACRYPT 2007, LNCS 4833, pp. 568-581, Springer, 2007.
[72] M. Hell and T. Johansson. Breaking the F-FCSR-H Stream Cipher in Real Time. Advances in Cryptology - ASIACRYPT 2008, LNCS 5350, pp. 557-569, Springer, 2008.
[73] M. Hell, T. Johansson and W. Meier. Grain - A Stream Cipher for Constrained Environments. Available at http://www.ecrypt.eu.org/stream/ciphers/grain/grain.pdf.
[74] M. Hell, T. Johansson, A. Maximov, and W. Meier. The Grain Family of Stream Ciphers. In M. Robshaw and O. Billet Editors, New Stream Cipher Designs, LNCS 4986, pp. 179-190,2008.
[75] M. Hell, T. Johansson and W. Meier. Grain - A Stream Cipher for Constrained Environments(New Version). Available at http://www.ecrypt.eu.org/stream/grainp3.html.
[76] M. Hell, T. Johansson. Cryptanalysis of Achterbahn-Version 2. Selected Areas in Cryptography - SAC 2006, LNCS 4356, pp. 45-55, Springer, 2007.
[77] J. Hong, D. H. Lee, Y. Yeom, D. Han and S. Chee. T-function based streamcipher TSC-4.Available at http://www.ecrypt.eu.org/stream/tsc3p2.html.
[78] J. H(?)stad and M. Naslund. A New Version of the Stream Cipher Polar Bear. Available at http://www.ecrypt.eu.org/stream/polarbearp2.html.
[79] X. L. Huang and C. K. Wu. Cryptanalysis of Achterbahn-Version 1 and - Version 2. Journal of Computer Science and Technology, vol. 22, No. 3, pp. 469-475, Springer, 2007.
[80] M. E. Hellman. A Cryptanalytic Time-Memory Trade-Off. IEEE Transactions on Information Theory, vol. IT-26, No. 4, pp. 401-406, July 1980.
[81] J. Hong, D. H. Lee, Y. Yeom, D. Han, S. Chee, T-function Based Stream Cipher TSC-3,Available at http://www.ecrypt.eu.org/stream/ciphers/tsc3/tsc3.pdf.
[82] J. Hong, D. H. Lee, Y. Yeom, and D. Han, New Class of Single Cycle T-functions, FSE 2005, LNCS 3557, pp.68-82,2005.
[83] J. Johansson and F. Jonsson. Improved Fast Correlation Attacks on Stream Ciphers via Convolutional Codes. In Advances in Cryptology - EUROCRYPT' 99, LNCS 1592, pp.347-362, Springer, 1999.
[84] T. Johansson and F. Jonsson. Fast Correlation Attacks Based on Turbo Code Techniques. In Advances in Cryptology - CRYPTO' 99, LNCS 1666, pp. 181-197, Springer-Verlag, 1999.
[85] T. Johansson and F. Jonsson. Fast Correlation Attacks through Reconstruction of Linear Polynomials. In Advances in Cryptology - CRYPTO 2000, LNCS 1880, pp. 300-315,Springer, 2000.
[86] C. Jansen and A. Kolosha. Cascade Jump Controlled Sequence Generator and Pomaranch Stream Cipher (Version 3). Available at http://www.ecrypt.eu.org/stream/pomaranchp2.hrml.
[87] T. Johansson, W. Meier and F. Muller. Cryptanalysis of Achterbahn. Fast Software Encryption - FSE 2006, LNCS 4047, pp. 1-14, Springer, 2006.
[88] J. Mitra and P. Sarkar, Time-memory Trade-Off Attacks on Multiplications and T-functions,AS1ACRYPT 2004, LNCS 3329, pp. 468-482, Springer, 2004.
[89] A. Joux and J. Reinhard. Overtaking VEST. Fast Software Encryption - FSE 2007, LNCS 4593, pp. 58-72, Springer, 2007.
[90] S. Khazaei. Divide and Conquer Attack on ABC Stream Cipher. Available at:http://www.ecrypt.eu.org/stream/papersdir/052.pdf.
[91] S. Khazaei, Divide and Conquer Attack on ABC Stream Cipher, Available at:http://www.ecrypt.eu.org/stream/papersdir/052.pdf.
[92] S. Khazaei, M. Hassanzadeh and M.Kiaei. Distinguishing Attack on Grain.ECRYPT Stream Cipher Project Report 2005/071, 2005. Available at http://www.ecrypt.eu.org/stream.
[93] S. Khazaei and M. Kiaei. Distinguishing attack on the ABC v.1 and v.2. eSTREAM,ECRYPT Stream Cipher Project, Report 2005/061, 2005.
[94] S. Kunzli and W. Meier. Distinguishing Attack on MAG. Available at http://www.ecrypt.eu.org/stream/papersdir/053.pdf.
[95] E. Kasper, V. Rijmen, T. E. Bjφrstad, C. Rechberger, M. Robshaw and G. Sekar. Correlated Keystreams in Moustique. Progress in Cryptology - AFRICACRYPT 2008, LNCS 5023, pp. 246-257, Springer, 2008.
[96] A. Klimov and A. Shamir, A New Class of Invertible Mappings, CHES 2002, LNCS 2523, pp.470-483,2003.
[97] A. Klimov and A. Shamir, Cryptographic Application of T-functions, SAC 2003, LNCS 3006, pp.248-261,2004.
[98] A. Klimov and A. Shamir, New Cryptographic Primitives Based on Multiword T-functions, FSE 2004, LNCS 3017, pp.1-15,2004.
[99] o. Kücük, Slide Resynchronization Attack on the Initialization of Grain 1.0. ECRYPT Stream Cipher Project Report 2006/044, 2006. Available at http://www.ecrypt.eu.org/stream.
[100] U. Kaiser. Hermes Stream Cipher. Available at http://www.ecrypt.eu.org/stream/hermes8p2.html.
[101] P. C. Kocher. Timing attacks on implementation of Diffie-Hellman, RSA, DSS, and Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104-113. Springer, 1996.
[102] S. K. Langford and M. E. Hellman. Differential-linear cryptanalysis. In Advances in Cryptology - CRYPTO'94, LNCS 839, pp. 17-25. Springer, 1994.
[103] Y. Lee, K. Jeong, J. Sung, and S. Hong. Related-Key Chosen IV Attacks on Grain-vl and Grain-128. In Y. Mu, W. Susilo, and J. Seberry (Eds.), ACISP 2008, LNCS 5107, pp. 321-335, 2008.
[104] A. P. Li. A new stream cipher DICING - An update for phase 2 of eSTREAM. Available at http://www.ecrypt.eu.org/stream/dicingp2.html.
[105] M. Mihaljevic, M.P.C. Fossorier and H. Imai. A Low-Complexity and High Performance Algorithm for Fast Correlation Attack. In Fast Software Encryption - FSE 2000, pp. 196-212, Springer, 2000.
[106] M. Matsumoto, H. Mariko, T. Nishimura and M. Saito. CryptMT stream cipher version 3. Available at http://www.ecrypt.eu.org/stream/cryptmtp3.html.
[107] A. Menezes, P. v. Oorschot, and S. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997. ISBN 0-8493-8523-7.
[108] W. Meier and O. Staffelbach. Fast Correlation Attacks on Certain Stream Ciphers. Journal of Cryptography, 1(3):159-176,1989.
[109] Magma Computational Algebra System available at http://magma.maths.usyd.edu.au/.
[110] M. Matsui. Linear cryptanalysis method for DES cipher. In Advance in Cryptology - EU-ROCRYPT'93, LNCS 765, pp. 386-397. Springer, 1994.
[111] A. Maximov. A New Stream Cipher "Mir-1". Available at http://www,ecrypt.eu.org/stream/mirl .html.
[112] T. Moreau. The Frogbit cipher, a data integrity algorithm. Available at http://www.ecrypt.eu.org/stream/frogbit.html.
[113] G. Marsaglia. The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness.
[114] M. Naya-Plasencia. Cryptanalysis of Achterbahn-128/80. Fast Software Encryption - FSE 2007, LNCS 4593, pp. 73-86, Springer, 2007.
[115] M. Naya-Plasencia. Cryptanalysis of Achterbahn-128/80 with a New Keystream Limitation. WEWoRC 2007, LNCS 4945, pp. 142-152, Springer, 2008.
[116] NESS1E. New European Schemes for Signatures, Integrity, and Encryption. Available at http://www.cryptonessie.org.
[117] NIST Statistical Test Suite. Available at http://csrc.nist.gov/mg/.
[118] S. O'Neil, B. Gittins and H. Landman. VEST ciphers. Available at http://www.ecrypt.eu.org/stream/vestp2.html.
[119] S. Paul and B. Preneel. On the (In)security of Stream Ciphers Based on Arrays and Modular Addition. Advances in Cryptology - ASIACRYPT 2006, LNCS 4284, pp. 69-83, Springer, 2007.
[120] G. Rose, P. Hawkes, M. Paddon and M. W. de Vries . Primitive Specification for NLSv2. Available at http://www.ecrypt.eu.org/stream/nlsp3.html.
[121] G. Rose, P. Hawkes, M. Paddon and M. W. de Vries. Primitive Specification for SSS. Available at http://www.ecrypt.eu.org/stream/sss.html.
[122] R. A. Rueppel. Stream Ciphers. In Gustavus J. Simmons, editor, Contemporary Cryptology: The Science of Information Integrity, chapter 2, pp. 65-134. IEEE Press, New York, 1992.
[123] C. Shannon. Communication Theory of Secrecy Systems. Bell System Technical Journal 28 (4): 656-715.
[124] T. Siegenthaler. Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications. IEEE Transactions on Information Theory, IT-30:776-780,1984.
[125] M. Stamp and R. M. Low. Applied Cryptanalysis: Breaking Ciphers in the Real World. WILEY-INTERSCIENCE, 2007.
[126] G. Sekar, S. Paul and B. Preneel. Distinguishing Attack on the Stream Cipher Py. Fast Software Encryption - FSE 2006, LNCS 4047, pp. 405-421, Springer, 2006.
[127] G. Sekar, S. Paul and B. Preneel. Attacks on the Stream Ciphers TPy6 and Py6 and Design of New Ciphers TPy6-A and TPy6-B. WEWoRC 2007, LNCS 4945, pp. 127-141, Springer, 2008.
[128] G. Sekar, S. Paul and B. Preneel. Related-key Attacks on the Py-family of Ciphers and an Approach to Repair the Weaknesses. Progress in Cryptology - INDOCRYPT 2007, LNCS 4859, pp. 58-72, Springer, 2007.
[129] S. Kunzli, P. Junod, W. Meier, Distinguishing Attacks on T-functions, International Confereence on Cryptology in Malaysia, 2005.
[130] A. Shamir and E. Tromer. Acoustic cryptanalysis: on nosy people and noisy machines. http://www.wisdom.weizmann.ac.il/tromer/acoustic/.
[131] S. Fischer, W. Meier, C. Berbain, etc. Non-randomness is eSTREAM Candidates Salsa20 and TSC-4, INDOCRYPT 2006, LNCS 4329, pp. 2-16. Springer, 2006.
[132] M. O. Saarinen. d-Monomial Tests are Effective Against Stream Ciphers. SASC 2006 - Stream Ciphers Revisited, 2006.
[133] A. Shamir. Stream Cipher: Dead or Alive? Invited Report, Advanced in Cryptogloy - ASI-ACRYPT 2004, LNCS 3788 , pp. 78-79. Springer, 2005.
[134] M.S. Turan, A. Doganaksoy, C. C alik. Statistical Analysis of Synchronous Stream Ciphers. SASC 2006 - Stream Ciphers Revisited, 2006.
[135] Y. Tsunoo, T. Saito, T. Kawabata, H. Nakashima. Distinguishing attack against TPypy. Selected Areas in Cryptography - SAC 2007, LNCS 4876, pp. 396-407, Springer, 2007.
[136] Y. Tsunoo, T. Saito, H. Kubo and M. Shigeri. Cryptanalysis of Mir-1, a T-function Based Stream Cipher. IEEE Transactions on Information Theory, Vol 53, pp. 4377-4382,2007.
[137] R. Vuckovac. MAG My Array Generator (a new strategy for random number generation). Available athttp://www.ecrypt.eu.org/stream/mag.html.
[138] S. Vaudenay. On the weak keys of Blowfish. Fast Software Encryption - FSE'96, LNCS 1039, Springer-Verlag, pp. 27-32,1996.
[139] H. Wu. Cryptanalysis and Design of Stream Ciphers. Ph.D thesis. 2008
[140] H. Wu. Stream Cipher HC-128. Available at http://www.ecrypt.eu.org/stream/hcp3.html.
[141] H. Wu and B. Preneel. Differential Cryptanalysis of the Stream Ciphers Py, Py6 and Pypy. Advances in Cryptology - EUROCRYPT 2007, LNCS 4515, pp. 276-290, Springer, 2007.
[142] H. Wu and B. Preneel. Resynchronization Attacks on WG and LEX. Fast Software Encryption - FSE 2006, LNCS 4047, pp. 422-433, 2006.
[143] H. Wu and B. Preneel. Distinguishing attack on stream cipher Yamb. Available at http://www.ecrypt.eu.org/stream/papersdir/043.pdf.
[144] H. Wu and B. Preneel. Cryptanalysis of the Stream Cipher ABC v2. Selected Areas in Cryptography - SAC 2006, LNCS 4356, pp. 56-66, 2007.
[145] D. Whiting, B. Schneier, S. Lucks and F. Muller. Phelix - Fast Encryption and Authentication in a Single Cryptographic Primitive. Available at http://www.ecrypt.eu.org/stream/phelixp2.html.
[146] A. C. Yao, Theroy and Applications of Trapdoor Functions, In Proc. of the 23th Annu. IEEE Symp. on Foundations of Computer Science, pp. 80-91, 1982.
[147] K. C. Zeng and M. Q. Huang. On the linear syndrome method in cryptanalysis, EURO-CRYPT'88, Berlin: Springer-Verlang, 469-478, 1990.
[148] K. C. Zeng, C. H. Yang and T. R. N. Rao. An improved linear syndrome algorithm in cryptanalysis with apllications, EUROCRYPT'90, Berlin: Spring-Verlag, 34-47, 1991.
[2] V. Anashin, A. Bogdanov, I. Kizhvatov, and S. Kumar. ABC: a New Fast Flexible Stream Cipher Specification, Version 3. Available at http://www.ecrypt.eu.org/stream/abcp2.html.
[3] V. Anashin, A. Bogdanov, I. Kizhvatov, Increasing the ABC Stream Cipher Period, Available at http://www.ecrypt.eu.org/stream/papersdir/050.pdf, Also available at http://crypto.rsuh.ru/papers/abc-spec-v2.pdf.
[4] F. Arnault, T. P. Berger and C. Lauradoux. Update on F-FCSR Stream Cipher. Available at http://www.ecrypt.eu.org/stream/ffcsrp3.html.
[5] M. Afzal, and A. Masood. Algebraic Cryptanalysis of A NLFSR Based Stream Cipher.ICTTA 2008,2008.
[6] R. G. Brown. DieHarder: A Random Number Test Suite. Available at http://www.phy.duke.edu/rgb/General/dieharder.php.
[7] C. Berbain, O. Billet, A. Canteaut, N. Courtois, B. Debraize, H. Gilbert, L. Goubin, A.Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin and H. Sibert. Decim v2.Available at http://www.ecrypt.eu.org/stream/decimp3.html.
[8] C. Berbain, O. Billet, A. Canteaut, N. Courtois, H. Gilbert, L. Goubin, A. Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin and H. Sibert. Sosemanuk: a fast software-oriented stream cipher. http://www.ecrypt.eu.org/stream/sosemanukp3.html.
[9] D. Brumley and D. Boneh. Remote Timing Attacks are Practical. In Proceedings of the 12th USENIX Security Symposium, August 2003
[10] S. Babbage, C. Cid, N. Pramstaller and H. Raddum. An Analysis of the Hermes8 Stream Ciphers. ACISP 2007, LNCS 4586, pp. 1-10, Springer, 2007.
[11] S. Babbage and M. Dodd. The stream cipher MICKEY 2.0. Available at http://www.ecrypt.eu.org/stream/mickeyp3.html.
[12] C. Berbain, H. Gilbert, and A. Maximov. Cryptanalysis of Grain. In M. J. B. Robshaw Editor, FSE 2006, LNCS 4047, pp. 15-29,2006.
[13] C. Berbain and H. Gilbert. Cryptanalysis of ABC. Available at http://www.ecrypt.eu.org/stream/papersdir/2005/048.pdf.
[14] A. Braeken, J. Lano, N. Mentens, B. Preneel and I. Verbauwhede. Snksspecication and-sourcecode. Available at http://www.ecrypt.eu.org/stream/sfinks.html.
[15] Y. Borissov, S. Nikova, B. Preneel and J. Vandewalle. On a Resynchronization Weakness in a Class of Combiners with Memory. In Security in Communication Networks - SCN 2002,LNCS 2576, pp. 164-173, Springer, 2002.
[16] A. Biryukov and A. Shamir. Cryptanalytic Time/Memory/Data Tradeoffs for Stream Ciphers, Asiacrypt 2000, LNCS 1976, pp. 1-13, Springer, 2000.
[17] E. Biham and A. Shamir. Differential cryptanalysis of DES-like cryptosystems. In Advances in Cryptology - CRYPTO'90, LNCS 537, pages 221. Springer, 1991.
[18] E. Biham and J. Seberry. Py: A fast and secure stream cipher using rolling arrays. Available at http://www.ecrypt.eu.org/stream/pyp2.html.
[19] M. Boesgaard, M. Vesterager, T. Christensen and E. Zenner. The Stream Cipher Rabbit. Available at http://www.ecrypt.eu.org/stream/rabbitp3.html.
[20] M. Boesgaard, M. Vesterager, T. Pedersen and O. Scavenius. Rabbit: A New High Performance Stream Cipher. Fast Software Encryption - FSE 2003, LNCS 2887, pages 226- 244,Springer, 2004.
[21] S. Babbage. A Space/Time Tradeoff in Exhaustive Search Attacks on Stream Ciphers. European Convention on Security and Detection, IEE Conference publication, No. 408, May 1995.
[23] D. Bernstein. Cache-Timing Attacks on AES (2005),http://cr.yp.to./antiforgery/cachetiming-20050414.pdf.
[23] D. J. Bernstein. Salsa20/8 and Salsa20/12. Available at http://www.ecrypt.eu.org/stream/salsa20p3.html.
[24] E. Biham. On Matsui's linear cryptanalysis. In Advances in Cryptology - EUROCRYPT'94,LNCS 950, pages 341-355. Springer-Verlag, 1995.
[25] A. Biryukov . A new 128 bit key stream cipher: LEX. Available at http://www.ecrypt.eu.org/stream/lexp3.html.
[26] T. Brigham. TRBDK3 YAEA: High Security, Synchronous Stream Cipher. Available at http://www.ecrypt.eu.org/stream/trbdk3.html.
[27] B. Buchberger, Grobner Base: An Algorithm Method in Polynomial Ideal Theory, Multi-deimension System Theory. Dordrecht, pp. 184-232,1985.
[28] C. Cid, H. Gilbert, and T. Johansson. Cryptanalysis of Pomaranch. IEE Information Security, 153(2):51-53, June 2006.
[29] C. Berbain and H. Gilbert. On the Security of IV Dependent Stream Ciphers. In A.Biryukov,editor, FSE 2007, LNCS 4593, pp.254-273. Springer, 2007.
[30] V. V. Chepyzhov, T. Johansson and B. Smeets. A Simple Algorithm for Fast Correlation Attacks on Stream Ciphers. In Fast Software Encryption - FSE 2000, LNCS 1978, pp. 181-195, Springer, 2000.
[31] C. D. Canniere, (?). K(?)k, and B. Preneel. Analysis of Grain' s Initialization Algorithm. In S. Vaudenay Editor, AFRICACRYPT 2008, LNCS 5023, pp. 276-289, 2008.
[32] N. Courtois, A. Klimov, J. Patarin, and A. Shamir. Efficient algorithms for solving overdeined systems of multivariate polynomial equations. In B. Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, LNCS 1807, pp. 392-407. Springer, 2000.
[33] C. Cid and G. Leurent. An analysis of the XSL algorithm. In B. Roy, editor, Advances in Cryptology - ASIACRYPT 2004, LNCS 3788 , pp. 333-352. Springer, 2005.
[34] J. Y. Cho and J. Pieprzyk. Crossword Puzzle Attack on NLS. Selected Areas in Cryptography - SAC 2006, LNCS 4356, pp. 249-265, Springer, 2007.
[35] C. D. Canne and B. Preneel. Trivium Specifications. Available at http://www.ecrypt.eu.org/stream/triviump3.html.
[36] N. Courtois and J. Pieprzyk. Cryptanalysis of block ciphers with overdefined systems of equations. In Y. Zheng, editor, Advances in Cryptology - ASIACRYPT 2002, LNCS 2501,pp. 267-287. Springer, 2002.
[37] A. Canteaut and M. Trabbia. Improved Fast Correlation Attacks Using Parity Check Equations of Weight 4 and 5." In Advances in Cryptology - EUROCRYPT 2000, LNCS 1807,pp. 573-588, Springer, 2000.
[38] N. T. Courtois. Cryptanalysis of Sfinks. Information Security and Cryptology - ICISC 2005,LNCS 3935, pp. 261-269, Springer, 2006.
[39] LAN Crypto. LAN Crypto Submission to the ECRYPT Stream Cipher Project (yamb).Available at http://www.ecrypt.eu.org/stream/yamb.html.
[40] E. Dawson, K. Chen, M. Henricksen, W. Millan, L. Simpson, H. Lee,S. Moon. Dragon: A Fast Word Based Stream Cipher. Available at http://www.ecrypt.eu.org/stream/dragonp3.html.
[41] D. Moon, D. Kwon, D. Han, etc., T-function Based Stream Cipher TSC-4, Available at http://www.ecrypt.eu.org/stream/p2ciphers/tsc4/tsc4_p2.pdf.
[42] J. Daemen, R. Govaerts and J. Vandewalle. Resynchronization Weakness in Synchronous Stream Ciphers. In Advances in Cryptology-EUROCRYPT' 93, LNCS 765, pp. 159-167,Springer, 1994.
[43] J. Daemen, R. Govaerts, and J. Vandewalle. Weak keys for IDEA, CRYPTO '93, pp. 224-231, 1993.
[44] O. Dunkelman, A. Hecht, C. Gressel, R. Granot and G. Vago. Zk-Crypt. Available at http://www.ecrypt.eu.org/stream/zkcryptp2.html.
[45] P. Delaunay and A. Joux. Yet Another Attack on Vest. Progress in Cryptology -AFRICACRYPT 2008, LNCS 5023, pp. 221-235, Springer, 2008.
[46] O. Dunkelman and N. Keller. A New Attack on the LEX Stream Cipher. Progress in Cryp-tology - AFRICACRYPT 2008, LNCS 5023, pp. 539-556, Springer, 2008.
[47] J. Daemen and P. Kitsos. The Self-synchronizing Stream Cipher Moustique. Available at http://www.ecrypt.eu.org/stream/mosquitop3.html.
[48] J. Daemen, J. Lano, B. Preneel. Chosen Ciphertext Attack on SSS. SASC 2006 - Stream Ciphers Revisited, 2006.
[49] C. Diem. The XL-algorithm and a conjecture from commutative algebra. In P. Lee, editor,Advances in Cryptology - ASIACRYPT 2004, LNCS 3329, pp. 323-337. Springer, 2004.
[50] ECRYPT. eSTREAM: ECRYPT Stream Cipher Project, IST-2002-507932. Available at http://www.ecrypt.eu.org/stream/.
[51] H. Englund, M. Hell and T. Johansson. Two General Attacks on Pomaranch-like Keystream Generators. Fast Software Encryption - FSE 2007, LNCS 4593, pp. 274-289, Springer,2007.
[52] eSTREAM. Call for Stream Cipher Primitives. Available at http://www.ecrypt.eu.org/stream/call/.
[53] eSTREAM. End of Phase 3 of the eSTREAM Projcet. Available at http://www.ecrypt.eu.org/stream/endofphase3.html.
[54] eSTREAM.The eSTREAM Portfolio.Available at http://www.ecrypt.eu.org/stream/portfolio.html.
[55] eSTREAM. Available at http://www.ecrypt.eu.org/stream/.
[56] J. C. Faugere, A New Efficient Algorithm for Computing Grobner Bases (F4), Journal of Pure and Applied Algebra. Vol.139, NO.1-3, pp. 61-88, June,1999.
[57] J. C. Faugere, A New Efficient Algorithm for Computing Grobner Bases without Reduction to Zero (F5), International Sysmposium on Symbolic and Algebraic Computation-ISSAC'02, pp. 75-83, ACM Press, 2002.
[58] FIPS, Guidelines for Implementing and Using the NBS Data Encryption Standard, F1PS-PUB 74, http://www.itl.nist.gov/fipspubs/fip74.html.
[59] S. Fluhere, I. Mantin and A. Shamir. Weaknesses in the Key Scheduling Algorithm of RC4.Eighth Annual Workshop on Selected Areas in Cryptography - SAC 2001, LNCS 2259, pp.1-24, Springer-Verlag, 2001.
[60] F. Muller and T. Peyrin, Linear Cryptanalysis of the TSC Family of Stream Ciphers, ASIACRYPT 2005, LNCS 3788, pp.373-394,2005.
[61] F. Muller and T. Peyrin, Linear Cryptanalysis of TSC Stream Ciphers - Applications to the ECRYPT Proposal TSC-3, Available at http://www.ecrypt.eu.org/stream/papersdir/042.ps.
[62] B. Gammel, R. Gottfert and O. Kniffler. Achterbahn-128/80. Available at http://www.ecrypt.eu.org/strearn/achterbahnp2.html.
[63] D. Gligoroski, S. Markovski, L. Kocarev and M. Gusev. Edon80. Available at http://www.ecrypt.eu.org/strearn/edon80p3.html.
[64] S. Goldwasser, S. Micali and C. Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Comput., Vol. 18, No. 1,1989.
[66] J. D. Golic, G. Morgari. On the Resynchronization Attack. In Fast Software Encryption -FSE 2003, LNCS 2887, pp. 100-110, Springer, 2003.
[66] S. Goldwasser and S. Micali. Probabilistic Enryption and How to Play Mental Poker Keeping Secret All Partial Information. 14th ACM STOC, pp. 365-377,1982.
[67] G. Gong and Y. Nawaz. The WG Stream Cipher. Available at http://www.ecrypt.eu.org/strearn/wgp2.html.
[68] J. D. Golic. Cryptanalysis of Alleged A5 Stream Cipher, Eurocrypt'97, LNCS 1233, pp.239-255, Springer, 1997.
[69] H. Wu and B. Preneel. Cryptanalysis of the stream cipher DECIM. In M. Robshaw, editor,FSE 2006, LNCS 4047, pages 30 - 40. Springer, 2006.
[70] H. Wu and B. Preneel. Resynchronization attacks on WG and LEX. In M. Robshaw, editor,FSE 2006, LNCS 4047, pages 422 - 432. Springer, 2006.
[71] M. Hell and T. Johansson. A Key Recovery Attack on Edon80. Advances in Cryptology -ASIACRYPT 2007, LNCS 4833, pp. 568-581, Springer, 2007.
[72] M. Hell and T. Johansson. Breaking the F-FCSR-H Stream Cipher in Real Time. Advances in Cryptology - ASIACRYPT 2008, LNCS 5350, pp. 557-569, Springer, 2008.
[73] M. Hell, T. Johansson and W. Meier. Grain - A Stream Cipher for Constrained Environments. Available at http://www.ecrypt.eu.org/stream/ciphers/grain/grain.pdf.
[74] M. Hell, T. Johansson, A. Maximov, and W. Meier. The Grain Family of Stream Ciphers. In M. Robshaw and O. Billet Editors, New Stream Cipher Designs, LNCS 4986, pp. 179-190,2008.
[75] M. Hell, T. Johansson and W. Meier. Grain - A Stream Cipher for Constrained Environments(New Version). Available at http://www.ecrypt.eu.org/stream/grainp3.html.
[76] M. Hell, T. Johansson. Cryptanalysis of Achterbahn-Version 2. Selected Areas in Cryptography - SAC 2006, LNCS 4356, pp. 45-55, Springer, 2007.
[77] J. Hong, D. H. Lee, Y. Yeom, D. Han and S. Chee. T-function based streamcipher TSC-4.Available at http://www.ecrypt.eu.org/stream/tsc3p2.html.
[78] J. H(?)stad and M. Naslund. A New Version of the Stream Cipher Polar Bear. Available at http://www.ecrypt.eu.org/stream/polarbearp2.html.
[79] X. L. Huang and C. K. Wu. Cryptanalysis of Achterbahn-Version 1 and - Version 2. Journal of Computer Science and Technology, vol. 22, No. 3, pp. 469-475, Springer, 2007.
[80] M. E. Hellman. A Cryptanalytic Time-Memory Trade-Off. IEEE Transactions on Information Theory, vol. IT-26, No. 4, pp. 401-406, July 1980.
[81] J. Hong, D. H. Lee, Y. Yeom, D. Han, S. Chee, T-function Based Stream Cipher TSC-3,Available at http://www.ecrypt.eu.org/stream/ciphers/tsc3/tsc3.pdf.
[82] J. Hong, D. H. Lee, Y. Yeom, and D. Han, New Class of Single Cycle T-functions, FSE 2005, LNCS 3557, pp.68-82,2005.
[83] J. Johansson and F. Jonsson. Improved Fast Correlation Attacks on Stream Ciphers via Convolutional Codes. In Advances in Cryptology - EUROCRYPT' 99, LNCS 1592, pp.347-362, Springer, 1999.
[84] T. Johansson and F. Jonsson. Fast Correlation Attacks Based on Turbo Code Techniques. In Advances in Cryptology - CRYPTO' 99, LNCS 1666, pp. 181-197, Springer-Verlag, 1999.
[85] T. Johansson and F. Jonsson. Fast Correlation Attacks through Reconstruction of Linear Polynomials. In Advances in Cryptology - CRYPTO 2000, LNCS 1880, pp. 300-315,Springer, 2000.
[86] C. Jansen and A. Kolosha. Cascade Jump Controlled Sequence Generator and Pomaranch Stream Cipher (Version 3). Available at http://www.ecrypt.eu.org/stream/pomaranchp2.hrml.
[87] T. Johansson, W. Meier and F. Muller. Cryptanalysis of Achterbahn. Fast Software Encryption - FSE 2006, LNCS 4047, pp. 1-14, Springer, 2006.
[88] J. Mitra and P. Sarkar, Time-memory Trade-Off Attacks on Multiplications and T-functions,AS1ACRYPT 2004, LNCS 3329, pp. 468-482, Springer, 2004.
[89] A. Joux and J. Reinhard. Overtaking VEST. Fast Software Encryption - FSE 2007, LNCS 4593, pp. 58-72, Springer, 2007.
[90] S. Khazaei. Divide and Conquer Attack on ABC Stream Cipher. Available at:http://www.ecrypt.eu.org/stream/papersdir/052.pdf.
[91] S. Khazaei, Divide and Conquer Attack on ABC Stream Cipher, Available at:http://www.ecrypt.eu.org/stream/papersdir/052.pdf.
[92] S. Khazaei, M. Hassanzadeh and M.Kiaei. Distinguishing Attack on Grain.ECRYPT Stream Cipher Project Report 2005/071, 2005. Available at http://www.ecrypt.eu.org/stream.
[93] S. Khazaei and M. Kiaei. Distinguishing attack on the ABC v.1 and v.2. eSTREAM,ECRYPT Stream Cipher Project, Report 2005/061, 2005.
[94] S. Kunzli and W. Meier. Distinguishing Attack on MAG. Available at http://www.ecrypt.eu.org/stream/papersdir/053.pdf.
[95] E. Kasper, V. Rijmen, T. E. Bjφrstad, C. Rechberger, M. Robshaw and G. Sekar. Correlated Keystreams in Moustique. Progress in Cryptology - AFRICACRYPT 2008, LNCS 5023, pp. 246-257, Springer, 2008.
[96] A. Klimov and A. Shamir, A New Class of Invertible Mappings, CHES 2002, LNCS 2523, pp.470-483,2003.
[97] A. Klimov and A. Shamir, Cryptographic Application of T-functions, SAC 2003, LNCS 3006, pp.248-261,2004.
[98] A. Klimov and A. Shamir, New Cryptographic Primitives Based on Multiword T-functions, FSE 2004, LNCS 3017, pp.1-15,2004.
[99] o. Kücük, Slide Resynchronization Attack on the Initialization of Grain 1.0. ECRYPT Stream Cipher Project Report 2006/044, 2006. Available at http://www.ecrypt.eu.org/stream.
[100] U. Kaiser. Hermes Stream Cipher. Available at http://www.ecrypt.eu.org/stream/hermes8p2.html.
[101] P. C. Kocher. Timing attacks on implementation of Diffie-Hellman, RSA, DSS, and Other Systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104-113. Springer, 1996.
[102] S. K. Langford and M. E. Hellman. Differential-linear cryptanalysis. In Advances in Cryptology - CRYPTO'94, LNCS 839, pp. 17-25. Springer, 1994.
[103] Y. Lee, K. Jeong, J. Sung, and S. Hong. Related-Key Chosen IV Attacks on Grain-vl and Grain-128. In Y. Mu, W. Susilo, and J. Seberry (Eds.), ACISP 2008, LNCS 5107, pp. 321-335, 2008.
[104] A. P. Li. A new stream cipher DICING - An update for phase 2 of eSTREAM. Available at http://www.ecrypt.eu.org/stream/dicingp2.html.
[105] M. Mihaljevic, M.P.C. Fossorier and H. Imai. A Low-Complexity and High Performance Algorithm for Fast Correlation Attack. In Fast Software Encryption - FSE 2000, pp. 196-212, Springer, 2000.
[106] M. Matsumoto, H. Mariko, T. Nishimura and M. Saito. CryptMT stream cipher version 3. Available at http://www.ecrypt.eu.org/stream/cryptmtp3.html.
[107] A. Menezes, P. v. Oorschot, and S. Vanstone. Handbook of Applied Cryptography. CRC Press, 1997. ISBN 0-8493-8523-7.
[108] W. Meier and O. Staffelbach. Fast Correlation Attacks on Certain Stream Ciphers. Journal of Cryptography, 1(3):159-176,1989.
[109] Magma Computational Algebra System available at http://magma.maths.usyd.edu.au/.
[110] M. Matsui. Linear cryptanalysis method for DES cipher. In Advance in Cryptology - EU-ROCRYPT'93, LNCS 765, pp. 386-397. Springer, 1994.
[111] A. Maximov. A New Stream Cipher "Mir-1". Available at http://www,ecrypt.eu.org/stream/mirl .html.
[112] T. Moreau. The Frogbit cipher, a data integrity algorithm. Available at http://www.ecrypt.eu.org/stream/frogbit.html.
[113] G. Marsaglia. The Marsaglia Random Number CDROM including the Diehard Battery of Tests of Randomness.
[114] M. Naya-Plasencia. Cryptanalysis of Achterbahn-128/80. Fast Software Encryption - FSE 2007, LNCS 4593, pp. 73-86, Springer, 2007.
[115] M. Naya-Plasencia. Cryptanalysis of Achterbahn-128/80 with a New Keystream Limitation. WEWoRC 2007, LNCS 4945, pp. 142-152, Springer, 2008.
[116] NESS1E. New European Schemes for Signatures, Integrity, and Encryption. Available at http://www.cryptonessie.org.
[117] NIST Statistical Test Suite. Available at http://csrc.nist.gov/mg/.
[118] S. O'Neil, B. Gittins and H. Landman. VEST ciphers. Available at http://www.ecrypt.eu.org/stream/vestp2.html.
[119] S. Paul and B. Preneel. On the (In)security of Stream Ciphers Based on Arrays and Modular Addition. Advances in Cryptology - ASIACRYPT 2006, LNCS 4284, pp. 69-83, Springer, 2007.
[120] G. Rose, P. Hawkes, M. Paddon and M. W. de Vries . Primitive Specification for NLSv2. Available at http://www.ecrypt.eu.org/stream/nlsp3.html.
[121] G. Rose, P. Hawkes, M. Paddon and M. W. de Vries. Primitive Specification for SSS. Available at http://www.ecrypt.eu.org/stream/sss.html.
[122] R. A. Rueppel. Stream Ciphers. In Gustavus J. Simmons, editor, Contemporary Cryptology: The Science of Information Integrity, chapter 2, pp. 65-134. IEEE Press, New York, 1992.
[123] C. Shannon. Communication Theory of Secrecy Systems. Bell System Technical Journal 28 (4): 656-715.
[124] T. Siegenthaler. Correlation-Immunity of Nonlinear Combining Functions for Cryptographic Applications. IEEE Transactions on Information Theory, IT-30:776-780,1984.
[125] M. Stamp and R. M. Low. Applied Cryptanalysis: Breaking Ciphers in the Real World. WILEY-INTERSCIENCE, 2007.
[126] G. Sekar, S. Paul and B. Preneel. Distinguishing Attack on the Stream Cipher Py. Fast Software Encryption - FSE 2006, LNCS 4047, pp. 405-421, Springer, 2006.
[127] G. Sekar, S. Paul and B. Preneel. Attacks on the Stream Ciphers TPy6 and Py6 and Design of New Ciphers TPy6-A and TPy6-B. WEWoRC 2007, LNCS 4945, pp. 127-141, Springer, 2008.
[128] G. Sekar, S. Paul and B. Preneel. Related-key Attacks on the Py-family of Ciphers and an Approach to Repair the Weaknesses. Progress in Cryptology - INDOCRYPT 2007, LNCS 4859, pp. 58-72, Springer, 2007.
[129] S. Kunzli, P. Junod, W. Meier, Distinguishing Attacks on T-functions, International Confereence on Cryptology in Malaysia, 2005.
[130] A. Shamir and E. Tromer. Acoustic cryptanalysis: on nosy people and noisy machines. http://www.wisdom.weizmann.ac.il/tromer/acoustic/.
[131] S. Fischer, W. Meier, C. Berbain, etc. Non-randomness is eSTREAM Candidates Salsa20 and TSC-4, INDOCRYPT 2006, LNCS 4329, pp. 2-16. Springer, 2006.
[132] M. O. Saarinen. d-Monomial Tests are Effective Against Stream Ciphers. SASC 2006 - Stream Ciphers Revisited, 2006.
[133] A. Shamir. Stream Cipher: Dead or Alive? Invited Report, Advanced in Cryptogloy - ASI-ACRYPT 2004, LNCS 3788 , pp. 78-79. Springer, 2005.
[134] M.S. Turan, A. Doganaksoy, C. C alik. Statistical Analysis of Synchronous Stream Ciphers. SASC 2006 - Stream Ciphers Revisited, 2006.
[135] Y. Tsunoo, T. Saito, T. Kawabata, H. Nakashima. Distinguishing attack against TPypy. Selected Areas in Cryptography - SAC 2007, LNCS 4876, pp. 396-407, Springer, 2007.
[136] Y. Tsunoo, T. Saito, H. Kubo and M. Shigeri. Cryptanalysis of Mir-1, a T-function Based Stream Cipher. IEEE Transactions on Information Theory, Vol 53, pp. 4377-4382,2007.
[137] R. Vuckovac. MAG My Array Generator (a new strategy for random number generation). Available athttp://www.ecrypt.eu.org/stream/mag.html.
[138] S. Vaudenay. On the weak keys of Blowfish. Fast Software Encryption - FSE'96, LNCS 1039, Springer-Verlag, pp. 27-32,1996.
[139] H. Wu. Cryptanalysis and Design of Stream Ciphers. Ph.D thesis. 2008
[140] H. Wu. Stream Cipher HC-128. Available at http://www.ecrypt.eu.org/stream/hcp3.html.
[141] H. Wu and B. Preneel. Differential Cryptanalysis of the Stream Ciphers Py, Py6 and Pypy. Advances in Cryptology - EUROCRYPT 2007, LNCS 4515, pp. 276-290, Springer, 2007.
[142] H. Wu and B. Preneel. Resynchronization Attacks on WG and LEX. Fast Software Encryption - FSE 2006, LNCS 4047, pp. 422-433, 2006.
[143] H. Wu and B. Preneel. Distinguishing attack on stream cipher Yamb. Available at http://www.ecrypt.eu.org/stream/papersdir/043.pdf.
[144] H. Wu and B. Preneel. Cryptanalysis of the Stream Cipher ABC v2. Selected Areas in Cryptography - SAC 2006, LNCS 4356, pp. 56-66, 2007.
[145] D. Whiting, B. Schneier, S. Lucks and F. Muller. Phelix - Fast Encryption and Authentication in a Single Cryptographic Primitive. Available at http://www.ecrypt.eu.org/stream/phelixp2.html.
[146] A. C. Yao, Theroy and Applications of Trapdoor Functions, In Proc. of the 23th Annu. IEEE Symp. on Foundations of Computer Science, pp. 80-91, 1982.
[147] K. C. Zeng and M. Q. Huang. On the linear syndrome method in cryptanalysis, EURO-CRYPT'88, Berlin: Springer-Verlang, 469-478, 1990.
[148] K. C. Zeng, C. H. Yang and T. R. N. Rao. An improved linear syndrome algorithm in cryptanalysis with apllications, EUROCRYPT'90, Berlin: Spring-Verlag, 34-47, 1991.