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

殷松瑜

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

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

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

0 引 言

隨著無線上網、移動辦公的普及與流行，無線局域網的使用已經越來越普遍。WLAN的安全加密標準為WEP、WPA和WPA2。WEP加密由于設計上的缺陷很容易被快速破解，并不能真正保護數據的安全，目前已很少在實際中使用。隨著數據安全保護技術的發展、計算機硬件計算能力的提升以及云計算的普及，我們會不斷發現正在使用的計算機設備軟硬件系統中的安全漏洞 [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，這時攻擊者就可以通過監聽方式得到握手認證包進行破解[3]。

2 WPA/WPA2的破解方法

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

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

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

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

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

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

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

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

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

彩虹表的根本原理是把暴力法和查表法結合在一起，時間和內存之間相互轉換，在空間和時間兩方面相互平衡。它的做法是，對于一個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用函數H、R依次迭代運算，最后得到pn，n可能的數值比較大。最后將p0和pn都存儲下來，其他的結果都不要。并用不同的p0代入計算，得到多個這樣的p的函數鏈。

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

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

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

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

4 彩虹表Hash Table的生成

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

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

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

5 結 語

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

參考文獻

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

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

[3]賀旭娜，陰東峰.基于802_11的無線局域網加密協議脆弱性研究[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]嚴蔚敏，吳偉民.數據結構與算法分析[M].北京：清華大學出版社，2011.