殷松瑜

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

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

中圖分類號：TP393.08 文獻(xiàn)標(biāo)識碼：A 文章編號：2095-1302（2016）08-00-02

0 引 言

隨著無線上網(wǎng)、移動(dòng)辦公的普及與流行，無線局域網(wǎng)的使用已經(jīng)越來越普遍。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]。

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

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

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

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

2 WPA/WPA2的破解方法

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

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

除了在硬件上提升計(jì)算能力之外，加速密碼破解還可以采用預(yù)運(yùn)算的策略，即事先對特定密碼長度和特定數(shù)字字母組合使用同樣的加密算法進(jìn)行計(jì)算，生成的加密值保存在數(shù)據(jù)文件里，需要破解時(shí)直接從文件中讀取進(jìn)行比對，從而節(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秒。這一方法使用了大型查找表，對加密的密碼和由人輸入的文本進(jìn)行匹配，意味著使用大量內(nèi)存能夠減少破解密碼所需要的時(shí)間[5]。

在2006年舉行的RECON 2006安全會(huì)議上，一位來自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)過很多安全組織改進(jìn)算法并優(yōu)化程序代碼后，可以將破解速度提升到200 000 key /s甚至更多。

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

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

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

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

彩虹表的根本原理是把暴力法和查表法結(jié)合在一起，時(shí)間和內(nèi)存之間相互轉(zhuǎn)換，在空間和時(shí)間兩方面相互平衡。它的做法是，對于一個(gè)Q = H（P），建立另一個(gè)還原算法R使得P'= R（Q），然后對于一個(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

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

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

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

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

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

4 彩虹表Hash Table的生成

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

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

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

5 結(jié) 語

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

參考文獻(xiàn)

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

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

[3]賀旭娜，陰東峰.基于802_11的無線局域網(wǎng)加密協(xié)議脆弱性研究[J].洛陽師范學(xué)院學(xué)報(bào)，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]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)與算法分析[M].北京：清華大學(xué)出版社，2011.