记录黑客技术中优秀的内容, 传播黑客文化,分享黑客技术精华
用过暴力破解工具 hashcat 的都知道，这款软件的强大之处在于它能充分利用 GPU 计算，比起 CPU 要快很多。所以在破解诸如 WiFi 握手包、数据库中的口令 Hash 值时，能大幅提高计算效率。
当然 GPU 仍属于通用硬件，显然还不是最优化的。要是为特定的算法打造特定的硬件，效率更是高出几个量级。比特币矿机就是很好的例子。
硬件的仍在不断进步，系统安全等级若不提高，暴力破解将会越来越容易。因此，一种能抵抗「硬件破解」的 Hash 算法，显得很有必要。
在探讨如何对抗硬件之前，先来讲解过去是如何对抗「暴力破解」的。
一些经典的 Hash 算法，例如 MD5、SHA256 等，计算速度是非常快的。如果口令 Hash 用了这类函数，将来攻击者跑字典时，可达到非常高的速度。那些强度不高的口令，很容易被破解。
为了缓解这种状况，密码学家引入了「拉伸」的概念：反复 Hash 多次，从而增加计算时间。
例如 PBKDF2 算法就运用了这种思想。它的原理很简单，对指定函数 F 反复进行 N 次：
function PBKDF2(F, ..., N)
for i = 0 to N
x = F(x, ...)
这样就能灵活设定 Hash 的时间成本了。例如设定 10000，对开发者来说，只是多了几十毫秒的计算；但对于攻击者，破解速度就降低了一万倍！
时间成本局限性
PBKDF2 确实有很大的效果，但对于硬件破解，却无任何对抗措施。
因为 PBKDF2 只是对原函数简单封装，多执行几次而已。如果原函数不能对抗硬件，那么套一层 PBKDF2 同样也不能。
例如 WiFi 的 WPA2 协议，就是让 HMAC-SHA1 重复执行 4096 次：
DK = PBKDF2(HMAC-SHA1, Password, SSID, 4096, ...)
虽然相比单次 Hash 要慢上几千倍，但这并不妨碍硬件破解。
硬件依然可发挥其「高并发」优势，让每个线程分别计算不同口令的 PBKDF2：
PBKDF2(…, &#8″, 4096, …) == KEY
PBKDF2(…, &#0″, 4096, …) == KEY
PBKDF2(…, &#8″, 4096, …) == KEY
虽然耗时确实增加了很多倍，但并没有影响到硬件的发挥。同样的破解，效率仍然远高于 CPU。
所以，时间成本并不能抵抗「硬件破解」。
单论计算性能，硬件是非常逆天的，但再综合一些其他因素，或许就未必那么强大了。
假如某个硬件可开启 100 个线程同时破解，但总内存却只有 100M —— 这显然是个很大的短板。
如果有种 PBKDF 算法空间复杂度为 2M，那将会有一半的线程，因内存不足而无法运行！
若再极端些，将空间复杂度提高到 100M，那么整个硬件只能开启 1&个线程，99%&的算力都无法得到发挥！
这样，即使硬件的计算性能再强劲，也终将卡在内存这个瓶颈上。
不过，怎样才能让算法消耗这么多内存，同时又不能被轻易绕过？这里举个简单的例子：
function MemoryHard(..., M)
int space[M]
for i = 0 .. 10000
x = Hash(x, ...)
space[int(x) % M] ^= int(x)
return Hash(space)
当然这个例子是随意写的，并不严谨。但主要思想是：
引入了空间成本 M，并申请相应的内存
利用经典 Hash 函数的结果，作为数组索引，对内存进行读写
每次内存读写，都会影响到最终结果
由于 Hash 函数的结果是不可预测的，因此事先无法知道哪些位置会被访问。只有准备充足的内存，才能达到 O(1) 的访问速度。
攻击者要想达到同样的速度，就不得不花费同样多的内存！
通常硬件的「计算资源」要比「存储资源」充足得多，因此可考虑「时间换空间」的策略 —— 使用更复杂的存储管理机制，从而减少空间分配，这样就能开启更多的线程。
比如牺牲 40% 的速度，换取 50% 的空间：
单线程速度
100 hash/s
120 hash/s
由于空间成本是之前的一半，因此可多启动一倍的线程。算上折损，最终速度仍增加了 20%。
当然，如果 性能折损比例 & 空间压缩比例，这个方案就没有意义了。
事实上，内存除了容量外，访问频率也是有限制的。
就内存本身而言，每秒读写次数是有上限的。其次，计算单元和内存之间的交互，更是一大瓶颈。
像 MD5、SHA256 这类 Hash 函数，空间复杂度非常低。硬件破解时，每个计算单元光靠自身的寄存器以及高速缓存，就差不多够用了，很少需要访问内存。
但对于 Memory-Hard 函数，就没那么顺利了。它不仅很占内存，而且还十分频繁地「随机访问」内存，因此很难命中高速缓存。这使得每次访问，几乎都会和内存进行交互，从而占用大量带宽。
如果有多个计算单元频繁访问，那么内存带宽就会成为瓶颈。这样，也能起到抑制并发的效果！
例如 bcrypt 算法就运用了类似思想，它在计算过程中频繁访问 4KB 的内存空间，从而消耗带宽资源。
不过随着硬件发展，bcrypt 的优势也在逐渐降低。为了能更灵活地设定内存大小，scrypt 算法出现了 —— 它既有时间成本，还有空间成本，这样就能更持久地对抗。
当然，空间成本也不是绝对有效的。如果攻击者不惜代价，制造出存储「容量」和「带宽」都很充足的硬件设备，那么仍能高效地进行破解。
十几年来，内存容量翻了好几翻，但 CPU 主频却没有很大提升。由于受到物理因素的制约，主频已很难提升，只能朝着多核发展。
然而像 PBKDF2 这样的算法，却只能使用单线程计算 —— 因为它每次 Hash 都依赖上一次的 Hash 结果。这种串行的模式，是无法拆解成多个任务的，也就无法享受多线程的优势。
这就意味着 —— 时间成本，终将达到一个瓶颈！
对此，多线程真的无能为力吗？
尽管单次 PBKDF 不能被拆解，但可以要求多次 PBKDF，并且互相没有依赖。这样多线程就能派上用场了。
例如我们对 PBKDF 进行封装，要求执行 4 次完全独立的计算，最后再将结果融合到一起：
function Parall(Password, Salt, ...)
-- 该部分可被并行 --
for i = 0 .. 4
DK[i] = PBKDF(Password, Salt + i, ...)
------------------
return Hash(DK)
这样，我们即可开启 4 个线程，同时计算这 4 个 PBKDF。
现在就能用 1 秒的时间，获得之前 4 秒的强度！攻击者破解时，成本就增加了 4 倍。
如今主流的口令 Hash 函数都支持「并行维度」。例如 scrypt 以及更先进的 argon2，都可通过参数 p 设定。
现实中，「线程数」未必要和「并行维度」一样多，因为还得考虑「空间成本」。
假设上述的 PBKDF 空间成本有 512MB，如果开启 4 个线程，就得占用 2GB 的内存！若用户只有 1.5 GB 的空闲内存，还不如只开 2 个线程，反而会更顺畅。
当然，也可以开 3 个线程，但这样会更快吗？显然不会！
因为 4 个任务分给 3 个线程，总有一个线程得做两份，所以最终用时并没有缩短。反而增加了线程创建、内存申请等开销。
这里有个 scrypt 算法在线演示：
大家可体会下 时空成本（N）、并行维度（P）、线程数（Thread）对计算的影响。
到此，我们讲解了 3 个对抗破解的因素：
时间成本（迭代次数）
空间成本（内存容量、带宽）
并行维度（多线程资源）
或许你已感悟到这其中的理念 —— 让 Hash 算法牵涉更多的硬件能力。这样，只有综合性能高的硬件，才能顺利运行；专为某个功能打造的硬件，就会出现瓶颈！
照这个思路，我们也可发挥想象：假如有个算法使用了不少条件分支指令，而 CPU 正好拥有强大的分支预测功能。这样该算法在 CPU 上运行时，就能获得很高的性能；而在其他精简过的硬件上，就没有这么好的效果了。
当然这里纯属想象，自创密码学算法是不推荐的。现实中还是得用更权威的算法，例如 argon2、scrypt 等。
本文提到的对抗方案，都是从硬件消耗上进行的。不过，这样伤敌一千也会自损八百。
假如服务器每 Hash 一次口令，就得花 1 秒时间加 1GB 内存，那么一旦有几十个人同时访问，系统可能就支撑不住了。
有什么办法，既能使用高成本的 Hash，又不耗费服务器资源？事实上，口令 Hash 完全可以在客户端计算：
DK = Client_PBKDF(Password, Username, Cost ...)
因为口令与 DK 的对应关系是唯一的。账号注册时，提交的就是 DK；登录时，如果提交的 DK 相同，也就证明口令是相同的。
所以客户端无需提供原始口令，服务端也能认证，这就是「零知识证明」。使用这种方案，还能进一步减少口令泄露的环节，例如网络被窃听、服务端恶意程序等。
当然，服务端收到 DK 后，还不能立即存储。因为万一 DK 泄露了，攻击者还是能用它登上用户的账号 —— 尽管不知道口令。
因此，服务端需对 DK 再进行 Hash 处理。
不过这一次，只需快速的 Hash 函数即可。因为 DK 是无规律的数据（熵很高），无法通过跑字典还原，所以用简单的 Hash 就能保护。
这样，服务器只需极小的计算开销，就能实现高强度的口令安全了！
将来即使被拖库，攻击者也只能使用如下 Hash 函数跑字典：
f(x) =& server_hash( client_hash(x) )
因为其中用到了 client_hash，所以这个最终函数同样能对抗硬件破解！
根据上述思想，这里做个简单的演示，放在我的虚拟空间里：&
（并且&&都是公开的，模拟被拖库的场景）
事实上，这个虚拟空间的配置非常低，但这并不影响高强度口令的实现 —— 只要你的电脑配置高、浏览器版本新，那就够了！
尽管这其中都是不能再弱的数字口令，不过相比简单使用 MD5、SHA256 这些的，成本至少高百万倍以上！大家试试多久能破解，成功了会显示红包哦
*本文作者：EtherDream，转载请注明来自Freebuf
阅读:33845 | 评论:0 | 标签:
想收藏或者和大家分享这篇好文章→
关注公众号hackdig，学习最新黑客技术（更新： ）
天下武功，唯快不破。但在密码学中则不同。算法越快，越容易破。
0x01 暴力破解
密码破解（严格地说应该是账号口令的破解），就是把散列值还原成明文口令。这貌似有不少方法，但事实上都得走一条路：暴力穷举。（也许你会说还可以查表，瞬间就出结果。虽然查表不用穷举，但表的制造过程仍然需要。查表只是将穷举提前了而已）
因为散列计算是单向的，是不可逆的，所以只能穷举。穷举的原理很简单。只要知道密文用的是什么 Hash 算法，我们也用同样的算法把常用词组跑一遍。若有结果和密文一样，那就猜中了。
穷举的速度有多快？这和算法有关。Hash 一次有多快，猜一次也这么快。
例如 MD5 就非常快的，若每次 Hash 耗费 1 微秒，那破解时猜一个词组，也只需 1 微秒（假设机器都性能一样，词组长度相近），攻击者一秒钟就能猜 100 万个！（而且这还只是单线程的速度）
所以，Hash 算法越快，破解起来就越容易。
0x02 慢 Hash
如果能提高 Hash 时间，显然也能增加破解时间。如果 Hash 一次提高到 10 毫秒，那么攻击者每秒只能猜 100 个，破解速度就慢了一万倍。
怎样才能让 Hash 变慢？最简单的，就是对 Hash 后的结果再 Hash，反复多次。例如原本 1 微秒，重复一万次，就慢一万倍了：
function slow_md5(x)
for i = 0 to 10000
x = md5(x)
攻击者破解时，也必须用这套算法跑字典。于是，破解时间就大幅增加了。
事实上，这样的「慢 Hash」算法早有现成的方案，例如 bcrypt、PBKDF2 等等。它们都有一个难度系数因子，可以控制 Hash 次数，想多慢就多慢。
所以 Hash 过程越慢，破解也就越费劲。
0x03 慢 Hash 应用
最需要慢 Hash 的场合，就是网站数据库里的账号口令。
近几年，经常能听到网站被「拖库」的新闻。用户资料都是明文存储，泄露了也无法挽回。唯独口令，还可以和攻击者对抗一下。
然而不少网站，使用的都是快速 Hash 算法，因此轻易就能破解出一堆弱口令账号。
当然，有时只想破解某个特定人物的账号。只要不是特别复杂的词汇，跑上几天，很可能就破出来。
但网站用了慢 Hash，结果可能就不一样了。如果把 Hash 时间提高 100 倍，破解时间就得长达数月，变得难以接受。
即使数据泄露，也能保障「明文口令」这最后一道隐私。
0x04 慢 Hash 缺点
不过，慢 Hash 也有明显的缺点：消耗大量计算资源。
使用慢 Hash 的网站，如果同时来了多个用户，服务器 CPU 可能就不够用了。要是遇到恶意用户，发起大量的登录请求，甚至造成资源被耗尽。
性能和安全总是难以兼得。所以，一般也不会使用太高的强度。
一些大型网站，甚至为此投入集群，用来处理大量的 Hash 计算。但这需要不少的成本。
有没有什么方法，可以让我们使用算力强劲、同时又免费的计算资源？
0x05 前端计算
在过去，个人电脑和服务器的速度，还是有较大差距的。但如今，随着硬件发展进入瓶颈，这个差距正缩小。在单线任务处理上，甚至不相上下。
客户端拥有强大的算力，能不能分担一些服务器的工作？
尤其像「慢 Hash」这种算法开源、但计算沉重的任务，为何不交给客户端来完成？
传统方案，提交的几乎是明文口令；现在，提交的则是明文口令的「Hash 结果」。（无论是注册，还是登陆）
而服务端则无需任何改动。先前是怎么保存的，现在还是怎么保存。
这样就算被拖库，攻击者破解出来的也只是「Hash 结果」，还需再破解一次，才能还原出「明文口令」。
事实上，这个「Hash 结果」是不可能还原出来的。为什么这么说呢？因为它是毫无规律的随机串，而字典都是有意义的词组，几乎不可能跑到它！除非字节逐个穷举，但这将是个天文数字。
所以中间值，是无法通过数据库泄露的数据「跑」出来的！
当然，即使不知道这个中间值，也没影响明文的破解。攻击者可以把前端 Hash + 后端的 Hash，组合成一个新的函数：
f(x) = back_hash( front_hash(x) )
然后使用这个新函数来跑字典。这样，理论上还是可以跑出来的。但是，有 front_hash 这个重量级的函数存在，跑字典的速度就大幅降低了，于是就能增加攻击者的破解成本！
0x06 对抗预先计算
不过前端的一切都是公开的，所以 front_hash 的算法大家都知道。
攻击者可以用这套算法，把常用词组的「慢 Hash 结果」提前算出来，制作成一个「新字典」。将来拖库后，就可以直接跑这个新字典了。
对抗这种方法，还得用经典的手段：加盐。最简单的，将用户名作为盐值：
front_hash(password, username)
这样即使相同的口令，对于不同的用户，「Hash 结果」也变得不一样了。
除了用户名，还可以将网站的域名、或者其他固定信息，也加入到盐值中，这样不同的网站也不能共享同个彩虹表了。使得破解方案更不通用。
0x07 强度策略
密码学上的问题到此结束，下面讨论实现上的问题。现实中，用户的算力是不均衡的。有人用的是神级配置，也有的是古董机。这样，Hash 的次数就很难设定。如果古董机用户登录会卡上几十秒，那肯定是不行的。因此必要得有控制强度的方案。
1.强度固定
根据大众的配置，制定一个适中的强度，绝大多数用户都可接受。
但如果超过规定时间还没完成，就把算到一半的 Hash 和步数提交上来，剩余部分让服务器来完成。
[前端] 完成 70% ----& [后端] 计算 30%
不过，这需要「可序列化」的算法，才能在服务端还原进度。如果计算过程涉及大量的内存，这种方案就不可行了。
相比过去 100% 后端慢 Hash，这种少量用户「前后参半」的方式，可以节省不少服务器资源。
2.强度可变
如果后端不提供任何协助，那只能根据自身条件做取舍了。配置差的用户，Hash 次数少一点。
用户注册时，算法不限步数放开跑，看看特定时间里能算到多少步：
# [注册阶段] 算力评估（线程 1 秒后中止）
x = hash(x)
iter = iter + 1
这个步数，就是 Hash 强度，会保存到账号信息里。之后每次登录时，先获取这个强度值，然后再做相应次数的 Hash：
# 先获取用户的强度值
# 重复 Hash 相应次数
for i = 0 to iter
x = hash(x)
使用这个方案，可以让 高配置的用户享受更高的安全性；低配置的用户，也不会影响基本使用。（用上好电脑还能提升安全性，很有优越感吧~）
但这有个重要的前提：注册和登录，必须在性能相近的设备上 —— 如果是在高配置电脑上注册的账号，某天去古董机登录，那就悲剧了，可能半天都算不出来。。。
3.动态调整方案
上述情况，现实中是普遍存在的。比如 PC 端注册的账号，在移动端登录，算力可能就不够用。
如果没有后端协助，那只能等。要是经常在低端设备上登陆，那每次都得干等吗？
等一两次就算了，如果每次都等，不如重新估量下自己的能力吧。把强度动态调低，更好的适应当前环境。
将来如果不用低端设备了，再自动的调整回来。让强度值，能动态适应常用的设备的算力。
0x08 性能优化
1.为什么要优化
或许你会问，「慢 Hash」不就是希望计算更慢吗，为什么还要去优化？
假如这是一个自创的隐蔽式算法，并且混淆到外人根本无法读懂，那不优化也没事。甚至可以在里面放一些空循环，故意消耗时间。但事实上，我们选择的肯定是「密码学家推荐」的公开算法。它们每一个操作，都是有数学上的意义的。
原本一个操作只需一条 CPU 指令，因为不够优化，用了两条指令，那么额外的时间就是内耗。导致用时更久，强度却未提升。
2.前端计算软肋
如果是本地程序，根本不用考虑这个问题，交给编译器就行。但在 Web 环境里，我们只能用浏览器计算！相比本地程序，脚本要慢的多，因此内耗会很大。
脚本为什么慢？主要还是这几点：
脚本，是用来处理简单逻辑的，并不是用来密集计算的，所以没必要强类型。不过如今有了一个黑科技：asm.js。它能通过语法糖，为 JS 提供真正的强类型。这样计算速度就大幅提升了，可以接近本地程序的性能！
但是不支持 asm.js 的浏览器怎么办？例如，国内还有大量的 IE 用户，他们的算力是非常低的。好在还有个后补方案 —— Flash，它有各种高性能语言的特征。类型，自然不在话下。相比 asm.js，Flash 还是要慢一些，但比 IE 还是快多了。
解释型语言，不仅需要语法分析，更是失去了「编译时深度优化」带来的性能提升。
好在 Mozilla 提供了一个可以从 C/C++ 编译成 asm.js 的工具：emscripten。有了它，就不用裸写了。而且编译时经过 LLVM 的优化，生成的代码质量会更高。
事实上，这个概念在 Flash 里早有了。曾经有个叫 Alchemy 的工具，能把 C/C++ 交叉编译成 Flash 虚拟机指令，速度比 ActionScript 快不少。
一些本地语言看似很简单的操作，在沙箱里就未必如此。例如数组操作：
vector[k] = v
虚拟机首先得检查索引是否越界，否则会有严重的问题。如果「前端慢 Hash」算法涉及到大量内存随机访问，那就会有很多无意义的内耗，因此得慎重考虑。
不过有些特殊场合，脚本速度甚至能超过本地程序！例如开头提到的 MD5 大量反复计算，比本地程序还快。这其实不难解释：
首先，MD5 算法很简单。没有查表这样的内存操作，使用的都是局部变量。
其次，emscripten 的优化能力，并不比本地编译器差。
最后，本地程序编译之后，机器指令就不会再变了；而如今脚本引擎，都有 JIT 这个利器，运行时生成更优化的机器指令。
所以选择算法时，还得兼顾实际运行环境，扬长避短，发挥出最大功效。
0x09 对抗 GPU
众所周知，跑密码使用 GPU 可以快很多倍。GPU 可以想象成一个有几百核的处理器，但只能执行一些简单的指令。虽然单核速度不及 CPU，但可以通过数量取胜。暴力穷举时，可以从字典里取出上千个词汇同时跑，破解效率就提高了。
那能否在算法里添加一些特征，正好命中 GPU 的软肋呢？
1.显存瓶颈
大家听过说「莱特币」吧。不同于比特币，莱特币挖矿使用了 scrypt 算法。这种算法对内存依赖非常大，需要频繁读写一个表。GPU 虽然每个线程都能独立计算，但显存只有一个，大家共享使用。
这意味着，同时只有一个线程能操作显存，其他有需要的只能等待了。这样，就极大遏制了并发的优势。
2.移植难度
山寨币遍地开花的时候，还出现了一个叫 X11Coin 的币，据称能对抗 ASIC。它的原理很简单，里面掺杂了 11 种不同的算法。这样，制造出相应的 ASIC 复杂度大幅增加了。
尽管这不是一个长久的对抗方案，但思路还是可以借鉴的。如果一件事过于复杂，很多攻击者就望而生畏了，不如去做更容易到手的事。
3.其他想法
之所以 GPU 能大行其道，是因为目前的 Hash 算法，都是简单的公式运算。这对 CPU 并没太大的优势。能否设计一个算法，充分依赖 CPU 的优势？
CPU 有很多隐藏的强项，例如流水线。如果算法中有大量的条件分支，也许 GPU 就不擅长了。
当然，这里只是设想。自己创造密码学算法，是非常困难的，也不推荐这么做。
0x0A 额外意义
慢 Hash 除了能降低破解速度，还有一些其他意义：
1.减少泄露风险
用户输入的明文口令，在浏览器内存里就已被散列化了。泄露风险，在用户输入后就就已结束。
而传统的方案，明文口令会一直传递服务器的业务程序中才消失，这中间存在极大的泄露风险。
2.增加撞库成本
「前端慢 Hash」需要消耗用户的计算资源。这个缺点，有时也是件好事。
对于正常用户来说，登录时多等一秒影响并不大；但对于频繁登录的用户来说，这就是一个障碍了。
谁会频繁登录？也许就是撞库攻击者。他们无法拖下这个网站的数据库，于是就用在线登录的方式，不断的测试弱口令账号。
如果通过 IP 来控制频率，攻击者可以找大量的代理 —— 网速有多快，就能试多快。但使用了前端慢 Hash，攻击者每次测试，就得消耗大量的计算，于是将瓶颈卡在硬件上 —— 能算多快，才能试多快。
所以，这里有点类似 PoW（Proof-of-Work，工作量证明）的意义。关于 PoW，以后我们会详细介绍。
0x0B 无法做到的
尽管「前端慢 Hash」有不少优势，但也不是万能的。如果环境本身就有问题，那么任何隐私都有泄露。
下面我们来思考一个场景：某网站使用了「前端慢 Hash」，但没有使用 HTTPS —— 这会导致链路被窃听。
回顾 0x05 小节，如果拿到 Hash 结果，就可以直接登上账号，即使不知道明文口令。
的确如此。但请仔细想一想，这不也降低损失了吗？
本来不仅账号被盗用，而且明文口令也会泄露；而如今，只是账号被盗用，明文口令对方仍无法获得。
所以，前端慢 Hash 的真正保护的是 明文口令，而不是账号的授权。简单地说：账号被盗，密码拿不到！
当然，如果攻击者不仅能窃听，还能控制流量的话，就可以往页面注入 JS 脚本，这样倒是可以拿到明文口令的。不过这和电脑中毒、摄像头偷窥一样，都属于「环境本身有问题」，不在本文讨论范围内。本文讨论的是数据库泄露的场景。
0x0C 多线程
用户的配置越来越好，不少都是四核、八核处理器。能否利用多线程的优势，将慢 Hash 计算进行分解？
如果每一步计算都依赖之前的结果，是无法进行拆解的。例如：
for i = 0 to 10000
x = hash(x)
这是一个串行的计算。然而只有并行的问题，才能分解成多个小任务。
不过，换一种方式的多线程也是可以的。例如我们使用 4 个线程：
x1 = hash(password, salt1)
for i = 0 to 2500
x1 = hash(x1)
x2 = hash(password, salt2)
for i = 0 to 2500
x2 = hash(x2)
最终将 4 个结果合并起来，再做一次散列，作为结果。
finalHash = hash(x1, x2, x3, x4)
这样，每 Hash 一个明文口令，就需要数倍的算力资源。同样，破解起来成本也变得更大了。而对于用户来说，只要支持多线程，总体花费的时间几乎没有增加，并不影响体验。
当然，这个细节不用自己实现，现实中早已有这样的算法。例如 2015 年《Password Hashing Competition》胜出者 ，就可设置并行数量。（这个算法很先进，包括了 GPU 抵抗等特性）
前端慢 Hash，就是让每个用户贡献少量的计算资源，使得 Hash 计算变得更强劲。使得数据泄露后，攻击者需要花费更大的成本去破解。
阅读(...) 评论()用过暴力破解工具 hashcat 的都知道，这款软件的强大之处在于它能充分利用 GPU 计算，比起 CPU 要快很多。所以在破解诸如 WiFi 握手包、数据库中的口令 Hash 值时，能大幅提高计算效率。
当然 GPU 仍属于通用硬件，显然还不是最优化的。要是为特定的算法打造特定的硬件，效率更是高出几个量级。比特币矿机就是很好的例子。
硬件的仍在不断进步，系统安全等级若不提高，暴力破解将会越来越容易。因此，一种能抵抗「硬件破解」的 Hash 算法，显得很有必要。
在探讨如何对抗硬件之前，先来讲解过去是如何对抗「暴力破解」的。
一些经典的 Hash 算法，例如 MD5、SHA256 等，计算速度是非常快的。如果口令 Hash 用了这类函数，将来攻击者跑字典时，可达到非常高的速度。那些强度不高的口令，很容易被破解。
为了缓解这种状况，密码学家引入了「拉伸」的概念：反复 Hash 多次，从而增加计算时间。
例如 PBKDF2 算法就运用了这种思想。它的原理很简单，对指定函数 F 反复进行 N 次：
function PBKDF2(F, ..., N)
for i = 0 to N
x = F(x, ...)
这样就能灵活设定 Hash 的时间成本了。例如设定 10000，对开发者来说，只是多了几十毫秒的计算；但对于攻击者，破解速度就降低了一万倍！
时间成本局限性
PBKDF2 确实有很大的效果，但对于硬件破解，却无任何对抗措施。
因为 PBKDF2 只是对原函数简单封装，多执行几次而已。如果原函数不能对抗硬件，那么套一层 PBKDF2 同样也不能。
例如 WiFi 的 WPA2 协议，就是让 HMAC-SHA1 重复执行 4096 次：
DK = PBKDF2(HMAC-SHA1, Password, SSID, 4096, ...)
虽然相比单次 Hash 要慢上几千倍，但这并不妨碍硬件破解。
硬件依然可发挥其「高并发」优势，让每个线程分别计算不同口令的 PBKDF2：
PBKDF2(…, “″, 4096, …) == KEY
PBKDF2(…, “″, 4096, …) == KEY
PBKDF2(…, “″, 4096, …) == KEY
虽然耗时确实增加了很多倍，但并没有影响到硬件的发挥。同样的破解，效率仍然远高于 CPU。
所以，时间成本并不能抵抗「硬件破解」。
单论计算性能，硬件是非常逆天的，但再综合一些其他因素，或许就未必那么强大了。
假如某个硬件可开启 100 个线程同时破解，但总内存却只有 100M —— 这显然是个很大的短板。
如果有种 PBKDF 算法空间复杂度为 2M，那将会有一半的线程，因内存不足而无法运行！
若再极端些，将空间复杂度提高到 100M，那么整个硬件只能开启 1 个线程，99% 的算力都无法得到发挥！
这样，即使硬件的计算性能再强劲，也终将卡在内存这个瓶颈上。
不过，怎样才能让算法消耗这么多内存，同时又不能被轻易绕过？这里举个简单的例子：
function MemoryHard(..., M)
int space[M]
for i = 0 .. 10000
x = Hash(x, ...)
space[int(x) % M] ^= int(x)
return Hash(space)
当然这个例子是随意写的，并不严谨。但主要思想是：
引入了空间成本 M，并申请相应的内存
利用经典 Hash 函数的结果，作为数组索引，对内存进行读写
每次内存读写，都会影响到最终结果
由于 Hash 函数的结果是不可预测的，因此事先无法知道哪些位置会被访问。只有准备充足的内存，才能达到 O(1) 的访问速度。
攻击者要想达到同样的速度，就不得不花费同样多的内存！
通常硬件的「计算资源」要比「存储资源」充足得多，因此可考虑「时间换空间」的策略 —— 使用更复杂的存储管理机制，从而减少空间分配，这样就能开启更多的线程。
比如牺牲 40% 的速度，换取 50% 的空间：
单线程速度
100 hash/s
120 hash/s
由于空间成本是之前的一半，因此可多启动一倍的线程。算上折损，最终速度仍增加了 20%。
当然，如果 性能折损比例 & 空间压缩比例，这个方案就没有意义了。
事实上，内存除了容量外，访问频率也是有限制的。
就内存本身而言，每秒读写次数是有上限的。其次，计算单元和内存之间的交互，更是一大瓶颈。
像 MD5、SHA256 这类 Hash 函数，空间复杂度非常低。硬件破解时，每个计算单元光靠自身的寄存器以及高速缓存，就差不多够用了，很少需要访问内存。
但对于 Memory-Hard 函数，就没那么顺利了。它不仅很占内存，而且还十分频繁地「随机访问」内存，因此很难命中高速缓存。这使得每次访问，几乎都会和内存进行交互，从而占用大量带宽。
如果有多个计算单元频繁访问，那么内存带宽就会成为瓶颈。这样，也能起到抑制并发的效果！
例如 bcrypt 算法就运用了类似思想，它在计算过程中频繁访问 4KB 的内存空间，从而消耗带宽资源。
不过随着硬件发展，bcrypt 的优势也在逐渐降低。为了能更灵活地设定内存大小，scrypt 算法出现了 —— 它既有时间成本，还有空间成本，这样就能更持久地对抗。
当然，空间成本也不是绝对有效的。如果攻击者不惜代价，制造出存储「容量」和「带宽」都很充足的硬件设备，那么仍能高效地进行破解。
十几年来，内存容量翻了好几翻，但 CPU 主频却没有很大提升。由于受到物理因素的制约，主频已很难提升，只能朝着多核发展。
然而像 PBKDF2 这样的算法，却只能使用单线程计算 —— 因为它每次 Hash 都依赖上一次的 Hash 结果。这种串行的模式，是无法拆解成多个任务的，也就无法享受多线程的优势。
这就意味着 —— 时间成本，终将达到一个瓶颈！
对此，多线程真的无能为力吗？
尽管单次 PBKDF 不能被拆解，但可以要求多次 PBKDF，并且互相没有依赖。这样多线程就能派上用场了。
例如我们对 PBKDF 进行封装，要求执行 4 次完全独立的计算，最后再将结果融合到一起：
function Parall(Password, Salt, ...)
-- 该部分可被并行 --
for i = 0 .. 4
DK[i] = PBKDF(Password, Salt + i, ...)
------------------
return Hash(DK)
这样，我们即可开启 4 个线程，同时计算这 4 个 PBKDF。
现在就能用 1 秒的时间，获得之前 4 秒的强度！攻击者破解时，成本就增加了 4 倍。
如今主流的口令 Hash 函数都支持「并行维度」。例如 scrypt 以及更先进的 argon2，都可通过参数 p 设定。
现实中，「线程数」未必要和「并行维度」一样多，因为还得考虑「空间成本」。
假设上述的 PBKDF 空间成本有 512MB，如果开启 4 个线程，就得占用 2GB 的内存！若用户只有 1.5 GB 的空闲内存，还不如只开 2 个线程，反而会更顺畅。
当然，也可以开 3 个线程，但这样会更快吗？显然不会！
因为 4 个任务分给 3 个线程，总有一个线程得做两份，所以最终用时并没有缩短。反而增加了线程创建、内存申请等开销。
这里有个 scrypt 算法在线演示：
大家可体会下 时空成本（N）、并行维度（P）、线程数（Thread）对计算的影响。
到此，我们讲解了 3 个对抗破解的因素：
时间成本（迭代次数）
空间成本（内存容量、带宽）
并行维度（多线程资源）
或许你已感悟到这其中的理念 —— 让 Hash 算法牵涉更多的硬件能力。这样，只有综合性能高的硬件，才能顺利运行；专为某个功能打造的硬件，就会出现瓶颈！
照这个思路，我们也可发挥想象：假如有个算法使用了不少条件分支指令，而 CPU 正好拥有强大的分支预测功能。这样该算法在 CPU 上运行时，就能获得很高的性能；而在其他精简过的硬件上，就没有这么好的效果了。
当然这里纯属想象，自创密码学算法是不推荐的。现实中还是得用更权威的算法，例如 argon2、scrypt 等。
本文提到的对抗方案，都是从硬件消耗上进行的。不过，这样伤敌一千也会自损八百。
假如服务器每 Hash 一次口令，就得花 1 秒时间加 1GB 内存，那么一旦有几十个人同时访问，系统可能就支撑不住了。
有什么办法，既能使用高成本的 Hash，又不耗费服务器资源？事实上，口令 Hash 完全可以在客户端计算：
DK = Client_PBKDF(Password, Username, Cost ...)
因为口令与 DK 的对应关系是唯一的。账号注册时，提交的就是 DK；登录时，如果提交的 DK 相同，也就证明口令是相同的。
所以客户端无需提供原始口令，服务端也能认证，这就是「零知识证明」。使用这种方案，还能进一步减少口令泄露的环节，例如网络被窃听、服务端恶意程序等。
当然，服务端收到 DK 后，还不能立即存储。因为万一 DK 泄露了，攻击者还是能用它登上用户的账号 —— 尽管不知道口令。
因此，服务端需对 DK 再进行 Hash 处理。
不过这一次，只需快速的 Hash 函数即可。因为 DK 是无规律的数据（熵很高），无法通过跑字典还原，所以用简单的 Hash 就能保护。
这样，服务器只需极小的计算开销，就能实现高强度的口令安全了！
将来即使被拖库，攻击者也只能使用如下 Hash 函数跑字典：
f(x) =& server_hash( client_hash(x) )
因为其中用到了 client_hash，所以这个最终函数同样能对抗硬件破解！
根据上述思想，这里做个简单的演示，放在我的虚拟空间里：
都是公开的，模拟被拖库的场景）
事实上，这个虚拟空间的配置非常低，但这并不影响高强度口令的实现 —— 只要你的电脑配置高、浏览器版本新，那就够了！
尽管这其中都是不能再弱的数字口令，不过相比简单使用 MD5、SHA256 这些的，成本至少高百万倍以上！大家试试多久能破解，成功了会显示红包哦
登录以评论
注册.36狂计
开启狂计之旅
还没账号!戳这}