密码哈希(Password Hashing)

密码哈希（password hashing），是常用的密码管理技术。在 web 开发等工程实践中，账户密码等敏感信息通常不会明文存储到数据库，而是转换成一段哈希值存储。这样即使哪天数据库泄露了，用户的密码也不会一眼被识破。密码哈希有以下特点：

加密及验证过程

为了避免相同的密码每次加密后哈希值都一样，加密前一般会对密码加盐（adding salt），就是在密码加密前加掺入一段随机字符串。比如密码是 123456，加盐加密就是 hash("123456" + "asERQWEvzz")，只要盐不同，每次得出的哈希值就会不同。

加盐需要注意：

加盐加密的场景，验证密码时也必须要知道盐时多少。所以，盐通常也会存在数据库，或者作为哈希值的一部分保存。

验证密码的过程，需要先从数据库取出盐和哈希值，然后对待验证的密码加盐后加密，得出新哈希值，然后和数据库取出的哈希值比较是否一致。

整个完整的加密和验证过程如下:

加密

验证

加密算法一般推荐使用 key stretching 算法。比如：PBKDF2, bcrypt, scrypt。

key stretching 使得加密的算法更慢，更耗 CPU，从而加大暴力破解的难度。当然，这种情况下，如果你的密码验证需求很大，则应该考虑给它分配额外的计算资源。

而 MD5, SHA1, SHA256, SHA512, RipeMD, WHIRLPOOL, SHA3 等加密算法以后计算很快，在要求更高的场景不推荐使用。

字典攻击（dictionary attack），是使用一个由常见密、词语、短句等有意义字符组成的字典，挨个尝试。

暴力攻击（brute-force attacks），使用每个可能的字符组合，相对来说更耗费计算，效率更低。

table 是指一个把明文密码和该密码经某个算法得出的哈希值存在一起的文件。例如：4fded1464736e77865df232cbcb4cd19:yolo ，yolo 是明文密码，冒号前的部分是它的哈希值。

lookup table，就是拿表里的哈希值去比对数据库里的哈希值，如果发现相同的，也就找到了它的明文密码。

使用 lookup table 攻击的前提是，已经得到了数据库的密码哈希值，然后用它去破译明文密码。

因为 lookup table 预先把很多密码（字典）计算出对应的哈希值，使用的也是目标采用的算法（或猜测的）。所以在攻击时可以节省下计算字典哈希的时间，在大量攻击的场景下，这些时间累积就来就很可观了。

彩虹表和查询表有相似之处，都是拿内存换取计算时间的 space–time tradeoff 方法。查询表有个缺点，如果要保存足够大的字典和哈希值对，需要很大的存储空间，彩虹表通过计算一条哈希链，来减少存储空间需求。

它的原理是，先假设一个反哈希的 R 函数（reduction function），它可以将一个哈希值计算成一个和原密码相同格式（可理解为相同长度）的字符串。

假设现在有密码 p0 ，经过哈希函数 H 计算得到哈希值 h0 = H(p0), 再经过 R 函数计算，p1 = R(h0)，然后重复这一步骤 n 次算出 h1 = H(p1), p2 = R(h1)…就得出一条哈希链，最后只要保留起点 p0 和终点 pn。

如果 p0=aaaaaa，这条哈希链就如下图：

假设现在有一个哈希值 h 需要破译明文密码，可以用先用 R 函数计算出p’，再用 H 函数算出 h’，如此重复 n 次。如果某个 p’ 值正好存在于彩虹表中，则明文密码很有可能就在这条哈希链上。只需要找出这条哈希链的起始点 p0 ，再跑一遍 H，R，H，R…运算，即推断出明文密码。

以上图为例，假如哈希值是 920ECF10，用 R 计算之后得出 kiebgt，正好是存在于彩虹表。于是，遍可取出起始点 aaaaaa ，重复跑 H、R 函数计算，当算到 H(sgfnyd) = 920ECF10 ，则说明，sgfnyd 就是我们要找的明文密码。

以上只是彩虹表的基本原理，在实践中，技术细节需要优化，比如原本统一的 R 函数会变成每步都不一样的 R1 、R2、 R3 ….等等

彩虹表对破解 md5 等加密方法很有效。而防范彩虹表攻击的最大办法，就是加盐来增加破解的难度。

参考