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

苑　超，徐蜜雪，斯雪明

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

0　引言

RC4(Rivest Cipher 4)算法是為軟件實現(xiàn)設計的一款流密碼算法，算法由密鑰調度算法(Key Scheduling Algorithm, KSA)和偽隨機密鑰生成算法(Pseudo Random Generation Algorithm, PRGA)組成，RC4算法的實施過程[1-2]如算法1所示。本文用Zr表示PRGA算法第r輪輸出，算法狀態(tài)包含一個S盒即{0,1，…，255}的排列，一個公開的參數(shù)i和一個私有參數(shù)j。KSA由一個可變長度的種子密鑰初始化S盒。在PRGA中，每一輪輸出一個密鑰流字節(jié)Zr，所有的加法都在Z/28中進行。明文字節(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)中都有廣泛應用，在改進版的安全傳輸層協(xié)議(Transport Layer Security, TLS)[3]和WPA-TKIP(Wi-Fi Protected Access-Temporal Key Integrity Protocol)[4]中也有應用。隨著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個密文情況下完全恢復cookie。Vanhoef等[9]提出的方法能夠在75 h之內解密存儲在用戶本地終端上的數(shù)據(cookie)，而且只需9×227個密文，成功率達到了94%。Ohigashi等[10]提出了一種恢復經RC4加密的明文的全字節(jié)的攻擊算法，在234個密文量的條件下，能夠以接近100%的成功率恢復明文的前257字節(jié)。

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

1　準備知識

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

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

為了直觀地表示這些非隨機性質，本文隨機選擇232個不同的種子密鑰，并得到由種子密鑰生成的密鑰流前256個字節(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é)時，Zr=0x00的t值較大；

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

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

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

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

2　明文恢復算法

本文考慮對RC4算法的明文恢復攻擊算法。攻擊需要由多個不同的種子密鑰對同一明文加密得到的密文集合、每個輸出字節(jié)的t值統(tǒng)計表以及事先經過實驗統(tǒng)計的標準t值表。

2.1　RC4算法明文恢復攻擊的核心思想

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

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

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

2.2　利用單字節(jié)和雙字節(jié)偏差規(guī)律恢復明文前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個不同的種子密鑰統(tǒng)計得到的。在算法實施過程中,密文字節(jié)統(tǒng)計數(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)計結果。然后統(tǒng)計偏差累積效應，得到明文的每個字節(jié)可能性最大的取值。算法的攻擊過程是先恢復明文的第1字節(jié)，然后依次恢復明文的下一字節(jié)，在恢復Pi(i=2,3,…,256)的過程中會用到已經恢復的P1,P2,…,Pi-1。

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

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

輸入要恢復的明文序列字節(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計算T[r][v]的最大值，記為T[r]，此時v=Xr。

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

步驟4計算密文第r(r=1,2,…,256)字節(jié)和第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字節(jié)能以超過0.3的成功率恢復。在種子密鑰長度為8的情況下，第2字節(jié)、第8字節(jié)、第16字節(jié)、第24字節(jié)以及第32字節(jié)可以以100%的成功率恢復；在種子密鑰長度為22的情況下，明文的第2字節(jié)、第22字節(jié)、第44字節(jié)可以以100%的成功率恢復。

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

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

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

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

圖2　不同密文量時攻擊成功率結果Fig. 2　Success rate with different ciphertexts

2.3　明文恢復算法的拓展性

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

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

表1　明文恢復攻擊結果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ī)律進行明文恢復的效果較差，但是RC4算法的密鑰流輸出序列除了單字節(jié)偏差規(guī)律外，還存在雙字節(jié)偏差規(guī)律，這在后續(xù)字節(jié)的明文恢復中有更好的效果[10]，這也是后續(xù)的研究重點。

3　結語

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

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

參考文獻(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的區(qū)分攻擊[J].計算機工程,2011,37(3):119-122. (CHANG Y Q. Distinguishing attack on stream cipher RC4 [J]. Computer Engineering, 2011, 37(3): 119-122.)

[13]師國棟,康緋,顧海文.隨機性測試的研究與實現(xiàn)[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].計算機工程與應用,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.