Introduce

哈希函数，或者叫散列函数，是一种从任何一种数据中创建一个数字指纹（也叫数字摘要）的方法，散列函数把数据压缩（或者放大）成一个长度固定的字符串。

Security

加密哈希函数

加密哈希函数（也叫密码学哈希函数）是指一类有特殊属性的哈希函数。

一个好的「加密哈希函数」必须满足抗碰撞（collision-resistant）和不可逆（irreversible）这两个条件。 抗碰撞是指通过统计学方法（彩虹表）很难或几乎不可能猜出哈希值对应的原始数据，而不可逆则是说攻击者很难或几乎不可能从算法层面通过哈希值逆向演算出原始数据。

具体而言，一个理想的加密哈希函数，应当具有如下属性：

  • 快速：计算速度要足够快
  • 确定性：对同样的输入，应该总是产生同样的输出
  • 难以分析：对输入的任何微小改动，都应该使输出完全发生变化
  • 不可逆：从其哈希值逆向演算出输入值应该是不可行的。这意味着没有比暴力破解更好的破解方法
  • 无碰撞：找到具有相同哈希值的两条不同消息应该非常困难（或几乎不可能）

现代加密哈希函数（如 SHA2 和 SHA3）都具有上述几个属性，并被广泛应用在多个领域，各种现代编程语言和平台的标准库中基本都包含这些常用的哈希函数。

量子安全性，现代密码学哈希函数（如 SHA2, SHA3, BLAKE2）都被认为是量子安全的，无惧量子计算机的发展。

加密哈希函数的应用

  1. 数据完整性校验
    加密哈希函数被广泛用于文件完整性校验。如果你从网上下载的文件计算出的 SHA256 校验和（checksum）跟官方公布的一致，那就说明文件没有损坏。
  2. 保存密码
    加密哈希函数还被用于密码的安全存储，现代系统使用专门设计的安全哈希算法计算用户密码的哈希摘要，保存到数据库中，这样能确保密码的安全性。除了用户自己，没有人清楚该密码的原始数据，即使数据库管理员也只能看到一个哈希摘要。
  3. 生成唯一 ID
    加密哈希函数也被用于为文档或消息生成（绝大多数情况下）唯一的 ID，因此哈希值也被称为数字指纹。加密哈希函数计算出的哈希值理论上确实有碰撞的概率，但是这个概率实在太小了，因此绝大多数系统（如 Git）都假设哈希函数是无碰撞的（collision free）。
  4. 伪随机数生成
    哈希值可以被当作一个随机数看待，生成一个伪随机数的简单流程如下：
    • 通过随机事件得到一个熵（例如键盘点击或鼠标移动），将它作为最初的随机数种子（random seed）。
    • 添加一个 1 到熵中，进行哈希计算得到第一个随机数
    • 再添加一个 2，进行哈希计算得到第二个随机数
    • 以此类推
      当然为了确保安全性，实际的加密随机数生成器会比这再复杂一些，我们会在后面的「随机数生成器」一节学习其中细节。

安全的加密哈希算法

1. SHA-2, SHA-256, SHA-512

SHA-2，即 Secure Hash Algorithm 2，是一组强密码哈希函数，其成本包括：SHA-256（256位哈希）、SHA-384（384位哈希）、SHA-512（512位哈希）等。基于密码概念「Merkle–Damgård 构造」，目前被认为高度安全。 SHA-2 是 SHA-1 的继任者，于 2001 年在美国作为官方加密标准发布。

SHA-2 在软件开发和密码学中被广泛使用，可用于现代商业应用。 其中 SHA-256 被广泛用于 HTTPS 协议、文件完整性校验、比特币区块链等各种场景。

2. 更长的哈希值 == 更高的抗碰撞能力

按照设计，哈希函数的输出越长，就有望实现更高的安全性和抗碰撞能力（但也有一些例外）。 一般来说，128 位哈希算法比 256 位哈希算法弱，256 位哈希算法比 512 位哈希算法弱。

因此显然 SHA-512 比 SHA-256 更强。我们可以预期，SHA-512 的碰撞概率要比 SHA-256 更低。

3. SHA-3, SHA3-256, SHA3-512, Keccak-256

在输出的哈希长度相同时，SHA-3（及其变体 SHA3-224、SHA3-256、SHA3-384、SHA3-512）被认为拥有比 SHA-2（SHA-224、SHA-256、SHA-384、SHA-512）更高的加密强度。 例如，对于相同的哈希长度（256 位），SHA3-256 提供比 SHA-256 更高的加密强度。

SHA-3 系列函数是 Keccak 哈希家族的代表，它基于密码学概念海绵函数。而 Keccak 是SHA3 NIST 比赛的冠军。

与 SHA-2 不同，SHA-3 系列加密哈希函数不易受到长度拓展攻击 Length extension attack.

SHA-3 被认为是高度安全的，并于 2015 年作为美国官方推荐的加密标准发布。

以太坊（Ethereum）区块链中使用的哈希函数 Keccak-256 是 SHA3-256 的变体，在代码中更改了一些常量。

哈希函数 SHAKE128(msg, length) 和 SHAKE256(msg, length) 是 SHA3-256 和 SHA3-512 算法的变体，它们输出消息的长度可以变化。

4. BLAKE2 / BLAKE2s / BLAKE2b

BLAKE / BLAKE2 / BLAKE2s / BLAKE2b 是一系列快速、高度安全的密码学哈希函数，提供 160 位、224 位、256 位、384 位和 512 位摘要大小的计算，在现代密码学中被广泛应用。BLAKE 进入了SHA3 NIST 比赛的决赛。

  • BLAKE2 函数是 BLAKE 的改进版本。
  • BLAKE2s（通常为 256 位）是 BLAKE2 实现，针对 32 位微处理器进行了性能优化。
  • BLAKE2b（通常为 512 位）是 BLAKE2 实现，针对 64 位微处理器进行了性能优化。

BLAKE2 哈希函数具有与 SHA-3 类似的安全强度，但开发人员目前仍然更倾向于使用 SHA2 和 SHA3。

5. RIPEMD-160

RIPEMD-160, RIPE Message Digest 是一种安全哈希函数，发布于 1996 年，目前主要被应用在 PGP 和比特币中。

RIPEMD 的 160 位变体在实践中被广泛使用，而 RIPEMD-128、RIPEMD-256 和 RIPEMD-320 等其他变体并不流行，并且它们的安全优势具有争议。

建议优先使用 SHA-2 和 SHA-3 而不是 RIPEMD，因为它们输出的哈希值更长，抗碰撞能力更强。

6. 其他安全哈希算法

以下是目前流行的强加密哈希函数，它们都可被用于替代 SHA-2、SHA-3 和 BLAKE2：

  • Whirlpool 发布于 2000 年，此算法输出固定的 512 位哈希值。该算法使用512位的密钥，参考了分组密码的思路，使用轮函数加迭代，算法结构与 AES 相似。
  • SM3 是中国国密密码杂凑算法标准，由国家密码管理局于 2010 年 12 月公布。它类似于 SHA-256（基于 Merkle-Damgård 结构），输出为 256 位哈希值。
  • GOST（GOST R 34.11-94）哈希函数是俄罗斯的国家标准，它的输出也是 256 位哈希值。

以下函数是 SHA-2、SHA-3 和 BLAKE 的不太受欢迎的替代品，它们是SHA3 NIST 比赛的决赛入围者

  • Skein 能够计算出 128、160、224、256、384、512 和 1024 位哈希值。
  • Grøstl 能够计算出 224、256、384 和 512 位哈希值。
  • JH 能够计算出 224、256、384 和 512 位哈希值。

不安全的加密哈希算法

一些老一代的加密哈希算法，如 MD5, SHA-0 和 SHA-1 被认为是不安全的，并且都存在已被发现的加密漏洞（碰撞）。不要使用 MD5、SHA-0 和 SHA-1！这些哈希函数都已被证明不够安全。

使用这些不安全的哈希算法，可能会导致数字签名被伪造、密码泄漏等严重问题！

另外也请避免使用以下被认为不安全或安全性有争议的哈希算法： MD2, MD4, MD5, SHA-0, SHA-1, Panama, HAVAL（有争议的安全性，在 HAVAL-128 上发现了碰撞），Tiger（有争议，已发现其弱点），SipHash（它属于非加密哈希函数）。

PoW 工作量证明哈希函数

区块链中的 Proof-of-Work 工作量证明挖矿算法使用了一类特殊的哈希函数，这些函数是计算密集型和内存密集型的。 这些哈希函数被设计成需要消耗大量计算资源和大量内存，并且很难在硬件设备（例如集成电路或矿机）中实现，也就难以设计专用硬件来加速计算。这种哈希函数被称为抗 ASIC（ASIC-resistant）。

大部分工作量证明（Proof-of-Work）算法，都是要求计算出一个比特定值（称为挖掘难度）更大的哈希值。 因为哈希值是不可预测的，为了找出符合条件的哈希值，矿工需要计算数十亿个不同的哈希值，再从中找出最大的那个。 比如，一个工作量证明问题可能会被定义成这样：已有常数 x，要求找到一个数 p，使 hash(x + p) 的前十个比特都为 0.

有许多哈希函数是专为工作量证明挖掘算法设计的，例如 ETHash、Equihash、CryptoNight 和 Cookoo Cycle. 这些哈希函数的计算速度很慢，通常使用 GPU 硬件（如 NVIDIA GTX 1080 等显卡）或强大的 CPU 硬件（如 Intel Core i7-8700K）和大量快速 RAM 内存（如 DDR4 芯片）来执行这类算法。 这些挖矿算法的目标是通过刺激小型矿工（家庭用户和小型矿场）来最大限度地减少挖矿的集中化，并限制挖矿行业中高级玩家们（他们有能力建造巨型挖矿设施和数据中心）的力量。 与少数的高玩相比，大量小玩家意味着更好的去中心化。

目前大型虚拟货币挖矿公司手中的主要武器是 ASIC 矿机，因此，现代加密货币通常会要求使用「抗 ASIC 哈希算法」或「权益证明（proof-of-stake）共识协议」进行「工作量证明挖矿」，以限制这部分高级玩家，达成更好的去中心化。

非加密哈希函数

加密哈希函数非常看重「加密」，为了实现更高的安全强度，费了非常多的心思、也付出了很多代价。

但是实际应用中很多场景是不需要这么高的安全性的，相反可能会对速度、随机均匀性等有更高的要求。 这就催生出了很多「非加密哈希函数」。

非加密哈希函数的应用场景有很多：

  • 哈希表 Hash Table: 在很多语言中也被称为 map/dict，它使用的算法很简单，通常就是把对象的各种属性不断乘个质数（比如 31）再相加，哈希空间会随着表的变化而变化。这里最希望的是数据的分布足够均匀。
  • 一致性哈希：目的是解决分布式缓存的问题。在移除或者添加一个服务器时，能够尽可能小地改变已存在的服务请求与处理请求服务器之间的映射关系。
  • 高性能哈希算法：SipHash MurMurHash3 等，使用它们的目的可能是对数据进行快速去重，要求就是足够快。

有时我们甚至可能不太在意哈希碰撞的概率。 也有的场景输入是有限的，这时我们可能会希望哈希函数具有可逆性。

Birthday Attack

只要不少于23个人，就至少有两人生日相同的概率大于50%；一个 30 人的班级中，存在两人生日相同的概率为 70%；对于 60 人的班级中，这种概率要大于 99%。

Hash collisions and exploitations

哈希函数的输入空间（文本或者二进制数据）是无限大，但是输出空间（一个固定长度的摘要）却是有限的。将「无限」映射到「有限」，不可避免的会有概率不同的输入得到相同的输出，这种情况我们称为碰撞（collision）。

Don't play with fire, don't rely on MD5.

https://github.com/corkami/collisions

Reference

https://www.fxajax.com/20210625222334.html - 一文带你了解哈希碰撞原理
https://thiscute.world/posts/practical-cryptography-basics-2-hash/ - 写给开发人员的实用密码学（二）—— 哈希函数