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.