哈希算法(Hash Algorithm)

哈希算法（又称散列算法）是把某个较大的集合P映射到另一个较小的集合Q中，假如这个算法叫H，那么就有Q = H(P)，对于P中任何一个值p都有唯一确定的q与之对应。

此外，哈希算法还应该满足：

给出一个q，很难反向推算出一个p满足q = H(p)（解读：哈希算法应该是单向不可逆的）；
给出一个p1，很难算出一个不等于p1的p2使得H(p1)=H(p2)（解读：如果原数据只改动了一丁点，哈希的结果也会完全不同）；

正因为有这样的特性，哈希算法有两大用途：

生成消息摘要(Message Digest)：例如我们在网上下载一份镜像，通常网站会同时提供一个MD5或者SHA256，即是用来验证数据的完整性；
保存密码：由于哈希后的密码是密文保存的，这样就避免了由于数据库被入侵而导致明文密码泄露的问题，同时由于哈希算法的单向不可逆特性，使得即使密文密码泄漏后也很难被破解掉。

附：哈希算法的雪崩效应，即任何输入信息的变化，哪怕数据改动一丁点，都会导致散列结果的明显不同。例如下面使用SHA-256算法进行哈希后的结果对比：

SHA256("helloworlc") = b961c4a38609d65842915bbffc5a91f781b5553c7d6875bbe327cdb4200161c0
SHA256("helloworld") = 936a185caaa266bb9cbe981e9e05cb78cd732b0b3280eb944412bb6f8f8f07af
SHA256("helloworle") = c4a8fb495a534f6cc9a0f1bbf1c683629b14aca39530b5ccd63937b1edd8eb08

破解Hash & 彩虹表

将密码哈希后存储在数据库的做法已经足够完美了，只要密码设计的足够复杂（比如我做过的一个项目，用户密码要求8-16位，至少有一个大写，一个小写，一个数字，一个特殊字符），就基本没有被破解的可能性。但是，仍然有方法对Hash算法进行破解，通常我们能想到的两种办法：

暴力破解法：把P中的每一个p都算一下H(p)，直到结果等于q；
查表法：搞一个很大的数据库，把每个p和对应的q都记录下来，按q做索引来查找对应的p。

这两种办法理论上都是可以的，但是前一种可能需要海量的时间，后一种需要海量的存储空间，以至于以目前的人类资源无法实现。有一种方法称作彩虹表(Rainbow Table)，它组合了暴力法和查表法，并在这两者之中取得一个折中，用我们可以承受的时间和存储空间进行破解。彩虹表的性能非常让人震惊，在一台普通PC上辅以NVidia CUDA技术，对于广泛使用的MD5算法可以达到每秒接近一千亿次的明文尝试。

Salted Hash

既然哈希算法可以通过彩虹表来破解明文密码，那么有人想到了将密码哈希化之前，先在密码中混入一段随机的字符串再进行哈希加密，也就是所谓的"salted hash"。即使被彩虹表破解出来的”密码“，也只是一串加了随机字符串的”伪密码“。这样就大大增加了破解难度。由于这串随机的字符串就像是在食物中撒了一撮盐，因此被形象的成为盐(Salt)。

随机盐的设计应满足以下的要求：

盐值不能重复：盐值被硬编码在程序中是不允许的。如果创建了新的用户，或者用户更改了密码，都应该生成新的盐值；
盐值不能太短：一个好的做法是使用和哈希函数输出的字符串等长的盐值，比如SHA256算法的输出是256bits(32 bytes)，那么盐值也至少应该是32个随机字节。

一个简单的密码加盐后的SHA256对比如下所示：

SHA256("hello") = 2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824
SHA256("hello"+"QxLUF1bgIAdeQX")=9e209040c863f84a31e719795b2577523954739fe5ed3b58a75cff2127075ed1
SHA256("hello"+"bv5PehSMfV11Cd")=d1d3ec2e6f20fd420d50e2642992841d8338a314b8ea157c9e18477aaef226ab
SHA256("hello"+"YYLmfY6IehjZMQ")=a49670c3c18b9e079b9cfaf51634f563dc8ae3070db2c4a8544305df1b60f007

bit/key stretching

In cryptography, key stretching techniques are used to make a possibly weak key, typically a password or passphrase, more secure against a brute-force attack by increasing the time it takes to test each possible key. Passwords or passphrases created by humans are often short or predictable enough to allow password cracking. Key stretching makes such attacks more difficult.

这种方案故意增加密码计算所需耗费的资源和时间，使得难以使用足够的资源建立所需的rainbow table。这类方案有一个特点，算法中都有个因子，用于指明计算密码摘要所需要的资源和时间，也就是计算强度。计算强度越大，攻击者建立rainbow table越困难，以至于不可继续。

这种方案常用的算法有三种：