哈希算法的现状——为什么、如何和未来

前言：哈希算法对于保证区块链网络的安全性非常重要。为了降低哈希碰撞的可能性，要么增加哈希内部运算的复杂度，要么增加哈希输出的长度，希望攻击者的计算速度不够快。本文分析了哈希算法的历史、原理和未来，对我们理解区块链的安全问题很有帮助。这篇文章的作者是劳尔乔丹。文章来自medium.com，由蓝狐笔记社区“李希禾”翻译。

新手在学习区块链时经常会接触到哈希、哈希算法等概念，在安全性方面可以说是无所不在。通过 P2P 运行具有许多节点（如比特币和以太坊）的去中心化网络需要无需信任的机制和有效的验证。

也就是说，这些系统需要找到以高效简洁的方式对信息进行编码的方法，并允许其参与者安全快速地验证它们。

比特币和以太坊涉及的主要概念是“块”，一种包含交易记录、时间戳和其他元数据的数据结构。这种数据结构安全性的关键在于，它可以将大量关于全球网络状态的信息压缩成一小段信息标准，而这一小段信息可以得到高效的验证。这一小块信息称为散列。

即使只更改输入消息的一个字符也会导致完全不同的哈希值！

加密哈希用于各种行业，从密码存储到文档验证系统。基本思想是使用确定性算法，每次都接受输入并生成固定长度的字符串。也就是说，相同的输入总是会得到相同的输出。

除了这种确定性之外，散列算法还有另一个属性：输入的任何微小变化都可能导致输出完全不同。

散列算法的一个问题是冲突的不可避免性。意思是由于哈希函数输出的字符串有一定的长度，不同的输入可能产生相同的哈希值。碰撞是不好的，如果攻击者可以故意产生碰撞，他可以将恶意文件或数据伪装成正确的哈希并传递它们。一个好的散列函数的目标是使冲突几乎不可能发生。

计算哈希值不应该太高效，因为它会使冲突太容易实现。散列算法应该能够抵抗“原像攻击”。也就是说，根据已知的哈希值找到输入值应该是非常困难的（输入值称为原像，例如 s = hash(x)，根据 s 找到 x 应该几乎是不可能的） .

综上所述，一个好的哈希算法应该具备以下特点：

改变输入的任何一点以产生完全不同的输出

发生冲突的概率非常低

在不牺牲对冲突的抵抗力的情况下达到一定的效率水平

攻击哈希

原始散列算法标准之一是 MD5 散列，它广泛用于文件完整性验证（校验和）以及将散列密码存储在 Web 应用程序的数据库中。当时它相当简单比特币采用的哈希算法是，因为无论输入如何，输出都是一个固定的 128 位字符串，并且它在几轮中使用低效的单向运算来计算确定性输出。

由于输出字符串长度短，操作简单，MD5容易破解，容易受到生日攻击。

什么是“生日攻击”？

你可能听说过：如果一个房间有 23 个人，那么有 50% 的机会两个生日会重叠，如果增加到一个房间有 70 个人，那么这个概率变成 99.@ >9% . 这就是鸽巢原理，如果有 100 只鸽子只有 99 个洞，那么一个洞一定有两只鸽子。

在散列算法的情况下，就变成了，固定长度的字符串意味着固定数量的排列，所以当输入值达到一定数量时，不可避免地会发生冲突。

鸽子太多了！至少一只鸽子会与另一只鸽子共用一个洞

MD5 对冲突的抵抗力非常弱，以至于 2.4GHz Pentium 可以在几秒钟内产生哈希冲突。事实上，由于早些年 MD5 的广泛使用，网上已经有大量原图被泄露，你甚至可以通过简单的谷歌搜索找到它们。

散列算法的多样性和演变

开始：SHA1 & SHA2

美国国家安全局 (NSA) 一直是哈希算法标准的先驱。他们首先提出了一种安全散列算法，即 SHA1，它输出一个 160 位的固定长度字符串。

然而，SHA1 相比 MD5 只是增加了输出的长度、单向运算的数量和单向运算的复杂度，但并没有做出任何根本性的改进以使其能够抵抗尝试不同攻击向量的更强大的机器.

那么我们该如何改进呢？

SHA3

2006 年，美国国家标准与技术研究院 (NIST) 开始寻找一种完全不同的 SHA2 替代方案，使其成为新的算法标准。因此，SHA3的诞生是散列算法伟大机制的一部分，称为KECCAK。

虽然名字看起来很相似，但 SHA3 的内部结构与之前的算法完全不同，因为它具有 Sponge Construct 机制。这种结构使用随机排列来吸收和输出数据，同时也为未来的输入值提供随机性来源。

KECCAK256海绵结构作用于输入值

SHA3​​ 保持了一个内部状态，使得输出的消息比字符串长度更长（并且仍然压缩消息），这使它能够克服以前算法的限制。它也在 2015 年成为 NIST 的标准算法。

哈希和 PoW

当哈希算法被集成到区块链协议中时，旧的比特币选择了 SHA256 算法，而以太坊选择了 SHA3 的改进版本（KECCAK256））作为 PoW 算法。在区块链 PoW 协议中选择哈希函数的一个重要标准是计算哈希值的效率。

比特币SHA256算法的执行效率可以通过制作ASIC等专用硬件进一步提高。这体现在矿池中 ASIC 的使用上，并使协议趋向于计算中心化。

也就是说，PoW 鼓励高效的计算组聚合成更大的组（矿池），以增加我们所说的散列能力（即一台机器可以定期计算的散列数量）。

以太坊选择了修改后的 SHA3，也称为 KECCAK256。此外，以太坊的 PoW 算法（Dagger-Hashimoto）被设计成在硬件内存中难以计算，这在一定程度上避免了 ASIC 的使用。

为什么比特币使用双 SHA256？

比特币使用 SHA256 转换数据的方式很有趣，它在协议中连续两次执行算法。请注意，这不是为了防御生日攻击比特币采用的哈希算法是，显然如果 hash(x) = hash(y) then also hash(hash(x)) = hash(hash(y))，而是为了减轻长度扩展攻击。

本质上，这种攻击需要恶意攻击者知道散列输入值的长度，在这个已知长度上添加一个秘密字符串可以释放散列函数的一部分内部来扰乱散列函数。由于 SHA256 是 SHA2 算法家族中的一员，它有这样的缺点，而比特币通过连续运行两次哈希函数来缓解这个缺陷。

以太坊2.0 和 BLAKE

SHA3​​ 并不是 NIST 在 2006 年发起的竞赛中唯一的突破。虽然 SHA3 最终获胜，但名为 BLAKE 的算法位居第二。对于以太坊2.0个分片的执行，更高效的哈希算法可以说是必不可少的。

BLAKE2b哈希算法是赛后高度升级优化的版本。由于其效率高（与 KECCAK256 相比）在保持高度安全性的同时，该算法也经过了更彻底的测试。

在现代 CPU 上计算 BLAKE2b 实际上比 KECCAK 快 3 倍。

哈希算法的未来

看来无论我们做什么都是（1）增加哈希函数内部操作的复杂度，或者（2）增加哈希输出的长度，希望攻击者的电脑速度不够快）有效地产生计算冲突。

我们网络的安全性目前依赖于单向操作原像的模糊性。也就是说，散列算法的安全目标是让任何人尽可能难以找到两个相同输出的值，从而使散列冲突的概率尽可能小，尽管仍然有无穷多个可能的冲突。

那么量子计算呢？面对量子计算，哈希算法是否足够安全？

根据目前的理解，简单的答案是：安全。哈希算法将能够承受量子计算的挑战。量子计算能够破解诸如 RSA 之类的加密问题，这些问题具有由巧妙的技巧和理论构建的严格的底层数学结构。哈希算法的内部结构中没有这样的形式结构。

量子计算机确实可以加速计算非结构化问题（如哈希），但归根结底，量子计算机发起攻击的方式仍然是蛮力，与传统计算机没有什么不同。

无论我们选择哪种算法，很明显我们正朝着计算效率更高的未来迈进，我们必须尽最大努力挑选最好的工具并经受住时间的考验。

------