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

DOI:10.16667/j.issn.2095-1302.2016.08.026

引 言

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

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

1 WLAN加密標準——WPA 和 WPA2

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

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

2 WPA/WPA2的破解方法

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

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

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

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

在 2006 年舉行的RECON 2006 安全會議上，一位來自O(shè)penciphers 組織的名為David Hulton 的安全人員詳細演示了使用WPA-PSK Hash Tables 破解的技術(shù)細節(jié)，即使用普通機器利用“時間內(nèi)存替換”法破解，調(diào)用 WPA Hash Table 字典進行破解的速度可以達到 50 000 key /s，經(jīng)過很多安全組織

改進算法并優(yōu)化程序代碼后，可以將破解速度提升到 200 000 key /s 甚至更多。

3“時間內(nèi)存替換”法和彩虹表

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

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

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

彩虹表的根本原理是把暴力法和查表法結(jié)合在一起，時間和內(nèi)存之間相互轉(zhuǎn)換，在空間和時間兩方面相互平衡。它的做法是，對于一個 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都存儲下來，其他的結(jié)果都不要。并用不同的 p0 代入計算，得到多個這樣的 p 的函數(shù)鏈。

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

做運算 R（q）= c1，然后把 c1 和每一個 p 散列函數(shù)鏈的最后一個進行比較，假如和某一個 pn 相等，那么 qn 所對應(yīng)的 pn －1 就有可能是我們尋找的 p，把 qn 對應(yīng)的 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 調(diào)整內(nèi)容，建立針對所有常見接入點，并采用簡單密碼的彩虹表Hash Table，其文件硬盤空間最少需要 1 G～3 G。生成彩虹表的工具有Ophcrack、rcracki_mt、Cain 等， 彩虹表函數(shù)鏈分割得越精確，破解成功率就越高，但是生成文件體積就越龐大，生成時間就越長。經(jīng)測試，4 核 4 GB 內(nèi)存的機器生成 2 GB 彩虹表，總共用了 8 天時間。

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

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

5 結(jié) 語

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