WEP數據加密協議的兩種改進攻擊

孫思維，胡磊

（中國科學院研究生院 信息安全國家重點實驗室，北京 100049）

1 引言

WEP協議是IEEE 802.11無線局域網標準[1]中的數據加密協議，在現實生活中的無線局域網中被廣泛使用，對其安全性分析是近年來研究的熱點。2001年，Borisov、Goldberg和Wagner首次對WEP協議進行了分析[2]，他們的分析揭示了WEP協議在保護數據完整性和機密性上的一些重大缺陷。同年，Fluhrer、Mantin和 Shamir[3]針對 WEP協議中RC4流密碼的使用不當，提出了一個恢復WEP密鑰的已知明文攻擊（以下稱為FMS攻擊）。此后，研究人員又發現了更多的攻擊方法，如 chop-chop攻擊[4]、KoreK 攻擊[5]、Klein 攻擊[6]和 PTW 攻擊[7]，等等。FMS攻擊和chop-chop攻擊是2類最重要的攻擊方法，其中，chop-chop攻擊是所有主動型WEP攻擊的基礎。這一切都表明，WEP加密協議的設計存在著嚴重缺陷。到目前為止，國際標準 WEP已被 WPA替換，但是出于經費等原因，市面上的多數無線接入點仍然使用 WEP協議。由于現今一些高效WEP攻擊需要向網絡中大量廣播偽造的ARP數據分組，許多入侵檢測系統可以迅速地發現那些主動攻擊者。這使得改善原有的被動型WEP攻擊變得很有意義，這是本文研究的一個出發點。

在本文的第3節中，描述chop-chop攻擊，并給出它的一個改進，此改進不僅提高了 chop-chop攻擊的速度，也減少了攻擊所需向網絡中發送的WEP數據幀的數量。在第4節中，分析RC4流密碼在WEP協議中的使用細節，給出原始的FMS攻擊。在第5節中，提出被動型的WEP攻擊，即FMS攻擊的一個改進方法——FMS+攻擊，理論分析表明，FMS+攻擊具有更高的成功率，并給出具體的實驗數據。

2 WEP協議概述

在 WEP協議中，無線接入點和每個合法客戶端共享一個 WEP密鑰 R。當數據發送端要發送明文M時，它首先計算M的32bit校驗值CRC32(M)，選擇一個初始向量V，然后用V||R作為RC4流密碼的密鑰生成密鑰流 X = RC4(V||R)去加密M||CRC32(M)，即密文為

最后，發送者發送的數據為 V||C，稱為一個 WEP數據幀，C為WEP數據幀的加密部分。當接收端收到WEP數據幀時，通過計算

得到明文M。

這里需要指出的是，每個從客戶端發送到客戶端的 WEP數據幀通常都是由無線接入點轉發的。當無線接入點接收到WEP數據幀V||C后，它首先對V||C的加密部分進行解密，然后對解密后的數據進行 CRC32完整性檢測。如果通過檢測，它就對WEP數據幀V||C進行轉發，否則丟棄此數據幀。下節的chop-chop攻擊正是利用了無線接入點的這個轉發特性。

3 chop-chop攻擊及其改進

在 WEP協議中，每個數據被看作一個二元序列，同時被看作二元域 F2上的一個多項式，例如，二元序列 100111101被看成多項式 x8+ x5+ x4+x3+ x2+ 1。下面將等同地看待二元序列和上的多項式。一個二元序列P可以通過CRC32檢驗，當且僅當它的多項式滿足

其中，J =x31+x30+…+1對應32bit全1二元序列，f = x32+ x26+ x23+ x22+ x16+ x12+ x11+ x10+ x8+x7+ x5+ x4+ x2+ x +1 是上的一個32次不可約多項式。由式(1)可以得出 M 的校驗值 CRC32(M)的計算方法：因為 M ||C RC 3 2(M )通過校驗，即Mx32+CRC 3 2(M ) = J ( mod f )，所以有

通過式(2)可由 M 計算出唯一的 32bit序列CRC32(M)。

如果用 Pi表示P的最后i位，Qi表示二元序列P去掉最后i位所形成的二元序列，則有

因為f是一個不可約多項式，對于 F2上任意多項式 g ≠ 0 (modf)，可以計算出唯一的小于32次的多項式，記為 g-1，使得 g-1g = 1 (mod f)。下面給出一個簡單性質。

第1步 攻擊者截獲一個WEP數據幀V||C。

第2步 攻擊者去掉 C = (M || C RC3 2(M )) ⊕X的最后i位，此時得到的二元序列記為。令 Qi為M | |C RC 3 2(M )去掉最后i位得到的二元序列， Xi為X去掉最后i位得到的二元序列，即 Xi是一個縮短的密鑰流。

第3步 攻擊者隨機猜測 P = C⊕ X = (M|| C RC32(M ) )的最后 i位為，然后計算= J +(xi)-1(J +Pi) (mod f )，并把作為新的WEP數據幀發送給接入點。

下面給出改進的chop-chop攻擊，并給出此攻擊的理論分析。原始的以代碼形式給出的chop-chop攻擊[4]實質上是上述攻擊 i = 8 的情形，此時當攻擊者進行到chop-chop攻擊的第3步時，它需要猜測一個 8bitP8并向接入點轉發數據幀由第2節中最后一段的討論可知，當接入點接收到這個數據幀后首先解密得到，然后對進行CRC32完整性檢測。如果攻擊者正確地猜到了P8的真實值，檢測通過，接入點便轉發攻擊者構造的數據幀。這樣，在第4步中，攻擊者會發現接入點的這個行為，從而知道它自己已經正確地猜測到了8P。然而，在第3步中，攻擊者平均要進行82/2 128= 次猜測才能猜到真實的8P，而當它猜錯時，由于檢測不到接入點轉發的數據幀，它必須重復第3步。

實際上，在chop-chop攻擊中，如果取 i =1，則在進行到第3步時，真實的 P1只可能為1或者0，不妨在每次進行到第3步時，都猜測 P1為0。那么在進行到第4步時，如果攻擊者監聽到接入點轉發的，那么顯然，它在第3步時正確地猜到了 P1，如果它沒有監聽，說明它猜錯了，然而此時的 P1只有2種可能，所以攻擊者此時并不需要重新進行第3步，而是直接確定出真實的 P1一定為1。也就是說，當取 i = 1時，攻擊者每發送1個數據幀就一定可以解密1bit數據，而當i= 8 時，攻擊者平均要進行128次才能猜到真實的8bitP8，即平均每發送16個數據幀才能正確地解密出1bit數據?？梢?，當 i = 1時，其攻擊效率是原始的 chop-chop攻擊的 16倍。對密文依次剪切 1bit并執行上述攻擊，可以恢復明文的所有數據位。

4 FMS攻擊

WEP協議中RC4流密碼的使用比較特別，即RC4的密鑰K是通過V與R的簡單鏈接V||R得到的。WEP協議中規定V為3byte，由第2節中的描述可知，這3byte的V是攻擊者知道的。2001年，Fluhrer、Mantin和Shamir發現這樣使用RC4是危險的[3]，一個被動監聽網絡的攻擊者在得到足夠多的 WEP數據幀后，可以通過它們的攻擊以很大的概率恢復WEP密鑰R。

4.1 RC4流密碼算法

RC4是一個密鑰長度可變，面向字節操作的流密碼。圖1給出了 RC4算法的描述，其中加法在Z256上進行。RC4算法的實現非常簡單，它包括RC4-KSA與RC4-PRGA 2部分。RC4-KSA首先將一個由 256byte組成的狀態向量 S初始化為[0,1,…,255]，然后利用密鑰K，對狀態向量S進行256次置換。每次置換時，首先用i、j標識出狀態向量S中的2個元素S[i]與S[j]，然后對換S[i]與S[j]的位置，即新的S[i]和S[j]為原來的S[j]和S[i]，其他位置的元素保持不變。

當 RC4-KSA完成對 S的 256次置換后，RC4-PRGA利用所得狀態向量不斷地輸出密鑰流字節。在每次輸出密鑰流字節前，都要對S進行一次新的置換。例如，當RC4輸出其第一個密鑰流字節時，狀態向量S共經歷了257次置換。下面的討論采用如下記號：

1) 用0,…,255表示全部的單字節值，即把每個字節看成Z256中的一個元素。

2) 用S0表示狀態向量S剛經過RC4-KSA Initialization后S的狀態，即此時有S = [0,…,255]。用S-1[i]表示滿足S[j] = i的j值。

圖1 RC4流密碼算法

3) K表示RC4算法的密鑰。特別地，在WEP協議中，K = V||R，其中，V是3byte的初始向量，R是WEP密鑰。

4) X表示RC4算法輸出的密鑰流，X[0]表示X的第 0個字節，X[0,…,u]表示 X的第 0到第 u個字節。

5) 用Sk表示經過k次Swap對換后的狀態向量S，S的第k次置換也稱為RC4算法的第k步，用ik，jk表示在第k次Swap對換發生的位置，即S[ik]與S[jk]發生了對換。

下面以K = [23,42,232,11]為例，給出RC4算法的具體運算步驟。首先是RC4-KSA：

初始化

?

i0= 0 , j0=0

第1步

?

i1= 0 , j1=23

第2步

?

i2= 1 , j2=66

……

接下來是RC4-PRGA：

第257步

?

i257= 2 , j257= 4 0，并輸出 X[0]= 8 5。

另外，通過RC4-KSA算法描述的Scrambling部分，可以得到如下等式：

而通過RC4-PRGA，還可以得到RC4算法輸出的第一個字節為 S257[ S257[ 1]+ S257[ S256[1]]]。

4.2 FMS條件與攻擊

下面給出 FMS攻擊的具體描述：首先攻擊者監聽網絡，收集足夠多的明密文對，即知道足夠多的形如(V,X[0])的數據對，這里V是變量，R是常量。FMS攻擊假設攻擊者知道密鑰K的前l個字節。初始假設l = 3，因為在WEP協議中，攻擊者知道K[0]= V[0]，K[1] = V[1]，K[2] = V[2]這 3個字節。當它收集到足夠多的數據對后，對每一個(V,X[0])，攻擊者運行 RC4(V||R)的前 l步。由式(3)可知，RC4算法的前l步只用到了K[0]至K[l-1]的值，所以攻擊者可以完成這個運行。接著，它檢查狀態向量S是否滿足如下FMS條件a：

如果不滿足上述條件，數據對(V,X[0])就被丟棄，否則，則計算

5 改進的FMS攻擊

自 FMS攻擊被發現以后，又出現了一些新的密鑰恢復攻擊，然而這些攻擊大都要求攻擊者知道X[0,…,u]，1u≥ ，或者要求攻擊者具有向網絡中大量注射 ARP數據分組的能力，而這種行為很容易被入侵檢測系統偵測到。本節中將指出，在假設攻擊者只能被動監聽網絡，并且只知道X[0]的情況下，FMS攻擊仍能得到改進，將改進后的FMS攻擊稱為FMS+攻擊。

同FMS攻擊一樣，假設攻擊者知道K的前l個字節。攻擊者首先要得到大量的 (V,X[0])數據對，利用每個數據對(V,X[0])攻擊者運行 RC4算法的前l步，然后檢查狀態向量S是否滿足FMS+條件a：

如果滿足，則對滿足

的K[l]投票；否則，檢查是否滿足FMS+條件c：

5.1 理論分析

假設當攻擊者運行完RC4(V||R)的前l步后，狀態向量S滿足FMS+條件a1和a2。此時有如下內部狀態：

?

對于第l+1步，il+1= l，jl+1=jl+K[l]+Sl[l]，于是S的第l和jl+1個位置的元素被交換，即有如下狀態：

?

如果在第l+1步至第256步中，狀態向量S的第1、Sl[1]、l個元素沒有參與交換，則有

?

對于第257步，i257= 1，j257= S256[1]=Sl[1]，所以有

?

從而，RC4(V||R)輸出如下字節：

此時有

又因為在RC4(V||R)計算的第l+1步至第256步中，Sl[1]和Sl[Sl[1]]沒有參與交換，而在第l+2步至第256步中，Sl+1[l]沒有參與交換，所以有

即

而在第 l+1步至第 256步中，Sl[1]和 Sl[Sl[1]]的位置沒有改變，在第l+2步至第256步中，Sl+1[l]的位置沒有改變，當且僅當i，j在第l+2步至第256步中不能取到1、l和Sl[1]，而RC4算法從第l+2步開始后，總有 i≥l+1,所以 i不可能取到 1、l和Sl[1](因為 Sl[1]＜l)。

如果把j看成隨機的，則j不取1、l和Sl[1](1＜Sl[1]＜l和2＜l)的概率為

所以，利用滿足FMS+條件a計算出的

為 K[l]的真實值的概率大于一個取值為隨機字節的概率，這是FMS攻擊利用這類數據進行投票的原因。

滿足FMS條件a的數據只占攻擊者所搜集到的數據的很少一部分，大部分數據沒有參與投票就被丟棄了，比如在FMS攻擊中，滿足Sl[1] = l的數據將全部被丟棄。FMS+攻擊表明，這類數據不僅不應該被丟棄，而且更具有參與投票的價值。

假設當攻擊者運行完RC4(V||R)的前l步后，Sl[1]= l，即

?

對于第l+1步，有

?

如果在第l+2步至第256步中，狀態向量S的第1、l和jl+1個位置的元素沒有參與交換，則有

?

對于輸出的X[0]分2種情況討論：

1) 若 X[0] = Sl[l]，則

即Sl[jl+1]+l = jl+1，其中，jl+1=jl+K[l]+Sl[l]。同樣可以利用 FMS+條件 b的數據計算出的滿足Sl[jl+1]+l = jl+1的K[l]的值是K[l]的真實值的概率為Pfms。所以對于這類數據不應該丟棄，也應讓其參與到對K[l]的投票中去，同理也可以得到 FMS+條件d。

2) 若 X[0] = l，則

即Sl[jl+1]+l = l或Sl[jl+1] = 0。注意，此時只要求狀態向量S的2個位置的元素不參與交換，利用滿足FMS+條件c的數據計算出的滿足Sl[jl+1] = 0的K[l]的真實值的概率為

所以說，這類數據更應該參與到對K[l]的投票中去。實際上，Pfms+比Pfms大很多，例如當l = 3時，有

此時Pfms+約為Pfms的2.7倍。利用這類數據投票，可以更容易地區分出K[l]的真實值。

最后指出，隨著攻擊的進行，攻擊者已知的WEP密鑰的字節數增多，即l變大，由式(4)可知，Pfms與Pfms+都會隨之增加，從而攻擊會變得越來越有效。

5.2 實驗分析

在實驗中，隨機生成100個8byte的R（8byte是WEP協議中經常使用的密鑰長度），然后對每一個R隨機生成一定數量的3byte V，將V||R作為輸入，由RC4計算出相應的X[0]。注意FMS攻擊和 FMS+攻擊是已知明文攻擊，這里的“一定數量的X[0]”用于模擬攻擊過程中能收集到的明密文對的數量。利用這些(V,X[0])，分別用 FMS攻擊與 FMS+攻擊猜測 R[0]，統計可用數據幀的數量與正確猜測出R[0]的次數，實驗結果見表1。例如，表1的最后一行表示隨機生成了100個R，然后對每個 R隨機生了 15 000 000個(V,X[0])數據對，在利用這些數據對猜測R[0]時，FMS平均可以利用651個，而FMS+攻擊可以利用1 429個；FMS攻擊正確地猜測到91個R[0]，而FMS+攻擊正確地猜測到98個R[0]。

從表 1可以看出，FMS+攻擊將 FMS攻擊可以利用的WEP數據幀的數量提高一倍以上。相對于 FMS攻擊，FMS+恢復密鑰的成功率也有明顯提高：當已知60 000至2 000 000個明密文對時，FMS+將FMS攻擊恢復WEP密鑰第一個字節的成功率提高20%以上。在已知100 000個明密文對的情況下即可以19%的概率恢復出WEP密鑰的第一個字節R[0]。

表1 可用(V, X[0])數量與成功恢復R[0]次數比較

在圖2中，對FMS與FMS+猜測R[0]的成功率隨攻擊者收集到的(V,X[0])數據對的數量的變化趨勢進行了描述。從圖中也可以看出，FMS+攻擊顯然優于FMS攻擊。

圖2 FMS+與FMS猜測R[0]成功率比較

需要指出的是，FMS攻擊和FMS+攻擊的效率還可以用如下方式提高。在上述實驗中，當且僅當得票最多的字節值為真實的R[0]時，才認為一個猜測是成功的。實際上，一個攻擊者可以每次猜測出一組R[0]的候選值。比如，可以認為如果R[0]的真實值在得票最多的前2個字節值中，則一次猜測是成功的。這樣，實驗的成功率可以更高，為取得同樣成功率所需的明密文數據可以更少。在實驗中，發現R[0]的真實值是得票第二多的字節值的情況經常發生，例如在上述已知 150 000個(V,X[0])數據對的實驗中，FMS攻擊與FMS+攻擊分別有5次和7次出現R[0]真實值是得票第二多的字節值的情況，相比表1第7行后2列的數據“10”和“23”來說，并不是很小。

在攻擊中使用的(V,X[0])數據量可以是很大的。保守估計，在一個比較繁忙的網絡中，由于多個用戶被分成一個用戶群而共享一個WEP密鑰，攻擊者可以每秒收集到 300個(V,X[0])數據對，要收集到10 000 000個這樣的數據對也不過10h的時間。攻擊者甚至可以通過一些方法使得網絡中的流量劇增[10]，從而大大提高收集數據對的速度。

6 結束語

對于WEP加密協議的chop-chop攻擊，通過減少每次猜測明文字節的位數，可以明顯地提高攻擊速度并減少攻擊過程中向網絡發送的 WEP數據幀的數量，從而提高所有基于chop-chop攻擊的主動型WEP攻擊的效率。

對于WEP加密協議的FMS攻擊，給出的改進方法FMS+攻擊可以利用更多的WEP數據幀，從而提高了攻擊速度與恢復 WEP密鑰的正確率，理論與實驗都證明了這一點。據筆者所知，這個改進是目前只利用每個密鑰流中一個已知字節就可以恢復 WEP密鑰的最好攻擊，另外它本身還是一種完全被動攻擊，這對真實的攻擊者很有意義，一些更高效的攻擊（如PTW攻擊[7]）需要攻擊者主動向網絡中廣播偽造的 ARP數據分組，而這很容易就會觸發入侵檢測系統，甚至暴露攻擊者的位置。

FMS+攻擊還很容易地與其他一些已有的WEP密鑰恢復攻擊（比如KroeK攻擊）結合起來，從而產生更有效的攻擊方法。

[1] IEEE, ANSI/IEEE Standard 802.11b∶ Wireless LAN Medium Access Control (MAC) and Physical Layer (Phy) Specifications[S]. 1999.

[2] BORISOV N, GOLDBERG I, WAGNER D. Intercepting mobile communications∶ the insecurity of 802.11[A]. Proceedings of ACM MobiCom 2001[C]. Italy, 2001. 180-189.

[3] FLUHRER S, MANTIN I, SHAMIR A. Weaknesses in the key scheduling algorithm of RC4[J]. Selected Areas in Cryptography , 2001,2559(10)∶ 101-117.

[4] KOREK.Chop-chop experimental WEP attacks [EB/OL]. http∶//www.netstumbler.org/showthread.php?t=12489, 2004.

[5] KOREK. Next generation of WEP attacks?[EB/OL]. http∶//www.netstumbler.org/showthread.php?p=93942&postcount=35, 2004.

[6] KLEIN A. Attacks on the RC4 stream cipher[J]. Designs, Codes, and Cryptography, 2008, 48(3) ∶ 269-286.

[7] TEWS E, BECK M. Practical attacks against WEP and WPA[A].Proceedings of the Second ACM Conference on Wireless Network Security[C]. Zurich, 2009. 79-86.

[8] BITTAU A, HANDLEY M, LACKEY J. The final nail in WEP’s coffin[A]. IEEE Symposium on Security and Privacy[C]. USA, 2006.386-400.

[9] BARON A. Hi-tech heist, how hi-tech thieves stole millions of customer financial records[EB/OL]. http∶//www.cbsnews.com/ , 2007.

[10] 楊哲. 無線網絡安全攻防實戰[M]. 北京∶ 電子工業出版社, 2008.YANG Z. Practical Wireless Attack and Defense[M]. Beijing∶ Electronic Industry Press, 2008.