哪种哈希算法可以用于重复内容验证？

Question

我有一个xml文件，需要确定它是否是重复的。

我要么对整个xml文件进行哈希处理，要么使用xml文件中的特定节点来生成某种哈希值。

这种情况下，md5适用吗？还是需要其他什么方法？生成哈希的速度也很重要，但保证唯一数据产生唯一哈希值更为重要。

- codecompleting

---

如果没有人试图通过放置伪造文件来“攻击”您，那么MD5就可以了。 如果安全是一个问题，比如在DVCS中，那么像SHA-1这样的东西应该成为您的朋友。 Git正在使用SHA-1，这就是为什么您不应该在数据集上发生冲突的原因：http://seejeffrun.blogspot.com/2009/08/hash-collisions-in-git.html - TacticalCoder

Answer 1

MD5已经被攻破（也就是说有可能故意生成哈希碰撞），如果你担心有人恶意创建与另一个文件相同哈希值的文件，那么你应该使用SHA系列算法（例如：SHA-256或SHA-2）。

---

请注意哈希函数的本质，无法保证每个可能的输入都有一个唯一的哈希值。哈希函数具有有限的长度（例如：MD5长度为128位，因此有2¹²⁸个可能的哈希值）。你无法将一个潜在的无限域映射到一个有限的共域，这在数学上是不可能的。

然而，根据birthday paradox，一个好的哈希函数发生冲突的机率是1/2^n/2，其中n是比特长度。（例如：对于128位的MD5，这将是2⁶⁴）这种情况在统计意义上非常微不足道，你不必担心意外发生碰撞。

- NullUserException

---

评论已清除，讨论已移至聊天室。 - NullUserException

在这个使用案例中，MD5被破解了并不起任何作用，对吗？ - cherouvim

Answer 2

MD5是一种适用且快速的加密算法。但是请注意，仅有一个字符的差异就会产生完全不同的MD5值。

尽管MD5有可能对不同的输入产生相同的哈希值，但这种情况非常罕见。因此，根据您的输入（您是否期望许多类似的XML文件或许多不同的文件？），当MD5给出匹配结果时，您可以比较纯文本内容。

- cherouvim

---

有什么办法可以在出现一些小改变时检测到重复的内容吗？还是它总被视为新内容？ - Parth Kapadia

Answer 3

如果有人至少部分更改了一些XML文件的内容，并且该人在使您声明两个XML文件（或XML摘录）相同时具有优势，而实际上它们并不相同时，则需要一种具有密码学安全哈希函数，即一种抗碰撞的哈希函数。碰撞是产生相同哈希输出的不同消息（字节序列）对-这正是您想要避免的情况。由于哈希函数接受比其输出更长的输入，因此必然存在碰撞。当没有人可以实际生成这样的碰撞时，哈希函数被认为是密码学安全的。

如果哈希函数输出n个比特，则可以预计在哈希大约2 ^{n / 2} 个不同的消息后找到碰撞。安全哈希函数是一种哈希函数，使得没有已知方法可以更快地获得碰撞。

如果没有安全问题（即没有人会主动尝试找到碰撞，你只是担心因为运气不好而发生碰撞），那么密码学上弱的哈希函数是一个选择，前提是它们有足够大的输出，使得2^n/2远远大于您将比较的XML文件的预期数量。对于n = 128（即2^n/2接近十八万亿亿），MD5是可以的，快速且广泛支持。您可能需要调查一下MD4，它甚至更弱，但速度更快。如果您想要更大的n，请尝试SHA-1，它提供160位的输出（此外，SHA-1的弱点目前仍然是理论性的，因此SHA-1比MD5“密码学上破解”要少得多）。

如果你拥有即使是潜在的安全问题，那么选择 SHA-256。目前该函数没有关于碰撞的加密弱点。如果你遇到性能问题（这是相当不可能的：在基本 PC 上，SHA-256 每秒可以处理超过 100MB 的数据，所以 XML 解析的机会要比哈希更昂贵），请考虑 SHA-512，在提供 64 位整数类型的平台上速度有所提升（但在不提供的平台上速度相对较慢）。

请注意，所有这些哈希函数都是针对字节序列而言的。单个反转的比特位将改变输出结果。在 XML 世界中，同一份文档可以用多种方式进行编码，这些编码在语义上是相同的，但在连线时却是不同的（例如，é 和 &#233 都代表相同的字符 é）。由你来定义你想使用哪种等价概念；参见 canonical XML。

- Thomas Pornin