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

DOI:10.16667/j.issn.2095-1302.2016.08.026

引 言

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

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

1 WLAN加密標(biāo)準(zhǔn)——WPA 和 WPA2

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

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

2 WPA/WPA2的破解方法

加密標(biāo)準(zhǔn)WPA/WPA2 到目前為止還沒(méi)有發(fā)現(xiàn)明顯的安全設(shè)計(jì)漏洞，唯一有效的破解手段就是字典攻擊，因?yàn)槟壳暗能浖€不支持在線暴力破解，所以一般都通過(guò)導(dǎo)入制作好的密碼字典來(lái)破解。

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

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

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

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

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

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

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

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

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

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

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

簡(jiǎn)單來(lái)說(shuō)，把 p 用函數(shù) H、R 依次迭代運(yùn)算，最后得到pn，n 可能的數(shù)值比較大。最后將 p0和 pn都存儲(chǔ)下來(lái)，其他的結(jié)果都不要。并用不同的 p0 代入計(jì)算，得到多個(gè)這樣的 p 的函數(shù)鏈。

在破解用Hash 函數(shù)加密時(shí)，對(duì)于給定的一個(gè) q，反過(guò)來(lái)計(jì)算滿足 H（p）=q 的數(shù)值 p。

做運(yùn)算 R（q）= c1，然后把 c1 和每一個(gè) p 散列函數(shù)鏈的最后一個(gè)進(jìn)行比較，假如和某一個(gè) pn 相等，那么 qn 所對(duì)應(yīng)的 pn －1 就有可能是我們尋找的 p，把 qn 對(duì)應(yīng)的 pn －1 再做一次鏈 式計(jì)算，比對(duì) H（pn －1）是否等于 qn，如果是，則 pn －1 就是 我們?cè)谡覍さ?p，因?yàn)?H（p）=q。

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

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

4 彩虹表Hash Table的生成

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

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

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

5 結(jié) 語(yǔ)

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