language-agnostic - 在某些条件下，密码散列是内射的吗？

Question

很抱歉这篇冗长的帖子，我有一个关于常见密码散列算法的问题，例如 SHA 系列、MD5 等。

一般来说，这样的散列算法不能是单射的，因为产生的实际摘要通常具有固定长度(例如，在 SHA-1 下为 160 位等)，而要被摘要的可能消息的空间实际上是无限的。

但是，如果我们生成一个消息的摘要，它最多与生成的摘要一样长，那么常用的散列算法的属性是什么？他们是否可能会在这个有限的信息空间上独断专行？是否存在已知即使在比特长度短于所产生的摘要的比特长度的消息上也会产生冲突的算法？

我实际上正在寻找一种具有此属性的算法，即，至少在原则上，即使对于短输入消息，它也可能生成冲突哈希。

背景:我们有一个浏览器插件，对于每个访问的网站，它都会向服务器发出请求，询问该网站是否属于我们已知的合作伙伴之一。但当然，我们不想监视我们的用户。因此，为了使生成某种冲浪历史记录变得困难，我们实际上并没有发送访问过的 URL，而是发送一些清理版本的哈希摘要(目前是 SHA-1)。在服务器端，我们有一个众所周知的 URI 的哈希表，它与接收到的哈希相匹配。我们可以在这里忍受一定程度的不确定性，因为我们认为无法跟踪我们的用户是一个功能，而不是一个错误。

由于显而易见的原因，这个方案非常模糊，并且承认误报以及不匹配的 URI 应该有。

所以现在，我们正在考虑将指纹生成更改为具有更多结构的东西，例如，而不是散列完整的(清理后的)URI，我们可能会改为:

将主机名拆分为“。”处的组件。并单独散列这些

在“。”检查组件的路径。并单独散列这些

将生成的哈希值加入指纹值。示例:使用此方案(并使用 Adler 32 作为哈希)散列“www.apple.com/de/shop”可能会产生“46989670.104268307.41353536/19857610/73204162”。

然而，由于这样的指纹有很多结构(特别是与普通的 SHA-1 摘要相比)，我们可能会意外地再次让计算用户访问的实际 URI 变得非常容易(例如，通过使用 pre -“常见”组件值的哈希值的计算表，例如“www”)。

所以现在，我正在寻找一种哈希/摘要算法，即使在短消息上也具有很高的冲突率(认真考虑 Adler 32)，因此给定组件哈希唯一的概率很低。我们希望，我们强加的额外结构为我们提供了足够的额外信息，以改善匹配行为(即降低误报/误报率)。

Answer 1

我不相信对于与摘要大小相同的消息，哈希值可以保证是内射的。如果它们是，它们将是双射的，这将丢失哈希的点。这表明它们对于小于摘要的消息也不是单射的。

如果你想鼓励碰撞，我建议你使用任何你喜欢的哈希函数，然后扔掉比特，直到它足够碰撞。

例如，丢弃 SHA-1 哈希的 159 位会给您带来相当高的冲突率。你可能不想扔掉那么多。

但是，您试图实现的目标似乎天生就令人怀疑。您希望能够分辨出该 URL 是您的 URL 之一，但不知道它是哪一个。这意味着您希望您的 URL 相互冲突，但不与不属于您的 URL 发生冲突。哈希函数不会为您做到这一点。相反，因为冲突是随机的，因为不属于你的 URL 比属于你的 URL 多得多(我假设!)，任何给定级别的冲突都会导致对一个 URL 是否属于你的 URL 的混淆比过度是你的哪一个。

相反，如何在启动时将 URL 列表发送到插件，然后让它返回一个指示它是否正在访问列表中的 URL 的位？如果您不想显式发送 URL，请发送哈希(不要尝试最大化冲突)。如果您想节省空间，请发送 Bloom filter .