WPA/WPA2密碼高速破解的方法

殷松瑜

摘 要：無線局域網(wǎng)在日常工作、學習、生活中的應用越來越廣泛，加密標準WPA/WPA2到目前為止沒有明顯的安全設計缺陷，有效的破解方法是采用字典攻擊，一般都用事先制作好的密碼字典來破解。文中針對“時間內存替換”法和彩虹表在WPA/WPA2字典攻擊中能夠顯著提高破解速度的應用進行了分析探討與研究。

關鍵詞：無線局域網(wǎng)；密碼破解；字典攻擊；時間內存替換法；彩虹表

中圖分類號：TP393.08 文獻標識碼：A 文章編號：2095-1302（2016）08-00-02

0 引 言

隨著無線上網(wǎng)、移動辦公的普及與流行，無線局域網(wǎng)的使用已經越來越普遍。WLAN的安全加密標準為WEP、WPA和WPA2。WEP加密由于設計上的缺陷很容易被快速破解，并不能真正保護數(shù)據(jù)的安全，目前已很少在實際中使用。隨著數(shù)據(jù)安全保護技術的發(fā)展、計算機硬件計算能力的提升以及云計算的普及，我們會不斷發(fā)現(xiàn)正在使用的計算機設備軟硬件系統(tǒng)中的安全漏洞 [1]。

本文針對WPA/WPA2加密標準使用“時間內存替換”法來破解密碼的性能展開分析，并對彩虹表的應用進行了探討研究。

1 WLAN加密標準——WPA和WPA2

WPA 的認證實際上是對MIC的認證。MIC由PTK產生，計算PTK需要ANonce、SNonce、客戶端STA的Mac地址SA、無線接入點AP的Mac地址AA以及PMK。而PMK由SSID和WPA密碼計算得出[2]。假如已經知道了密碼，且握手過程是由合法的STA產生，那么只要獲得第1次和第2次握手的相關信息就可以計算出MIC的值。

由于加密標準設計原理的不同，破解WPA/WPA2和破解WEP完全不同，任何一個客戶端AP連接時必須事先握手認證，攻擊者對已經連接到AP的合法用戶通過攻擊手段使其掉線，合法用戶會再次自動連接AP，這時攻擊者就可以通過監(jiān)聽方式得到握手認證包進行破解[3]。

2 WPA/WPA2的破解方法

加密標準WPA/WPA2到目前為止還沒有發(fā)現(xiàn)明顯的安全設計漏洞，唯一有效的破解手段就是字典攻擊，因為目前的軟件還不支持在線暴力破解，所以一般都通過導入制作好的密碼字典來破解。

對WPA/WPA2的破解很大程度上受制于現(xiàn)有的計算機處理能力，已經有研究機構和公司從提升擴展計算能力的角度來展開研究，利用顯卡中GPU強大的并行計算能力來提高破解密碼的速度。俄羅斯安全公司Elcomsoft已經開發(fā)出一款口令恢復軟件—Elcomsoft Distributed Password Recovery，該軟件不僅具有暴力破解和字典破解功能，還可以借助GPU硬件加速破解，提升速度達50倍以上，支持Nvidia和ATI部分型號顯卡，更重要的是它還支持分布式計算功能，可以利用互聯(lián)網(wǎng)上的多臺計算機并行計算破解同一個加密系統(tǒng)，成倍提高破解密碼的效率[4]。

除了在硬件上提升計算能力之外，加速密碼破解還可以采用預運算的策略，即事先對特定密碼長度和特定數(shù)字字母組合使用同樣的加密算法進行計算，生成的加密值保存在數(shù)據(jù)文件里，需要破解時直接從文件中讀取進行比對，從而節(jié)省計算密碼所需的大量時間和資源，使攻擊效率大幅度提高[3]。

2003年7月瑞士洛桑聯(lián)邦技術學院Philippe Oechslin公布了一些實驗結果，他及其所屬的安全密碼學實驗室（LASEC）采用了時間內存替換的方法，將一個常用操作系統(tǒng)的密碼破解速度由1分41秒提升到13.6秒。這一方法使用了大型查找表，對加密的密碼和由人輸入的文本進行匹配，意味著使用大量內存能夠減少破解密碼所需要的時間[5]。

在2006年舉行的RECON 2006安全會議上，一位來自Openciphers組織的名為David Hulton的安全人員詳細演示了使用WPA-PSK Hash Tables破解的技術細節(jié)，即使用普通機器利用“時間內存替換”法破解，調用WPA Hash Table 字典進行破解的速度可以達到50 000 key /s，經過很多安全組織改進算法并優(yōu)化程序代碼后，可以將破解速度提升到200 000 key /s甚至更多。

3 “時間內存替換”法和彩虹表

哈希（Hash）算法是將任意長度的二進制值映射為較短的固定長度的二進制值，這個值就是哈希值。如果散列計算一段明文哪怕只更改該段落的一個字母，隨后產生的哈希值都會不同[6]。要找到兩個不同的輸入散列值為同一個數(shù)值的，在計算上幾乎是不可能的，所以數(shù)據(jù)的哈希值可以檢驗數(shù)據(jù)沒有被修改過的完整性。Hash算法經常被用來保存密碼，這樣既不用泄露密碼，又可以校驗輸入的密碼是否正確。常用的散列函數(shù)有MD5、SHA1等。

破解用Hash函數(shù)加密，即對于給定的一個q，反過來計算出一個p來滿足q = H（p）。通常有兩種辦法，一種是暴力破解窮舉法，把每一個可能的p都算出H（p），直到結果等于q；另一種辦法是預先運算查表法，把每一個可能的p和對應的q都記錄下來，按q做索引，做成數(shù)據(jù)庫文件，查表校對即可。在這兩種辦法中，前一種可能需要海量的時間，后一種需要海量的存儲空間，因此目前無法實現(xiàn)。

舉例來說，對于14位的大小寫字母和數(shù)字（不算特殊字符）所有可能的組合組成的密碼集合是（26×2+10）14 = 6214 = 1.24×1025，假如每納秒校驗一個p，暴力破解法大概需4億年；若采用查表法，假定哈希（Hash）算法的計算值是128位即16字節(jié)，光存放哈希值也需要1026字節(jié)的存儲空間。

彩虹表的根本原理是把暴力法和查表法結合在一起，時間和內存之間相互轉換，在空間和時間兩方面相互平衡。它的做法是，對于一個Q = H（P），建立另一個還原算法R使得P'= R（Q），然后對于一個p0，這樣進行計算：

H（p0）=q1 ，R（q1）=p1，H（p1）=q2，R（q2）=p2，H（p2）=q3，R （q3）=p3，……

H（pn-2）=qn-1，R（qn-1）=pn-1，H（pn-1）=qn，R（qn）=pn

簡單來說，把p用函數(shù)H、R依次迭代運算，最后得到pn，n可能的數(shù)值比較大。最后將p0和pn都存儲下來，其他的結果都不要。并用不同的p0代入計算，得到多個這樣的p的函數(shù)鏈。

在破解用Hash函數(shù)加密時，對于給定的一個q，反過來計算滿足H（p）=q的數(shù)值p。

做運算R （q）= c1，然后把c1和每一個p散列函數(shù)鏈的最后一個進行比較，假如和某一個pn相等，那么qn所對應的pn-1就有可能是我們尋找的p，把qn對應的pn-1再做一次鏈式計算，比對H （pn-1）是否等于qn，如果是，則pn-1就是我們在找尋的p，因為H （p）=q。

把c1和每一個p散列函數(shù)鏈的最后一個做比較，假如和任何一個pn都不相等，我們再算R （q）= c1，H（c1）=c2，再比對c2是否等于qn，如果是，那么pn-2就可能是p；否則再算c3、c4直到cn-1。 如果還找不到p，就繼續(xù)尋找直到遍歷所有的p0pn函數(shù)鏈。

如上所述，用一個p0pn對來存儲一個函數(shù)鏈的數(shù)據(jù)，可以大大減小存儲的空間。但是這樣可能要做n次比對，時間很長，甚至幾天破解一個密碼也很正常。

4 彩虹表Hash Table的生成

彩虹表Hash Table的生成效率很慢，加上需要根據(jù)預攻擊AP的SSID調整內容，建立針對所有常見接入點，并采用簡單密碼的彩虹表Hash Table，其文件硬盤空間最少需要1 G ～3 G。生成彩虹表的工具有Ophcrack、rcracki_mt、Cain等，彩虹表函數(shù)鏈分割得越精確，破解成功率就越高，但是生成文件體積就越龐大，生成時間就越長。經測試，4核4 GB內存的機器生成2 GB彩虹表，總共用了8天時間。

建立彩虹表還有其他相關問題，例如怎樣選擇合適的函數(shù)R，解決Hash沖突，如何選擇p0來實現(xiàn)足夠的覆蓋，如何在有限資源下生成彩虹表等。

最小彩虹表是最基本的字母數(shù)字表，其大小為388 MB，這是Ophcrack啟動盤默認的表，該表可以在11分鐘內破解所有長度為14位數(shù)字加字母密碼組合中的99.9%。國內有比較流行的傳說中的120 G的彩虹表，國外還有幾T的海量彩虹表。

5 結 語

綜上所述，彩虹表Hash Table雖然能夠顯著提高WPA/WPA2的破解速度，但這些彩虹表都有其特定適用的密碼長度和字母組合，不存在能夠破解所有密碼的萬能彩虹表。WPA/WPA2設置的密碼太長（如數(shù)十位），或者包含表中沒有的字符，那么用彩虹表就無法破解，這也是字典攻擊在密碼破解中普遍存在的局限性。

參考文獻

[1]朱海濤.WLAN加密原理與破解方法[J].保密科學，2012（12） ： 55-58

[2]白珅，王軼駿，薛質.WPA_WPA2協(xié)議安全性研究[J].信息安全與通信保密， 2012（1）：106-108

[3]賀旭娜，陰東峰.基于802_11的無線局域網(wǎng)加密協(xié)議脆弱性研究[J].洛陽師范學院學報，2012，31（8）：79-81

[4] Lei Zhang， Jiang Yu， Rong Zong， et al.Prevention research of Cracking WPA-PSK key based on GPU[C].Consumer Electronics， Communications and Networks（CECNet）， 2012 2nd International Conference： 1965-1959.

[5] Philippe Oechslin. Making a Faster Cryptanalytic Time-Memory Trade-Off[C].Advances in Cryptology - CRYPTO 2003Volume 2729 of the series Lecture Notes in Computer Science： 617-630.

[6]嚴蔚敏，吳偉民.數(shù)據(jù)結構與算法分析[M].北京：清華大學出版社，2011.