（应用数学专业论文）rc4算法及其安全性分析.pdf

摘要 r c 4 算法是r o nr i v e s t 在1 9 8 7 年为r s a 数据安全公司开发的可变密钥长 度的序列密码。该算法与众多序列密码的算法设计思想不同，安全性高，而且易 于软件实现，并被广泛地应用于商业密码产品中，包括l o t u s n o t e s ，苹果计算机 的a o c e 和o r a c l e 安全s o l 数据库等。 在得到广泛应用的同时，该算法的安全性分析也成为一个重要的研究方向。 了解该算法并分析该算法的安全性正是本文所研究的内容。现阶段对r c 4 的攻 击类型已有很多，详见第三章。 本文的主要结论是提出了一种新的对r c 4 的错误引入分析方法。错误引入 分析方面的技术现在正在不断发展，它在一定物理条件的支持下可以在实践中实 现。针对r c 4 进行错误引入分析具有一定的研究意义。本文提出的错误引入分 析方法由算法1 与算法2 组成，用以恢复整个r c 4 的初始内部状态。算法1 是 一轮攻击，攻击后在最理想的状态下，可以得到3 个r c 4 初始状态的值：s 。【1 1 、 s 。m 】、瓯【 】。算法2 是整个2 5 6 轮攻击，在需要严个输出密钥字，至多引入严 个错误下，几乎可以恢复整个r c 4 的初始状态。 另一个结论是利用上面的错误引入方法进行1 2 0 轮攻击，大约引入2 1 4 到2 1 5 个错误后，能以6 3 3 的概率成功的确定s 0 中大约2 0 3 个位置上的值，其余5 3 个值可以结合状态猜测攻击方法，以2 “1 3 的复杂度有效地进行恢复。 关键词：流密码，r c a 算法，错误引入攻击 a b s t r a c t t h er c aa l g o r i t h mi sas t r e a mc i p h e rw i t hav a r i a b l e - l e n g t hk e y , w h i c hw a s d e s i g n e db yr o nr i v e s tf o rr s ad a t as e c u r i t yc o r p o r a t i o ni n1 9 8 7 d u et oh i g h s e c u r i t ya n de f f i c i e n ts o f t w a r ei m p l e m e n t a t i o n ，t h ed e s i g ni d e ao fr e 4d i f f e r sf r o m t h a to fo t h e rs t r e a mc i p h e r s i th a sb e e nw i d e l yu s e di nt h ec o m m e r c i a lp r o d u c t s ， i n c l u d i n gl o t u sn o t c s 、a o c eo fa p p l ec o m p u t e ra n do r a c l es e c u r es q ld a t u b a s e a n dm a n yo t h e ra p p l i c a t i o n s a si ti su s e ds ow i d e l y , r e 4h a st u r n e dt ob eo n eo fi m p o r t a n tr e s e a r c hf i e l d s t h i sp a p e ri st oi n t r o d u c et h i sa l g o r i t h ma n da n a l y z ei t ss e c u r i t y t h e r eh a v eb e e n m a n yk i n d so fa t t a c k so nr c 4 a tp r e s e n t , w h i c ha r er e p r e s e n t e di nc h a p t e r3 o u rm a i nr e s u l ti si n t r o d u c t i o no fan l q o vf a u l ti n d u c t i o na t t a c ko nr c a f a u l t i n d u c t i o na t t a c k sc a nb ep r a c t i c a li nc e r t a i ne x t e n t ，a n da l lk i n d so ft e c h n i q u e so ff a u l t i n d u c t i o na l ed e v e l o p i n g s ot h ea n a l y s i si nt h i sw a yo nr c 4h a sc e r t a i nr e s e a r c h s e n s e t h en o wf a n l ti n d u c t i o na t t a c ki nt h i sp a p e rc o n s i s t so fa l g o r i t h m1a n d a l g o r i t h m2 ，a i m i n ga tr e v e a l i n gt h ew h o l ei n i t i a ls t a t e so fr c 4 t h ea l g o r i t h m1i s o n er o u n da t t a c ko nr c a , w h i c hc a ng e t3e n t r i e so ft h ei n i t i a ls t a t e ：s o 【1 】、& 【亢】 a n d s o 【 】t h ea l g o r i t h m2i st h ew h o l e2 5 6r o u n d sa t t a c ko nr c a , w h i c h 伽 a l m o s tr e v e a l t h e w h o l e i n i t i a ls t a t e s o f r c 4 w i t h l e s s t h a n 2 1 6 b y t e s o f s t r e a ma n d l e s s t h a n2 1 6f a u l ti n d u c t i o n s a n o t h e rr e s u l ti sa sf o l l o w a b o u t2 0 3e n t r i e so fs oc a nb er e v e a l e dw i t ht h e p o s s i b i l i t yo f6 3 3 b yt h ea b o v ea t t a c ka f t e r2 “t o2 1 5f a u l ti n d u c t i o n s t h er e s t5 3 e n t r i e so ft h ei n i t i a ls t a t e 啪b er e v e a l e de f f i c i e n t l yw i t ht h ec o m p l e x i t yo f2 1 4 1 3 c o m b i n i n g w i t hk n u d s e n sa t t a c k k e y w o r d s ：s t r e a mc i p h e r , r c 4a l g o r i t h m ，f a u l ta n a l y t i ca t t a c k 广州大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指 导下，独立进行研究工作所取得的成果。除文中已经注明引 用的内容外，本论文不含任何其他个人或集体已经发表或撰 写过的作品成果。对本文的研究做出重要贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律 后果由本人承担。 学位论文作者签名：f 定罐辱日期：驴9 年z 刖1 l q 7 广州大学学位论文版权使用授权书 本人授权广州大学有权保留并向国家有关部门或机构送 交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权 广州大学可以将学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存、汇 编学位论文。( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：( 次聿零日期：砷年莎月r 日 导师签名：甥蟛一日期：伽7 年f 月r - e l 第一章绪论 第一章绪论 密码学是信息安全领域的一门重要学科。自从电子时代开始以来，基于移位 寄存器的序列密码己被广泛地用于军事密码中。大多数实际的序列密码都是围绕 线性反馈移位寄存器1 1 l ( l i n e a rf e e d b a c ks h i f tr e g i s t e r , l f s r ) 而设计的，但l s f r 的问题是用软件实现其效率非常低。事实上，一个类似收缩式发生器的l f s r 算 法用软件实现并不比d e s 快。流密码中另一类非常著名的算法l c 4 算法则 克服了基于线性反馈移位寄存器算法的不足。 r c 4 算法由一个包含2 5 6 个元素的s 盒以及两个指针和工组成，大约由 2 1 7 0 0 ( 2 5 61x 2 5 62 ) 种可能的状态，是一个非常庞大的数字。s 盒在使用中慢慢 改变：指针保证每个元素的改变，指针工保证元素随机的改变。算法简单到足 以使大多数程序员能很快地对它进行编程。 错误引入攻击也是本文一个重要的模块，它最初是针对r s a 和其它一些密 码协议的。随后出现了对私钥密码体制的差分错误分析方法。假设攻击者控制了 密码设备( 如智能卡) ，可以正确地使用密码设备进行加密，还可以向密码设备 中引入错误，影响加密过程，使密码设备输出错误的加密结果。攻击者不知道隐 藏在密码设备中的秘密信息( 如密钥) ，她的目标是利用错误的加密结果找出秘 密信息。攻击者也会同时利用正确的和错误的加密结果进行分析比较，从而揭示 隐藏的秘密，这样的错误引入攻击也被称为差分错误分析。基于错误引入的密码 分析方法一定程度上可以在实践中实现，各种各样的错误引入技术也在不断发 展。本文的重心就是研究r c 4 的错误引入攻击，其目的是为了找出r e 4 的初始 状态。 这篇文章主要研究的是r c a 算法以及它的安全性分析。目前，对r c 4 的错 误分析方面的研究还较少，本文就是受到e l ib i h a m 等人的“不可能状态分析方 法”以及“差分错误分析方法”的启发，运用了一种新的错误引入攻击方法，分析 可以得出整个r c 4 的初始状态。 本文的另一个结果就是在这个新的错误引入分析方法所得的结论的基础上， 1 , 1r c 4 算法的历史 结合k n u d s e n 等人的状态猜测攻击方法再去分析r c 4 算法，更有效地恢复r c 4 的 初始状态。 本章首先介绍了r c 4 的历史。通过对r c a 历史的介绍，读者可以清晰地了 解r c 4 的一些背景知识，把握它所具备的特点。从该算法的特点可看出它的广 泛应用以及它在密码学领域中所处的地位。 本章的第二部分给出了整篇文章的大纲。 1 1r c 4 算法的历史 现代密码学形成于2 0 世纪7 0 年代，其中重要的标志有两个，一是美国制定 并于1 9 7 7 年1 月1 5 日批准公布的数据加密标准d e s ，二是公钥密码体制的诞 生。这两个事件在密码学发展史上具有里程碑意义，成为现代密码学的开端。现 代密码学的划时代突破，是d i f f i e 和h e l l m a n 于1 9 7 6 年发表的有关公开密钥加 密系统的构想。真正有生命力的公开密钥加密系统算法是由r i v e s t 、a d is h a m i r 和a d l e m e n 在1 9 7 7 年发明并沿用至今的r s a 算法。它是第一个既能用于数据加 密也能用于数字签名的算法。 随后，密码学得到了迅速的发展，并进入了一个全新的时期，各种更加安全 有效的加密算法、签名方案、鉴别体制、攻击方法等被提出并得到广泛的应用。 例如：1 9 8 2 年a c y a o 提出的计算复杂度方法，1 9 8 5 年提出的e i g a m a l 方案、 零知识证明思想、椭圆曲线密码系统、h a s h 函数，1 9 9 0 年b i h a m 和s h a m l r 提出 的差分密码分析方法，1 9 9 3 年m i t s u r um a t s u i 的线性密码分析方法等。1 9 9 7 2 0 0 0 年美国高级加密标准a e s 的征集活动以及2 0 0 0 2 0 0 3 年欧洲n e s s i e 计划的实 施，再次掀起了密码研究的新高潮，1 5 个a e s 候选算法和2 4 个n e s s i e 终选算 法反映了当前密码设计的水平，同时也将密码学算法的设计和分析技术推进到了 一个更高的层次。 正是根据2 0 世纪7 0 年代现代密码学形成的这两个标志，密码学算法可以划 分为两大类：对称算法和非对称算法。对称算法有时也称私钥加密算法，非对称 算法也称公钥算法。二者之间的主要区别在于加密者和解密者所共享的密钥信息 不同。对称算法可分为两类：一类是序列密码或流密码，另一类是分组算法。公 钥密码算法中用作加密的密钥和用作解密的密钥不同，而且解密密钥不能根据加 2 第一章绪论 密密钥计算出来。对称加密算法和非对称加密算法在运行效率上有很大的区别， 非对称加密算法相对于对称加密算法来讲运行速度比较缓慢，但是它在通信中具 有对称算法所没有的优点。在实际应用中一般采用二者结合的方法，特别是在协 议的设计中，充分发挥二者结合的功效。 在运用分组算法加密时，先将明文划分为固定长度数据组，然后以组为单位 进行加密。若明文分组相同，那么密文分组也相同。设计分组密码算法的核心技 术是建立在这样的数学规则下：复杂函数可以通过简单函数迭代若干次后得到， 利用简单函数和非线性函数等运算，产生比较复杂的变换。而流密码则是通过产 生性能优良的伪随机序列，使用该序列加密信息流，( 逐比特加密) 得到密文序 列，所以，序列密码算法的安全强度完全决定于它所产生的伪随机序列的好坏。 s h a n n o n 在1 9 4 8 年就从理论上证明了一次一密密码体制是不可破的。这一 结果给密码学研究带来了很大的推进作用。若能以一种方式产生一个随机序列， 这个序列由密钥所确定，则利用这样的序列就可以进行加密。这个体制的运行如 图1 - 1 所示。 图1 - 1 f i g 1 - 1 在流密码中，加密器中存储器的状态随时间而变化，这以变化过程可用一个 函数正来描述，这个函数通常称为状态转移函数。根据状态转移函数是否依赖 于输入的明文符号( 字符或比特) ，流密码分为两类：同步流密码和白同步流密 码。 3 1 1r c a 算法的历史 在同步流密码中，状态转移函数正与输入的明文符号无关。此时密码流与明 文符号无关，而某一时刻，输出的密文：c j ；e 七，) 也不依赖于j 时刻之前 的明文符号。因此同步流密码可分为伪随机序列生成器或密钥流生成器和加密变 换器两部分，在同步流密码中，只要发送端和接收端有相同的密钥k 和内部状态， 就能产生相同的伪随机数。此时，发送端和接收端的密钥生成器是同步的。一旦 二者不同步，解密工作立即失败，这时密码系统必须提供某种辅助手段以重建同 步。同步流密码有两种基本的工作模式，一种是输出一分组反馈模式，另一种是 计数模式。 在自同步流密码中，状态转移函数丘与输入的明文符号有关，此时伪随机 数与明文符号有关，而_ 时刻的密文c ，不仅仅依赖于明文符号x ，。密码反馈模 式是自同步流密码的一种最常用的工作模式。 目前绝大多数有关流密码的研究成果都是同步流密码方面的，包括本文研究 的r c 4 算法。由于自同步流密码系统一般需要密文反馈，因而使得分析工作变 得复杂。但自同步流密码具有抵抗搜索攻击和认证功能等优点，所以这种流密码 也是一个有待进一步研究的课题。 在过去的2 0 年里，很多流密码算法被提出和使用，但大部分都是基于线性 反馈移位寄存器( l f s r ) 的。基于线性反馈移位寄存器的算法在硬件上易于实 现，但在软件实现方面，其速度相对较慢。而流密码中另一类非常著名的算法 l c 4 算法则克服了基于线性反馈移位寄存器算法的不足。由于r c 4 算法具 有良好的随机性和抵抗各种攻击的能力，该算法在众多领域里得到了广泛的应 用。 r c 4 算法是由r s a 公司在1 9 8 7 年开发的一个非常著名的流密码体制，由美 国著名密码学家r o nr i v e s t 设计( r c 代表r o n sc o d e ) 。该算法被设计出来之后 的一段时问，设计者未公开算法的细节。在开始的七年中它具有专利，必须在签 署保密协议后才能得到算法的细节。1 9 9 4 年9 月，有人把它的源代码匿名张贴 在c y p h e r p u n k s 邮件列表中。该代码迅速传到u s e n e t 新闻组s c i c r y p t 栏目中，并 且通过互联网传遍了全世界的f p t 站点。拥有r c a 合法拷贝的用户对它进行了完 全的验证，自此r c a 算法变得众所周知。 4 第一章绪论 正是由于r c 4 算法具有线性反馈移位寄存器等其他流密码算法所不具备的 特性，该算法迅速走入了人们的视眼，并得到了广泛的关注。r c 4 在现代密码学 的发展过程中起着非常重要的作用，它的应用非常广泛，很多领域的安全模块中 都使用了该算法。在国际著名的安全协议标准s s l ( s e c u r e s o c k e t s l a y e r p r o t o c 0 1 ) 中，该算法用以保护互联网传输中的保密性，而且，它也被集成于m i c r o s o f t w m d o w s ，l o t u sn o t e s ，a p p l ea o c e ，o r a c l es e c u r es q l 等，还包括t l s ( 传输 层协议) ，w e p 协议( 有线等价隐私协议) ，磷酸( 基于w i f i 保护接入) ，简介 ( 题关键完整议定书) ，微软p p t p 的微软办公，并应用于a d o b e r a c r o b a t ，其他 很多应用领域也使用该算法。另外，该算法也被选为蜂窝数字数据包规范1 2 l 的一 部分 1 2 大纲与成果 本文的主要成果就是运用一种新的错误引入攻击方法，在一定物理条件的支 持下，能以一定的成功概率分析得出整个r c 4 的初始状态。并在此基础上，结 合k n u d s e n 等人的状态猜测攻击方法，更有效地恢复r c 4 的初始状态。 本文共分为四章； 第一章是一个总的概述。作者先从r c 4 算法的历史入手，详细介绍了该算 法出现的一些背景知识。通过这些介绍，读者可以清晰的了解到该算法从被设计 出来到进入人们视线，再到广为人知，是走过了一个漫长的过程。并可以把握 r c 4 算法客观存在的特点，以及它在商业领域里的特殊作用，同时，读者也可以 感受到r c 4 算法在整个密码学领域里所处的重要地位。接着给出了本文的大纲， 方便读者了解本文的框架和结构。 第二章作者对r c 4 算法做了一个非常详细的描述，包括参数的选取，以及 算法本身的两个组成部分：密钥调度算法( k s a ) 和伪随机序列生成算法 ( p r g a ) 。并以图形的形式对算法做了一个概括，使r c 4 算法一日了然地展现 在读者面前。接着对算法做了一个很细致的分析，包括其内部状态、状态变化函 数、输出函数、密钥调度算法等等，充分展示出他们的特点和性质。通过本章的 介绍，读者对r c 4 算法的了解会进一步加深。本章也为作者接下来的分析打下 坚实的基础。 5 1 2 大纲与成果 第三章作者从全文的研究目的角度出发，阅读大量文献，先对已有的一些研 究方法做出一定的分析，概括和总结了一些他人的研究成果，包括现阶段对r c 4 的攻击类型。寻找偏差、设计区分器也是r c a 的攻击类型中比较重要的部分， 作者在第三节对其作出一些总结，给出了这方面一个典型的例子第二字节偏 差。作者也曾尝试寻找某些偏差，并作了大量的试验去检验，虽没有成功，但在 以后的研究过程中可以继续朝这方面努力。作者在第二节对k n u d s e n 的状态猜测 攻击作出详细的介绍，并会在第四章中运用新的方法先找出一定量的初始状态 值，再结合此方法去分析寻找整个r c 4 的初始状态。 本文的第四章是全文的核j d 部分，作者在s h a m i r 及b i h a m 等人的研究思想 的启发下，提出了一种新的对r c 4 的错误引入攻击方法，即第四章的以t 为循环 参数的两个算法。算法1 介绍t = l 时的情形，通过引入错误得到一系列输出值， 把这些输出值与正确输出值进行比较，从中发现一些信息，再利用这些信息可以 以1 一o 4 6 的概率成功地找到3 个( 有时2 个) 初始状态的值：瓯【1 】、瓯印】、 晶【 】。算法2 是在算法1 的基础上进行的循环操作，成功的得到所有so 的值 需要严个输出密钥字，至多引入严个错误。当然，这两个算法都是概率型算法。 至此得出了本文的第一个研究成果。 本文第二个研究成果是利用此攻击方法与状态猜测方法相结合，达到另外一 个非常有效的分析效果。在执行1 2 0 轮算法2 的操作后，能以6 3 3 的概率成功 的确定s 0 中大约2 0 3 个位置上的值，且这些值都是正确的，其余5 3 个值待定， 如果状态猜测算法能实现，则确定这5 3 个值的复杂度仅为2 “1 3 。 6 第二章r c 4 算法 第二章r c 4 算法 r c 4 算法本身并不复杂，尽管人们对其作了大量的研究，并得出了许许多多 的攻击方法，但它在许多应用上仍然是非常安全的。本章给出了r c 4 算法的具体 描述，以及讨论了它的一些结构，同时分析了这些结构的作用。 2 1 算法的具体描述 首先我们来说明一下本文中所使用的符号所代表的意义。以表示该算法中使 用的一个字节的长度( 该算法可以根据用户需要来定义一个字节的长度，实际上， 在应用中一般都取n - 8 ) ，n 表示长度为厅的一个字节能够显示的值的总量，即 n - 2 。i s ( i , ，工，s ) 表示该算法的内部状态，f 表示一个参数，t o 1 ，。墨 表示参数f 时的状态，每一个墨中有个n 比特长度的值。f f 和工表示参数t 时 的对应的两个指针，它们指向状态s 中的值。k 表示一个密钥，是密钥k 包 含的字节数，即i - k 的比特数n 。互表示每一个t 对应的伪随机数生成器 的输出值。 r c a 是一个以分组长度以为参数的二元加法流密码体制。r c 4 的内部状态由 一个包含n 一2 。个字节的s 盒和两个n 比特字节的指针和工组成。s 盒看作 一个随机置换，s ，- ( s t 【i m - 。1 ) 。r c a 算法包含一个密钥调度算法( k e ys c h e d u l e a l g o r i t h m ) 和一个伪随机数生成算法( p s e u d or a n d o mg e n e r a t i o na l g o r i t h m ) ， 前者用可变长度的加密密钥产生密钥流生成器的初始状态品，后者根据初始状 态产生密钥流，使之与明文相异或产生密文。算法中所有的“+ ”运算都是模的 加法。 图2 - 1 给出了r c a 的密钥调度算法k s a ( k e ys c h e d u l e a l g o r i t h m ) 。它以一 个z 字长的随机初始密钥k ( 整个r c 4 的加密密钥) 作为整个算法的输入，以 一个恒等置换的s 盒开始，包含步操作：连续跑遍s 盒中的每一个位置， 7 2 2r c a 的特点与性质 随着的每一次更新， 都在墨，瞳】和k 的作用下随机产生一个新的值，每次交 换s 中和五对应的两个字，其它保持不变。经过步后k s a 产生了r c 4 的 初始状态品，然后将两个指针初始化为0 ，并输出毛一矗= 0 和5 0 。 图2 2 给出了r c 4 的伪随机数生成算法p r g a ( p s e u d or a n d o mg e n e r a t i o n a l g o r i t h m ) 。指针f f 和五的更新与k s a 相似，只是此算法中的丘不已不依赖于 初始密钥k ，然后交换置中和五对应的两个字，每次除了相互交换的两个字 之外，其他的都保持不变。这样密钥流生成器连续不断地改变s 盒中的置换，每 次改变后从s 盒中选择一个值作为输出，一轮r c a 输出一个n 比特字作为密钥 流的一个密钥字，输出的咒比特字节的序列为z - ( z ，) 二。 加密时，每个z 。和长度为忍的明文异或，产生密文。 图2 - 1 密钥调度算法 f i g 2 - ik e y s c h e d u l ea l g o r i t h m 2 2r c 4 的特点与性质 图2 - 2 伪随机数生成算法 f i g 2 - 2p s e u d or a n d o mg e n e r a t i o n k l g o r i t h m 定理1 p l ：假设我们使用下列的方法产生一个同步流密码。令七k 为密钥， l 为密钥流字母表，表示所有状态的有限集。首先，初始状态q 宅，由七按照 某种规则产生。对任意的i 1 ，状态q 由状态q 。通过如下规则决定： 8 第二章r c 4 算法 q 。， - t 童) ，这里，：x t 一另外，对任意的f 乏1 ，密钥流元素z j 按如 下的规则计算：z r ，g ( o ，七) ，这里g ：芝x k - l 。使用这种方法产生的密钥流 的周期至多医i 。 把这个定理运用到r c 4 中，令七k 为密钥，工为密钥流字母表，s 表示 所有状态的有限集。首先，初始状态s 。s 由k 按照某种规则产生。对任意的 f 每1 ，状态s ，由状态s 。通过如下规则决定：墨一，( 置。鼻) 。这里，：s 娃一s 。 另外，对任意的i 苫1 ，密钥流元素z 。按如下的规则计算：z ，s ，f s 】+ s t 【力】。 根据定理可得r c 4 密钥流的周期至多2 “( ! ) ，这正好是r c 4 内部状态的大小。 另外，r c 4 的内部状态z s ( i , ，z ，s ) 中和工指向s ，它们既控制s ，的变 化又控制输出函数。 2 2 1 内部状态i s ( , ，工，s ) 对于一个流密码，其内部状态的大小是用以衡量对其进行穷搜攻击时所需的 复杂度的上限的一个重要因素。r c a 的内部状态非常大，根据s 。，和工的不 同取值知其可能的取值为2 知( ! ) 。r c a 可以看作是一个等概率分布事件，因此， 根据熵( e n t r o p y ，这个概念来自于s h a n n o n 于1 9 4 8 年创建的信息论) 的定义， 其内部状态提供了2 n + l o g ，! 比特的信息量。当y - 8 时约为1 7 0 0 比特。这么大 的信息量使得用穷搜的方法得到r c 4 的内部状态是不可能的，因为虽然可以得 到f 时亥m j i , 的8 比特信息，但是要得到其余的1 6 9 2 比特的信息是相当困难的。 内部状态的大小也是用以确定流密码的周期大小的上限的一个重要因素。 2 2 2 状态变化函数s c f ( i , ，工，墨) 状态变化函数用以改变、工和s ，表现在图2 - 2 中的1 ，2 ，3 步。 自增加，其增加不依赖于 和s ，若只考虑r c 4 运行一2 ”轮，贝l j i , 恰 9 2 2r c 4 的特点与性质 好跑遍l s ，的每一个位置，这样，保证轮后，交换运算改变了s ，中每一个位 置的值。由于改变不依赖于别的变量，因此，可以认为是公开的。 工并不是自增加，它是加了置。瞳】后再增加。若考虑s ，是一个伪随机函数， 那么，就可以认为是以一种不可预测的方式指向s ，中不同位置的伪随机变量。 工增加不仅依赖于工- l 它还依赖于s 。【f ，】，因而，工并不是公开的信息。 第3 步交换运算是整个算法的核心，若考虑是一个置换的话，交换运算 相当于嚣换群里的乘法运算。如果没有第3 步这步交换运算，r c 4 作为一个密钥 流生成器是很不安全的。下面的定理说明了这一点。 定理2 嘲：在r c 4 的伪随机序列生成算法中，如果省略了交换操作，那么所 生成的密钥流是一个周期为2 ”1 的序列。 证明：定理2 实际上是要求证明 z f 。z f + 2 - 1 。 ( 算法中的加法都是模2 4 ) 由p r g a 算法知：z | - s 【s 【f ，】+ 研五】，而 z t + z n + l 。s s i i + 掣“】+ s j t + z “】 由于算法中的加法都是模2 “的，因此， j f + 2 4 1 24 +1+jf- j f 那么有 z t + 2 “。s s f t i + s e j , + 掣“盯。 下证j f 。i t + 2 , s + 1 由于算法中没有交换操作，墨相当与是一个常数函数，重复操作p r g a 算法中 的步骤2 ，可以递归得到： “ - - ”皑j t + 2 舌。五1 s i t + u 】 以1 由于s 是一个置换 乏答孑s 坼1 1 + 2 + + ( j v + 2 2 ) - o ( 枷d d ) ， 1 0 第二章r c 4 算法 因而， i t 。l t + 2 _ “ 故有 z t 。z t + z + 1 。得证。 2 2 3 输出函数 r c 4 的输出函数相当简单。如果我们还是把s 考虑成伪随机函数，那么我 们只要先找到两个随机数s i 】和s j 】，交换然后相加得到s 的一个新位置，把 这个位置上的值输出即可。这样多次使用s 有很多好处。首先，s 并不可能是 真正随机的，因此通过一定的方法就可以检测到它的一些偏差，这些偏差会暴露 出r c a 内部状态的一些信息，多次使用s 后一定程度上可以减少内部状态信息 的泄漏。其次，我们使用了加法运算，一个线性操作来随机选择所要输出的字， 加大了运用非线性操作后分析的难度。 2 2 4 密钥调度算法 r c a 的伪随机序列生成算法以一个特定的状态作为输入。算法进行过程中 将不再依赖k 。要满足这种要求只能寻找一个算法，让它产生依赖于k 的初始状 态瓯。作为p r g a 的输入。密钥调度算法正是满足以上要求的一个算法。 r c a 的密钥调度算法( k s a ) 以一个恒等置换开始，把指针工也置为0 。交 换函数与p r g a 类似，唯一不同的就是对每一个参数t ，工的增加不仅与s 。【f | 】 有关，还与七有关，这里k 的选择余地很大，它可以是任意长度( f 个字节) 的。 由于k s a 与p r g a 类似，因而，给对k s a 的分析工作带来了很大的方便。 值得注意的是，在k s a 结束得到p r g a 的& 后，将i 与，都置为0 ，一起 作为p r g a 的输入。这样做纯粹是出于习惯，因为j 可以是o 到2 “一1 之间的 任意值。事实上，我们可以让，等于k s a 最后一轮交换后所得到的值作为p r g a 的输入。这个值与k 具有一定的相关性的变量，从而增加了r c 4 的安全性。 1 1 2 3r c 4 的软件实现 2 3r c 4 的软件实现 r c a 的算法简单，软件容易实现。作者在m s v i l s u a lc + + 6 o 开发环境下用c 语言编写代码，实现了r c 4 算法，其初始密钥长度l 和s 盒的大小n 均可变， 代码详见附录1 。利用r c a 产生的密钥流与给定的文件逐字节相异或得到密文， 然后成功地进行了解密。 作者把r c a 算法中的两个指针， 和s 盒作为其内部状态。基于这种观 点，编写程序时把内部状态封装在一个结构体r c 4 _ s t a t e 中，密钥调度算法和 伪随机数生成算法则直接对这一结构体进行操作。由此得到的代码有利于实现我 们后面对r c a 算法进行的安全性分析。 2 4 本章小结 要对r c 4 算法进行分析，首先是要非常了解该算法。r c 4 算法包含两个指 针和工，t 一0 ，1 ，以及一个由n 一2 4 个字节组成的s 盒，它是o ，? 一1 的 一个随机置换。整个r c 4 算法由两个小算法组成：密钥调度算法( k s a ) 和伪 随机数生成算法( p r g a ) 。初始密钥的长度可以根据自己的需要任意选择，它 只跟密钥调度算法有关。当密钥调度算法执行完毕后，得到了伪随机数生成算法 的初始状态& ，在这个初始状态& 的基础上，指针和工从t o 开始，执行伪 随机数生成算法，得到一串输出密钥流z | ，z 2 ，。 文中对算法的结构作了很细致的剖析，包括内部状态、输出函数、密钥调度 算法等。这些结构特点正是密码分析者非常关心的东西，在后面的章节中提到的 对r c 4 的攻击正是围绕这些结构特点来展开的。当然，对p r g a 的攻击也很多， 尤其是错误引入攻击方面，这将在第四章着重进行分析。对r c 4 算法的软件实 现也是给第四章做好铺垫。 第三章对r c 4 的攻击研究进展 第三章对r c 4 的攻击研究进展 由于具有广泛的应用及其新颖特殊的结构，一直以来r c 4 都备受关注。在 对其攻击方面，人们也做了大量的研究，本章作者进一步观察r c 4 的结构，通 过阅读大量有关r c 4 的文献，讨论并总结了现在已有的一些攻击方法。 3 1 攻击类型 r c 4 算法属于流密码体制，虽然其输出序列的随机性很强，用一般的统计方 法已无法检验，但也不可能做到真正随机。因此，任何可以用来区分r c 4 的输 出序列与真正随机序列的攻击方法都揭示了r c a 的一种脆弱性。另外，任何能 揭示r c a 的部分密钥信息或者全部密钥信息的攻击也说明了r c 4 的一种脆弱 性。 3 1 1 密钥流区分器 理论上，一个好的流密码体制的密钥流生成器生成的密钥流应该表现出很强 随机性。如果生成的密钥流是真正随机的，那么它将构成一个一次一密密码体制。 然而，密钥流生成器生成的密钥流不可能是真正随机的，于是我们可以区分出密 钥流生成器生成的密钥流和真正随机的密钥序列。一般认为，区分一个密钥流生 成器生成的密钥流越困难，那么这一密钥流生成器就越优。因此，区分一个密钥 流生成器成为攻击它的理论模型。这种理论上的攻击模型虽然不能够找出整个流 密码的加密密钥，但是它在理论上说明了某一流密码体制的优劣。 更具体地说，区分器是指区分一串密钥流和一串真正随机序列的一种有效算 法。我们所说的区分r c 4 产生的密钥流和真正随机的密钥流就是提供了一些依 据和方法，来证实r c 4 产生的密钥流中具体哪些密钥字或密钥字中的比特表现 出不随机性。区分器是以密钥流的某些弱点为基础的，这些弱点体现出给定的密 钥流具有的不随机性，或称为偏差。区分器利用这些弱点来设计算法。 r c 4 的一个重要研究方向是其输出值的概率统计特性，特别是在区分r c 4 和真正伪随机数生成方面。考虑以下的情形：假设攻击者得到了一个可以输出数 3 1 攻击类型 据的盒子，并被告知此盒予要么执行给定密钥的r c 4 算法，输出一串密钥流， 要么只是一个随机序列库，可以直接输出一串随机密钥流。不管他用什么方法， 只要他能以大于1 尼的概率猜出盒子的性质，则可认为他攻击成功。此时，衡量 攻击方法的好坏的参数是：所需的输出密钥字及攻击的计算量。符合这种思想方 案的攻击被称为弱区分器。现在对这方面所作的研究已有很多。 g o l i c 描述了r c a 的线性统计弱点【4 j ，这个弱点表明，利用2 “。( n = 8 时为 2 “2 ) 个输出值，能够使得r c a 的输出值与随机串区分开。这个结果后来被 f l u h r e r 和m c g - r e w1 5 改进，他们分析了连续两个输出值和i - t ( modn ) 的已 知值的分布，从7 n 一8 个这样的值中发现了一些小的偏差：其中一些概率为 2 - 3 0 + 2 ”) ( 很小的正偏差) ，也有一些概率为2 “( 1 2 - ) ( 很小的负偏差) 。 他们利用信息理论方法证明了这些偏差可以用来从2 个输出值中区分r c a 和 真正随机序列。在这些分析中他们还发现了一类特殊的状态，这类特殊的状态造 成了这些偏差。这类状态可以用来找到内部状态的部分值，但是r c 4 的内部状 态非常大，所以并不能用于实际的攻击中。 另一种类型的区分器叫做强区分器。同样假设攻击者得到一个盒子，不过这 盒子里带有一个额外的控制器。如果此盒子内执行r c a 算法，那么控制器会随 时选择一个密钥，输出的是一串由新密钥产生r c 4 密钥流。如果盒子是随机序 列装置，则控制器不起任何作用，也不作任何事情。同样的，攻击者的目标是能 否以大于l 2 的概率猜测出此盒子是一个执行r c 4 算法的装置还是一个随机序列 装置。衡量参数与弱区分器相比，除了所需的输出密钥字及攻击的计算量外，还 需统计所需新的密钥字的数量。 这种方案就是通过检查由弱密钥调度引起的偏差或者影响密钥流初始化的 其他特质所带来的偏差来进行攻击的。m a n t i na n ds h i m i t l 6 1 最早提出了这方面的 攻击。他们对于r c 4 算法的第二个输出值的主要偏差进行研究发现，这个位置 为0 的概率为2 n ，这样通过梦个输出值就可以从随机字串中区别开来，这个结 论我们将在第三节给出具体描述。他们还发现了另一个相似的偏差，第一个输出 值都为0 的概率为3 2 ，而不是1 n 2 。 1 4 第三章对r c - a 的攻击研究进展 3 1 2 快速穷搜攻击 区分一个密钥流是否是真正随机的密钥流在理论上具有很好的研究意义， 但大多数这样的攻击在实际运用中都是不可能完全攻破一个密码体制。因而找出 一个密码体制的密钥或者找出它的内部状态往往更实用。密钥穷搜就是大家最容 易想到的攻击方法。但穷搜的工作量非常大，有时候根本就不可能实现。不过， 每个密码算法往往都会存在一些特性，这些特性在恢复内部状态信息的过程中起 着重要的作用，根据这些特性可以加快穷搜的速度。这类攻击我们把它称为快速 穷搜攻击。 k n u d s e n 攻击就可以说是这类攻击中最成功的攻击方法，它主要采取猜测 赋值的方式进行攻击关于这种攻击方法我们将在后面第二节给出具体的描述。 另外，这类攻击也可利用前面区分器中提到的偏差来进行。 3 1 3 相关密钥攻击和弱密钥攻击 分析一个密码体制往往可以通过分析其密钥调度来实现，也就是说，攻击者 已知一些密钥信息，通过分析发现，这些密钥表现出一定的特性，根据这些特性， 攻击者就可以找出更多的密钥，来达到攻击的目的。 这类攻击方法可分为好几种。一种是弱密钥攻击，这种攻击要求找出一类密 钥，由这类密钥输出的密钥流与其余的输出序列存在着显著的区别。另一种攻击 是相关密钥攻击，有时，由于两个不同的密钥所产生的两个不同输出密钥流之间 存在着惊人的相似性。因而，通过分析这两个密钥之间存在的联系，再根据所具 备的联系可以找出更多的密钥。 这些攻击可通过各种方法搜集密钥的信息，如：检查输出序列，看不同的序 列之间是否存在某种相似的地方；或者确认由某类密钥产生的输出序列的性质， 再或者通过取定一些密钥，每输出一串密钥流，都与这些已知的密钥进行比较， 来寻找一些与我们所求的整个初始密钥有关的信息。 针对r c 4 的这方面的攻击方法，a n d r e wr o o s 在【刀中最早找出了一类在输 出序列中可以引起某种偏差的弱密钥，即如果密钥满足 l + 脚1 】；o ，第一个输出 值以2 。”的概率等于研2 】+ 3 ，由此可以以2 4 “”的概率推出密钥字的两个字节 3 2l c = 咖n 的状态猜测攻击 ( 研o 】+ 圈r 1 】和研2 】) ，而不是2 。g r o s u l 和w a l l a c h 发现，如果密钥长度接近 2 一字节，r c 4 算法对于相关密钥攻击是脆弱的i 埘。 另外，m a n t i n 和m i r o n o v 都分析了k s a 的输出值的分布情况1 9 1 1 1 0 1 ，他们通过 计算状态中每一个位置的值的分布情况发现，值x 在k s a 过程结束时出现在状 态s 中的位置y 的概率为： 邓【y m 比p ( q x + q y r ) - 2 轧y 此处的s 表示k s a 过程最后的状态，y - 一1 一y ，p = i n ，q - 1 p ，特 别是值1 出现在位置0 的概率比随机概率1 n 高3 7 ，值2 5 5 出现在位置0 的 概率随机概率低2 6 ，并且k s a 过程结束时状态 的概率比 随机概率高2 ”倍。m a n t i n 同时指出了如何将这些分析与n 轮p r g a 之后的状态 关联起来。另外他还分析了k s a 密钥很短时的偏差。 f l u h r e r , m a n t i n 和s h a m i r 在【1 1 】中提到了k s a 的另一个弱点。他们分析了很 多种弱密钥，发现密钥的一小部分可以决定k s a 结束时状态s 的很多比特。另 外，他们还发现，p r g a 将初始内部状态中的这种模式转变成输出流的一种模式。 j e n k i n s 【1 2 】发现秘密信息 ，j ) 和公开信息( f ，z ) 的概率相关性，研j 】= f z 和，一s i 】- z 出现的概率大约是期望概率的两倍。 另外，f i n n e y 发现【1 射，满足工一+ 1 和s 【工卜1 的所有状态都应该避免，这 些状态的周期为( 一1 ) ，所以选择密钥时，产生的状态应该避免这种情形。本文 在第四章