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-Ⅳ出现的概率很低,但可以说明这两个算法的密钥初始化过程存在安全问题,有必要进行修改。