160 秒搞定——用 Rainbow Hash 破解密码

Jeff Atwood 最近撰文提到一个被称为“ Rainbow Hash 破解法”的密码破解技巧。这种技巧，一个字典攻击（dictionary attack）的变种，依赖于一种快速搜索机制从而针对一些预先计算出来的 hash 值进行表格查找。Jeff 由审视密码存储的形势入手，指出密码无论何时也不应该以明文保存：

密码永远不要保存成明文。 至少是不应该这么做，除非你是用世界上最小儿科的程序员们构建一个全世界最不安全的系统。相反的，密码要存储成某个 hash 函数的输出。hash 是单向操作。即使一个攻击者获得权限看到你经过 hash 的密码，也不可能只从 hash 值重建密码。

Rainbow 表方法是预先算出 hash 值，通过创建很大的表格而节省时间：

但是有可能通过rainbow 表去攻击密码的 hash 值：预先计算出来的数量庞大的 hash 值，涵盖所有可能的字符组合。一台攻击 PC 当然可以凭空计算所有这些 hash，但借助一个预计算 hash 值的海量表带来的优势，就会使攻击进程加快好几个数量级。——假定用来攻击的机器有足够内存可以把整张表（至少其大部分）都保存在主存里。

Ophcrack ，一个 Windows 密码破解工具，正是利用了 Rainbow 表技巧。在一台 Windows XP 机器上，Jeff 用 ophcrack 附带的最小的（388Mb）表以 3 分钟找出了五个密码中的两个。这个表包括大小写混合字母以及数字（大约 800 亿 hash 值），并能够破解 99.9% 的 Windows LanManager 密码。Jeff 忠告说 LM hash 支持应该默认被禁用，这种微软早期加密机制在 Rainbow 表攻击面前非常脆弱：

我震惊于遗留的 Lan Manager 支持“特性”仍旧在 Windows Server 2003 中默认启用。高度建议禁用 Lan Manager hash ，特别是在保存着域中每个用户的认证信息的 Windows 服务器上。

LM Hash 容易被此类攻击攻破，是因为它没有使用现今常用的给加密过程引入“salt”的方式。加密的密码如果不使用 salt，通过反向检索找到明文密码就相对简单。

但是当一个远程黑客从服务器或者数据库拿到了一长串 hash 过的密码时，我们就有麻烦了。Rainbow 表攻击是严重的风险。这就是为什么你无论何时都不该仅仅依赖 hash——永远给 hash 加些 salt 以获得独一无二的 hash 结果值。

“salt”由一些随机数据位组成，用于和密码同时输入 hash 函数，而从以下两个主要方面缓解风险：

• 它使得 hash 值有所加长，并有可能加入表生成过程所用字符集以外的字符
• 由于每个用户的 salt 都是不同的，实际上每个密码需要一个独立的 Rainbow 表

这两项都显著增加了破解每个和全部密码所需要的时间。继 Jeff 的文章之后，Thomas Ptacek 撰文“ Rainbow 表讨论得够多了：关于安全密码方案你需要知道些什么”指出，击退密码攻击的关键是使用一个加密算法，它相对较慢，而且能够一直慢下去，比如 bcrypt ：

为什么 bcrypt 是这么大的赢家？请从两方面来考虑这个问题：服务器和攻击者。 首先看服务器：你每小时处理几万个登录，或者说每秒几十个。比起数据库访问、页面刷新和 IO，密码校验是微不足道的。你并不介意密码校验需要花费两倍时间，或甚至是十倍时间，因为密码 hash 并不是瓶颈所在。

现在看看攻击者。很简单，攻击者相当介意密码校验要花费两倍时间。如果一次密码校验需要两倍时间，那整个密码破解时间也要两倍。

Jeff 得出结论，保护你的密码免于 Rainbow 表攻击的解决方案就是向你的密码中加入 salt。

查看英文原文： http://www.infoq.com/news/2007/09/rainbowtables