利用浏览器的计算能力打击密码破解

本文前半部分讨论流行的PBKDF函数的含义，后半部分讨论前端计算的可行性。

前言

几乎每隔一段时间，你就会听到“XX网站被拖到图书馆”的消息。然后会有报告分析网站最常用的密码是什么，有多少，等等。

众所周知，密码通常以哈希值的形式存储在数据库中，并且也是加盐的。即使攻击者知道具体的Hash算法，也只能通过蛮力破解。按理说这是极其费力的，但在现实中，总是有大量的密码被破解。是什么让安全如此脆弱？

这有两个原因：密码和算法成本。

密码密码

密码可以记录在很多地方。最常见的是把它放在你的脑海里。当然，你也可以把它写在属于你的物品上，比如小本子、卡片等等。反正不用记在脑子里，还不如把它设置在一个长长的乱七八糟的地方方式，例如：

QQ: n5Py 2r8W qGyg 4tU6
GMail: 3TkS mVwQ hUrs wtmA
...

这种无意义的长字符串是很安全的。即使他们的Hash值和算法被泄露，攻击者也只能暴力破解所有组合获取明文：

泄露的值是 BF656DEC5DD8BA0B，泄露的算法是 f(x)。开始穷举...
尝试组合 f(x) 结果
aaaa aaaa aaaa aaaa 02F49B3EA5592B14 ×
aaaa aaaa aaaa aaab BD4E960D990DA3F3 ×
... 
n5Py 2r8W qGyg 4tU5 4CEA28A904326A26 ×
n5Py 2r8W qGyg 4tU6 BF656DEC5DD8BA0B √

即使只有字母和数字，也接近 10^28 次猜测。这是一个天文数字，几乎是不可能的。所以，这种密码还是很安全的。

但是，实际上并没有做太多事情。物品需要随身携带，非常不方便，丢失或被盗更麻烦。除非你把它们都记住了，但这并不能回到“记住在你的脑海中”的方式！

头部确实安全，但容量有限。像上面这样一个不规则的字符串，很难记住一个句子，更别说记住一个以上了。所以大家都会选择一些有意义的、有规律的字符串作为密码，比如iloveyou2016、qwert12345，或者手机号和生日的组合。这种不需要背诵的字符串就是密码（pass word）。

密码虽然方便，但也有明显的缺点：因为是正规的，所以更容易猜到。攻击者只需要测试常用词组合，或许就能猜到：

泄露的值是 2B649D47C4546A3E，泄露的算法是 f(x)。开始跑字典...
尝试组合 f(x) 结果
...
qwert yuiop 52708233CFFD6BFD ×
qwert asdfg CD07933880702B97 ×
qwert zxcvb 343F78782D73AB3A ×
qwert 12345 2B649D47C4546A3E √

这个过程就是所谓的“运行字典”。一本好的词典可以大大提高猜测的概率。

算法成本

在同一个字典的情况下，速度尤为重要。每秒可以进行多少次猜测？这取决于具体的算法。

例如 MD5 函数，每次调用大约需要 1 微秒，这意味着每秒有 100 万次猜测！ （而且这还只是单线程的速度，多用并发就更可怕了）

可见，算法越快，对破解者越有利。如果每次调用需要 10 毫秒，那么每秒只能猜测 100 次，也就是慢了 10000 倍！

不幸的是，常用的哈希函数很快。因为它们本质上是通用的，所以它们不是为密码处理而设计的。比如计算一个大文件的校验和，速度显然很重要。

因此，使用 MD5、SHA256 之类的“快速函数”来处理密码是不合理的。包括一些简单的变种，比如MD5(SHA256(x))，仍然是“快速函数”。一旦Hash值和算法泄露，很容易被“跑字典”破解。

现实中，由于很多网站使用“快速函数”处理密码，在数据库泄露后难免会恢复大量密码。

成本增加

虽然Hash函数执行一次很快，但我们可以多次重复执行，这样整体耗时变长。例如：

function slow_sha256(x)
 for i = 0 to 100000
 x = sha256(x)
 end
 return x
end

在密码学中，这称为拉伸。现实中有很多解决方案，比如PBKDF2——它没有重新设计新的算法，而是封装了已有的功能，更适合密码处理：

function pbkdf2(fn, ..., iter)
 ...
 for i = 0 to iter
 ...
 x = fn(x, ...)
 ...
 end
 ...
 return x
end

它有一个迭代参数，指定重复Hash的次数——迭代次数越多，执行时间越长，破解难度越大。

PBKDF（Password-Based Key Derivation Function，基于密码的密钥派生函数），顾名思义就是输入“password”（正则字符串）输出“key”（不规则长字符串）函数，而计算过程会消耗一定的资源。本质上也是一个Hash函数，输出结果称为DK（派生键）。

前端拉伸

越拉伸越安全，但代价是会消耗服务器上大量的计算资源！为了能够在安全性和性能之间进行折衷，通常只选择几十到几百毫秒的计算时间。

服务端计算量大到不堪重负；在今天的客户端，系统资源普遍过剩。用户可以分享一些计算吗？

听起来不可行。毕竟前端意味着公开暴力破解软件的难度，公开密码相关算法不会造成安全问题。

让我们回顾一下传统网站是如何处理密码的——前端通常只做提交，密码由后端处理：

现在，我们尝试改造前端——当用户在注册、登录等页面提交时，不再发送原密码，而是发送密码的DK：

后端，不要做任何更改。 （当然这会影响现有账号的使用，这里暂不考虑，假设这是一个新网站）

这样，即使用户的密码很简单，对应的DK仍然是无意义的长字符串。通过 DK 的 Hash 值恢复 DK 是极其困难的。 （本文开头提到）

当然，攻击者更感兴趣的不是DK，而是密码。这个是可以破解的——只要把前后端算法结合起来，组成一个新函数：

F(x) = server_hash(client_hash(x))

使用这个最终的函数F来运行字典，你仍然可以猜到密码：

尝试组合 耗时 F(x) 结果
...
qwert yuiop 1s 1C525DC73898A8EF ×
qwert asdfg 1s F9C0A131F43F1969 ×
qwert zxcvb 1s 08F026D689D26746 ×
...

只是有个client_hash的障碍，大大降低了破解速度！

所以，我们需要：

这样，大部分计算可以移到前端，后端只需要很少的处理就可以实现强密码保护系统。

反预算

因为前端的一切都是公开的，所以client_hash的算法大家都知道。攻击者可以提前计算出常用密码的DK，并编译一个新的字典。以后拖库后，直接运行这个“新词典”会节省不少时间。

对于这种方法，需要使用“salt”处理（其实PBKDF本身需要提供salt参数）。例如，选择用户 ID 作为盐：

function client_hash(password, salt) {
 return pbkdf2(sha256, password, salt, 1000000);
}
client_hash('888888', 'tom@163.com'); // b80c97beaa7ca316...
client_hash('888888', 'jack@qq.com'); // 465e26b9d899b05f...

这样即使密码相同，但用户不同，生成的DK也会不同。攻击者只能为特定账户生成字典，适用范围要小得多。

更进一步，我们甚至可以将“站点 ID”添加到 salt 中：

function client_hash(password, salt) {
 return pbkdf2(sha256, password, salt, 1000000);
}
client_hash('888888', 'jack@qq.com/www.site-a.com'); // 77a1b139aa93ac8b...
client_hash('888888', 'jack@qq.com/www.site-b.com'); // fab6b82e6a1d17d7...

这样即使是相同的“账号密码”，不同网站生成的DK也不同！

思考题：ID是公开的，可以选择一个隐藏字段作为client_hash的盐吗？

DK 泄露

DK诞生于前端，经过哈希处理后后端不再存在，所以它是一个临时值。理想情况下，它不会泄漏。

但是，在某些情况下，DK 仍可能会被泄露。比如服务器中毒、网络传输被窃听等，都会导致DK泄露。

DK泄露后，攻击者可以控制账号，这是不可避免的。幸运的是，DK 只是一个长长的无意义字符串，攻击者并不知道它背后有意义的“密码”是什么。因此，其他密码相似的账号就免了！

如果攻击者想通过DK恢复密码，他必须使用client_hash算法来运行字典——这个成本还是很高的。与之前的“最终函数F”相比，只计算了少一个server_hash。 （server_hash 本来就很快，可以忽略）。所以即使DK被泄露，破解密码的难度也基本没有降低。

“账号被盗，无法获取密码”，就是“前端Hash”的意思。

附加意义

前端拉伸计算在用户登录时会消耗一定的系统资源，这个副作用，其实也可以起到一定的防御作用。

对于普通用户来说，多花几秒的登录时间可能影响不大；但对于那些经常登录的人来说，这将是一个巨大的开销。谁登录非常频繁？这很可能是一个“撞库攻击者”——他们从其他地方获得了一堆帐户密码，然后他们来这里试试运气，看看他们能上多少。

因为我们使用DK登录，所以攻击者在提交之前还必须计算出要测试的DK，这样会增加很多计算成本。这有点类似于上一篇文章中的工作量证明。

就像拉伸弹簧需要能量一样，拉伸哈希也需要真正的计算能力。

优化体验

其实只要设计合理，就可以将等待“拉伸计算”的时间降到最低。例如，当用户输入完帐号和密码后，程序立即开始计算DK，而不是等到提交。如果网站有验证码，可以在用户输入的同时进行计算。这可以极大地改善用户体验。

总结

本文提到的3种密码：

类型安全，使用方便暴力破解软件的难度，无意义的键高差，难以记忆，只能外存，增加了存储成本。常规密码低且易记，但也容易被“运行字典”攻击转化为密钥，同上。但是，转换过程非常耗时，并且增加了运行字典的成本。

两个哈希函数：

关于“前端哈希”，其实是“零知识证明”（zero-knowledge proof）的一种。什么是零知识证明，这里有一个经典的例子：

你有一个宝库，可以通过吟唱咒语来打开。有一天你想向朋友证明你可以打开一个宝库，但你不想让他听到咒语。如何解决？

就这样，他知道你的宝库里有独一无二的宝藏。如果你能拿出来给他看，那自然就证明你能打开了。这样一来，你就不用带他到现场了，自己打开取出宝物，然后拿给他看。因此，您可以证明您可以在不暴露咒语的情况下打开。

这是一个零知识证明——证明者在不透露“任何有用信息”的情况下让验证者相信一个陈述是真实的。

实际应用

“前端Hash”的做法在“密码管理插件”中很常见：用户的密码不再发给后端，只用于生成DK。然后根据DK，为不同的账号生成不同的密码。这样，即使最坏的情况（如服务器中毒、传输窃听、后端明文存储等）导致密码泄露，您的密码也不会暴露。最多丢失一个帐号，不影响其他帐号！

(另外，密码不再填在原文本框中，而是在插件的界面中填写。插件计算出DK后，会自动填入原文本框。这样可以降低密码泄露的风险。比如网页中可能潜伏着恶意脚本）

网络应用程序

但实际上，内置前端 KDF 计算的网站并不多。不像可以调用本地程序的插件，性能高且稳定，而且浏览器混杂，不同版本的性能差异很大，所以计算时间很不稳定。

另外，长期以来（在IE时代），浏览器的计算能力非常低，以至于大家一直保持着前端计算毫无意义，“一切都是后端计算”的概念。然而，如今主流浏览器的性能已经有了很大的提升，甚至 HTML5 也引入了 WebCrypto 规范。 JS可以直接调用浏览器内置的密码算法库，包括PBKDF2。由于是原生实现的，所以性能非常高。这是一个简单的演示：

更好的 KDF

当然，PBKDF2 作为密码散列函数并不是最好的，因为它只是简单地应用现有的散列，它只是一个函数，而不是有针对性的设计。

2015 年密码哈希竞赛的获胜者 argon2 非常先进。它不仅可以设置时间成本（迭代次数），还可以设置空间成本（内存占用），使得算法严重依赖内存，因此对于一些计算能力强但存储性能一般的设备（如GPU 、ASIC 等）大幅减少。同时它还支持多线程计算，因此可以同时投入更多的工作在Hash计算上，成倍增加破解成本。