对不同种子密钥长度的RC4算法的明文恢复攻击

苑　超，徐蜜雪，斯雪明

(信息工程大学 数学工程与先进计算国家重点实验室，郑州 450001)(*通信作者电子邮箱sxm@fudan.edu.cn)

0　引言

RC4(Rivest Cipher 4)算法是为软件实现设计的一款流密码算法，算法由密钥调度算法(Key Scheduling Algorithm, KSA)和伪随机密钥生成算法(Pseudo Random Generation Algorithm, PRGA)组成，RC4算法的实施过程[1-2]如算法1所示。本文用Zr表示PRGA算法第r轮输出，算法状态包含一个S盒即{0,1，…，255}的排列，一个公开的参数i和一个私有参数j。KSA由一个可变长度的种子密钥初始化S盒。在PRGA中，每一轮输出一个密钥流字节Zr，所有的加法都在Z/28中进行。明文字节表示为Pr，密文字节表示为Cr，所以密文字节可以表示为Cr=Pr⊕Zr。

算法1

1)KSA:

输入密钥K,密钥长度l。

步骤1fori=0 to 255 do

S[i]=i

步骤2j=0

fori=0 to 255 do

j=j+S[i]+K[imodl]

swap(S[i],S[j])

步骤3i,j=0

st0=(i,j,S)

输出st0

2)PRGA:

输入str

步骤1(i,j,S)=str

步骤2i=i+1

j=j+S[i]

swap(S[i],S[j])

Zr+1=S[S[i]+S[j]]

str+1= (i,j,S)

输出(Zr+1,str+1)。

RC4算法是使用最为广泛的流密码算法之一，在安全套接层(Security Sockets Layer, SSL)和有线等效保密协议(Wired Equivalent Privacy, WEP)中都有广泛应用，在改进版的安全传输层协议(Transport Layer Security, TLS)[3]和WPA-TKIP(Wi-Fi Protected Access-Temporal Key Integrity Protocol)[4]中也有应用。随着TLS中密码分组链接(Cipher-Block Chaining, CBC)模式出现漏洞，对RC4算法的攻击算法不断出现，尤其像BEAST[5]、LUCKY13[6]和PO(Padding Oracle)[7]攻击算法。AlFardan等[8]提到的攻击方法能够在HTTPS(Hyper Text Transfer Protocol over Secure Socket Layer)协议中接收13×230个密文情况下完全恢复cookie。Vanhoef等[9]提出的方法能够在75 h之内解密存储在用户本地终端上的数据(cookie)，而且只需9×227个密文，成功率达到了94%。Ohigashi等[10]提出了一种恢复经RC4加密的明文的全字节的攻击算法，在234个密文量的条件下，能够以接近100%的成功率恢复明文的前257字节。

本文利用t-值统计量，结合RC4算法密钥流输出序列的单字节偏差规律、双字节偏差规律给出对RC4加密的明文的前256字节的攻击方法。

1　准备知识

RC4算法的密钥流输出序列偏差规律已经有学者进行了研究[7,11]，本文用t值代替概率作为统计指标，t值的定义为：

其中：xij表示第Zi=j出现的个数，N表示样本总量，pij表示Zi=j的理论概率,qij=1-pij。

为了直观地表示这些非随机性质，本文随机选择232个不同的种子密钥，并得到由种子密钥生成的密钥流前256个字节的输出。本文探究的RC4算法采用8字节、16字节和22字节长的密钥。首先，单字节偏差规律如下所示：

1)输出密钥流第1字节中，Z1=0x81的t值最小；

2)输出密钥流第2字节中，Z2=0x00的t值最大；

3)输出密钥流第r(3≤r≤255)字节时，Zr=0x00的t值较大；

4)输出密钥流第ln(1≤n≤7)字节中，Zln=256-ln的t值较大(l为种子密钥长度)；

5)在每个输出密钥流字节，取值的t值大致呈现递增状态；

6)输出密钥流第r(3≤r≤255)字节时，Zr=r的t值较大。

图1是单字节输出偏差的图像(横坐标代表取值，纵坐标代表t值)。

2　明文恢复算法

本文考虑对RC4算法的明文恢复攻击算法。攻击需要由多个不同的种子密钥对同一明文加密得到的密文集合、每个输出字节的t值统计表以及事先经过实验统计的标准t值表。

2.1　RC4算法明文恢复攻击的核心思想

本文对RC4算法明文恢复攻击算法的研究主要由猜测确定攻击和区分攻击构成，其核心思想描述如下。

首先，本文得到由不同的种子密钥实施的RC4算法的密钥流输出集合。其中第i(1≤i≤256)字节出现频率最高的值定义为ki。同样对于由不同种子密钥加密的同一明文得到的密文集合，本文定义第i(1≤i≤256)字节出现频率最高的值定义为ci。当然，这两次运算中不同的种子密钥集合是不同的。本文认为ci⊕ki就是第i字节可能性最大的明文[12-13]。

图1　不同字节的t-值分布Fig. 1　t-value distribution of different bytes

2.2　利用单字节和双字节偏差规律恢复明文前256字节

本文给出的攻击算法主要利用了RC4算法密钥流输出序列的单字节偏差规律和双字节偏差规律[14]。其中攻击所需的密钥流输出序列的t-值表T[r][v](r=1,2,…,256,v=0,1,…,255)以及联合t-值表W[r][r-s][v][u](s=1,2,…,r-1,v,u=0,1,…,255)是由232个不同的种子密钥统计得到的。在算法实施过程中,密文字节统计数量表N[r][v](r=1,2,…,256,v=0,1,…,255)以及联合数量表M[r][r-s][v][u](s=1,2,…,r-1,v,u=0,1,…,255)是由不同的种子密钥对同一明文加密得到的统计结果。然后统计偏差累积效应，得到明文的每个字节可能性最大的取值。算法的攻击过程是先恢复明文的第1字节，然后依次恢复明文的下一字节，在恢复Pi(i=2,3,…,256)的过程中会用到已经恢复的P1,P2,…,Pi-1。

在研究的过程中，本文发现种子密钥的长度对明文的攻击结果有影响，因此本文选取种子密钥长度为8字节、16字节和22字节。分别利用算法2对经RC4算法那加密的前256字节进行攻击，选取密文量为224、226、228、231，攻击结果如图2所示。

算法2双字节正向攻击算法。

输入要恢复的明文序列字节号r;已知的明文序列字节P1,P2,…,Pr-1；密文序列集合(C1,C2,…,Cr-1,Cr)s；Zr的t值分布T[r][v],v=0,1,…,255;Zr和Zr-s的联合t值分布W[r][r-s][v][u],v,u=0,1,…,255。

步骤1计算T[r][v]的最大值，记为T[r]，此时v=Xr。

步骤3计算密文的第r(r=1,2,…,256)字节出现v(v=0,1,…,255)的个数N[r][v]。

步骤4计算密文第r(r=1,2,…,256)字节和第r-s(1≤s

步骤5计算N[r][v]的最大值，记为N[r]，此时v=Yr。

步骤7令R[r][v]=0，计算R[r][Xr⊕Yr]=R[r][Xr⊕Yr]+N[r]·T[r]。

步骤8fors=1 tor-1 do

M[r][r-s][Pr-s]·W[r][r-s][Pr-s]

步骤10Pr=argR[r]。

输出Pr。

从图2(a)的结果可以看出，在密文量为224的条件下，对三种种子密钥长度的RC4算法的恢复效果都不尽理想，且三种攻击效果相近。明文的前100字节能以超过0.3的成功率恢复。在种子密钥长度为8的情况下，第2字节、第8字节、第16字节、第24字节以及第32字节可以以100%的成功率恢复；在种子密钥长度为22的情况下，明文的第2字节、第22字节、第44字节可以以100%的成功率恢复。

从图2(b)的结果可以看出，在密文量为226的条件下，当种子密钥长度为8或16时，能以超过0.5的成功率恢复明文的前150字节明文，而且种子密钥长度为8时能完全恢复22个字节，在种子长度为16时能完全恢复15个字节，并且攻击算法能够以超过0.1的成功率恢复全部256字节。

从图2(c)的结果可以看出，在密文量为228的条件下，当种子密钥长度为8字节和16字节时，除第4字节外，攻击算法能够以100%的成功率恢复明文的前128字节;当种子密钥长度为8字节时，明文的前256字节的恢复成功率都超过了0.61。相应的，当种子密钥长度为16字节时，恢复成功率都超过0.52，当种子密钥长度为22字节时，恢复成功率都超过了0.5。

从图2(d)的结果可以看出，在密文量为231的条件下，除了第4字节外，攻击算法能够以100%的成功率恢复明文的前196字节；当种子密钥长度为8字节时，明文的前256字节的恢复成功率都超过了0.91。相应的，当种子密钥长度为16字节时，恢复成功率都超过0.87；当种子密钥长度为22字节时，恢复成功率都超过了0.81。

从上述实验结果可知，种子密钥长度的选取会影响到明文恢复攻击算法恢复经RC4算法加密的前256字节的恢复成功率，但从攻击的整体效果来看，本文给出的攻击算法对不同种子密钥长度的RC4算法加密的明文都有较好的攻击效果。

图2　不同密文量时攻击成功率结果Fig. 2　Success rate with different ciphertexts

2.3　明文恢复算法的拓展性

算法2给出的原始攻击算法具有较好的拓展性。在步骤1、2、5、6中都只是选取了每个列表中的最大值，为了进一步提升算法的攻击效果，可以取每个列表最大的前n个值,这样会在一定程度上提高明文恢复算法的成功率、减少明文恢复所需要的密文数量。当然随着n的增大，算法的复杂度也会提升。本文以种子密钥长度为16字节的RC4算法为例，分别在步骤1、2、5、6中取每个列表最大的前三个值，在密文量为228的条件下，运用算法2对经RC4算法加密的明文进行恢复得到的恢复结果如图3。从图3可以看出，利用拓展攻击算法，在同样的条件下，有34个字节的攻击成功率较原始攻击算法有所提高。

在考虑了对经不同种子密钥的RC4算法加密的明文恢复算法之后，本文又对种子密钥长度为16字节的RC4算法加密的明文的任意字节的恢复算法进行了研究，从明文的第3 072字节开始考虑，在完全套用本文的明文恢复算法时，因为密钥流偏差降低，攻击效果较经RC4算法加密的明文的前256字节的恢复效果较差，表1给出了对256个明文的攻击结果(攻击条件为231～234个经不同密钥加密同一明文得到的密文，结果显示为从3 072字节开始的第114字节到第127字节)。

表1　明文恢复攻击结果Tab. 1　Results of plaintext recovery attack

图3　原始攻击算法和拓展攻击算法效果对比Fig. 3　Comparison of basic attack and extended attack

在研究的过程中也发现，RC4算法的密钥流序列的后续字节的偏差规律较弱，单纯利用单字节偏差规律进行明文恢复的效果较差，但是RC4算法的密钥流输出序列除了单字节偏差规律外，还存在双字节偏差规律，这在后续字节的明文恢复中有更好的效果[10]，这也是后续的研究重点。

3　结语

本文利用RC4的单字节偏差和双字节偏差，对RC4算法的明文恢复攻击算法进行了改进，提出了双字节正向攻击算法，并通过实验验证了攻击算法的效果。本文给出的算法在任意长度的种子密钥下，都能够对经RC4算法加密的明文的前256字节进行恢复，在有231密文量的情况下可以对前256进行高概率恢复。与文献[10-11]给出的明文恢复算法相比，在恢复成功率相近的情况下，所需的密文量减少为原来的1/8，并且文献[10-11]只是给出了种子密钥长度为16字节时的攻击效果，而本文的算法适用于任意种子密钥长度。

在今后的研究中，一方面要进一步综合利用RC4算法密钥流输出序列的偏差规律，提高对经RC4算法加密的明文的前256字节的恢复效率,同时也要考虑对经RC4算法加密的明文的任意字节的恢复算法，以进一步提高算法的拓展性。

参考文献(References)

[1]胡亮,迟令,袁巍,等.RC4算法的密码分析与改进[J].吉林大学学报(理学版),2012,50(3):511-516. (HU L, CHI L, YUAN W, et al. Cryptanalysis and improvements of RC4 algorithm [J]. Journal of Jilin University (Science Edition), 2012, 50(3): 511-516.)

[2]侯整风,孟毛广,朱晓玲,等.RC4流密码算法的分析与改进[J].计算机工程与应用,2015,51(24):97-101. (HOU Z F, MENG M G, ZHU X L, et al. Analysis and improvement of RC4 stream cipher algorithm [J]. Computer Engineering and Applications, 2015, 51(24)： 97-101.)

[3]TSCHOFENIG H, SHEFFERY, NIR Y, et al. A flexible authentication framework for the Transport Layer Security (TLS) protocol using the Extensible Authentication Protocol (EAP) [J]. Journal for the Study of the Pseudepigrapha, 2011, 7(1): 243-243.

[4]KRISTOL D, MONTULLI L. RFC 6265, HTTP state management mechanism [S]. Geneva: IETF, 1997: 82-89.

[5]BIHAM E, CARMELI Y. Efficient reconstruction of RC4 keys from internal states [C]// FSE 2008: Proceedings of the 2008 International Workshop on Fast Software Encryption, LNCS 5086. Berlin: Springer, 2008: 270-288.

[6]ALFARDAN N J, PATERSON K J. Lucky thirteen: breaking the TLS and DTLS record protocols [C]// SP 2013: Proceedings of the 2013 IEEE Symposium on Security and Privacy. Piscataway, NJ: IEEE, 2013: 526-540.

[7]PATERSON K G, YAU A. Padding oracle attacks on the ISO CBC mode encryption standard [C]// CT-RSA 2004: Proceedings of the 2004 Cryptographers’ Track at the RSA Conference, LNCS 2964. Berlin: Springer, 2004: 305-323.

[8]ALFARDAN N J, BERNSTEIN D J, PATERSON K G, et al. On the security of RC4 in TLS [C]// Proceedings of the 22nd USENIX Conference on Security. Berkeley, CA: USENIX Association, 2013:305-320.

[9]VANHOEF M, PIESSENS F. All your biases belong to us:breaking RC4 in WPA-TKIP and TLS [C]// Proceedings of the 24th USENIX Conference on Security Symposium. Berkeley, CA: USENIX Association, 2015: 97-112.

[10]OHIGASHI T, ISOBE T, WATANABE Y et al. How to recover any byte of plaintext on RC4 [C]// SAC 2013: Proceedings of the 2013 International Conference on Selected Areas in Cryptography, LNCS 8282. Berlin: Springer, 2014: 155-173.

[11]ISOBE T, OHIGASHI T, WATANABE Y, et al. Full plaintext recovery attack on broadcast RC4 [C]// FSE 2013: Proceedings of the 2013 International Workshop on Fast Software Encryption, LNCS 8424. Berlin: Springer, 2013: 179-202.

[12]常亚勤.对流密码RC4的区分攻击[J].计算机工程,2011,37(3):119-122. (CHANG Y Q. Distinguishing attack on stream cipher RC4 [J]. Computer Engineering, 2011, 37(3): 119-122.)

[13]师国栋,康绯,顾海文.随机性测试的研究与实现[J].计算机工程,2009,35(20):145-150. (SHI G D, KANG F, GU H W. Research and implementation of randomness tests [J]. Computer Engineering, 2009, 35(20): 145-150.)

[14]王信敏,郑世慧.PRGA的初始状态与RC4算法的安全性[J].计算机工程与应用,2009,45(8):107-108. (WANG X M, ZHENG S H. PRGA’s initial state and RC4’s security [J]. Computer Engineering and Applications, 2009, 45(8): 107-108.