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

DOI:10.16667/j.issn.2095-1302.2016.08.026

引 言

随着无线上网、移动办公的普及与流行， 无线局域网的使用已经越来越普遍。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已经开发出一款口令恢复软件—ElcomsoftDistributedPasswordRecovery， 该软件不仅具有暴力破解和字典破解功能，还可以借助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 设置的密码太长（如数十位），或者包含表中没有的字符，那么用彩虹表就无法破解，这也是字典攻击在密码破解中普遍存在的局限性。