對不同種子密鑰長度的RC4算法的明文恢復(fù)攻擊

苑　超，徐蜜雪，斯雪明

(信息工程大學(xué) 數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，鄭州 450001)(*通信作者電子郵箱sxm@fudan.edu.cn)

0　引言

RC4(Rivest Cipher 4)算法是為軟件實(shí)現(xiàn)設(shè)計(jì)的一款流密碼算法，算法由密鑰調(diào)度算法(Key Scheduling Algorithm, KSA)和偽隨機(jī)密鑰生成算法(Pseudo Random Generation Algorithm, PRGA)組成，RC4算法的實(shí)施過程[1-2]如算法1所示。本文用Zr表示PRGA算法第r輪輸出，算法狀態(tài)包含一個(gè)S盒即{0,1，…，255}的排列，一個(gè)公開的參數(shù)i和一個(gè)私有參數(shù)j。KSA由一個(gè)可變長度的種子密鑰初始化S盒。在PRGA中，每一輪輸出一個(gè)密鑰流字節(jié)Zr，所有的加法都在Z/28中進(jìn)行。明文字節(jié)表示為Pr，密文字節(jié)表示為Cr，所以密文字節(jié)可以表示為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)和有線等效保密協(xié)議(Wired Equivalent Privacy, WEP)中都有廣泛應(yīng)用，在改進(jìn)版的安全傳輸層協(xié)議(Transport Layer Security, TLS)[3]和WPA-TKIP(Wi-Fi Protected Access-Temporal Key Integrity Protocol)[4]中也有應(yīng)用。隨著TLS中密碼分組鏈接(Cipher-Block Chaining, CBC)模式出現(xiàn)漏洞，對RC4算法的攻擊算法不斷出現(xiàn)，尤其像BEAST[5]、LUCKY13[6]和PO(Padding Oracle)[7]攻擊算法。AlFardan等[8]提到的攻擊方法能夠在HTTPS(Hyper Text Transfer Protocol over Secure Socket Layer)協(xié)議中接收13×230個(gè)密文情況下完全恢復(fù)cookie。Vanhoef等[9]提出的方法能夠在75 h之內(nèi)解密存儲(chǔ)在用戶本地終端上的數(shù)據(jù)(cookie)，而且只需9×227個(gè)密文，成功率達(dá)到了94%。Ohigashi等[10]提出了一種恢復(fù)經(jīng)RC4加密的明文的全字節(jié)的攻擊算法，在234個(gè)密文量的條件下，能夠以接近100%的成功率恢復(fù)明文的前257字節(jié)。

本文利用t-值統(tǒng)計(jì)量，結(jié)合RC4算法密鑰流輸出序列的單字節(jié)偏差規(guī)律、雙字節(jié)偏差規(guī)律給出對RC4加密的明文的前256字節(jié)的攻擊方法。

1　準(zhǔn)備知識(shí)

RC4算法的密鑰流輸出序列偏差規(guī)律已經(jīng)有學(xué)者進(jìn)行了研究[7,11]，本文用t值代替概率作為統(tǒng)計(jì)指標(biāo)，t值的定義為：

其中：xij表示第Zi=j出現(xiàn)的個(gè)數(shù)，N表示樣本總量，pij表示Zi=j的理論概率,qij=1-pij。

為了直觀地表示這些非隨機(jī)性質(zhì)，本文隨機(jī)選擇232個(gè)不同的種子密鑰，并得到由種子密鑰生成的密鑰流前256個(gè)字節(jié)的輸出。本文探究的RC4算法采用8字節(jié)、16字節(jié)和22字節(jié)長的密鑰。首先，單字節(jié)偏差規(guī)律如下所示：

1)輸出密鑰流第1字節(jié)中，Z1=0x81的t值最小；

2)輸出密鑰流第2字節(jié)中，Z2=0x00的t值最大；

3)輸出密鑰流第r(3≤r≤255)字節(jié)時(shí)，Zr=0x00的t值較大；

4)輸出密鑰流第ln(1≤n≤7)字節(jié)中，Zln=256-ln的t值較大(l為種子密鑰長度)；

5)在每個(gè)輸出密鑰流字節(jié)，取值的t值大致呈現(xiàn)遞增狀態(tài)；

6)輸出密鑰流第r(3≤r≤255)字節(jié)時(shí)，Zr=r的t值較大。

圖1是單字節(jié)輸出偏差的圖像(橫坐標(biāo)代表取值，縱坐標(biāo)代表t值)。

2　明文恢復(fù)算法

本文考慮對RC4算法的明文恢復(fù)攻擊算法。攻擊需要由多個(gè)不同的種子密鑰對同一明文加密得到的密文集合、每個(gè)輸出字節(jié)的t值統(tǒng)計(jì)表以及事先經(jīng)過實(shí)驗(yàn)統(tǒng)計(jì)的標(biāo)準(zhǔn)t值表。

2.1　RC4算法明文恢復(fù)攻擊的核心思想

本文對RC4算法明文恢復(fù)攻擊算法的研究主要由猜測確定攻擊和區(qū)分攻擊構(gòu)成，其核心思想描述如下。

首先，本文得到由不同的種子密鑰實(shí)施的RC4算法的密鑰流輸出集合。其中第i(1≤i≤256)字節(jié)出現(xiàn)頻率最高的值定義為ki。同樣對于由不同種子密鑰加密的同一明文得到的密文集合，本文定義第i(1≤i≤256)字節(jié)出現(xiàn)頻率最高的值定義為ci。當(dāng)然，這兩次運(yùn)算中不同的種子密鑰集合是不同的。本文認(rèn)為ci⊕ki就是第i字節(jié)可能性最大的明文[12-13]。

圖1　不同字節(jié)的t-值分布Fig. 1　t-value distribution of different bytes

2.2　利用單字節(jié)和雙字節(jié)偏差規(guī)律恢復(fù)明文前256字節(jié)

本文給出的攻擊算法主要利用了RC4算法密鑰流輸出序列的單字節(jié)偏差規(guī)律和雙字節(jié)偏差規(guī)律[14]。其中攻擊所需的密鑰流輸出序列的t-值表T[r][v](r=1,2,…,256,v=0,1,…,255)以及聯(lián)合t-值表W[r][r-s][v][u](s=1,2,…,r-1,v,u=0,1,…,255)是由232個(gè)不同的種子密鑰統(tǒng)計(jì)得到的。在算法實(shí)施過程中,密文字節(jié)統(tǒng)計(jì)數(shù)量表N[r][v](r=1,2,…,256,v=0,1,…,255)以及聯(lián)合數(shù)量表M[r][r-s][v][u](s=1,2,…,r-1,v,u=0,1,…,255)是由不同的種子密鑰對同一明文加密得到的統(tǒng)計(jì)結(jié)果。然后統(tǒng)計(jì)偏差累積效應(yīng)，得到明文的每個(gè)字節(jié)可能性最大的取值。算法的攻擊過程是先恢復(fù)明文的第1字節(jié)，然后依次恢復(fù)明文的下一字節(jié)，在恢復(fù)Pi(i=2,3,…,256)的過程中會(huì)用到已經(jīng)恢復(fù)的P1,P2,…,Pi-1。

在研究的過程中，本文發(fā)現(xiàn)種子密鑰的長度對明文的攻擊結(jié)果有影響，因此本文選取種子密鑰長度為8字節(jié)、16字節(jié)和22字節(jié)。分別利用算法2對經(jīng)RC4算法那加密的前256字節(jié)進(jìn)行攻擊，選取密文量為224、226、228、231，攻擊結(jié)果如圖2所示。

算法2雙字節(jié)正向攻擊算法。

輸入要恢復(fù)的明文序列字節(jié)號r;已知的明文序列字節(jié)P1,P2,…,Pr-1；密文序列集合(C1,C2,…,Cr-1,Cr)s；Zr的t值分布T[r][v],v=0,1,…,255;Zr和Zr-s的聯(lián)合t值分布W[r][r-s][v][u],v,u=0,1,…,255。

步驟1計(jì)算T[r][v]的最大值，記為T[r]，此時(shí)v=Xr。

步驟3計(jì)算密文的第r(r=1,2,…,256)字節(jié)出現(xiàn)v(v=0,1,…,255)的個(gè)數(shù)N[r][v]。

步驟4計(jì)算密文第r(r=1,2,…,256)字節(jié)和第r-s(1≤s

步驟5計(jì)算N[r][v]的最大值，記為N[r]，此時(shí)v=Yr。

步驟7令R[r][v]=0，計(jì)算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)的結(jié)果可以看出，在密文量為224的條件下，對三種種子密鑰長度的RC4算法的恢復(fù)效果都不盡理想，且三種攻擊效果相近。明文的前100字節(jié)能以超過0.3的成功率恢復(fù)。在種子密鑰長度為8的情況下，第2字節(jié)、第8字節(jié)、第16字節(jié)、第24字節(jié)以及第32字節(jié)可以以100%的成功率恢復(fù)；在種子密鑰長度為22的情況下，明文的第2字節(jié)、第22字節(jié)、第44字節(jié)可以以100%的成功率恢復(fù)。

從圖2(b)的結(jié)果可以看出，在密文量為226的條件下，當(dāng)種子密鑰長度為8或16時(shí)，能以超過0.5的成功率恢復(fù)明文的前150字節(jié)明文，而且種子密鑰長度為8時(shí)能完全恢復(fù)22個(gè)字節(jié)，在種子長度為16時(shí)能完全恢復(fù)15個(gè)字節(jié)，并且攻擊算法能夠以超過0.1的成功率恢復(fù)全部256字節(jié)。

從圖2(c)的結(jié)果可以看出，在密文量為228的條件下，當(dāng)種子密鑰長度為8字節(jié)和16字節(jié)時(shí)，除第4字節(jié)外，攻擊算法能夠以100%的成功率恢復(fù)明文的前128字節(jié);當(dāng)種子密鑰長度為8字節(jié)時(shí)，明文的前256字節(jié)的恢復(fù)成功率都超過了0.61。相應(yīng)的，當(dāng)種子密鑰長度為16字節(jié)時(shí)，恢復(fù)成功率都超過0.52，當(dāng)種子密鑰長度為22字節(jié)時(shí)，恢復(fù)成功率都超過了0.5。

從圖2(d)的結(jié)果可以看出，在密文量為231的條件下，除了第4字節(jié)外，攻擊算法能夠以100%的成功率恢復(fù)明文的前196字節(jié)；當(dāng)種子密鑰長度為8字節(jié)時(shí)，明文的前256字節(jié)的恢復(fù)成功率都超過了0.91。相應(yīng)的，當(dāng)種子密鑰長度為16字節(jié)時(shí)，恢復(fù)成功率都超過0.87；當(dāng)種子密鑰長度為22字節(jié)時(shí)，恢復(fù)成功率都超過了0.81。

從上述實(shí)驗(yàn)結(jié)果可知，種子密鑰長度的選取會(huì)影響到明文恢復(fù)攻擊算法恢復(fù)經(jīng)RC4算法加密的前256字節(jié)的恢復(fù)成功率，但從攻擊的整體效果來看，本文給出的攻擊算法對不同種子密鑰長度的RC4算法加密的明文都有較好的攻擊效果。

圖2　不同密文量時(shí)攻擊成功率結(jié)果Fig. 2　Success rate with different ciphertexts

2.3　明文恢復(fù)算法的拓展性

算法2給出的原始攻擊算法具有較好的拓展性。在步驟1、2、5、6中都只是選取了每個(gè)列表中的最大值，為了進(jìn)一步提升算法的攻擊效果，可以取每個(gè)列表最大的前n個(gè)值,這樣會(huì)在一定程度上提高明文恢復(fù)算法的成功率、減少明文恢復(fù)所需要的密文數(shù)量。當(dāng)然隨著n的增大，算法的復(fù)雜度也會(huì)提升。本文以種子密鑰長度為16字節(jié)的RC4算法為例，分別在步驟1、2、5、6中取每個(gè)列表最大的前三個(gè)值，在密文量為228的條件下，運(yùn)用算法2對經(jīng)RC4算法加密的明文進(jìn)行恢復(fù)得到的恢復(fù)結(jié)果如圖3。從圖3可以看出，利用拓展攻擊算法，在同樣的條件下，有34個(gè)字節(jié)的攻擊成功率較原始攻擊算法有所提高。

在考慮了對經(jīng)不同種子密鑰的RC4算法加密的明文恢復(fù)算法之后，本文又對種子密鑰長度為16字節(jié)的RC4算法加密的明文的任意字節(jié)的恢復(fù)算法進(jìn)行了研究，從明文的第3 072字節(jié)開始考慮，在完全套用本文的明文恢復(fù)算法時(shí)，因?yàn)槊荑€流偏差降低，攻擊效果較經(jīng)RC4算法加密的明文的前256字節(jié)的恢復(fù)效果較差，表1給出了對256個(gè)明文的攻擊結(jié)果(攻擊條件為231～234個(gè)經(jīng)不同密鑰加密同一明文得到的密文，結(jié)果顯示為從3 072字節(jié)開始的第114字節(jié)到第127字節(jié))。

表1　明文恢復(fù)攻擊結(jié)果Tab. 1　Results of plaintext recovery attack

圖3　原始攻擊算法和拓展攻擊算法效果對比Fig. 3　Comparison of basic attack and extended attack

在研究的過程中也發(fā)現(xiàn)，RC4算法的密鑰流序列的后續(xù)字節(jié)的偏差規(guī)律較弱，單純利用單字節(jié)偏差規(guī)律進(jìn)行明文恢復(fù)的效果較差，但是RC4算法的密鑰流輸出序列除了單字節(jié)偏差規(guī)律外，還存在雙字節(jié)偏差規(guī)律，這在后續(xù)字節(jié)的明文恢復(fù)中有更好的效果[10]，這也是后續(xù)的研究重點(diǎn)。

3　結(jié)語

本文利用RC4的單字節(jié)偏差和雙字節(jié)偏差，對RC4算法的明文恢復(fù)攻擊算法進(jìn)行了改進(jìn)，提出了雙字節(jié)正向攻擊算法，并通過實(shí)驗(yàn)驗(yàn)證了攻擊算法的效果。本文給出的算法在任意長度的種子密鑰下，都能夠?qū)?jīng)RC4算法加密的明文的前256字節(jié)進(jìn)行恢復(fù)，在有231密文量的情況下可以對前256進(jìn)行高概率恢復(fù)。與文獻(xiàn)[10-11]給出的明文恢復(fù)算法相比，在恢復(fù)成功率相近的情況下，所需的密文量減少為原來的1/8，并且文獻(xiàn)[10-11]只是給出了種子密鑰長度為16字節(jié)時(shí)的攻擊效果，而本文的算法適用于任意種子密鑰長度。

在今后的研究中，一方面要進(jìn)一步綜合利用RC4算法密鑰流輸出序列的偏差規(guī)律，提高對經(jīng)RC4算法加密的明文的前256字節(jié)的恢復(fù)效率,同時(shí)也要考慮對經(jīng)RC4算法加密的明文的任意字節(jié)的恢復(fù)算法，以進(jìn)一步提高算法的拓展性。

參考文獻(xiàn)(References)

[1]胡亮,遲令,袁巍,等.RC4算法的密碼分析與改進(jìn)[J].吉林大學(xué)學(xué)報(bào)(理學(xué)版),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]侯整風(fēng),孟毛廣,朱曉玲,等.RC4流密碼算法的分析與改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,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的區(qū)分攻擊[J].計(jì)算機(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ī)性測試的研究與實(shí)現(xiàn)[J].計(jì)算機(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的初始狀態(tài)與RC4算法的安全性[J].計(jì)算機(jī)工程與應(yīng)用,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.