精子新上线了一个名为  Stream  的服务,希望提供一个基于发布、订阅模型的消息服务,提供 HTTP API 并传输结构化的 JSON 数据。
查看源代码

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

大家都知道散列算法,如 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 系列函数目前来讲是足够安全的。

撰写评论

精子写了这么多年博客,收到的优秀评论少之又少,在这个属于 SNS 的时代也并不缺少向作者反馈的渠道。因此如果你希望撰写评论,请发邮件至 jysperm@gmail.com 并注明文章标题,我会挑选对读者有价值的评论附加到文章末尾。

精子生于 1995.11.25, 21 岁,英文 ID jysperm.

订阅推送

通过邮件订阅精子的博客日志、产品和项目的最新动态,精子承诺每一封邮件都会认真撰写(历史邮件),有想和精子说的话也可以直接回复邮件。

该博客使用基于  Hexo  的  simpleblock  主题。博客内容使用  CC BY-NC-SA 3.0  授权发布。最后生成于 2017-02-19.