RC4密鑰流序列統(tǒng)計(jì)漏洞分析

劉鶯迎

【摘要】 在大數(shù)據(jù)的條件下，利用黑盒統(tǒng)計(jì)法對(duì)RC4密鑰流序列進(jìn)行統(tǒng)計(jì)，尋找密鑰流序列的不隨機(jī)現(xiàn)象。針對(duì)不同長(zhǎng)度密鑰，統(tǒng)計(jì)了隨機(jī)生成密鑰和固定位置遍歷密鑰兩種情形下密鑰流序列的分布特點(diǎn)。對(duì)統(tǒng)計(jì)結(jié)果作出曲線圖，詳細(xì)分析了RC4密鑰流序列的非隨即現(xiàn)象。

【關(guān)鍵詞】 RC4算法 密鑰流序列 統(tǒng)計(jì) 偏差

一、RC4算法的相關(guān)介紹

序列密碼作為一種計(jì)算速度快，實(shí)現(xiàn)簡(jiǎn)單的密碼，在網(wǎng)絡(luò)密碼系統(tǒng)中得到了廣泛的應(yīng)用，例如RC4、A5、snow、seal等加密算法。尤其是美國(guó)密碼學(xué)家設(shè)計(jì)的RC4加密算法，憑借其簡(jiǎn)單、高效的特點(diǎn)，目前仍然在許多領(lǐng)域中被應(yīng)用，如安全協(xié)議標(biāo)準(zhǔn)SSL協(xié)議、TLS協(xié)議、WEP協(xié)議、基于Wi-Fi保護(hù)接入中的WPA協(xié)議等。RC4算法也被集成于Microsoft Windows、Lotus Notes、Apple AOCE、Oracle Secure SQL中。另外，該算法也被選為蜂窩數(shù)字?jǐn)?shù)據(jù)包規(guī)范的一部分。

二 、預(yù)備知識(shí)

2.1 RC4算法流程

RC4由密鑰調(diào)度算法和密鑰流序列生成算法兩部分組成。RC4的密鑰長(zhǎng)度可變，變化范圍是[1，255]。給定一個(gè)密鑰，偽隨機(jī)數(shù)生成器接受密鑰，混淆用與產(chǎn)生密鑰流序列的S盒。在算法的第二部分，S盒也會(huì)隨著加密過(guò)程發(fā)生變化。RC4加密算法是按字節(jié)產(chǎn)生密鑰流序列，并將密鑰流序列逐個(gè)字節(jié)與明文異或，加密得到密文。由于異或運(yùn)算的對(duì)合性，解密過(guò)程與加密過(guò)程一致。

Z ： 當(dāng)前時(shí)刻輸出的密文；

i， j： 指針變量。

RC4算法首先執(zhí)行密鑰調(diào)度算法，對(duì)長(zhǎng)度為256的S盒初始化，將0到255的互不重復(fù)的元素依次裝入S盒，再利用密鑰key將S盒打亂，得到算法第二部分S盒的初始狀態(tài)。其次執(zhí)行密鑰流序列生成算法，將S打亂，再隨機(jī)輸出盒中某個(gè)位置的狀態(tài)。每輸出一個(gè)字節(jié)的密鑰，S盒的狀態(tài)發(fā)生變化。

2.2統(tǒng)計(jì)方法

1. 基于大數(shù)據(jù)的黑盒統(tǒng)計(jì)法

關(guān)于統(tǒng)計(jì)方法，有許多種，如簡(jiǎn)單統(tǒng)計(jì)、復(fù)雜統(tǒng)計(jì)、簡(jiǎn)單找重、組合找重等。在本文的統(tǒng)計(jì)過(guò)程中，使用到的是簡(jiǎn)單統(tǒng)計(jì)法，即在用大量密鑰流序列做大量實(shí)驗(yàn)的基礎(chǔ)上，對(duì)單個(gè)數(shù)值進(jìn)行頻數(shù)或者頻率等的統(tǒng)計(jì)。

2. 漏洞分析方法

在漏洞分析上采用黑盒分析法，即用大量不同的初始密鑰產(chǎn)生大量密鑰流序列，用不同的統(tǒng)計(jì)方法對(duì)密鑰流序列進(jìn)行頻率和t-值等進(jìn)行統(tǒng)計(jì)，并根據(jù)條件和需要做相應(yīng)圖表，觀察統(tǒng)計(jì)結(jié)果，憑借經(jīng)驗(yàn)等去判斷序列的不隨機(jī)性。

三、RC4密鑰流序列的統(tǒng)計(jì)偏差尋找

3.1偏差統(tǒng)計(jì)的理論基礎(chǔ)

在前期的研究工作中，若遍歷四字節(jié)的初始密鑰，數(shù)據(jù)量為232，即42億的種子密鑰，由每個(gè)密鑰種子生成密鑰流序列的前32或者40個(gè)字節(jié)。

3.2密鑰流序列的非隨機(jī)性和規(guī)律

1.隨機(jī)選取密鑰種子

從上面五種情況的折線圖中，在隨機(jī)選取232個(gè)密鑰的情況下，有以下五個(gè)明顯的單字節(jié)非隨機(jī)性：

（1）前40個(gè)字節(jié)的統(tǒng)計(jì)結(jié)果中，每個(gè)字節(jié)從0x00到0xFF的t-值隨著該字節(jié)取值的變大而波動(dòng)上升；

（2）前40個(gè)字節(jié)的每個(gè)字節(jié)中，取值為0x00的t-值很大，同時(shí)0x00出現(xiàn)的頻率遠(yuǎn)大于其隨機(jī)概率1/256；

（3）第1個(gè)字節(jié)中，取值為0x00和0x81的t-值偏小，約為-20，且隨著取值的變化，t-值不隨逐漸增大，而是呈s-型變化的；

（4）第2個(gè)字節(jié)中，實(shí)驗(yàn)數(shù)據(jù)表明，0x00出現(xiàn)的頻率是其理論隨機(jī)概率的兩倍，t值非常高，在數(shù)據(jù)量為232的基礎(chǔ)上，其t-值達(dá)到4000多倍；

（5）第3個(gè)字節(jié)中，取值為0x00和0x83的t-值偏大，

2. 固定32位遍歷種子密鑰

在本次實(shí)驗(yàn)中，僅對(duì)密鑰長(zhǎng)度為128bits和256bis的情況作了研究，可以發(fā)現(xiàn)以下幾點(diǎn)不隨機(jī)性：

（1）對(duì)于前40個(gè)字節(jié)的每一個(gè)字節(jié)，隨著各個(gè)字節(jié)取值的增大，其t-值分布依然有增大的趨勢(shì)，但不如隨機(jī)選取密鑰的增長(zhǎng)趨勢(shì)明顯；

（2）對(duì)每個(gè)字節(jié)，其t-值普遍比隨機(jī)選取種子密鑰時(shí)大，在相同數(shù)據(jù)量的情況下，固定位置遍歷密鑰的t-值約為隨機(jī)選取密鑰的2倍；

（3）前40個(gè)字節(jié)的每個(gè)字節(jié)中，取值為0x00的情況和隨機(jī)選取密鑰一致，t-值很大，同時(shí)0x00出現(xiàn)的頻率大于其隨機(jī)概率1/256；

參 考 文 獻(xiàn)

[1]Nadhem J.AlFardan，DanielJ.Bernstein，Kenneth G.Paterson，Bertram Poettering，Jacob C.N.Schuldt， On the Security of RC4 in TLS ， 2013；

[2]Scott R. Fluhrer and David A. McGrew，Statistical Analysis of the Alleged RC4 Keystream Generator，170 West Tasman Drive， San Jose， 2000；

[3]Itsik Mantin and Adi Shamir，A Practical Attack on Broadcast RC4，Compute-r Science Department， The Weizmann Institute， 2001；