笔记：散列算法的使用场景

大家都知道散列算法，如 MD5, SHA, 但是对其具体特性恐怕都很模糊。说不准哪些用法是可靠的，哪些用法是不可靠的，只是通过加 salt, 或者反复散列的方式提高可靠性。本文将精确地讨论它们在各种使用方法下的可靠性，本文不讨论原理，只讨论使用，以下部分资料来自网络，感谢 wxy 帮忙检验文中的论断。

MD5 和 SHA 系列算法都属于同一类——我还没给这类算法找到一个足够贴切的名字。首先在大的分类上，它们都是散列算法。
散列是怎么个定义呢？典型的散列算法可以是任何一个：具有无限的定义域，且具有有限的值域的函数。甚至，宽松的广义散列算法可以是任何一个(数学意义上的)函数，因为函数本身的概念就是将一个或多个值映射到一个唯一的值。

从具体特征上来说，它们(的目标)都是足够安全的信息摘要算法。究竟何谓安全？
MD5 和 SHA 系列函数所追求的安全，在于下面两个方面。

• 单向性
• 抗冲突性

所谓单向性，就是指明文 M, 经过散列后的 hash(M). 从 hash(M) 无法推算出 M. 这是大部分摘要算法都具有的特征，因为大多数情况下，被摘要的信息长度要大于散列值，因为缺少信息，且值域明显小于定义域，即一个散列值会对应多个(无限个)原文，所以天然地就无法从散列值反向计算出原文。MD5 和 SHA 系列函数在单向性方面目前都还没有被发现明显的漏洞。

但是以上讨论的只是理论上的单向性，实际使用中，攻击者可以通过穷举，即暴力破解的方式推算出可能的原文。这种情况适用于已知信息原文定义域且范围较小的情况。例如如果直接对用户的密码进行散列，因为密码大多在十位字母左右，攻击者可以以很低的成本计算所有密码组合的散列值，以得到可能的信息原文。

从散列算法的角度，应对暴力破解攻击没有明显有效的手段，但也可以通过『提高计算成本』和『减少散列值长度』的方式提升单向性。

提高计算成本即通过将算法设计得更为复杂，增加更多次计算，来提高对单个信息进行散列的时间。对于正常单次散列来讲，即使增加十倍的计算时间，仍然是可以接受的。但当攻击者进行暴力破解时，同样需要原来十倍的计算时间，这个成本对攻击者来说可能无法接受。除此之外，还可以改造算法，使其只能运行于 CPU 上，无法使用显卡或专用芯片进行计算，以提高暴力破解的计算成本。
但似乎这种方式并没有被业界接受，SHA 系列函数中的新成员均减少而不是提高了计算成本。

减少散列值长度，即通过减少散列值的长度来使得多个(大量)信息原文映射到同一个散列值，使攻击者无法分辨究竟哪个才是真正的原文。
例如将散列值减少到 8 bit, 这样密码组合中 1/256 的密码都会映射到同一个散列值，根本无法分别哪个才是真正的密码。
这种方式显然很扯淡，因为这种方式会明显降低下面要提到的抗冲突性。

实际使用中，我们可以通过提高定义域范围的方式，来增强单向性。同样是散列用户密码的例子，我们可以将原来的 hash(M) 改为 hash(hash(M)). 因为 hash 的值域范围通常要比密码(约 10 位字母，即约 60 bit)大, 如 MD5 的值域是 128 bit, SHA-1 的值域是 160 bit. 因此我们通过第一次散列将第二次散列的定义域提高到了 2-4 倍，一定程度上提高了攻击者暴力破解的成本。

但是，攻击者会将 hash(hash(x)) 视为一个独立的散列函数 hash2(x), 除了正常地增加了一倍的计算时间，并没有受到我们增加作用域的影响。因此，这时我们需要引入 salt(佐料，干扰), 将散列算法改为 hash(hash(x + salt)), salt 需要与散列值一同储存。

在已知 salt 的情况下，对攻击者其实没有任何影响，因为这个函数依旧可以转换为 hash2(x + salt), 当然，有些攻击者会通过 Rainbow Table(彩虹表) 的方式进行协作和缓存，加 salt 会使他们无法使用 Rainbow Table.

Rainbow Table, 即事先对预定范围的数据进行散列，储存散列结果。然后通过数据库或者分布式技术(小型 Rainbow Table 就不需要了), 来优化从散列值到原文的『反向』查询。相似的技术还有『字典』，即收集大家常用的原文(密码，或其他短语), 代替穷举，以提高暴力破解的效率。

而在这个场景中，将 hash(hash(x + salt)) 更换为 hash(hash(x) + salt) 会获得更好的效果。因为前一种情况，攻击者可以将密码和 salt 视为一个整体来使用 Rainbow Table (虽然在 Rainbow Table 中很可能查不到这些信息); 后者则不能。因为后者是一个散列值加一个 salt, 长度已经远远超出了 Rainbow Table 的范围。当然，单纯加长 salt 也可以实现 hash(hash(x) + salt) 的效果。

在攻击者不知道 salt 的情况下，有两种选择。
一是将 hash2(x) 改为 hash2(x, salt), 这种情况适用攻击者知道 salt 的长度或范围的情况，因为这个函数有两个参数，因此破解成本与 x 或 salt 的长度呈指数函数，只要 salt 足够长，那么可以认为攻击者即使暴力破解也无能为力。
二是将第二个 hash 的输入视为一个散列值，换言之就是进行两次爆破，这种方式的计算成本相比于前一种会更高，因为暴力破解的成本同原文长度也是呈指数关系的。

所以，在未知 salt 的情况下，可以防御所有暴力破解，除非攻击者拥有极其惊人的计算力。
举个例子，如果密码为 10 位的字母，salt 为 3 位的字母，暴力破解需要相当于 Bitcoin 全网计算力的约 60 天时间。

虽然我们还拥有更强大的变种，例如：

hash(x, salt[]) = hash(hash(x + salt[1]) + hash(x + salt[2]) + ...)

但是我们认为，使用 hash(hash(x) + salt) 和足够长的 salt(大致相当于散列值的长度), 已经足够安全。

接下来，那么如何生成 salt 呢？是否有必要为每条数据(还是前面的例子，每个用户)使用单独的 salt 呢。通过前面的讨论我们看到，要保证单向性，对 salt 进行保密十分必要。如果你能够保证 salt 的绝对安全的话，那么是否使用单独的 salt 其实无关紧要。不要担心使用相同的 salt 会让攻击者找到某种规律而计算出 salt(当然前提是 salt 足够长), 因为 MD5, SHA 系列函数保证了单向性，攻击者无法从散列值推测出原文的任何信息。

至于 salt 的取值，没有什么特别的要求，基于保密的考虑，通常要使用随机生成的字符串，然后就是足够长(大约等于散列值的长度).

但我们认为仍有必要为每条数据使用单独的 salt, 这是基于下面两点考虑。
一是虽然暴力破解需要惊人的计算力，但是如果只需破解一个散列值，就可以获知所有数据的 salt, 这个破解也是值得的，也许攻击者就能够提供这么多的计算力也说不定，虽然如果你使用足够长的 salt 的话，这种可能性极小。
二是也许你不能保证 salt 的绝对安全，当你的 salt 泄漏后，每条数据使用不同的 salt 将会为攻击者制造最后一道障碍。

如果你所有的数据都使用同样的 salt, 那么攻击者在拿到数据后，只需进行一次暴力破解，即可破解出所有的数据(如果都命中了的话), 但如果你为每条数据使用不同的 salt, 那么攻击者将不得不为每条数据单独运行一次暴力破解，因为每条数据相当于在使用不同的散列函数，因为 salt 是不同的。

综上，我们认为网站的用户系统使用下面的散列即可保证安全性：

hash(hash(passwd) + salt)

其中 salt 是随机生成的，长度等于散列值长度的字符串。hash 可以是 MD5 或 SHA 系列函数。

---

我们接着来谈抗冲突性，所谓抗冲突性即从计算上不可能找到两个有同样散列值的原文。抗冲突性分为抗强冲突性，和抗弱冲突性。
抗强冲突性，即给定一个散列值，无法找到另一个具有同样散列值的信息原文。
抗弱冲突性，即无法找到两个具有同样散列值的信息原文。

加上单向性，这三条特性是呈阶梯状的，满足『抗弱冲突性』就一定满足『抗强冲突性』也就一定满足『单向性』同时也就满足『散列映射具有随机性和均匀性』。MD5 和 SHA 系列函数在设计上都满足这三条特征，但目前已经被发现了存在某些漏洞。

抗冲突性的主要应用场景就是为信息原文进行摘要，鉴别两段信息原文是否相同。
而攻击者的目标就是，对信息原文进行修改，然后在信息原文后(或者修改信息原文)添加给定的数据段，使其能够生成与之前相同的散列值，实现伪造数据原文。

在这种场景下攻击者是否也能够进行暴力破解呢？很难，因为在这种情况下，攻击者需要不断更换附加在信息原文后的数据，以获得和之前相同的散列值，在不理想的情况下，需要尝试所有的散列值，这个计算力被认为是无法接受的。但通过算法的一些漏洞，可以降低这个暴力破解的成本。

抗冲突性是检验散列算法设计是否优秀的重要指标，很多散列算法被淘汰都是因为抗冲突性存在漏洞。

目前 MD5 已在 2005 年被中国数学家王小云发现有抗强冲突性的漏洞，给定一个散列值，可以在几分钟内用普通计算机找到一个碰撞，即具有相同散列值的信息原文。

SHA-0 被发现漏洞可以将寻找碰撞的难度从 2^80 次暴力破解降低到 2^39 次，SHA-1 被发现漏洞可以将寻找碰撞的难度从 2^80 次降低到 2^63 次，SHA-2 系列函数还未发现漏洞。

因此目前使用 MD5 进行信息摘要并不安全，攻击者可以轻易地伪造一段散列值相同，但内容不同的原文，虽然攻击者还不能够自由地修改原文。
而 SHA-1 和 SHA-2 系列函数目前来讲是足够安全的。