一种单向哈希（非加密/安全用途），使用SHA256（而非MD5、SHA-1）？

Question

在新系统中，我们需要一个单向哈希算法来从二进制输入（例如一千字节的文本或更大的文本和二进制文件）计算数字签名。这个需求类似于 Scons （构建系统）如何对命令行和源文件进行哈希以及 Git （版本控制系统）如何对文件进行哈希以计算存储/同步的签名。

请注意，Scons 使用的是 MD5，而 Git 使用的是 SHA-1。

尽管 MD5 和 SHA-1 已经被“破解”，但 Scons 和 Git 并没有专门为安全目的使用它们的哈希（例如，不是用来存储密码），因此常规实践仍认为这些算法对于该用途是可以接受的。（当然，这部分是由于早期采用的合理化解释。） 问题：在新系统中，你会使用 SHA256（而不是 MD5 或 SHA-1）作为（非加密/安全性）单向哈希吗？

主要关注点是：

1. MD5 和 SHA-1 有着长时间的历史。
2. SHA256 相对较新（历史不长），但目前似乎被推荐用于新工作（但并不特别需要更强的算法强度）。
3. SHA256 计算耗时更长。
4. SHA256 产生更长的密钥（这些将用作目录/文件名，并存储在索引文件中），但我认为可以截断生成的密钥（哈希不太强，但应该足够），或者只是假设存储便宜且文件系统可以处理。

如果 Scons 或 Git 社区表示“我们会一直保留原有的！”或“我们想尽快转移到新的哈希算法！”的答案，我会特别感兴趣。（我不确定他们的计划是什么？）

- charley

---

2017年12月更新，使用Git 2.16（2018年第一季度）：正在努力支持替代SHA：请参见“为什么Git不使用更现代的SHA？”。 - VonC

Answer 1

是的，我会使用SHA-256。 SHA-256考虑了比安全更多的目的;实际上，SHA1需要被替换的原因之一就是您需要哈希函数的原因。哈希算法产生有限大小的输出；同时具有不确定的输入量。最终会出现碰撞。输出越大；在使用适当的哈希算法时，发生碰撞的可能性就越小。

Git选择了SHA1，因为它将其用作文件名；他们希望它小而紧凑。SHA256会产生更大的摘要；占用更多的磁盘空间和传输到网线上的数据。此问题特别阐述了如果git遇到冲突会发生什么。

看看您的要点：

1. SHA256已经在野外使用了足够长的时间，如果存在问题，我们现在应该已经看到了。
2. 它并不是“更强壮”的，它更不可能产生碰撞（如果这是您对更强大的标准；那么是的，它更强大）。
3. SHA-256较慢；是的。很慢吗？取决于您的需求。对于95％的人来说，假设您使用适当的实现，性能是可以接受的。
4. 总的来说，截断SHA2的哈希是可以的。

- vcsjones

---

你能否尝试将哈希值的上半部分和下半部分进行异或运算，而不是截断哈希值呢？ - user541686

截断和使用异或进行“折叠”应该是等效的，因为它们在哈希状态中固定了相同数量的位值。然而，使用异或折叠时，您不会固定已知位的位置。 - u0b34a0f6ae

你可以使用base32/base36代替十六进制（base16）- 这样你就可以得到相同的哈希字符串长度 = 不需要截断。 - DarkWanderer

Answer 2

即使使用MD5，非恶意碰撞的概率也非常小。以下是一个思想实验：

一个硬盘可能存有100万个文件。在这个实验中，假设有1000万个文件。假设全球人口为1亿，每个人都有一台电脑，并且每个文件都是不同的。

我们将处理10E6 * 10E9 = 1E17个不同的文件，即2^57以下的数字。

在这种极端情况下，MD5发生碰撞的概率将小于2^71，或者大约是2E21中的1个！为了让碰撞概率达到1/10000000，我们需要重复实验约2E14次，也就是说自宇宙诞生以来每小时更换一次所有文件，然后再继续进行几十亿年。

2E14 / 24 / 365 / 13500E6 = 1.69

当然，使用SHA1或SHA256，概率会更小，并且还会抵抗恶意攻击-与MD5不同，现在不可能（现在）有人故意构造具有相同哈希的文件。

- Lobotomik

---

有趣的计算，尽管我无法完全理解它。你计算了碰撞概率大于1时的情况。但是这个假设是哈希值完美分布的前提条件。我们怎么知道呢？你知道哪些文献可以解释如何最小化系统错误的机会吗？如果我们假设某些模式会以不良的方式使分布崩溃，那么碰撞的可能性就会变得更高。我想计算算法中未检测问题的概率有多大。 - Christian Tismer

如果您想知道“这个特定的”文件是否与另一个文件发生了冲突，那么这个计算是正确的。如果您想知道是否有“一个”文件与另一个文件发生了冲突，您可以预期每sqrt(2^128) = 2^64个文件中会有约一个冲突（由于生日悖论）。因此，在您的思想实验中，您拥有MD5冲突的概率更像是128分之1。 - Jander

Answer 3

这取决于你在做什么。计算SHA-256哈希需要更长的时间。对于许多应用程序来说并不是什么大问题，但如果你的应用程序每分钟尝试计算数百或数千个哈希值，你可能会发现额外的时间太多了。

另一方面，SHA-1发生碰撞的几率比SHA-256高得多。然而，要理解这种机会是微小的（我认为SHA-1的2^160/2中有1个），大多数应用程序可能永远不会遇到。但是，你哈希的东西越多，发生碰撞的几率就越高。如果你正在哈希数百万或数十亿的东西，这可能是一个问题。

- wadesworld

---

如果您只是对数百万或数十亿个东西进行哈希处理，那么SHA-1碰撞（假设输入非恶意）不是一个问题。请参阅Scott Chacon的《Pro Git》第6.1.3节：“每个编程团队成员在同一晚上遭受无关事件中狼群攻击和杀害的概率更高。” - Keith Thompson

Answer 4

为了增加安全性（无论如何定义），减少攻击者或意外事件的机会，您可能想考虑添加盐或使用带密钥的（HMAC）变体。此外，一些小技巧，例如Git的前缀（包括消息长度或CRC），可以使攻击者更难以构造出一个不仅具有相同哈希值，而且格式正确的消息。

您还可以考虑使用类似Glacier（Amazon）或Branch Cache Hash（Microsoft）这样的树状哈希，或者像BitTorrent或其他基于Merkle或Tiger Tree的结构一样的某些点对点网络。

- eckes