哈希算法的现状——原因、方式和未来

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

新手在了解区块链时，往往会接触到哈希、哈希算法等概念，在安全方面可以说是无处不在。 具有许多节点的去中心化网络，例如比特币和以太坊，需要通过 P2P 的去信任机制和高效验证。

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

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

即使只更改输入的一个字符也会产生完全不同的哈希值！

密码哈希用于各种行业，从密码存储到文档认证系统。 基本思想是使用确定性算法（deterministic gorithm），它可以接受一个输入并每次产生一个固定长度的字符串。 也就是说，相同的输入将始终产生相同的输出。

除了这种确定性之外，哈希算法还有一个特性：输入的任何细微变化都会导致完全不同的输出。

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

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

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

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

· 冲突的可能性很低

在不牺牲对冲突的抵抗力的情况下提高效率

攻击哈希

最初的哈希算法标准之一是 MD5 哈希，它广泛用于文件完整性验证（校验和）以及在 Web 应用程序的数据库中存储哈希密码。 当时它的功能很简单，因为无论输入如何，输出都是固定的128位字符串，而且采用多轮单向运算（one-way operations across several rounds），计算效率不高确定性输出。

由于输出字符串长度较短，操作相对简单，MD5容易被破解，容易受到生日攻击（Birthday Attack）的攻击。

什么是“生日袭击”？

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

在hash算法中，定长的字符串意味着固定的排列次数，所以当输入值达到一定数量时，必然会发生碰撞。

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

MD5 的抗冲突能力非常弱，2.4GHz 的奔腾处理器可以在几秒钟内产生哈希冲突。 事实上，由于早期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算法的执行效率可以通过制造ASICs矿机等专用硬件进一步提高。 这体现在矿池中使用 ASIC 并将协议推向计算中心化。

换句话说，PoW鼓励高效的计算群体聚合成更大的群体（矿池），以增加我们所说的哈希算力（即机器在固定时间间隔内可以计算的哈希数）。

以太坊，选择了改进后的 SHA3，也称为 KECCAK256。 另外，以太坊的PoW算法（Dagger-Hashimoto）设计成硬件内存难以计算，一定程度上避免了使用ASICs矿机。

为什么比特币使用双SHA256？

比特币使用 SHA256 转换数据的方式很有趣，它在协议中连续执行两次算法。 请注意，这不是为了防御生日攻击，显然 if 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 加密之类的问题，这些问题具有由巧妙的技巧和理论构建的严格的底层数学结构。 哈希算法的内部结构中没有这种形式结构。

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

无论我们选择哪种算法，很明显我们正在驶向一个计算效率更高的未来，我们必须尽最大努力选择经得起时间考验的最佳工具。

------