量子哈希function PBKDF2(F, ..., N) ...
for i = 0 to N
...
x = F(x, ...) ...
...
return x引言：熟悉暴力破解工具hashcat的人都知道，该软件的强大之处在于其能够充分利用GPU计算，比CPU快得多。因此，在破解WiFi握手包、数据库中的密码哈希值等情况下，可以大大提高计算效率。然而，GPU仍然属于通用硬件，显然还不是最优化的。如果为特定算法定制特定硬件，效率将提高几个数量级。比特币矿机就是一个很好的例子。硬件仍在不断进步，如果不提高系统的安全等级，暴力破解将变得越来越容易。因此，抵抗“硬件破解”的哈希算法变得非常必要。
时间成本：在讨论如何抵抗硬件破解之前，让我们先解释一下过去是如何抵抗“暴力破解”的。一些经典的哈希算法，如MD5、SHA256等，计算速度非常快。如果密码哈希使用了这些函数，当攻击者运行字典攻击时，速度将非常快。弱密码很容易被破解。为了缓解这种情况，密码学家引入了“拉伸”的概念：反复进行多次哈希计算，从而增加计算时间。例如，PBKDF2算法就使用了这种思想。它的原理很简单，对指定函数F进行N次迭代：
DK = PBKDF2(HMAC−SHA1, Password, SSID, 4096, ...)通过这种方式，可以灵活地设置哈希的时间成本。例如，设置为10000，对于开发者来说，只是多了几十毫秒的计算时间；但对于攻击者来说，破解速度降低了一万倍！然而，时间成本也有局限性。PBKDF2确实有很大的效果，但对于硬件破解来说，它并没有任何对抗措施。因为PBKDF2只是对原始函数进行简单的封装，多次执行而已。如果原始函数无法抵抗硬件破解，那么套一层PBKDF2也无济于事。例如，WiFi的WPA2协议就是让HMAC-SHA1重复执行4096次：
虽然相对于单次哈希要慢上几千倍，但这并没有阻止硬件破解。硬件仍然可以发挥其高并发的优势，让每个线程分别计算不同密码的PBKDF2：
线程1：PBKDF2(…, “12345678”, 4096, …) == KEY
线程2：PBKDF2(…, “00000000”, 4096, …) == KEY
…
…
线程100：PBKDF2(…, “88888888”, 4096, …) == KEY
虽然耗时确实增加了很多倍，但并没有影响到硬件的发挥。相同的破解任务，效率仍然远高于CPU。因此，时间成本并不能抵抗“硬件破解”。
空间成本：单纯从计算性能来看，硬件非常强大，但综合考虑其他因素，可能并不那么强大。假设某个硬件可以同时启动100个线程进行破解，但总内存只有100MB，这显然是一个很大的短板。如果有一种PBKDF算法的空间复杂度为2MB，那么将会有一半的线程因为内存不足而无法运行！如果将空间复杂度提高到100MB，那么整个硬件只能启动1个线程，99%的计算能力都无法发挥！这样，即使硬件的计算性能再强大，也最终会受限于内存瓶颈。然而，如何让算法消耗更多的内存，同时又不能轻易绕过？这里举个简单的例子：
当然，这个例子只是随意写的，并不严谨。但主要思想是，由于哈希函数的结果是不可预测的，因此无法事先知道哪些位置会被访问。只有准备充足的内存，才能实现O(1)的访问速度。攻击者要想达到相同的速度，就不得不花费同样多的内存！这就是空间成本的概念。
时空权衡：通常情况下，硬件的计算资源要比存储资源充足得多，因此可以考虑“时间换空间”的策略，即使用更复杂的存储管理机制，从而减少空间分配，这样就能开启更多的线程。例如，牺牲40%的速度，换取50%的空间：
方案 可用内存空间 分配可用线程 单线程速度 总速度
1000M 100M 10/100 10 hash/s 100 hash/s
1000M 50M 20/100 6 hash/s 120 hash/s
由于空间成本减少了一半，因此可以多启动一倍的线程。经过折损后，最终速度仍然增加了20%。当然，如果性能折损比例大于空间压缩比例，这个方案就没有意义了。
访问瓶颈：事实上，内存除了容量外，访问频率也是有限制的。内存本身每秒的读写次数是有上限的。此外，计算单元和内存之间的交互也是一个瓶颈。像MD5、SHA256这样的哈希函数，空间复杂度非常低。在硬件破解时，每个计算单元仅依靠自身的寄存器和高速缓存就足够了，很少需要访问内存。但对于Memory-Hard函数来说，情况就不那么顺利了。它不仅占用大量内存，而且还频繁地随机访问内存，很难命中高速缓存。这使得每次访问几乎都需要与内存进行交互，从而占用大量带宽。如果有多个计算单元频繁访问，那么内存带宽就会成为瓶颈。这样，也能起到抑制并发的效果！例如，bcrypt算法就运用了类似的思想，它在计算过程中频繁访问4KB的内存空间，从而消耗带宽资源。然而，随着硬件的发展，bcrypt的优势也在逐渐降低。为了能更灵活地设定内存大小，出现了scrypt算法，它既有时间成本，又有空间成本，这样就能更持久地对抗。当然，空间成本也不是绝对有效的。如果攻击者不惜代价，制造出存储容量和带宽都很充足的硬件设备，仍然能高效地进行破解。
并行维度：多年来，内存容量增加了好几倍，但CPU主频并没有大幅提升。由于受到物理因素的限制，主频已经很难提高，只能朝着多核发展。然而，像PBKDF2这样的算法只能使用单线程计算，因为它每次哈希都依赖上一次的结果。这种串行模式无法拆分成多个任务，也无法享受多线程的优势。这意味着时间成本最终会达到一个瓶颈。然而，多线程真的无能为力吗？尽管单次PBKDF无法拆分，但可以要求多次PBKDF，并且彼此之间没有依赖关系。这样，多线程就能派上用场了。例如，我们对PBKDF进行封装，要求执行4次完全独立的计算，最后将结果合并在一起：
这样，我们可以同时启动4个线程，同时计算这4个PBKDF。现在，我们可以在1秒钟内获得之前需要4秒才能达到的强度！攻击者破解时，成本增加了4倍。现在，主流的密码哈希函数都支持“并行维度”。例如，scrypt和更先进的argon2都可以通过参数p进行设置。
线程开销：实际上，并不一定需要与并行维度一样多的线程，因为还需要考虑“空间成本”。假设上述PBKDF的空间成本为512MB，如果启动4个线程，就需要占用2GB的内存！如果用户只有1.5GB的可用内存，那么只启动2个线程可能会更顺畅。当然，也可以启动3个线程，但这样会更快吗？显然不会！因为4个任务分配给3个线程，总有一个线程需要处理两份任务，所以最终用时并没有缩短。反而增加了线程创建、内存申请等开销。
DK = Client_PBKDF(Password, Username, Cost ...)这里有一个scrypt算法的在线演示，大家可以体验一下时间成本（N）、并行维度（P）和线程数（Thread）对计算的影响。
小结：通过以上讨论，我们介绍了三个对抗破解的因素。也许你已经意识到其中的理念——让哈希算法涉及更多的硬件能力。这样，只有综合性能高的硬件才能顺利运行，而专为某个功能定制的硬件就会出现瓶颈！按照这个思路，我们也可以发挥想象力：假如某个算法使用了许多条件分支指令，而CPU恰好具有强大的分支预测功能。这样，当该算法在CPU上运行时，就能获得很高的性能；而在其他精简的硬件上，效果就不会那么好。当然，这只是一种想象，自创密码学算法是不推荐的。在现实中，我们仍然应该使用更权威的算法，如argon2、scrypt等。
应用：本文提到的对抗方案都是从硬件消耗的角度进行的。然而，这样做可能会伤害自己。如果服务器每次哈希一个密码，需要花费1秒的时间和1GB的内存，那么一旦有几十个人同时访问，系统可能无法承受。有没有办法既能使用高成本的哈希函数，又不会耗费服务器资源？事实上，密码哈希完全可以在客户端计算：
因为口令与派生密钥（DK）的对应关系是唯一的。在用户注册时，提交的就是DK；在登录时，如果提交的DK相同，就证明口令是相同的。因此，客户端无需提供原始口令，服务器也能进行认证，这就是“零知识证明”。使用这种方案，还可以进一步减少口令泄露的风险，例如网络被窃听、服务器上的恶意程序等。当然，服务器收到DK后，仍然不能立即存储。因为如果DK泄露，攻击者仍然可以使用它登录用户的账号，尽管不知道口令。因此，服务器需要对DK进行哈希处理。不过，这一次只需要使用快速的哈希函数即可，因为DK是无规律的数据（熵很高），无法通过运行字典攻击来还原口令，所以简单的哈希就足以保护。
f(x) => server_hash( client_hash(x) )
这样，服务器只需要极小的计算开销，就能实现高强度的口令安全！即使将来发生了数据泄露，攻击者也只能使用如下哈希函数进行字典攻击：
因为其中使用了client_hash，所以这个最终函数同样能对抗硬件破解！
演示：根据上述思想，这里做了一个简单的演示，放在我的虚拟空间中（并且后台程序和数据都是公开的，模拟被泄露的场景）。事实上，这个虚拟空间的配置非常低，但这并不影响高强度口令的实现——只要你的电脑配置高，浏览器版本新，就足够了！尽管这些口令都是非常强的，但与简单使用MD5、SHA256等相比，成本至少高出百万倍以上！大家可以试试看多久能破解，成功后会显示红包哦。
内容来自黑客与极客
