孫思維，胡磊

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

1 引言

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

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

2 WEP協(xié)議概述

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

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

得到明文M。

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

3 chop-chop攻擊及其改進

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

其中，J =x31+x30+…+1對應(yīng)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)。下面給出一個簡單性質(zhì)。

第1步 攻擊者截獲一個WEP數(shù)據(jù)幀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數(shù)據(jù)幀發(fā)送給接入點。

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

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

4 FMS攻擊

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

4.1 RC4流密碼算法

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

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

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

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

圖1 RC4流密碼算法

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

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

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

下面以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算法輸出的第一個字節(jié)為 S257[ S257[ 1]+ S257[ S256[1]]]。

4.2 FMS條件與攻擊

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

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

5 改進的FMS攻擊

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

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

如果滿足，則對滿足

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

5.1 理論分析

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

?

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

?

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

?

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

?

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

此時有

又因為在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]的真實值的概率大于一個取值為隨機字節(jié)的概率，這是FMS攻擊利用這類數(shù)據(jù)進行投票的原因。

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

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

?

對于第l+1步，有

?

如果在第l+2步至第256步中，狀態(tài)向量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的數(shù)據(jù)計算出的滿足Sl[jl+1]+l = jl+1的K[l]的值是K[l]的真實值的概率為Pfms。所以對于這類數(shù)據(jù)不應(yīng)該丟棄，也應(yīng)讓其參與到對K[l]的投票中去，同理也可以得到 FMS+條件d。

2) 若 X[0] = l，則

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

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

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

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

5.2 實驗分析

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

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

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

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

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

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

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

6 結(jié)束語

對于WEP加密協(xié)議的chop-chop攻擊，通過減少每次猜測明文字節(jié)的位數(shù)，可以明顯地提高攻擊速度并減少攻擊過程中向網(wǎng)絡(luò)發(fā)送的 WEP數(shù)據(jù)幀的數(shù)量，從而提高所有基于chop-chop攻擊的主動型WEP攻擊的效率。

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

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

[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] 楊哲. 無線網(wǎng)絡(luò)安全攻防實戰(zhàn)[M]. 北京∶ 電子工業(yè)出版社, 2008.YANG Z. Practical Wireless Attack and Defense[M]. Beijing∶ Electronic Industry Press, 2008.