摘? 要: 以Fluhrer， S.， Mantin， I.， Shamir， A.提出的KSA(Key Schedule Algorithm)攻擊為基礎(chǔ),提出了一種改進(jìn)的KSA攻擊方法。與Fluhrer等提出的KSA攻擊相比,新方法具有更高攻擊效率。利用這種方法,成功地實(shí)現(xiàn)了針對(duì)802.11網(wǎng)絡(luò)鏈路層" title="鏈路層">鏈路層安全協(xié)議——WEP的攻擊,成功地恢復(fù)出了原加密密鑰。本文詳細(xì)地描述了這種攻擊,同時(shí)針對(duì)802.11網(wǎng)絡(luò)存在的安全問題,提出了一些安全建議。

　　關(guān)鍵詞: 有線等效加密? 密鑰調(diào)度算法? 偽隨機(jī)數(shù)" title="隨機(jī)數(shù)">隨機(jī)數(shù)發(fā)生器

?

　　隨著802.11標(biāo)準(zhǔn)的制定以及相關(guān)軟硬件技術(shù)的逐漸成熟,802.11無線局域網(wǎng)產(chǎn)品的使用愈來愈廣泛。其通信范圍廣、數(shù)據(jù)傳輸速率高的特點(diǎn)使802.11同藍(lán)牙等協(xié)議一起成為無線局域網(wǎng)組網(wǎng)的可選協(xié)議之一,廣泛應(yīng)用于辦公、會(huì)議等場(chǎng)合。這些場(chǎng)合中所使用的PC卡絕大多數(shù)提供了一種稱為WEP(Wired Equivalent Privacy)的加密協(xié)議。

　　WEP便于管理,每塊802.11卡具有一個(gè)加密密鑰(key)。在實(shí)際使用中,大多數(shù)設(shè)備均使用同一個(gè)加密密鑰,包括接入點(diǎn)AP(Access Point)。802.11通過WEP來防止對(duì)局域網(wǎng)的非法訪問,為用戶提供與傳統(tǒng)有線局域網(wǎng)保密程度相當(dāng)?shù)耐ㄐ怒h(huán)境。

WEP中采用的RC4算法是一種對(duì)稱流加密算法。由于RC4算法的加密或解密速度均非常快,又提供了相當(dāng)?shù)膹?qiáng)度,所以得到了廣泛應(yīng)用。其最重要的應(yīng)用就是SSL(Security Socket Layer)加密套接字協(xié)議層和WEP。

　　針對(duì)RC4算法及其弱點(diǎn),人們進(jìn)行了許多研究,其中大多數(shù)為理論研究,并不具有實(shí)際意義。直到最近,Borisov、Goldberg and Wagner指出^[1]:在WEP中,由于沒有明確規(guī)定IV(Initialization Vectors)的使用方法,有些廠商簡(jiǎn)單地在每次初始化時(shí)將IV置零,然后加一。這種不當(dāng)使用導(dǎo)致密鑰重用的概率大增,可用于簡(jiǎn)單的密碼分析攻擊。另外,作者還指出,由于IV的可用空間太小,將不可避免地導(dǎo)致相同的密鑰重用問題。

　　Fluhrer、Mantin and Shamir 描述了一種針對(duì)WEP采用的RC4算法的被動(dòng)密文攻擊方法^[2]。作者針對(duì)RC4的狀態(tài)初始化,提出了一種KSA攻擊方法。揭示了WEP存在的嚴(yán)重漏洞。

　　本文在文獻(xiàn)[2]提出的KSA攻擊方法的基礎(chǔ)上,提出了一種更為高效的攻擊方法。并在實(shí)際環(huán)境中,成功地實(shí)施了針對(duì)WEP的攻擊。實(shí)驗(yàn)結(jié)果表明,與文獻(xiàn)[2]中提出的KSA攻擊相比,本文提出的方法具有效率高、所需數(shù)據(jù)量更小的優(yōu)點(diǎn)。

1 RC4算法

1.1 RC4概述

　　RC4算法屬于二進(jìn)制異或同步流密碼算法" title="密碼算法">密碼算法,其密鑰長(zhǎng)度可變,在WEP中,密鑰長(zhǎng)度可選擇128bit或64bit。

　　RC4算法由偽隨機(jī)數(shù)產(chǎn)生算法PRGA(Pseudo Random Generation Algorithm)和密鑰調(diào)度算法KSA(Key Schedule Algorithm)兩部分構(gòu)成。其中PRGA為RC4算法的核心,用于產(chǎn)生與明文相異或的偽隨機(jī)數(shù)序列；KSA算法的功能是將密鑰映射為偽隨機(jī)數(shù)發(fā)生器的初始化狀態(tài),完成RC4算法的初始化。

　　RC4算法實(shí)際上是一類以加密塊大小為參數(shù)的算法。這里的參數(shù)n為RC4算法的字長(zhǎng)。在WEP中,n=8。

RC4算法的內(nèi)部狀態(tài)包括2ⁿ個(gè)字的狀態(tài)表和兩個(gè)大小為一個(gè)字的計(jì)數(shù)器。狀態(tài)表,也稱為狀態(tài)盒(S-box,以下用S表示),用來保存2ⁿ個(gè)值的轉(zhuǎn)置狀態(tài)。兩個(gè)計(jì)數(shù)器分別用i和j表示。

　　KSA算法和PRGA算法可表示如下:

　　KSA:????????????????????????????????? PRGA:

?????? Initialization:????????????????? ? 　Initialization:

????????????? For i=0 to 2n-1???????????? ? 　　i=0,j=0

????????????? ?? S[i]=i??????? ? 　　　　 　Generation Loop:

????????????? j=0???????????????????????????　??i=i+1

　　Scrambling:???????????????????????????????　j=j+S[i]

????????????? For? i=0 to 2n-1????????????　　　Swap(S[i],S[j])

????????????? j=j+S[i]+K[i mod l]?? 　　　　　　Output z=S[S[i]+S[j]]

?????? ?????? Swap(S[i],S[j])

　　其中,l為密鑰的長(zhǎng)度。

1.2 RC4算法安全性能分析

　　仔細(xì)研究RC4的算法流程,不難發(fā)現(xiàn):

　　狀態(tài)盒S從一個(gè)統(tǒng)一的2ⁿ個(gè)字的轉(zhuǎn)置開始,對(duì)其進(jìn)行的唯一操作是交換。S始終保存2ⁿ個(gè)字的某個(gè)轉(zhuǎn)置狀態(tài),而且轉(zhuǎn)置隨著時(shí)間而更新。這也是RC4算法的強(qiáng)度所在。算法的內(nèi)部狀態(tài)存儲(chǔ)在M=n2ⁿ+2ⁿ比特中,由于S為一個(gè)轉(zhuǎn)置,此狀態(tài)大約保存了log₂(2ⁿ!)+2n≈1700bit的信息。

　　狀態(tài)盒的初始化狀態(tài)僅僅依賴于加密密鑰K,因此,若已知加密密鑰就可完全破解RC4。加密密鑰完全且唯一確定了偽隨機(jī)數(shù)序列,相同的密鑰總是產(chǎn)生相同的序列。另外,RC4算法本身并不提供數(shù)據(jù)完整性校驗(yàn)功能,此功能的實(shí)現(xiàn)必須由其他方法實(shí)現(xiàn)(例如WEP中的數(shù)據(jù)完整性校驗(yàn)向量,即ICV)。

　　下面考慮一些特殊的攻擊模型,這些模型均與要討論的RC4的安全問題密切相關(guān)。

　　RC4算法屬于同步流密碼算法中的一種,由于其偽隨機(jī)數(shù)發(fā)生器PRNG(Pseudo Random Number Gernerator)的輸出完全由加密密鑰確定,所以對(duì)于一個(gè)設(shè)計(jì)良好的流密碼算法必須滿足兩個(gè)條件:輸出的每個(gè)比特應(yīng)該依賴于所有加密密鑰的所有比特；而且,任意一個(gè)比特或者某些比特同加密密鑰之間的關(guān)系應(yīng)該極其復(fù)雜。

　　上述第一個(gè)條件意味著輸出的每個(gè)比特依賴于加密密鑰所有比特的值。密鑰中任意比特值的改變均有1/2的幾率影響到輸出的每一個(gè)比特。如果滿足此條件,那么,破解此加密需要嘗試所有可能的密鑰值,輸出值同加密密鑰之間幾乎不存在任何聯(lián)系。

　　如果上面的" title="面的">面的條件得不到滿足,那么就可被利用來對(duì)其進(jìn)行攻擊。舉例來說,假設(shè)輸出的某8個(gè)比特僅僅依賴于加密密鑰的某8個(gè)比特,那么就可以簡(jiǎn)單地進(jìn)行對(duì)此8比特密鑰的所有可能值進(jìn)行嘗試,并與實(shí)際輸出相比較獲取此8比特密鑰的值,這樣就大大降低了窮舉攻擊所需的計(jì)算量。

　　因此,如果輸出以比較高的概率由密鑰的某些比特所確定,那么此信息就可被利用來對(duì)此流密碼進(jìn)行攻擊。

第二個(gè)條件意味著即使已知兩個(gè)加密密鑰之間的聯(lián)系,也無法得出PRNG輸出之間的聯(lián)系。此信息也可用來降低窮舉攻擊的搜索空間,從而導(dǎo)致加密強(qiáng)度的降低。

　　RC4算法屬于二進(jìn)制異或流密碼,相同的密鑰總是產(chǎn)生相同的PRNG輸出。為解決密鑰重用的問題,WEP中引入了初始化向量IV(Initialization Vector)。初始化向量為一隨機(jī)數(shù),每次加密時(shí)隨機(jī)產(chǎn)生。初始化向量以某種形式與原密鑰相組合,作為此次加密的加密密鑰。由于IV并不屬于密鑰的一部分,所以無須保密,多以明文傳輸。雖然初始化向量的使用很好地解決了密鑰重用的問題,然而,Fluhrer， S等人在文獻(xiàn)[2]中指出:初始化向量的使用將導(dǎo)致嚴(yán)重的安全隱患。

　　下面詳細(xì)地討論本文所提出的KSA攻擊方法。

2 KSA攻擊

　　本文著重討論WEP中所采用的RC4算法,即前附加初始化向量IV的RC4算法。

2.1 KSA

　　考慮KSA,注意到唯一影響狀態(tài)表的是交換操作。因此，狀態(tài)表的每個(gè)元素至少交換一次(盡管有可能同它自己交換)。假設(shè)j是一個(gè)均勻分布" title="均勻分布">均勻分布的隨機(jī)數(shù)，那么，考慮狀態(tài)表中某一個(gè)特殊元素，在所有初始化期間j都不指向此元素的概率為：

　　P=(255/256)∧255≈37%

　　(指數(shù)為255是因?yàn)楫?dāng)index2和counter相等時(shí)可以忽略)

　　這意味著有37%的概率某一特定元素在初始化期間僅交換一次。

　　由此可看出：

　　給定一密鑰長(zhǎng)度K(bytes)，如果E

　　那么由RC4的KSA 算法可看出僅K[0]....K[E-1]，和K[E]影響它。這只是近似估算，因?yàn)閕ndex2不可能是均勻分布。

　　為利用上述結(jié)果，需要確定狀態(tài)表最可能的值。因?yàn)槊總€(gè)元素至少交換一次(當(dāng)counter指向它時(shí))，所以有必要對(duì)交換可能帶來的影響加以考慮。交換是令人討厭的非線性操作，難于分析。然而當(dāng)處理狀態(tài)表前幾個(gè)元素時(shí)，某個(gè)具體元素有很高的概率沒有參與它前面的幾次交換，因此還保留初始值(S[X]=X)。

相似地,僅處理狀態(tài)表中前幾個(gè)元素時(shí),即i比較小時(shí),S[j]有很高的概率等于j。因此,可以得到:

　　狀態(tài)表中元素S[E](E比較小時(shí))最可能的值為:

　　注意,本文中兩個(gè)元素操作均為模256操作。

　　基于以上分析,可以計(jì)算出狀態(tài)表中各個(gè)元素滿足B的概率。為統(tǒng)計(jì)狀態(tài)表中元素滿足上式的概率,采用8比特RC4算法進(jìn)行實(shí)驗(yàn)。下面為100000次實(shí)驗(yàn)中S[E]中前48個(gè)元素滿足上式的概率:

?

????結(jié)果表明,經(jīng)過KSA后,狀態(tài)表中前面的一些元素實(shí)際值與用B所預(yù)測(cè)出的值強(qiáng)相關(guān)。

2.2 弱密鑰

　　首先定義i_t,j_t分別為KSA算法經(jīng)過t步后相應(yīng)的兩個(gè)計(jì)數(shù)器的值,S_t為KSA經(jīng)t步后狀態(tài)盒的狀態(tài)。從其流程可以看出,PRNG首字節(jié)輸出僅僅依賴于狀態(tài)盒S中的三個(gè)值:S[1]、S[S[1]]和S[S[1]+S[S[1]]]。如果此三個(gè)值為已知,那么就可以完全確定PRNG的首字節(jié)輸出。

　　KSA經(jīng)過i步操作后(i>1)，設(shè)S_i[1]=X,S[X]=Y,假設(shè)j為均勻分布的隨機(jī)數(shù),那么S[1],S[X],S[X+Y]均不參與剩余交換的概率約為e-3≈0.05,此時(shí)RC4的首字節(jié)輸出為S[X+Y]。　

　　假設(shè)IV的長(zhǎng)度為I個(gè)字節(jié),IV附加在密鑰Key前面組成加密密鑰K,即K=IV|Key,且我們已知K中前B個(gè)字節(jié)的值(初始化時(shí)B=0)。如果KSA經(jīng)過I+B-1次迭代后滿足:

　　S_I+B-1[1]

　　S_I+B-1[1]+S_I+B-1 [S_I+B-1[1]]=I+B

　　考慮第I+B次迭代:

?????? i_I+B=I+B

?????? j_I+B=j_I+B-1+S[I+B]+K[(I+B) mod L]

?????? 交換SI+B-1[iI+B],SI+B-1 [jI+B]:

　　S_I+B [i_I+B]=S_I+B-1 [j_I+B] ,

　　S_I+B [j_I+B]=S_I+B-1 [i_I+B]

　　S_I+B [i_I+B]=S_I+B-1 [j_I+B] ,

　　S_I+B [j_I+B]=S_I+B-1 [i_I+B]

　　在滿足上述條件的情況下,S[1],S[S[1]]和S[S[1]+S[S[1]]]這三個(gè)元素以很高的概率(大于5%)均不參與KSA剩余的交換操作,也即首字節(jié)輸出以很高的概率滿足:

　　這種情況下,通過重建KSA,能夠成功地從首字節(jié)輸出中獲取加密密鑰中某個(gè)特定字節(jié)K[I+B]的信息:

　　表示元素Out在狀態(tài)表中的位置。

　　從前面分析可以看出,在滿足S_I[1]I[1]+S_I[S_I[1]]=I+B條件的情況下,可以準(zhǔn)確重建K[B]的概率大于5%,遠(yuǎn)遠(yuǎn)大于1/256。這樣通過收集足夠數(shù)量的滿足上述條件的數(shù)據(jù)包,就可以成功地重建密鑰K[B]。同理,在成功重建K[B]的基礎(chǔ)上,就可以用類似的方法重建所有密鑰。

　　具體算法如下:

2.3 算法改進(jìn)

　　可以看出,以上的攻擊方法中,所有關(guān)于K[I+B]的預(yù)測(cè)均是基于其前面所有密鑰(K[0],...,K[I+B-1])已知的基礎(chǔ)上。換言之,前面的預(yù)測(cè)錯(cuò)誤將直接導(dǎo)致K[I+B]的錯(cuò)誤預(yù)測(cè)。那么能否從K[I+B]中推測(cè)出K[0],...,K[I+B-1]的信息?

考慮KSA,如果經(jīng)過I次迭代后,滿足:

?????? II[1]+S_I[S_I[1]]=I+B≤L

?????? S_I[1]≤I

　　則S_I[1]和S_I[S_I[1]]以很大的概率((254/256)L-I≈1)不參與第I步與第L步之間的迭代。同時(shí),j以很大的概率不指向S_I[I],...,S_I[I+B]這幾個(gè)元素。

　　即:

　　S_I[1]=S_I+B-1[1]????????????????? i_L-1=L-1???????

　　j_I+B-1=j_I+S_I[I]+...+S_I[I+B-1]+K[I]+...+K[I+B-1]

　　考慮第L步:

　　i_I+B=I+B??????? j_I+B=j_I+B-1+S_I[I+B]+K[I+B]

　　交換S[i],S[j],則SI+B[I+B]=SI+B-1[jI+B]。

　　如果S_I+B-1[j_I+B],S_I+B-1[1]和S_I+B-1[S_I+B-1[1]]不參與剩余的交換操作,那么輸出為:

　　Out=S_I+B-1[j_I+B]

　　而由前面的分析可以看出,S_I+B-1[j_I+B]以很高的概率(約為1)沒有參與前面的交換操作,也即S_I+B-1[j_I+B]=j_I+B。由此可知

　　Out=j_I+S_I[I]+...+S_I[I+B-1]+K[I]+...+K[I+B-1]+S_I[I+B]+K[I+B]

　　利用上述關(guān)系可以成功地推出不同K字節(jié)之間的關(guān)系,從而加速攻擊。

　　另外,由于密鑰管理時(shí)密鑰需要手工輸入,所以絕大多數(shù)情況下,密鑰只是ASIIC字符。這樣大大減小了密鑰的搜索空間,提高了攻擊效率。

3 實(shí)驗(yàn)結(jié)果與結(jié)論

　　為對(duì)上述算法進(jìn)行驗(yàn)證,進(jìn)行了實(shí)驗(yàn)。實(shí)驗(yàn)中所采用的硬件為朗訊的ORiNOCO無線網(wǎng)卡,操作系統(tǒng)為Redhat7.1。實(shí)驗(yàn)結(jié)果表明,本文所提出的算法平均在收集100萬到200萬加密數(shù)據(jù)包的情況下,成功地恢復(fù)出了原加密密鑰。與Fluhrer，S.、Mantin，I.、 Shamir， A.所提出的KSA攻擊需要400萬到600萬數(shù)據(jù)包相比,攻擊效率有了很大提高。

　　基于以上分析,不難看出:現(xiàn)有WEP加密中存在重大的安全漏洞,這種情況并不因加密密鑰長(zhǎng)度的增加而得到改善,所以在WEP2中同樣存在。為此,建議現(xiàn)有的802.11用戶:

　　.假設(shè)802.11鏈路層并不提供安全措施；

　　.為保障網(wǎng)絡(luò)通信的安全,使用IPSEC或者SSH等高層加密手段；

　　.把所有通過802.11接入的用戶置于防火墻之外。

　　.經(jīng)常更換密鑰,同時(shí)針對(duì)密鑰應(yīng)盡量采用某種HASH算法,避免采用全為ASIIC字符的加密密鑰。

?

參考文獻(xiàn)

1 BORISOV， N.， GOLDBERG， I.， and WAGNER， D. Intercepting mobile communications：The insecurity of 802.11.

MOBICOM, 2001 (2001)

2 FLUHRER， S.， MANTIN， I.， and SHAMIR， A. Weaknesses in the key scheduling algorithm of RC4. Eighth

Annual Workshop on Selected Areas in Cryptography， August 2001

3 LAN/MAN Standard Comitee. Wireless LAN medium access

control (MAC) and KSA physical layer (PHY) specification?1999 edition. IEEE standard 802.11， IEEE or Computer?Society， 1999

4 SCHNEIER， B. Applied Cryptography-Protocols， Algorithms.and Source Code in C. John Wiley & Sons，Inc.，1994

5 Scott R. Fluhrer and David A. McGrew， Statistical analysis of the alleged RC4? keystream generator， FSE：Fast?Software Encryption， FSE＇2000， Springer-Verlag，nalytic?2000:19～30

6 Jovan Dj. Golic. Linear statistical weakness of alleged?RC4 key-stream generator， EUROCRYPT： Advances in

Cryptology-EUROCRYPT ＇97， International And Conference on the Theory and Application of Cryptographic Techniques，EUROCRYPT＇97 (Konstanz， Germany)， LNCS， vol. 1233，?Springer-Verlag， May 1997， eloved:226～238