WEP安全性能攻擊研究論文

導語：WEP安全性能攻擊研究論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

摘要：以Fluhrer,S．,Mantin,I．,Shamir,A．提出的KSA（KeyScheduleAlgorithm）攻擊為基礎，提出了一種改進的KSA攻擊方法。與Fluhrer等提出的KSA攻擊相比，新方法具有更高攻擊效率。利用這種方法，成功地實現了針對802．11網絡鏈路層安全協議——wep的攻擊，成功地恢復出了原加密密鑰。本文詳細地描述了這種攻擊，同時針對802．11網絡存在的安全問題，提出了一些安全建議。

關鍵詞：有線等效加密密鑰調度算法偽隨機數發生器

隨著802．11標準的制定以及相關軟硬件技術的逐漸成熟，802．11無線局域網產品的使用愈來愈廣泛。其通信范圍廣、數據傳輸速率高的特點使802．11同藍牙等協議一起成為無線局域網組網的可選協議之一，廣泛應用于辦公、會議等場合。這些場合中所使用的PC卡絕大多數提供了一種稱為WEP（WiredEquivalentPrivacy）的加密協議。

WEP便于管理，每塊802．11卡具有一個加密密鑰（key）。在實際使用中，大多數設備均使用同一個加密密鑰，包括接入點AP（AccessPoint）。802．11通過WEP來防止對局域網的非法訪問，為用戶提供與傳統有線局域網保密程度相當的通信環境。

WEP中采用的RC4算法是一種對稱流加密算法。由于RC4算法的加密或解密速度均非?？?，又提供了相當的強度，所以得到了廣泛應用。其最重要的應用就是SSL（SecuritySocketLayer）加密套接字協議層和WEP。

針對RC4算法及其弱點，人們進行了許多研究，其中大多數為理論研究，并不具有實際意義。直到最近，Borisov、GoldbergandWagner指出1：在WEP中，由于沒有明確規定IV（InitializationVectors）的使用方法，有些廠商簡單地在每次初始化時將IV置零，然后加一。這種不當使用導致密鑰重用的概率大增，可用于簡單的密碼分析攻擊。另外，作者還指出，由于IV的可用空間太小，將不可避免地導致相同的密鑰重用問題。

Fluhrer、MantinandShamir描述了一種針對WEP采用的RC4算法的被動密文攻擊方法2。作者針對RC4的狀態初始化，提出了一種KSA攻擊方法。揭示了WEP存在的嚴重漏洞。

本文在文獻2提出的KSA攻擊方法的基礎上，提出了一種更為高效的攻擊方法。并在實際環境中，成功地實施了針對WEP的攻擊。實驗結果表明，與文獻2中提出的KSA攻擊相比，本文提出的方法具有效率高、所需數據量更小的優點。

1RC4算法

1．1RC4概述

RC4算法屬于二進制異或同步流密碼算法，其密鑰長度可變，在WEP中，密鑰長度可選擇128bit或64bit。

RC4算法由偽隨機數產生算法PRGA（PseudoRandomGenerationAlgorithm）和密鑰調度算法KSAKeyScheduleAlgorithm兩部分構成。其中PRGA為RC4算法的核心，用于產生與明文相異或的偽隨機數序列；KSA算法的功能是將密鑰映射為偽隨機數發生器的初始化狀態，完成RC4算法的初始化。

RC4算法實際上是一類以加密塊大小為參數的算法。這里的參數n為RC4算法的字長。在WEP中，n＝8。

RC4算法的內部狀態包括2n個字的狀態表和兩個大小為一個字的計數器。狀態表，也稱為狀態盒（S－box，以下用S表示），用來保存2n個值的轉置狀態。兩個計數器分別用i和j表示。

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

KSA：PRGA：

Initialization：Initialization：

Fori＝0to2n－1i＝0，j＝0

S[i]＝iGenerationLoop：

j＝0i＝i＋1

Scrambling：j＝j＋S[i]

Fori＝0to2n－1Swap（S[i]，S[j]）

j＝j＋S[i]＋K[imodl]Outputz＝S[S[i]＋S[j]]

Swap（S[i]，S[j]）

其中，l為密鑰的長度。

1．2RC4算法安全性能分析

仔細研究RC4的算法流程，不難發現：

狀態盒S從一個統一的2n個字的轉置開始，對其進行的唯一操作是交換。S始終保存2n個字的某個轉置狀態，而且轉置隨著時間而更新。這也是RC4算法的強度所在。算法的內部狀態存儲在M＝n2n＋2n比特中，由于S為一個轉置，此狀態大約保存了log2（2n?。?n≈1700bit的信息。

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

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

RC4算法屬于同步流密碼算法中的一種，由于其偽隨機數發生器PRNG（PseudoRandomNumberGernerator）的輸出完全由加密密鑰確定，所以對于一個設計良好的流密碼算法必須滿足兩個條件：輸出的每個比特應該依賴于所有加密密鑰的所有比特；而且，任意一個比特或者某些比特同加密密鑰之間的關系應該極其復雜。

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

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

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

第二個條件意味著即使已知兩個加密密鑰之間的聯系，也無法得出PRNG輸出之間的聯系。此信息也可用來降低窮舉攻擊的搜索空間，從而導致加密強度的降低。

RC4算法屬于二進制異或流密碼，相同的密鑰總是產生相同的PRNG輸出。為解決密鑰重用的問題，WEP中引入了初始化向量IV（InitializationVector）。初始化向量為一隨機數，每次加密時隨機產生。初始化向量以某種形式與原密鑰相組合，作為此次加密的加密密鑰。由于IV并不屬于密鑰的一部分，所以無須保密，多以明文傳輸。雖然初始化向量的使用很好地解決了密鑰重用的問題，然而，FluhrerS等人在文獻2中指出：初始化向量的使用將導致嚴重的安全隱患。

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

2KSA攻擊

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

2．1KSA

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

P＝(255／256)∧255≈37％

(指數為255是因為當index2和counter相等時可以忽略)

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

由此可看出:

給定一密鑰長度K(bytes),如果E＜K,那么元素E有37％的概率僅在i指向它時被交換。

那么由RC4的KSA算法可看出僅K[0]．．．．K[E－1],和K[E]影響它。這只是近似估算,因為index2不可能是均勻分布。

為利用上述結果,需要確定狀態表最可能的值。因為每個元素至少交換一次(當counter指向它時),所以有必要對交換可能帶來的影響加以考慮。交換是令人討厭的非線性操作,難于分析。然而當處理狀態表前幾個元素時,某個具體元素有很高的概率沒有參與它前面的幾次交換,因此還保留初始值(S[X]＝X)。

相似地，僅處理狀態表中前幾個元素時，即i比較小時，S[j]有很高的概率等于j。因此，可以得到：

狀態表中元素S[E]（E比較小時）最可能的值為：

注意，本文中兩個元素操作均為模256操作。

基于以上分析，可以計算出狀態表中各個元素滿足B的概率。為統計狀態表中元素滿足上式的概率，采用8比特RC4算法進行實驗。下面為100000次實驗中S[E]中前48個元素滿足上式的概率：

Probability％

0～737．036．836．235．834．934．033．032．2

8～1530．929．828．527．526．024．522．921．6

16～2320．318．917．316．114．713．512．411．2

24～3110．19．08．27．46．45．75．14．4

32～393．93．53．02．62．32．01．71．4

40～471．31．21．00．90．80．70．60．6

結果表明，經過KSA后，狀態表中前面的一些元素實際值與用B所預測出的值強相關。

2．2弱密鑰

首先定義it，jt分別為KSA算法經過t步后相應的兩個計數器的值，St為KSA經t步后狀態盒的狀態。從其流程可以看出，PRNG首字節輸出僅僅依賴于狀態盒S中的三個值：S[1]、S[S[1]]和S[S[1]＋S[S[1]]]。如果此三個值為已知，那么就可以完全確定PRNG的首字節輸出。

KSA經過i步操作后(i＞1),設Si[1]＝X，S[X]＝Y，假設j為均勻分布的隨機數，那么S[1]，S[X]，S[X＋Y]均不參與剩余交換的概率約為e－3≈0．05，此時RC4的首字節輸出為S[X＋Y]。

假設IV的長度為I個字節，IV附加在密鑰Key前面組成加密密鑰K，即K＝IV｜Key，且我們已知K中前B個字節的值（初始化時B＝0）。如果KSA經過I＋B－1次迭代后滿足：

SI＋B－1[1]＜I

SI＋B－1[1]＋SI＋B－1[SI＋B－1[1]]＝I＋B

考慮第I＋B次迭代：

iI＋B＝I＋B

jI＋B＝jI＋B－1＋S[I＋B]＋K[（I＋B）modL]

交換SI＋B－1[iI＋B]，SI＋B－1[jI＋B]：

SI＋B[iI＋B]＝SI＋B－1[jI＋B]，

SI＋B[jI＋B]＝SI＋B－1[iI＋B]

在滿足上述條件的情況下，S[1]，S[S[1]]和S[S[1]＋S[S[1]]]這三個元素以很高的概率（大于5％）均不參與KSA剩余的交換操作，也即首字節輸出以很高的概率滿足：

Out＝SI＋B－1[jI＋B]＝SI＋B－1[jI＋B－1＋K[B]＋SI＋B－1[I＋B]]

這種情況下，通過重建KSA，能夠成功地從首字節輸出中獲取加密密鑰中某個特定字節K[I＋B]的信息：

K[B]＝S[Out]－jI＋B－1－SI＋B－1[I＋B]]

S[Out]表示元素Out在狀態表中的位置。

從前面分析可以看出，在滿足SI[1]＜I＋B且SI[1]＋SI[SI[1]]＝I＋B條件的情況下，可以準確重建K[B]的概率大于5％，遠遠大于1／256。這樣通過收集足夠數量的滿足上述條件的數據包，就可以成功地重建密鑰K[B]。同理，在成功重建K[B]的基礎上，就可以用類似的方法重建所有密鑰。

具體算法如下：

RecoverWepKey(CurrentKeyGuess,KeyByte)

Counts[0．．．255]＝0

Foreachpacket－＞P

IfResolved﹖(P．IV）

Counts[SimulateResolved(P,CurrentKeyGuess)]＋＝1

ForeachSelectMaximalIndexesWithBias(Counts)－＞ByteGuess

CurrentKeyGuess[KeyByte]＝ByteGuess

IfEqual﹖(KeyByte,KeyLength)

IfCheckChecksums(CurrentKeyGuess)

ReturnCurrentKeyGuess

Else

Key＝RecoverWEPKey(CurrentKeyGuess,KeyByte＋1)

IfnotEqual﹖(Key,Failure)

ReturnKey

ReturnFailure

2．3算法改進

可以看出，以上的攻擊方法中，所有關于K[I＋B]的預測均是基于其前面所有密鑰（K[0]，．．．，K[I＋B－1]）已知的基礎上。換言之，前面的預測錯誤將直接導致K[I＋B]的錯誤預測。那么能否從K[I＋B]中推測出K[0]，．．．，K[I＋B－1]的信息？

考慮KSA，如果經過I次迭代后，滿足：

I＜SI[1]＋SI[SI[1]]＝I＋B≤L

SI[1]≤I

則SI[1]和SI[SI[1]]以很大的概率（（254／256）L－I≈1）不參與第I步與第L步之間的迭代。同時，j以很大的概率不指向SI[I]，．．．，SI[I＋B]這幾個元素。

即：

SI[1]＝SI＋B－1[1]iL－1＝L－1

jI＋B－1＝jI＋SI[I]＋．．．＋SI[I＋B－1]＋K[I]＋．．．＋K[I＋B－1]

考慮第L步：

iI＋B＝I＋BjI＋B＝jI＋B－1＋SI[I＋B]＋K[I＋B]

交換S[i]，S[j]，則SI＋B[I＋B]＝SI＋B－1[jI＋B]。

如果SI＋B－1[jI＋B]，SI＋B－1[1]和SI＋B－1[SI＋B－1[1]]不參與剩余的交換操作，那么輸出為：

Out＝SI＋B－1[jI＋B]

而由前面的分析可以看出，SI＋B－1[jI＋B]以很高的概率（約為1）沒有參與前面的交換操作，也即SI＋B－1[jI＋B]＝jI＋B。由此可知

Out＝jI＋SI[I]＋．．．＋SI[I＋B－1]＋K[I]＋．．．＋K[I＋B－1]＋SI[I＋B]＋K[I＋B]

利用上述關系可以成功地推出不同K字節之間的關系，從而加速攻擊。

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

3實驗結果與結論

為對上述算法進行驗證，進行了實驗。實驗中所采用的硬件為朗訊的ORiNOCO無線網卡，操作系統為Redhat7．1。實驗結果表明，本文所提出的算法平均在收集100萬到200萬加密數據包的情況下，成功地恢復出了原加密密鑰。與FluhrerS．、MantinI．、ShamirA．所提出的KSA攻擊需要400萬到600萬數據包相比，攻擊效率有了很大提高。

基于以上分析，不難看出：現有WEP加密中存在重大的安全漏洞，這種情況并不因加密密鑰長度的增加而得到改善，所以在WEP2中同樣存在。為此，建議現有的802．11用戶：

．假設802．11鏈路層并不提供安全措施；

．為保障網絡通信的安全，使用IPSEC或者SSH等高層加密手段；

．把所有通過802．11接入的用戶置于防火墻之外。

．經常更換密鑰，同時針對密鑰應盡量采用某種HASH算法，避免采用全為ASIIC字符的加密密鑰。