亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

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

        2018-04-12 05:51:07徐蜜雪斯雪明
        計(jì)算機(jī)應(yīng)用 2018年2期
        關(guān)鍵詞:明文密文字節(jié)

        苑 超,徐蜜雪,斯雪明

        (信息工程大學(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)包含一個S盒即{0,1,…,255}的排列,一個公開的參數(shù)i和一個私有參數(shù)j。KSA由一個可變長度的種子密鑰初始化S盒。在PRGA中,每一輪輸出一個密鑰流字節(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個密文情況下完全恢復(fù)cookie。Vanhoef等[9]提出的方法能夠在75 h之內(nèi)解密存儲在用戶本地終端上的數(shù)據(jù)(cookie),而且只需9×227個密文,成功率達(dá)到了94%。Ohigashi等[10]提出了一種恢復(fù)經(jīng)RC4加密的明文的全字節(jié)的攻擊算法,在234個密文量的條件下,能夠以接近100%的成功率恢復(fù)明文的前257字節(jié)。

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

        1 準(zhǔn)備知識

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

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

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

        1)輸出密鑰流第1字節(jié)中,Z1=0x81的t值最?。?/p>

        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é)輸出偏差的圖像(橫坐標(biāo)代表取值,縱坐標(biāo)代表t值)。

        2 明文恢復(fù)算法

        本文考慮對RC4算法的明文恢復(fù)攻擊算法。攻擊需要由多個不同的種子密鑰對同一明文加密得到的密文集合、每個輸出字節(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個不同的種子密鑰統(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),得到明文的每個字節(jié)可能性最大的取值。算法的攻擊過程是先恢復(fù)明文的第1字節(jié),然后依次恢復(fù)明文的下一字節(jié),在恢復(fù)Pi(i=2,3,…,256)的過程中會用到已經(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],此時v=Xr。

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

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

        步驟5計(jì)算N[r][v]的最大值,記為N[r],此時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時,能以超過0.5的成功率恢復(fù)明文的前150字節(jié)明文,而且種子密鑰長度為8時能完全恢復(fù)22個字節(jié),在種子長度為16時能完全恢復(fù)15個字節(jié),并且攻擊算法能夠以超過0.1的成功率恢復(fù)全部256字節(jié)。

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

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

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

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

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

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

        在考慮了對經(jīng)不同種子密鑰的RC4算法加密的明文恢復(fù)算法之后,本文又對種子密鑰長度為16字節(jié)的RC4算法加密的明文的任意字節(jié)的恢復(fù)算法進(jìn)行了研究,從明文的第3 072字節(jié)開始考慮,在完全套用本文的明文恢復(fù)算法時,因?yàn)槊荑€流偏差降低,攻擊效果較經(jīng)RC4算法加密的明文的前256字節(jié)的恢復(fù)效果較差,表1給出了對256個明文的攻擊結(jié)果(攻擊條件為231~234個經(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é)時的攻擊效果,而本文的算法適用于任意種子密鑰長度。

        在今后的研究中,一方面要進(jìn)一步綜合利用RC4算法密鑰流輸出序列的偏差規(guī)律,提高對經(jīng)RC4算法加密的明文的前256字節(jié)的恢復(fù)效率,同時也要考慮對經(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.

        猜你喜歡
        明文密文字節(jié)
        一種針對格基后量子密碼的能量側(cè)信道分析框架
        一種支持動態(tài)更新的可排名密文搜索方案
        No.8 字節(jié)跳動將推出獨(dú)立出口電商APP
        基于模糊數(shù)學(xué)的通信網(wǎng)絡(luò)密文信息差錯恢復(fù)
        No.10 “字節(jié)跳動手機(jī)”要來了?
        奇怪的處罰
        簡談MC7字節(jié)碼
        奇怪的處罰
        四部委明文反對垃圾焚燒低價競爭
        久久无码人妻一区二区三区午夜| 日韩AV无码一区二区三不卡| 国产成人精品蜜芽视频| 国产在线一区二区三区香蕉| 一本大道熟女人妻中文字幕在线| 国产精品沙发午睡系列990531| 久久久久亚洲AV无码专| 亚洲av性色精品国产| 亚洲中文字幕舔尻av网站| 亚洲人成影院在线观看| 无码一区二区三区AV免费换脸| 二区三区视频在线观看| 丁香婷婷激情视频在线播放| 蜜桃视频无码区在线观看| 精品免费福利视频| 国产在线精彩自拍视频| 亚洲在线视频免费视频| 日躁夜躁狠狠躁2001| 妞干网中文字幕| 久久精品蜜桃美女av| 最近中文字幕国语免费| 亚洲gv白嫩小受在线观看| 国产一级r片内射免费视频| 在线免费看91免费版.| 亚洲啪av永久无码精品放毛片| 日韩免费一区二区三区在线| 富婆叫鸭一区二区三区| 亚洲欧洲免费无码| 久久无码人妻精品一区二区三区 | 96精品免费视频大全| 亚洲中文字幕一区精品| 日本阿v片在线播放免费| 亚洲欧洲高潮| 蜜桃av一区在线观看| 国产18禁黄网站免费观看| 免费无码又爽又刺激聊天app| 国产亚洲精品hd网站| 被灌醉的日本人妻中文字幕| 免费人妻精品一区二区三区| 人妻无码一区二区在线影院| 亚洲少妇一区二区三区老|