摘? 要: 以Fluhrer,， S.,， Mantin， I.,， Shamir,， A.提出的KSA(Key Schedule Algorithm)攻擊為基礎(chǔ),提出了一種改進的KSA攻擊方法。與Fluhrer等提出的KSA攻擊相比,新方法具有更高攻擊效率,。利用這種方法,成功地實現(xiàn)了針對802.11網(wǎng)絡(luò)鏈路層" title="鏈路層">鏈路層安全協(xié)議——WEP的攻擊,成功地恢復(fù)出了原加密密鑰,。本文詳細地描述了這種攻擊,同時針對802.11網(wǎng)絡(luò)存在的安全問題,提出了一些安全建議。
關(guān)鍵詞: 有線等效加密? 密鑰調(diào)度算法? 偽隨機數(shù)" title="隨機數(shù)">隨機數(shù)發(fā)生器
?
隨著802.11標(biāo)準(zhǔn)的制定以及相關(guān)軟硬件技術(shù)的逐漸成熟,802.11無線局域網(wǎng)產(chǎn)品的使用愈來愈廣泛,。其通信范圍廣,、數(shù)據(jù)傳輸速率高的特點使802.11同藍牙等協(xié)議一起成為無線局域網(wǎng)組網(wǎng)的可選協(xié)議之一,廣泛應(yīng)用于辦公、會議等場合,。這些場合中所使用的PC卡絕大多數(shù)提供了一種稱為WEP(Wired Equivalent Privacy)的加密協(xié)議,。
WEP便于管理,每塊802.11卡具有一個加密密鑰(key)。在實際使用中,大多數(shù)設(shè)備均使用同一個加密密鑰,包括接入點AP(Access Point),。802.11通過WEP來防止對局域網(wǎng)的非法訪問,為用戶提供與傳統(tǒng)有線局域網(wǎng)保密程度相當(dāng)?shù)耐ㄐ怒h(huán)境,。
WEP中采用的RC4算法是一種對稱流加密算法。由于RC4算法的加密或解密速度均非?？?又提供了相當(dāng)?shù)膹姸?所以得到了廣泛應(yīng)用,。其最重要的應(yīng)用就是SSL(Security Socket Layer)加密套接字協(xié)議層和WEP。
針對RC4算法及其弱點,人們進行了許多研究,其中大多數(shù)為理論研究,并不具有實際意義,。直到最近,Borisov,、Goldberg and Wagner指出[1]:在WEP中,由于沒有明確規(guī)定IV(Initialization Vectors)的使用方法,有些廠商簡單地在每次初始化時將IV置零,然后加一。這種不當(dāng)使用導(dǎo)致密鑰重用的概率大增,可用于簡單的密碼分析攻擊,。另外,作者還指出,由于IV的可用空間太小,將不可避免地導(dǎo)致相同的密鑰重用問題,。
Fluhrer、Mantin and Shamir 描述了一種針對WEP采用的RC4算法的被動密文攻擊方法[2],。作者針對RC4的狀態(tài)初始化,提出了一種KSA攻擊方法,。揭示了WEP存在的嚴(yán)重漏洞。
本文在文獻[2]提出的KSA攻擊方法的基礎(chǔ)上,提出了一種更為高效的攻擊方法,。并在實際環(huán)境中,成功地實施了針對WEP的攻擊,。實驗結(jié)果表明,與文獻[2]中提出的KSA攻擊相比,本文提出的方法具有效率高、所需數(shù)據(jù)量更小的優(yōu)點,。
1 RC4算法
1.1 RC4概述
RC4算法屬于二進制異或同步流密碼算法" title="密碼算法">密碼算法,其密鑰長度可變,在WEP中,密鑰長度可選擇128bit或64bit,。
RC4算法由偽隨機數(shù)產(chǎn)生算法PRGA(Pseudo Random Generation Algorithm)和密鑰調(diào)度算法KSA(Key Schedule Algorithm)兩部分構(gòu)成,。其中PRGA為RC4算法的核心,用于產(chǎn)生與明文相異或的偽隨機數(shù)序列；KSA算法的功能是將密鑰映射為偽隨機數(shù)發(fā)生器的初始化狀態(tài),完成RC4算法的初始化,。
RC4算法實際上是一類以加密塊大小為參數(shù)的算法,。這里的參數(shù)n為RC4算法的字長。在WEP中,n=8,。
RC4算法的內(nèi)部狀態(tài)包括2n個字的狀態(tài)表和兩個大小為一個字的計數(shù)器,。狀態(tài)表,也稱為狀態(tài)盒(S-box,以下用S表示),用來保存2n個值的轉(zhuǎn)置狀態(tài)。兩個計數(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為密鑰的長度,。
1.2 RC4算法安全性能分析
仔細研究RC4的算法流程,不難發(fā)現(xiàn):
狀態(tài)盒S從一個統(tǒng)一的2n個字的轉(zhuǎn)置開始,對其進行的唯一操作是交換。S始終保存2n個字的某個轉(zhuǎn)置狀態(tài),而且轉(zhuǎn)置隨著時間而更新,。這也是RC4算法的強度所在,。算法的內(nèi)部狀態(tài)存儲在M=n2n+2n比特中,由于S為一個轉(zhuǎn)置,此狀態(tài)大約保存了log2(2n!)+2n≈1700bit的信息。
狀態(tài)盒的初始化狀態(tài)僅僅依賴于加密密鑰K,因此,若已知加密密鑰就可完全破解RC4,。加密密鑰完全且唯一確定了偽隨機數(shù)序列,相同的密鑰總是產(chǎn)生相同的序列。另外,RC4算法本身并不提供數(shù)據(jù)完整性校驗功能,此功能的實現(xiàn)必須由其他方法實現(xiàn)(例如WEP中的數(shù)據(jù)完整性校驗向量,即ICV),。
下面考慮一些特殊的攻擊模型,這些模型均與要討論的RC4的安全問題密切相關(guān),。
RC4算法屬于同步流密碼算法中的一種,由于其偽隨機數(shù)發(fā)生器PRNG(Pseudo Random Number Gernerator)的輸出完全由加密密鑰確定,所以對于一個設(shè)計良好的流密碼算法必須滿足兩個條件:輸出的每個比特應(yīng)該依賴于所有加密密鑰的所有比特；而且,任意一個比特或者某些比特同加密密鑰之間的關(guān)系應(yīng)該極其復(fù)雜,。
上述第一個條件意味著輸出的每個比特依賴于加密密鑰所有比特的值,。密鑰中任意比特值的改變均有1/2的幾率影響到輸出的每一個比特。如果滿足此條件,那么,破解此加密需要嘗試所有可能的密鑰值,輸出值同加密密鑰之間幾乎不存在任何聯(lián)系,。
如果上面的" title="面的">面的條件得不到滿足,那么就可被利用來對其進行攻擊,。舉例來說,假設(shè)輸出的某8個比特僅僅依賴于加密密鑰的某8個比特,那么就可以簡單地進行對此8比特密鑰的所有可能值進行嘗試,并與實際輸出相比較獲取此8比特密鑰的值,這樣就大大降低了窮舉攻擊所需的計算量。
因此,如果輸出以比較高的概率由密鑰的某些比特所確定,那么此信息就可被利用來對此流密碼進行攻擊,。
第二個條件意味著即使已知兩個加密密鑰之間的聯(lián)系,也無法得出PRNG輸出之間的聯(lián)系,。此信息也可用來降低窮舉攻擊的搜索空間,從而導(dǎo)致加密強度的降低。
RC4算法屬于二進制異或流密碼,相同的密鑰總是產(chǎn)生相同的PRNG輸出,。為解決密鑰重用的問題,WEP中引入了初始化向量IV(Initialization Vector),。初始化向量為一隨機數(shù),每次加密時隨機產(chǎn)生。初始化向量以某種形式與原密鑰相組合,作為此次加密的加密密鑰,。由于IV并不屬于密鑰的一部分,所以無須保密,多以明文傳輸,。雖然初始化向量的使用很好地解決了密鑰重用的問題,然而,Fluhrer， S等人在文獻[2]中指出:初始化向量的使用將導(dǎo)致嚴(yán)重的安全隱患,。
下面詳細地討論本文所提出的KSA攻擊方法,。
2 KSA攻擊
本文著重討論WEP中所采用的RC4算法,即前附加初始化向量IV的RC4算法。
2.1 KSA
考慮KSA,注意到唯一影響狀態(tài)表的是交換操作,。因此,，狀態(tài)表的每個元素至少交換一次(盡管有可能同它自己交換),。假設(shè)j是一個均勻分布" title="均勻分布">均勻分布的隨機數(shù)，那么,，考慮狀態(tài)表中某一個特殊元素,，在所有初始化期間j都不指向此元素的概率為：
P=(255/256)∧255≈37%
(指數(shù)為255是因為當(dāng)index2和counter相等時可以忽略)
這意味著有37%的概率某一特定元素在初始化期間僅交換一次。
由此可看出：
給定一密鑰長度K(bytes),，如果E 那么由RC4的KSA 算法可看出僅K[0]....K[E-1],，和K[E]影響它,。這只是近似估算，因為index2不可能是均勻分布,。 為利用上述結(jié)果,，需要確定狀態(tài)表最可能的值。因為每個元素至少交換一次(當(dāng)counter指向它時),，所以有必要對交換可能帶來的影響加以考慮,。交換是令人討厭的非線性操作，難于分析,。然而當(dāng)處理狀態(tài)表前幾個元素時,，某個具體元素有很高的概率沒有參與它前面的幾次交換，因此還保留初始值(S[X]=X),。 相似地,僅處理狀態(tài)表中前幾個元素時,即i比較小時,S[j]有很高的概率等于j,。因此,可以得到: 狀態(tài)表中元素S[E](E比較小時)最可能的值為: 注意,本文中兩個元素操作均為模256操作。 基于以上分析,可以計算出狀態(tài)表中各個元素滿足B的概率,。為統(tǒng)計狀態(tài)表中元素滿足上式的概率,采用8比特RC4算法進行實驗,。下面為100000次實驗中S[E]中前48個元素滿足上式的概率: ? ????結(jié)果表明,經(jīng)過KSA后,狀態(tài)表中前面的一些元素實際值與用B所預(yù)測出的值強相關(guān)。 2.2 弱密鑰 首先定義it,jt分別為KSA算法經(jīng)過t步后相應(yīng)的兩個計數(shù)器的值,St為KSA經(jīng)t步后狀態(tài)盒的狀態(tài),。從其流程可以看出,PRNG首字節(jié)輸出僅僅依賴于狀態(tài)盒S中的三個值:S[1],、S[S[1]]和S[S[1]+S[S[1]]]。如果此三個值為已知,那么就可以完全確定PRNG的首字節(jié)輸出,。 KSA經(jīng)過i步操作后(i>1),，設(shè)Si[1]=X,S[X]=Y,假設(shè)j為均勻分布的隨機數(shù),那么S[1],S[X],S[X+Y]均不參與剩余交換的概率約為e-3≈0.05,此時RC4的首字節(jié)輸出為S[X+Y]?！?/P>
假設(shè)IV的長度為I個字節(jié),IV附加在密鑰Key前面組成加密密鑰K,即K=IV|Key,且我們已知K中前B個字節(jié)的值(初始化時B=0),。如果KSA經(jīng)過I+B-1次迭代后滿足: SI+B-1[1] 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) mod L] ?????? 交換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] SI+B [jI+B]=SI+B-1 [iI+B] 在滿足上述條件的情況下,S[1],S[S[1]]和S[S[1]+S[S[1]]]這三個元素以很高的概率(大于5%)均不參與KSA剩余的交換操作,也即首字節(jié)輸出以很高的概率滿足: 這種情況下,通過重建KSA,能夠成功地從首字節(jié)輸出中獲取加密密鑰中某個特定字節(jié)K[I+B]的信息: 從前面分析可以看出,在滿足SI[1] 具體算法如下: 2.3 算法改進 可以看出,以上的攻擊方法中,所有關(guān)于K[I+B]的預(yù)測均是基于其前面所有密鑰(K[0],...,K[I+B-1])已知的基礎(chǔ)上,。換言之,前面的預(yù)測錯誤將直接導(dǎo)致K[I+B]的錯誤預(yù)測,。那么能否從K[I+B]中推測出K[0],...,K[I+B-1]的信息? 考慮KSA,如果經(jīng)過I次迭代后,滿足: ?????? I ?????? 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+B??????? jI+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] 利用上述關(guān)系可以成功地推出不同K字節(jié)之間的關(guān)系,從而加速攻擊,。 另外,由于密鑰管理時密鑰需要手工輸入,所以絕大多數(shù)情況下,密鑰只是ASIIC字符,。這樣大大減小了密鑰的搜索空間,提高了攻擊效率。 3 實驗結(jié)果與結(jié)論 為對上述算法進行驗證,進行了實驗,。實驗中所采用的硬件為朗訊的ORiNOCO無線網(wǎng)卡,操作系統(tǒng)為Redhat7.1,。實驗結(jié)果表明,本文所提出的算法平均在收集100萬到200萬加密數(shù)據(jù)包的情況下,成功地恢復(fù)出了原加密密鑰。與Fluhrer,，S.,、Mantin，I.,、 Shamir,， A.所提出的KSA攻擊需要400萬到600萬數(shù)據(jù)包相比,攻擊效率有了很大提高。 基于以上分析,不難看出:現(xiàn)有WEP加密中存在重大的安全漏洞,這種情況并不因加密密鑰長度的增加而得到改善,所以在WEP2中同樣存在,。為此,建議現(xiàn)有的802.11用戶: .假設(shè)802.11鏈路層并不提供安全措施,； .為保障網(wǎng)絡(luò)通信的安全,使用IPSEC或者SSH等高層加密手段； .把所有通過802.11接入的用戶置于防火墻之外,。 .經(jīng)常更換密鑰,同時針對密鑰應(yīng)盡量采用某種HASH算法,避免采用全為ASIIC字符的加密密鑰。 ? 參考文獻 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
表示元素Out在狀態(tài)表中的位置。