（更新：https://www.cnblogs.com/index-html/p/frontend_kdf.html ）

[h1]0x00 前言[/h1]
天下武功，唯快不破。但在密码学中则不同。算法越快，越容易破。

[h1]0x01 暴力破解[/h1]
密码破解（严格地说应该是账号口令的破解），就是把散列值还原成明文口令。这貌似有不少方法，但事实上都得走一条路：暴力穷举。（也许你会说还可以查表，瞬间就出结果。虽然查表不用穷举，但表的制造过程仍然需要。查表只是将穷举提前了而已）

因为散列计算是单向的，是不可逆的，所以只能穷举。穷举的原理很简单。只要知道密文用的是什么 Hash 算法，我们也用同样的算法把常用词组跑一遍。若有结果和密文一样，那就猜中了。

穷举的速度有多快？这和算法有关。Hash 一次有多快，猜一次也这么快。

例如 MD5 就非常快的，若每次 Hash 耗费 1 微秒，那破解时猜一个词组，也只需 1 微秒（假设机器都性能一样，词组长度相近），攻击者一秒钟就能猜 100 万个！（而且这还只是单线程的速度）

所以，Hash 算法越快，破解起来就越容易。

[h1]0x02 慢 Hash[/h1]
如果能提高 Hash 时间，显然也能增加破解时间。如果 Hash 一次提高到 10 毫秒，那么攻击者每秒只能猜 100 个，破解速度就慢了一万倍。

怎样才能让 Hash 变慢？最简单的，就是对 Hash 后的结果再 Hash，反复多次。例如原本 1 微秒，重复一万次，就慢一万倍了：

function slow_md5(x)

    for i = 0 to 10000

        x = md5(x)

    return x

end

攻击者破解时，也必须用这套算法跑字典。于是，破解时间就大幅增加了。

事实上，这样的「慢 Hash」算法早有现成的方案，例如

bcrypt

、

PBKDF2

等等。它们都有一个难度系数因子，可以控制 Hash 次数，想多慢就多慢。

所以 Hash 过程越慢，破解也就越费劲。

[h1]0x03 慢 Hash 应用[/h1]
最需要慢 Hash 的场合，就是网站数据库里的账号口令。

近几年，经常能听到网站被「拖库」的新闻。用户资料都是明文存储，泄露了也无法挽回。唯独口令，还可以和攻击者对抗一下。

然而不少网站，使用的都是快速 Hash 算法，因此轻易就能破解出一堆弱口令账号。

当然，有时只想破解某个特定人物的账号。只要不是特别复杂的词汇，跑上几天，很可能就破出来。

但网站用了慢 Hash，结果可能就不一样了。如果把 Hash 时间提高 100 倍，破解时间就得长达数月，变得难以接受。

即使数据泄露，也能保障「明文口令」这最后一道隐私。

[h1]0x04 慢 Hash 缺点[/h1]
不过，慢 Hash 也有明显的缺点：消耗大量计算资源。

使用慢 Hash 的网站，如果同时来了多个用户，服务器 CPU 可能就不够用了。要是遇到恶意用户，发起大量的登录请求，甚至造成资源被耗尽。

性能和安全总是难以兼得。所以，一般也不会使用太高的强度。

一些大型网站，甚至为此投入集群，用来处理大量的 Hash 计算。但这需要不少的成本。

有没有什么方法，可以让我们使用算力强劲、同时又免费的计算资源？

[h1]0x05 前端计算[/h1]
在过去，个人电脑和服务器的速度，还是有较大差距的。但如今，随着硬件发展进入瓶颈，这个差距正缩小。在单线任务处理上，甚至不相上下。

客户端拥有强大的算力，能不能分担一些服务器的工作？

尤其像「慢 Hash」这种算法开源、但计算沉重的任务，为何不交给客户端来完成？




传统方案，提交的几乎是明文口令；现在，提交的则是明文口令的「Hash 结果」。（无论是注册，还是登陆）

而服务端则无需任何改动。先前是怎么保存的，现在还是怎么保存。

这样就算被拖库，攻击者破解出来的也只是「Hash 结果」，还需再破解一次，才能还原出「明文口令」。




事实上，这个「Hash 结果」是不可能还原出来的。为什么这么说呢？因为它是毫无规律的随机串，而字典都是有意义的词组，几乎不可能跑到它！除非字节逐个穷举，但这将是个天文数字。

所以中间值，是无法通过数据库泄露的数据「跑」出来的！

当然，即使不知道这个中间值，也没影响明文的破解。攻击者可以把前端 Hash + 后端的 Hash，组合成一个新的函数：

f(x) = back_hash( front_hash(x) )

然后使用这个新函数来跑字典。这样，理论上还是可以跑出来的。但是，有

front_hash

这个重量级的函数存在，跑字典的速度就大幅降低了，于是就能增加攻击者的破解成本！

[h1]0x06 对抗预先计算[/h1]
不过前端的一切都是公开的，所以 front_hash 的算法大家都知道。

攻击者可以用这套算法，把常用词组的「慢 Hash 结果」提前算出来，制作成一个「新字典」。将来拖库后，就可以直接跑这个新字典了。

对抗这种方法，还得用经典的手段：加盐。最简单的，将用户名作为盐值：

front_hash(password, username)

这样即使相同的口令，对于不同的用户，「Hash 结果」也变得不一样了。

除了用户名，还可以将网站的域名、或者其他固定信息，也加入到盐值中，这样不同的网站也不能共享同个彩虹表了。使得破解方案更不通用。

[h1]0x07 强度策略[/h1]
密码学上的问题到此结束，下面讨论实现上的问题。现实中，用户的算力是不均衡的。有人用的是神级配置，也有的是古董机。这样，Hash 的次数就很难设定。如果古董机用户登录会卡上几十秒，那肯定是不行的。因此必要得有控制强度的方案。

[h2]1.强度固定[/h2]
根据大众的配置，制定一个适中的强度，绝大多数用户都可接受。

但如果超过规定时间还没完成，就把算到一半的 Hash 和步数提交上来，剩余部分让服务器来完成。

[前端] 完成 70% ----> [后端] 计算 30%

不过，这需要「可序列化」的算法，才能在服务端还原进度。如果计算过程涉及大量的内存，这种方案就不可行了。

相比过去 100% 后端慢 Hash，这种少量用户「前后参半」的方式，可以节省不少服务器资源。

[h2]2.强度可变[/h2]
如果后端不提供任何协助，那只能根据自身条件做取舍了。配置差的用户，Hash 次数少一点。

用户注册时，算法不限步数放开跑，看看特定时间里能算到多少步：

# [注册阶段] 算力评估（线程 1 秒后中止）

while

    x = hash(x)

    iter = iter + 1

end

这个步数，就是 Hash 强度，会保存到账号信息里。之后每次登录时，先获取这个强度值，然后再做相应次数的 Hash：

# 先获取用户的强度值

...



# 重复 Hash 相应次数

for i = 0 to iter

    x = hash(x)

end

使用这个方案，可以让高配置的用户享受更高的安全性；低配置的用户，也不会影响基本使用。（用上好电脑还能提升安全性，很有优越感吧~）

但这有个重要的前提：注册和登录，必须在性能相近的设备上 —— 如果是在高配置电脑上注册的账号，某天去古董机登录，那就悲剧了，可能半天都算不出来。。。

[h2]3.动态调整方案[/h2]
上述情况，现实中是普遍存在的。比如 PC 端注册的账号，在移动端登录，算力可能就不够用。

如果没有后端协助，那只能等。要是经常在低端设备上登陆，那每次都得干等吗？

等一两次就算了，如果每次都等，不如重新估量下自己的能力吧。把强度动态调低，更好的适应当前环境。

将来如果不用低端设备了，再自动的调整回来。让强度值，能动态适应常用的设备的算力。

[h1]0x08 性能优化[/h1]
[h2]1.为什么要优化[/h2]
或许你会问，「慢 Hash」不就是希望计算更慢吗，为什么还要去优化？

假如这是一个自创的隐蔽式算法，并且混淆到外人根本无法读懂，那不优化也没事。甚至可以在里面放一些空循环，故意消耗时间。但事实上，我们选择的肯定是「密码学家推荐」的公开算法。它们每一个操作，都是有数学上的意义的。

原本一个操作只需一条 CPU 指令，因为不够优化，用了两条指令，那么额外的时间就是内耗。导致用时更久，强度却未提升。

[h2]2.前端计算软肋[/h2]
如果是本地程序，根本不用考虑这个问题，交给编译器就行。但在 Web 环境里，我们只能用浏览器计算！相比本地程序，脚本要慢的多，因此内耗会很大。

脚本为什么慢？主要还是这几点：

• 弱类型
• 解释型
• 沙箱

[h2]3.弱类型[/h2]
脚本，是用来处理简单逻辑的，并不是用来密集计算的，所以没必要强类型。不过如今有了一个黑科技：asm.js。它能通过语法糖，为 JS 提供真正的强类型。这样计算速度就大幅提升了，可以接近本地程序的性能！

但是不支持 asm.js 的浏览器怎么办？例如，国内还有大量的 IE 用户，他们的算力是非常低的。好在还有个后补方案 —— Flash，它有各种高性能语言的特征。类型，自然不在话下。相比 asm.js，Flash 还是要慢一些，但比 IE 还是快多了。

[h2]4.解释型[/h2]
解释型语言，不仅需要语法分析，更是失去了「编译时深度优化」带来的性能提升。

好在 Mozilla 提供了一个可以从 C/C++ 编译成 asm.js 的工具：emscripten。有了它，就不用裸写了。而且编译时经过 LLVM 的优化，生成的代码质量会更高。

事实上，这个概念在 Flash 里早有了。曾经有个叫 Alchemy 的工具，能把 C/C++ 交叉编译成 Flash 虚拟机指令，速度比 ActionScript 快不少。

[h2]5.沙箱[/h2]
一些本地语言看似很简单的操作，在沙箱里就未必如此。例如数组操作：

vector[k] = v

虚拟机首先得检查索引是否越界，否则会有严重的问题。如果「前端慢 Hash」算法涉及到大量内存随机访问，那就会有很多无意义的内耗，因此得慎重考虑。

不过有些特殊场合，脚本速度甚至能超过本地程序！例如开头提到的 MD5 大量反复计算，比本地程序还快。这其实不难解释：

首先，MD5 算法很简单。没有查表这样的内存操作，使用的都是局部变量。

其次，emscripten 的优化能力，并不比本地编译器差。

最后，本地程序编译之后，机器指令就不会再变了；而如今脚本引擎，都有 JIT 这个利器，运行时生成更优化的机器指令。

所以选择算法时，还得兼顾实际运行环境，扬长避短，发挥出最大功效。

[h1]0x09 对抗 GPU[/h1]
众所周知，跑密码使用 GPU 可以快很多倍。GPU 可以想象成一个有几百核的处理器，但只能执行一些简单的指令。虽然单核速度不及 CPU，但可以通过数量取胜。暴力穷举时，可以从字典里取出上千个词汇同时跑，破解效率就提高了。

那能否在算法里添加一些特征，正好命中 GPU 的软肋呢？

[h2]1.显存瓶颈[/h2]
大家听过说「莱特币」吧。不同于比特币，莱特币挖矿使用了 scrypt 算法。这种算法对内存依赖非常大，需要频繁读写一个表。GPU 虽然每个线程都能独立计算，但显存只有一个，大家共享使用。

这意味着，同时只有一个线程能操作显存，其他有需要的只能等待了。这样，就极大遏制了并发的优势。

[h2]2.移植难度[/h2]
山寨币遍地开花的时候，还出现了一个叫 X11Coin 的币，据称能对抗 ASIC。它的原理很简单，里面掺杂了 11 种不同的算法。这样，制造出相应的 ASIC 复杂度大幅增加了。

尽管这不是一个长久的对抗方案，但思路还是可以借鉴的。如果一件事过于复杂，很多攻击者就望而生畏了，不如去做更容易到手的事。

[h2]3.其他想法[/h2]
之所以 GPU 能大行其道，是因为目前的 Hash 算法，都是简单的公式运算。这对 CPU 并没太大的优势。能否设计一个算法，充分依赖 CPU 的优势？

CPU 有很多隐藏的强项，例如流水线。如果算法中有大量的条件分支，也许 GPU 就不擅长了。

当然，这里只是设想。自己创造密码学算法，是非常困难的，也不推荐这么做。

[h1]0x0A 额外意义[/h1]
慢 Hash 除了能降低破解速度，还有一些其他意义：

[h2]1.减少泄露风险[/h2]
用户输入的明文口令，在浏览器内存里就已被散列化了。泄露风险，在用户输入后就就已结束。

而传统的方案，明文口令会一直传递服务器的业务程序中才消失，这中间存在极大的泄露风险。

[h2]2.增加撞库成本[/h2]
「前端慢 Hash」需要消耗用户的计算资源。这个缺点，有时也是件好事。

对于正常用户来说，登录时多等一秒影响并不大；但对于频繁登录的用户来说，这就是一个障碍了。

谁会频繁登录？也许就是撞库攻击者。他们无法拖下这个网站的数据库，于是就用在线登录的方式，不断的测试弱口令账号。

如果通过 IP 来控制频率，攻击者可以找大量的代理 —— 网速有多快，就能试多快。但使用了前端慢 Hash，攻击者每次测试，就得消耗大量的计算，于是将瓶颈卡在硬件上 —— 能算多快，才能试多快。

所以，这里有点类似 PoW（Proof-of-Work，工作量证明）的意义。关于 PoW，以后我们会详细介绍。

[h1]0x0B 无法做到的[/h1]
尽管「前端慢 Hash」有不少优势，但也不是万能的。如果环境本身就有问题，那么任何隐私都有泄露。

下面我们来思考一个场景：某网站使用了「前端慢 Hash」，但没有使用 HTTPS —— 这会导致链路被窃听。

回顾 0x05 小节，如果拿到 Hash 结果，就可以直接登上账号，即使不知道明文口令。

的确如此。但请仔细想一想，这不也降低损失了吗？

本来不仅账号被盗用，而且明文口令也会泄露；而如今，只是账号被盗用，明文口令对方仍无法获得。

所以，前端慢 Hash 的真正保护的是明文口令，而不是账号的授权。简单地说：账号被盗，密码拿不到！

当然，如果攻击者不仅能窃听，还能控制流量的话，就可以往页面注入 JS 脚本，这样倒是可以拿到明文口令的。不过这和电脑中毒、摄像头偷窥一样，都属于「环境本身有问题」，不在本文讨论范围内。本文讨论的是数据库泄露的场景。

[h1]0x0C 多线程[/h1]
用户的配置越来越好，不少都是四核、八核处理器。能否利用多线程的优势，将慢 Hash 计算进行分解？

如果每一步计算都依赖之前的结果，是无法进行拆解的。例如：

for i = 0 to 10000

    x = hash(x)

end

这是一个串行的计算。然而只有并行的问题，才能分解成多个小任务。

不过，换一种方式的多线程也是可以的。例如我们使用 4 个线程：

# 线程 1

x1 = hash(password, salt1)

for i = 0 to 2500

    x1 = hash(x1)

end



# 线程 2

x2 = hash(password, salt2)

for i = 0 to 2500

    x2 = hash(x2)

end



# ...

最终将 4 个结果合并起来，再做一次散列，作为结果。

finalHash = hash(x1, x2, x3, x4)

这样，每 Hash 一个明文口令，就需要数倍的算力资源。同样，破解起来成本也变得更大了。而对于用户来说，只要支持多线程，总体花费的时间几乎没有增加，并不影响体验。

当然，这个细节不用自己实现，现实中早已有这样的算法。例如 2015 年《Password Hashing Competition》胜出者 argon2 算法，就可设置并行数量。（这个算法很先进，包括了 GPU 抵抗等特性）

[h1]0x0D 总结[/h1]
前端慢 Hash，就是让每个用户贡献少量的计算资源，使得 Hash 计算变得更强劲。使得数据泄露后，攻击者需要花费更大的成本去破解。