科普 | 哈希函数的过去、现在与未来

以下文章来源于以太坊爱好者  翻译&校对:  闵敏 & 阿剑

科普 | 哈希函数的过去、现在与未来

哈希值和哈希函数的概念是初次入门区块链的人常听到的两个关键词，而且似乎对安全性来说特别关键。（实际上也确实是。）对于像比特币和以太坊这样由成千上万的节点通过 P2P 方法组成的去中心化网络来说，“免信任性” 和验证效率无疑是关键。 也就是说，这些系统需要找到方法把信息编码成紧凑的形式，同时让参与者能够安全快速地进行验证。

比特币和以太坊网络所处理的主要内容叫做 “区块”，指的是由交易、时间戳和其他重要元数据所组成的数据结构。 比特币和以太坊网络的安全性的关键一环是：它能将表达网络全局状态的大块信息压缩成一个简短的消息。在有需要之时，我们可以高效地验证这个消息的真实性。这个过程就是用哈希函数来完成的，而得到的结果（消息）就是哈希值。

- 即使只更改输入中的一个字符，最后得出的哈希值也会完全不同 -

密码学哈希广泛应用于口令存储和文件验证系统。简单来说，密码学哈希函数是一种 确定性的 算法，不论输入什么值，都能得到一个 固定长度 的字符串。也就是说， 同一个输入值 始终 对应同一个输出值。

对哈希函数来说，重要的不仅是确定性（还有结果的随机性）： 即使只更改输入中的一个比特位，也会导致最终得到的哈希值截然不同。

哈希算法有一个无可回避的问题叫 碰撞可能性 。因为哈希值是固定长度的字符串 ， 同一个输出哈希值有可能对应多个输入。 碰撞会造成很严重的后果 。 如果有人能够按需要发起碰撞攻击，他就可以用恰当的哈希值将恶意文件或数据伪装成合法的、能够通过验证的文件。好的哈希函数的设计目标是让攻击者极难找到方法来找出对应同一个哈希的不同输入。

哈希计算的效率不应过高，以免让攻击者可以更简单地人为计算出碰撞。哈希算法必须能够抵御“原像攻击（pre-image attack）”。也就是说，对于特定哈希值，攻击者很难通过确定性计算步骤倒推出输入值（即，原像）。

假设 s = hash(x)，倒推 x 应该是近乎不可能的。

总的来说，“好的” 哈希算法需要具备以下 3 个特性：

• 更改输入中的一个比特位会产生雪崩效应，导致最后得出的哈希值截然不同

• 出现哈希碰撞的概率非常低

• 在无需牺牲抗碰撞性的前提下计算效率过得去

破解哈希算法

哈希算法的初始标准之一是 MD5 哈希。MD5 哈希广泛应用于文件完整性验证（校验和），以及在网络应用数据库中存储经过哈希计算的账号口令。MD5 的功能非常简单，因为它会将每个输入转换成一个固定的 128 位字符串输出，并通过多轮简单的单向操作来计算确定性输出。由于输出值长度较短，操作又较为简单，MD5 很容易被破解，一种常见的攻击方法叫 生日攻击 。

“生日攻击” 是啥玩意？

你有没有听说过这样一个事实？如果你将 23 个人放到一个房间里，其中两个人生日相同的概率为 50% 。如果将 70 个人放到一个房间里，其中两个人生日相同的概率高达 99.9% 。这就是我们所说的 鸽笼原理（pigeonhole principle） ，即，将 100 只鸽子装进 99 个鸽笼，必然有两只鸽子分享同一个鸽笼。也就是说，固定长度的输出意味着所有输入输出组合中一定存在 碰撞 。

- 笼子不够时，鸽子就会凑对 -

事实上，MD5 的抗碰撞性太差，以至于一台家用 2.4 GHz 奔腾处理器都能在几秒内计算出哈希碰撞。此外，由于 MD5 在互联网早期阶段得到了广泛应用，网络上有大量 MD5 原像遭到泄漏，通过谷歌搜索它们的哈希值就能找到。

哈希算法的多样性发展

源起：SHA1 和 SHA2

NSA （没错，就是美国国家安全保障局）是哈希算法标准的先驱。 安全哈希算法（Secure Hashing Algorithm，SHA1） 是最早提出的标准，将输出值的长度固定在 160 位。遗憾的是，SHA1 只是在 MD5 的基础上增加了输出值长度、单向操作的次数和复杂度，但是并没有作出能够抵御更强大机器攻击的根本性改进。

我们如何才能做得更好？

SHA3 兴起

在 2006 年，美国国家标准技术研究所（NIST）举办了一场竞赛，旨在找到一个本质上不同于 SHA2 的替代标准。因此，SHA3 应运而生，它是 KECCAK 哈希算法的一种方案。

虽然 SHA 3 在名称上与 SHA1 和 SHA2 一脉相承，但是在本质上差异很大，因为它采用了一种名为 海绵结构（sponge construct） 的机制。该机制使用随机排列来吸收并输出数据，同时为将来用于哈希算法的输入值提供随机性。

- KECCAK256 海绵结构是如何进行输入操作的 -

SHA3 的内部状态相较于输出值拥有更多信息，突破了以往算法的局限性。NIST 于 2015 年正式认可了 SHA3 标准。

哈希计算和工作量证明

就整合进区块链协议的哈希算法而言，比较早的比特币选择了 SHA256 ，而以太坊采用了改进后的 SHA3 （KECCAK256）作为工作量证明算法。对于采用工作量证明的区块链来说，选择哈希函数的一大重要标准是哈希运算效率。

使用一类名为专用集成电路（ASIC）的硬件，我们可以大幅提高比特币 SHA256 算法的哈希运算的效率。有很多文章已经阐述了矿池是如何利用 ASIC 的，以及 ASIC 是如何让协议趋向于计算中心化的。也就是说，工作量证明会激励计算效率较高的机器聚集成矿池，从而形成较大的哈希算力（算力大小的衡量标准就是矿机在每个时间间隔内可以完成多少次哈希运算）。

以太坊选择的是改进后的 SHA3 算法（叫做 KECCAK256 ）。此外，以太坊的工作量证明算法 Dagger-Hashimoto 被设计成了内存密集型模式，计算硬件需要加大内存才能提高计算效率。

为什么比特币采用双重 SHA256 ？

有趣的是，比特币协议（的工作量证明）需要重复运行两遍 SHA256 算法。请注意，这不是为了抵御生日攻击，毕竟在 hash(x) = hash(y) 的情况下，hash(hash(x)) = hash(hash(y)) 。双重 SHA256 旨在抵御长度扩展攻击。

从本质上来说，所谓的长度扩展攻击，指的是如果恶意攻击者知道了某个哈希输入的长度，就可以在哈希值上添加一个秘密的字符串、欺骗哈希函数从其内部状态的一个特定部分开始计算。作为 SHA2 算法家族的一员，SHA256 也存在这一缺陷。因此，比特币采取执行两遍哈希计算的方式来解决这一缺陷。

Ethereum 2.0 和 BLAKE

SHA3 并非哈希算法竞赛取得的唯一突破。虽然最终胜出的是 SHA3 ，但是 BLAKE 算法紧随其后，位居第二。对于以太坊 2.0 的分片实现来说，更高效的哈希算法可以说是一项功能性要求，研究团队对此非常重视。BLAKE2b 哈希算法是 BLAKE 算法的高度升级版本。与 KECCAK256 相比，BLAKE2b 哈希算法在保持高度安全性的同时，在提升效率方面也进行了深入探索。

使用一台现代 CPU 计算 BLAKE2b 的速度比计算 KECCAK 快了 3 倍。

哈希算法的前景展望

这么看来，无论我们做了什么，无非就是（1）增加内部哈希操作的复杂度，或者（2）增加哈希输出值的长度，让攻击者的计算机无法足够快地有效计算出碰撞。

我们依靠单向操作的原像模糊性来保护网络的安全性。也就是说，哈希算法的 安全性目标 是在有无限多可能的冲突的情况下，让找出哈希碰撞的难度尽可能高。

如果量子计算时代到来，哈希算法依然安全吗？

就目前来看，答案是肯定的，哈希算法将经受时间的考验，抵御量子计算。量子计算能够解决的是那些严格按照某些小技巧或 RSA 加密理论打造底层结构的数学问题。另一方面，哈希算法的内部构造没那么形式化。

量子计算机确实能够提高哈希等非结构化问题的计算速度，但它们最终还是会像如今的计算机一样采取暴力破解手段。

无论我们为协议选择了哪种算法，我们显然都在迈向计算高效化的未来。为此，我们必须慎重选择最合适的工具，使之经受住时间的检验。

参考文献

[1]: https://bitcoin.stackexchange.com/questions/6037/why-are-hashes-in-the-bitcoin-protocol-typically-computed-twice-double-computed

[2]: https://en.wikibooks.org/wiki/Cryptography/Breaking_Hash_Algorithms

[3]: https://learncryptography.com/hash-functions/hash-collision-attack

[4]: https://github.com/zcash/zcash/issues/2233

[5]: https://crypto.stackexchange.com/questions/18612/how-is-sha1-different-from-md5

[6]: https://en.wikipedia.org/wiki/Birthday_attack

[7]: https://keccak.team/

[8]: https://en.wikipedia.org/wiki/Cryptographic_hash_function

[9]: https://crypto.stackexchange.com/questions/44386/are-cryptographic-hash-functions-quantum-secure

（完）