哈希函数的过去、现在和未来

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

哈希值和哈希函数的概念是区块链新手经常听到的两个关键词，似乎对安全性尤为重要。 （事实确实如此。）对于像比特币和以太坊这样通过 P2P 方法由数万个节点组成的去中心化网络，“免信任”和验证效率无疑是关键。 也就是说，这些系统需要找到将信息编码成紧凑形式的方法，同时允许参与者安全快速地验证它。

比特币和以太坊网络处理的主要事物称为“区块”，指的是由交易、时间戳和其他重要元数据组成的数据结构。 比特币和以太坊网络安全性的一个关键部分是能够将表达网络全局状态的大量信息压缩成一条短消息。 必要时，我们可以高效地验证此消息的真实性。 这个过程是使用散列函数完成的，结果（消息）就是散列值。

- 即使更改输入中的一个字符也会导致完全不同的散列 -

密码哈希广泛用于密码存储和文件认证系统。 简单地说，密码哈希函数是一种确定性算法，无论输入什么值，它都返回一个固定长度的字符串。 也就是说，相同的输入值总是对应相同的输出值。

对于散列函数而言，重要的不仅是确定性（还有结果的随机性）：即使更改输入中的一位也可能导致最终散列值大不相同。

哈希算法有一个无法避免的问题，称为碰撞的可能性。 由于哈希值是定长字符串，所以同一个输出哈希值可能对应多个输入。 碰撞会产生严重的后果。 如果有人可以按需进行碰撞攻击，他可以使用适当的哈希值将恶意文件或数据伪装成合法的、可验证的文件。 一个好的散列函数旨在使攻击者极难找到一种方法来找到与同一散列相对应的不同输入。

哈希计算不应该如此高效以至于攻击者更容易人为地计算冲突。 散列算法必须能够抵抗“原像攻击”。 也就是说，对于特定的哈希值，攻击者很难通过确定性的计算步骤向后推导出输入值（即原像）。

假设 s = hash(x)，将 x 反转几乎是不可能的。

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

更改输入中的单个位会产生雪崩效应，导致最终哈希值大不相同

哈希冲突的概率非常低

在不牺牲抗碰撞性的情况下获得不错的计算效率

破解哈希算法

散列算法的原始标准之一是 MD5 散列。 MD5 散列广泛用于文件完整性验证（校验和），以及在 Web 应用程序数据库中存储散列帐户密码。 MD5 的功能非常简单，因为它将每个输入转换为一个固定的 128 位字符串输出，并通过多轮简单的单向运算计算出确定性输出。 由于输出值长度较短，操作比较简单，MD5很容易被破解。 一种常见的攻击方法称为生日攻击。

什么是“生日袭击”？

你听说过这样的事实吗？ 如果你把 23 个人放在一个房间里，那么其中两人生日相同的概率为 50%。 如果你把 70 个人放在一个房间里，那么其中两人生日相同的可能性为 99.9%。 这就是我们所说的鸽笼原理，就是把100只鸽子放在99个鸽笼里，一定有两只鸽子共享同一个鸽笼。 也就是说，固定长度的输出意味着所有输入输出组合都必须存在冲突。

- 笼子不够时，鸽子会聚在一起 -

事实上，MD5 具有很强的抗冲突性，家用 2.4 GHz 奔腾处理器可以在几秒钟内计算出哈希冲突。 另外，由于MD5在互联网早期的广泛使用，网上流传着大量泄露的MD5原像，通过Google搜索其哈希值即可找到。

哈希算法的多样化发展

来源：SHA1 和 SHA2

NSA（是的，美国国家安全局）是哈希算法标准的先驱。 Secure Hashing Algorithm (SHA1) 是最早提出的标准，它将输出值的长度固定为 160 位。 遗憾的是，SHA1只是在MD5的基础上增加了输出值的长度、单向运算的次数和复杂度，并没有从根本上改进以抵抗更强大的机器攻击。

我们怎样才能做得更好？

SHA3​​ 的兴起

2006 年，美国国家标准技术研究院 (NIST) 举办了一场竞赛，旨在寻找与 SHA2 有根本区别的替代标准。 因此，SHA3应运而生，它是KECCAK哈希算法的一种方案。

SHA 3虽然在名称上与SHA1、SHA2一脉相承，但本质上却大不相同，因为它使用了一种叫做海绵构造的机制。 该机制使用随机排列来摄取和输出数据，同时为哈希算法的未来输入值提供随机性。

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

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

哈希计算和工作量证明

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

使用一种称为专用集成电路 (ASIC) 的硬件，我们可以显着提高比特币 SHA256 算法的哈希运算效率。 有很多文章解释了矿池如何使用 ASIC，以及 ASIC 如何使协议在计算上趋向于中心化。 也就是说，工作量证明会鼓励计算效率更高的机器聚集到一个矿池中，从而形成更大的算力（算力的衡量标准是一台矿机在每个时间间隔内可以完成多少次算力。希腊操作）。

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

为什么比特币使用双SHA256？

有趣的是，比特币协议（Proof of Work）需要运行两次 SHA256 算法。 请注意，这并不是为了防止生日攻击，毕竟在 hash(x) = hash(y) 的情况下是 hash(hash(x)) = hash(hash(y))。 双 SHA256 旨在抵抗长度扩展攻击。

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

以太坊 2.0 和 BLAKE

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

使用现代 CPU 计算 BLAKE2b 比计算 KECCAK 快 3 倍。

哈希算法的前景

因此，无论我们做什么，似乎要么 (1) 增加内部散列操作的复杂性，要​​么 (2) 增加散列输出的长度，以便攻击者的计算机无法足够快地有效计算冲突。

我们依靠原像模糊性进行单向操作来保护网络。 也就是说，散列算法的安全目标是在给定无限数量的可能冲突的情况下，尽可能难以找到散列冲突。

如果量子计算时代来临比特币算法会被破解吗，哈希算法还安全吗？

就目前而言，答案是肯定的，哈希算法将经得起时间的考验，抵抗量子计算。 量子计算可以解决严格遵循一些技巧或RSA加密理论构建底层结构的数学问题。 另一方面，散列算法的内部结构不太形式化。

量子计算机确实可以提高哈希等非结构化问题的速度，但它们最终还是会像今天的计算机一样使用蛮力方法。

无论我们为协议选择哪种算法，我们显然都在朝着计算高效的未来迈进。 为此，我们必须慎重选择最合适的工具比特币算法会被破解吗，使其经得起时间的考验。

参考

[1]:

[2]:

[3]:

[4]:

[5]:

[6]:

[7]:

[8]:

[9]:

（结束）