对RC4算法的明文恢复算法研究.docx

对RC4算法的明文恢复算法研究徐蜜雪 苑超 斯雪明（信息工程大学数学工程与先进计算国家重点实验室，郑州，450001）摘要：随着RC4算法输出密钥流偏差规律的不断暴露，RC4算法面临极大的安全挑战。2013年AlFardan等人利用RC4算法输出密钥流偏差规律，提出了一种明文恢复算法。在他们的算法中，利用13230个不同种子密钥加密同一明文得到的密文，可以以100%的成功率恢复明文的前256字节。同年，为了恢复经RC4算法加密的明文任意字节，Ohigashi等人提出了猜测确定攻击算法，利用235个不同种子密钥加密同一明文得到的密文，可以以100%的成功率恢复明文的任意字节，但是当密文量小于235时，恢复成功率下降明显。本文用t值统计量代替传统概率统计，充分利用现有偏差规律，改进了算法的猜测部分，提出了一种更有效的猜测确定攻击算法。利用234个不同种子密钥加密同一明文得到的密文，可以以接近100%的概率恢复明文的任意字节，当密文量为233时，能以超过98%的概率恢复任意字节。关键词：RC4算法；流密码；明文恢复攻击；偏差规律Abstract: With the exposing of biases of the output key streams of RC4, it is confronted with great security challenges. In 2013, AlFardan et al proposed a plaintext recovery attack using single-byte and double-byte biases. Given 13230 ciphertexts encrypted by different keys, the first 256 bytes can be recovered with probability 1. The same year, Ohigashi et al proposed a guess and determine attack to recover the plaintexts encrypted by RC4. Given 235 ciphertexts encrypted by different keys, any byte of a plaintext can be recovered with probability close to one but when the amount of ciphertexts is less than 235, the success probability decreases rapidly. In this paper, t value is used to replace the traditional probability, and the existing bias is fully utilized to modify the guess phase of the algorithm above, then a more effective guess and determine attack is proposed. Given 234 ciphertexts encrypted by different keys, any byte of a plaintext can be recovered with probability close to one. And given 233 ciphertexts encrypted by different keys, any byte of a plaintext can be recovered with probability over 0.98.Keywords: RC4 algorithm; stream cipher; plaintext recover; biases1 引言RC4算法是Rivest在1987设计的密钥长度可变的流密码算法。由于简单高效，常用于协议中，例如有线等效保密(WEP)、无线网卡(WPA)、安全套接字层(SSL)以及传输层安全(TLS)等。随着越来越多的密钥流偏差问题被发现，RC4算法的使用受到一定限制，但是RC4算法在某些协议中还未被完全废止。针对RC4算法的攻击方法有线性化攻击方法1，对RC4算法简化版本的攻击2、初始状态恢复攻击3和引入错误攻击4等。2013年伦敦大学的AlFardan等人提出明文恢复攻击5，能够在HTTPS协议中接收13230个密文情况下，100%得恢复前256字节。同年，Ohigashi和Isobe等人为了恢复经RC4算法加密的明文任意字节，提出猜测确定攻击算法67，当密文量为235时，可以100%的恢复所有字节对应的明文。本文第2节给出RC4算法，t值统计量定义，以及单字节、双字节、ABSAB偏差。第3节给出典型有效的攻击算法，包括AlFardan等人提出的明文恢复攻击算法， Ohigashi和Isobe等人提出的猜测确定攻击算法。第4节给出改进后的对前256字节的SD（单、双字节）明文恢复算法，第5节给出改进后的对任意字节进行猜测确定的明文恢复算法。第6节对工作进行了总结，并介绍未来研究方向。2 准备知识2.1 RC4算法RC4加密算法由密钥调度算法KSA和密钥流序列生成算法PRGA组成。以S盒元素长度等于8比特为例，算法步骤如下：（1）密钥调度算法（KSA）:Step1 初始化S盒 Step2 初始化指数 ; Step3 混淆S盒 , .Step4 输出S盒（2）密钥流序列生成算法（PRGA）:Step1初始化指数 ;Step2输入明文流 Step3对应明文输出密文流 .其中St指当前状态下的S盒；i和j是指针变量，常用来表示S盒的下标；KeySt表示当前输出的密钥；Pt表示明文第t字节；Zt表示当前时刻输出的密文。2.2 t值统计量在引言提到的攻击方法中，对偏差规律总结时通常使用频率来表明偏差大小。但是，对于一些比较弱的偏差规律，使用频率无法明显区分。所以，本文采用t值统计量对偏差进行描述。t值的定义如下： (1)Xij表示第i轮输出密钥流值为j的频数。N表示统计的样本总量，pi表示第i轮输出密钥流为j的理论概率，qij表示第i轮输出密钥流不为j的理论概率，即qij=1-pij。2.3单字节偏差RC4算法没有基于严格的数学理论，有学者通过对输出密钥流的分析发现了不随机现象。为了更加直观反映不随机现象，我们将232个不同的种子密钥代入RC4算法，对算法产生的输出密钥流进行统计。由于种子密钥长度可能会对最终的偏差规律产生影响，我们分别选用长度为8字节、16字节、22字节的种子密钥进行实验。以16字节为例，得到的单字节偏差规律如下：(1) 在Z1中, 值为129的t值最小；(2) 在Z2中, 值为0的t值最大；(3) 在Zr(3r255)中, 值为0的t值较大8；(4) 在Z16n (1n7)中, 值为256-16n的t值较大；(5) 除了第一个输出字节外, 其他字节t值呈递增状态；(6) 在Zr(3r255)中, 值为r的t值较大。种子密钥长度不同，呈现的规律也有所不同，下面选取几个典型密钥流字节的t值分布图（横坐标代表取值，纵坐标代表t值），来说明不同长度种子密钥对输出偏差的影响。图1 Z1的t值分布图图2 Z2的t值分布图图3 Z8的t值分布图图4 Z16的t值分布图图5 Z22的t值分布图根据上图可以发现，规律(1)在种子密钥长度为22字节时不出现；规律(4)根据种子密钥长度的不同而发生改变，变为在Zln (ln255)中, 值为256-ln的t值较大。2.4双字节偏差由Fluhrer和McGrew总结的双字节偏差9如下：表1 FM偏差取值对条件概率(0,0)i=12-16(1+2-7)(0,0)i1,2552-16(1+2-8)(0,1)i0,12-16(1+2-8)(0,i+1)i0,2552-16(1-2-8)(i+1,255)i254r12-16(1+2-8)(129,129)i=2r22-16(1+2-8)(255,i+1)i1,2542-16(1+2-8)(255,i+2)i1,252r22-16(1+2-8)(255,0)i=2542-16(1+2-8)(255,1)i=2552-16(1+2-8)(255,2)i=0,12-16(1+2-8)(255,255)i254r52-16(1-2-8)上表中第1列表示接连两个输出密钥流的取值对；第2列的i表示PRGA中的指针变量，r表示第一列取值对的第一个元素对应的位置；第3列是输出为取值对的概率。2.5 ABSAB偏差ABSAB偏差10 中A和B指的是输出密钥流的取值，S表示一段未知的短密钥流。S的长度用G来表示，则有如下结果成立： (2)根据上述公式可知，随着短密钥流长度G的增大，偏差出现的概率变小。3 攻击现状现在针对RC4算法在同一明文用不同密钥流重复加密的情况下，已经出现了一些具备实用价值的攻击算法。下面将简要描述这些算法的实现与效果。3.1 单、双字节明文恢复攻击AlFardan等人利用单字节偏差恢复明文，模拟RC4算法在WPA中的实际应用，获得N次会话下的前40字节的密文，对密文进行偏差统计，找出密文中第i字节偏差最大的值Zi。 单字节偏差统计时第i字节t值最大对应的取值记为Ti。将Zi与Ti异或，即可得到明文Pi。在226次会话条件下，可以以50%的概率恢复前40字节。运用双字节偏差恢复明文，在单字节偏差攻击基础上，利用连续两字节的偏差，增加后续字节恢复概率。能够在接收13230个密文情况下，100%得恢复前256字节3.2 IOWM攻击Isobe等人在2013年提出了任意字节明文恢复攻击算法，该算法包含两个阶段：分别是字节恢复阶段和对后续字节接连恢复阶段。在字节恢复阶段，前257字节可以用累积偏差来恢复，累积偏差包括之前提到的所有单字节偏差、双字节偏差以及第257字节取值为0对应概率偏大的偏差。在给定密文量为232的条件下，能够以80%的概率恢复前257字节。在对后续字节接连恢复的阶段，从第258字节开始，需要有效利用前257字节已经恢复出的明文。在后续字节恢复算法中用到了ABSAB偏差。如下等式将会在攻击算法中用到： (3)如果确实出现了ABSAB偏差，那么等式(3)就可以写作： (4)为了使攻击更加有效，可以将短密钥流长度G不同的ABSAB偏差累积起来。不妨假设已经猜测出第r、r+1、r+2字节的明文，则当ABSAB偏差中第一个A字节对应位置为r，短密钥长度为1时，等式右边为；当第一个A字节对应位置为r+1，短密钥长度为0时，等式右边为。可以通过累计两种偏差的方式更有效地猜测确定的值。定义为短密钥流最大长度，即。假设前257字节通过累计偏差已经被确定。接下来基于k个密文流序列C1, C2, . . . , Ck用连续算法恢复。恢复算法具体如下：（1） 根据加密每次产生的密文流做概率表TcountrG (,)，概率表中的值为对应的t值。（2） 令r = 258，（3） 通过等式(4)来恢复明文：对，利用TcountrG和已经猜测过的值计算，并对应累加到概率表Tmerger中，得到对应的概率；通过已知的，抽取Tmerger中前8字节刚好为的部分组成概率表Tguessr，得到可能明文对应的概率。其中取值最高对应的即为。（4） 增加r的值，如果，终止该算法，否则转到第（3）步。改进版本：这些攻击都是基于1257字节已经恢复的条件。如果密钥流前面产生的字节被舍弃，那么文献6中提到的算法将失效。因此丢弃RC4算法密钥流前面的字节可以作为一种RC4算法应用的改进方法。 Mironov认为11应该丢弃RC4算法生成密钥流的前512字节或者768字节，而且说明如果丢弃3072字节将是安全的。3.3 OIWM攻击Ohigashi等人在2013年提出了使用猜测确定的明文恢复攻击算法。算法目的是恢复，攻击算法的概况如下：（1） 首先猜测的值。（2） 通过表1第一行的FM00偏差，恢复前x项明文。（3） 通过已经恢复的明文猜测新一轮第r字节的值。（4） 如果，就将其作为正确明文的候选，否则排除。算法的攻击思想是，如果明文猜测正确，那么的概率较高，猜测错误时由于使用的偏差不同，导致的概率较低。4对前256字节的明文恢复攻击本节给出对前256字节的明文恢复攻击算法，能够对经RC4算法加密的前256字节明文进行恢复，与3.1节相比，攻击效果更好，使用的密文量更少。4.1 攻击算法我们给出由前至后恢复的SD（single-double）算法主要用到了RC4算法输出密钥流的单字节偏差和双字节偏差规律，其中攻击所需的t值表Trv，以及联合t值表Trr-svu， ，是从232个不同种子密钥加密产生的密钥流中得来。算法实施过程中密文字节统计数量表Nrv，以及联合统计数量表Nrr-svu，是由不同种子密钥对同一明文加密产生的密文流中得来的。根据统计偏差的累积效应，得到明文的每个字节可能性最大的取值。算法的攻击过程是先恢复明文的第一字节，然后依次恢复明文的下一字节，在恢复的过程中会用到已经恢复的，恢复算法如下表所示：表2 SD明文恢复算法SD明文恢复算法输入: r, /*被攻击的字节*/ P1,P2,Pr-1, /*已知明文字节*/ (C1,C2,Cr-1,Cr) /*C(1),C(2),C(k)中的密文字节*/ Trv, /* Zr=v的t值*/ Trr-svu, /* Zr=v和Zr-s=u的t值*/输出: Pr1: 对于所有 v0,255，将 Trv 的最大值存入表 Tr，值记作Xr； 将Trr-svu 的最大值存入表 Trr-su, 值记作 .2: 表Nrv 表示Cr =v的个数，Nrr-svu ，（1sr） 表示 Cr =v且Cr-s =u的个数3: 对于所有v0,255，将Nrv的最大值存入表 Nr ，值记作Yr ；将Nrr-svu 的最大值存入表 Nrr-su ，值记作。4: 另Rrv=0, 计算RrXrYr= RrXrYr +Nr.Tr, 5: 对0s256进行循环 6: 7: 通过SD明文恢复算法可以有一定概率得恢复由RC4算法加密的明文前256字节。4.2攻击结果本文分别利用224,226,228 和231个密文，通过我们的明文恢复算法对经RC4算法加密的明文的前256字进行攻击，得到恢复成功率如下。图6 前256字节在密文量为224时的成功率根据图6, 在密文量为224的条件下，前100字节以超过0.3的成功率被恢复。当种子密钥长度为8时，第2、8、16、24、32字节可以完全恢复；种子密钥长度为16字节时，第2、16、32、48字节可以完全恢复；种子密钥长度为22时，第2、22、44字节可以完全恢复。图7 前256字节在密文量为226时的成功率根据图7, 在密文量为226的条件下，当种子密钥长度为8或者16时，前40字节以超过0.9的成功率被恢复。当种子密钥长度为8时，有22个位置可以被完全恢复，长度为16时，有15个位置可以被完全恢复。图8 前256字节在密文量为228时的成功率根据图8, 在密文量为228的条件下，当种子密钥长度为8或者16时，前128字节中除了第4字节，其他字节都以概率1被恢复。前256字节在种子密钥长度为8时以0.61的概率恢复，当长度为16时以0.52的概率恢复，当长度为22时以0.5的概率恢复。图9 前256字节在密文量为231时的成功率根据图9, 在密文量为231的条件下，当种子密钥长度为8或者16时，前196字节中除了第4字节，其他字节都以概率1被恢复。前256字节在种子密钥长度为8时以0.91的概率恢复，当长度为16时以0.87的概率恢复，当长度为22时以0.81的概率恢复。实验发现，攻击算法使用不同种子密钥长度时，对成功率有一定影响，但是同时也说明我们的算法对不同种子密钥长度都有效。5 对任意字节的猜测确定攻击本节提出了一种改进的猜测确定攻击算法来恢复由RC4算法加密的明文。与IOWN攻击算法和OIWN攻击算法相比，攻击算法更加充分得利用了单字节偏差、双字节偏差和ABSAB偏差。5.1 攻击算法为了应对丢弃密钥流前面字节的改进方法，我们给出交叉验证的猜测确定攻击算法，其中有两个子算法：第一个子算法是自后向前依次恢复明文的SDBTF算法，在给定已知明文的情况下，恢复；第二个子算法是利用ABSAB偏差自前向后恢复明文的算法，在已知明文的情况下恢复。第一个子算法如表3所示，第二个子算法如表4所示，进行交叉验证的猜测确定攻击算法如表5所示。表3 SDBTF算法SDBTF算法输入: r, g /*被攻击字节 */ Pr, /*已知明文字节*/ (Cr-g,Cr-1,Cr) /*C(1),C(2),C(k)中的密文字节*/ Tiv, /* Zi=v的t值*/ Tijvu, /* Zi=v和Zj=u的t值(r-gir-1,xjr)*/输出: 1: 对于所有 v0,255，将 Tiv 的最大值存入表 Ti，值记作Xi； 将Trr-svu 的最大值存入表 Tiju, 值记作 .2: 表Niv 表示Ci =v的个数，Nijvu ， 表示 Ci =v且Cj =u的个数, ijr.3: 对于所有v0,255，将Niv 的最大值存入表 Ni ，值记作Yi ；将Nijvu 的最大值存入表 Nijv ，值记作。4: 另Riv=0,计算RiXiYi= RiXiYi+ Ni.Ti, 5: 对r-g-1i r且ij r+1进行循环 6: 7: Pi=argRi通过运用了单字节和双字节偏差的SDBTF算法，我们可以在已知Pr条件下求解未知明文字节。表4 ABSABFTB算法ABSABFTB算法输入: r /*被攻击字节Pr,*/ /*已知明文字节*/ /*C(1),C(2),C(k)中的密文字节*/ GM, /* ABSAB 偏差短密钥流最大长度*/输出: Pr,1:对0GGM进行循环TrGv意思是对应攻击字节为r，短密钥长度为G，关于v= (Cr-3-G| Cr-2-G)(Cr-1| Cr)的t值表。2:利用TrGv,和已知明文，合并计算u=的t值分布Tru，与对应。3: 利用T ru和已知的得到的t值分布Tguessru。4: 5: 通过ABSABFTB算法我们可以在已知条件下求解未知明文字节Pr。我们对于RC4算法的任意字节明文恢复需要首先用SD算法，得到Pr可能的w个候选。然后用SDBTF攻击算法接连求解未知明文字节，不妨将的候选个数也设为w。为了排除错误的Pr，用ABSABFTB攻击算法在已知条件下求解明文字节Pr。如果，将其作为正确明文的候选，否则排除。具体攻击算法如下：表5 猜测确定攻击算法恢复任意字节的猜测确定攻击算法输入: r /*被攻击字节Pr,*/ C(1),C(2),C(k)/*被k个不同密钥加密的密文流序列*/ GM, /* ABSAB 偏差短密钥流最大长度*/Tiv, /* Zi=v的t值*/ Tii-svu, /* Zi=v和Zi-s=u的t值(r-GM-3ir,1si-r+GM+3)*/输出: Pr,1: 选取候选个数w，将计算的Trv表中w个最大值对应的下标v作为Pselect集合中的元素。2：对PrPselect做循环根据C(1),C(2),C(k)，用SDBTF算法恢复出GM+3个字节的明文。再根据C(1),C(2),C(k)，已经被猜测出的明文，用ABSABFTB算法恢复出Pr。如果PrPr，则Pr将会从中Pselect移除，否则继续做循环。3: 如果最后Pselect中只剩一个候选明文，那么算法输出该明文，否则算法失败。通过猜测确定攻击算法，我们可以在一定概率下恢复出由RC4算法加密的任意字节正确明文。5.2 攻击结果我们实验是基于丢弃前3072的RC4算法。为了度量算法正确率，不妨假设第128字节（从3073字节处开始计数）通过SD算法被正确恢复。在给定参数GM =11的情况下，利用表6算法恢复，密文量从229 到234，每种密文量下的实验次数为256次，得到的实验结果将在表6中呈现。为了直观看到结果，图10中分字节展示了的恢复成功率。表6 猜测确定攻击算法成功率229230231232233234P1140.05860.06640.13280.39450.99611.0000P1150.05860.06640.12110.37500.98831.0000P1160.05080.06640.08200.34380.98051.0000P1170.04690.05470.09380.35160.98051.0000P1180.05080.06640.04690.34380.98051.0000P1190.00780.00780.00780.27730.96481.0000P1200.03130.05470.08200.21090.98051.0000P1210.03130.04300.04690.30080.86721.0000P1220.00780.00390.00780.25780.93751.0000P1230.04690.05470.08200.23430.90231.0000P1240.00390.00390.00780.30080.87591.0000P1250.00780.04300.04690.25390.85941.0000P1260.00390.00390.00780.21480.90231.0000P1270.00390.00390.00390.34380.83401.0000由表6可知，在234的密文量下，(P114,P127)的恢复成功率都达到了100%。图10 猜测确定攻击成功率根据图10可知，在已知一个字节明文的情况下，密文量为233时恢复其他字节的概率在0.9左右，第3.3节和3.4节提到的算法成功概率约为0.3，改进后的算法恢复正确率为原算法的3倍。在进行算法之前还需要由SD算法恢复3072字节之后的第128字节。我们的恢复环境为CPU单线程 (Intel(R)Core(TM) i7-5500U CPU 2.40 GHz)，总恢复时间为200h。在密文量从232 到235，实验次数为256次的情况下，给出了第128字节恢复的成功概率如表8所示。表7对128字节的恢复成功率232233234235P1280.01170.12890.93361.0000经分析，我们的算法具有高扩展性，比如ABSABFTB攻击算法中候选个数w可以灵活选取，w选取的值越大，算法成功概率越高；其次在SDBTF攻击算法t值表中取最大值可以改进为取最大的几个值，算法成功率随取值个数的增加而增高。6 总结本文给出了RC4算法密钥流输出的单字节、双字节、ABSAB偏差。在单一明文由不同种子密钥生成的密钥流加密情况下，改进了两种明文恢复算法：一种是针对前256字节的SD明文恢复算法，另一种是针对任意字节的猜测确定明文恢复算法。第一种算法与文献6的算法相比恢复效率更高，在密文量为231、种子密钥长度为16字节时，以0.87的高概率恢复前256字节，而文献6在密文量为232、种子密钥长度为16字节时，以0.5的概率恢复前256字节。第二种方法可以对丢弃前面字节密钥流的RC4加密算法进行有效攻击，与文献7相比，攻击需要密文量更少，在密文量为234时，可以以概率1恢复任意字节。在未来工作中，一方面，我们将会继续探索RC4输出流密钥的偏差，不断改进对明文恢复攻击效率；另一方面，我们将会探索更多实际情境下对RC4算法的破解。参考文献1 Jovan. Dj.Goli, Linear Statistical Weakness of Alleged RC4 Keystream Generator.1997.2 Lars R. Knudsen, Willi Meier, Bart Preneel, Vincent Rijmen, and Sven Verdoolaege, Analysis Methods for (Alleged) RC4,1998.3 Giancola G, De Nardis L, Di B