减少哈希值的大小

Question

如果我有一些数据，我会像这样使用 SHA256 进行哈希处理：- hash=SHA256(data)

然后只复制哈希的前 8 个字节而不是整个 32 个字节，找到不同数据的哈希冲突有多容易？是 2^64 还是 2^32 ？

如果我需要将某些数据的哈希减少到较小的大小（n 位），有什么方法可以确保搜索空间 2^n ？

Answer 1

我认为你实际上对三件事感兴趣。

\n

您首先需要了解的是哈希的熵分布。如果哈希函数的输出为n位长，则最大熵为n位。请注意，我说的是最大值；你永远无法保证拥有n位熵。同样，如果将哈希输出截断为n/4位，则不能保证结果中有 2 ^{n/4位的熵。}SHA-256分布相当均匀，这在一定程度上意味着高位的熵不可能比低位的熵多（反之亦然）。

\n

然而，关于此的信息很少，因为哈希函数旨在与其整个哈希输出一起使用。如果您只需要 8 字节的哈希输出，那么您甚至可能不需要加密哈希函数，可以考虑其他算法。（重点是，如果您需要加密哈希函数，那么您需要它能够提供的尽可能多的位，因为缩短输出会削弱函数的安全性。）

\n

第二个是搜索空间：它根本不依赖于哈希函数。搜索在哈希函数上创建给定输出的输入通常称为暴力攻击。必须搜索的输入数量并不取决于哈希函数本身；而是取决于哈希函数本身。怎么可能呢？每个哈希函数的输出都是相同的：每个 SHA-256 输出都是 256 位。如果您只需要碰撞，您可以找到一个特定的输入来生成每个可能的 256 位输出。不幸的是，这将占用 256 * 2 ²⁵⁶ \xe2\x89\x88 3 * 10 ⁷⁹的最小存储空间用于散列值本身（即不计算生成它们所需的输入），这大大掩盖了整个硬盘驱动器整个世界的容量。

\n

因此，搜索空间取决于哈希函数输入的复杂性和长度。如果您的数据是 8 个字符长的 ASCII 字符串，那么您可以很好地保证永远不会发生冲突，但是这些哈希值的搜索空间仅为 2 ^7*8 \xe2\x89\x88 7.2 * 10 ¹⁶，您的计算机可能会在几分钟内搜索到它。毕竟，如果您可以找到原始输入本身，则无需查找碰撞。这就是为什么盐在密码学中很重要。

\n

第三，您有兴趣了解抗碰撞性。正如 GregS 的链接文章指出的那样，由于鸽巢原理，空间的碰撞阻力比输入搜索空间要有限得多。

\n

\n

每个输入多于输出的哈希函数必然会发生冲突。考虑一个哈希函数，例如 SHA-256，它可以从任意大的输入生成 256 位的输出。由于它必须为一组更大的输入中的每个成员生成 2 ²⁵⁶个输出之一，因此鸽巢原理保证了某些输入将散列到相同的输出。抗碰撞并不意味着不存在碰撞；只是因为它们很难找到。

\n

“生日悖论”对碰撞抵抗力设置了上限：如果哈希函数产生 N 位输出，则对随机输入“仅”计算 2 ^N/2（或 sqrt(2 ^N )）哈希运算的攻击者很可能会找到两个匹配的输出。如果有比这种暴力攻击更简单的方法，那么它通常被认为是哈希函数中的缺陷。

\n

\n

因此，考虑一下当您仅检查和存储输出的前 8 个字节（四分之一）时会发生什么。您的碰撞阻力已从 2 ^256/2 = 2 ¹²⁸下降到 2 ^64/2 = 2 ³²。^{2 32}比 2 ¹²⁸小多少？事实证明，它小了很多，最多大约是大小的 0.0000000000000000000000000001% 。

\n