通常,这种散列算法不能是单射的,因为产生的实际摘要通常具有固定长度(例如,SHA-1下的160位等),而要消化的可能消息的空间实际上是无限的.
但是,如果我们生成的消息摘要最多与生成的摘要一样长,那么常用的散列算法的属性是什么？它们在这个有限的信息空间中是否可能是单独的？是否存在算法,即使在比特长度短于所产生的摘要的比特长度的消息上,也会产生冲突？
我实际上正在寻找具有这种属性的算法,即,至少原则上,即使对于短输入消息,也可以产生冲突哈希.
背景：我们有一个浏览器插件,对于访问的每个网站,都会发出服务器请求,询问该网站是否属于我们的已知合作伙伴之一.但当然,我们不想窥探我们的用户.因此,为了难以生成某种冲浪历史记录,我们实际上并不发送访问过的URL,而是发送一些清理版本的哈希摘要(目前为SHA-1).在服务器端,我们有一个众所周知的URI哈希表,它与收到的哈希值相匹配.我们在这里可能存在一定的不确定性,因为我们认为无法跟踪用户的功能,而不是错误.
由于显而易见的原因,这个方案非常模糊,并且承认误报以及URI应该具有的不匹配.
所以现在,我们正在考虑将指纹生成更改为具有更多结构的内容,例如,而不是散列完整(已清理)的URI,我们可能会改为：
>将主机名拆分为“.”的组件.并单独散列
>检查“.”处的组件路径.并单独散列
将生成的哈希值加入指纹值.示例：使用此方案散列“www.apple.com/de/shop”(并使用Adler 32作为散列)可能会产生“46989670.104268307.41353536 / 19857610/73204162”.
但是,由于这样的指纹具有很多结构(特别是与普通的SHA-1摘要相比),我们可能会不小心再次计算用户访问的实际URI(例如,使用pre – “常用”compont值的哈希值的计算表,例如“www”).
所以现在,我正在寻找一种散列/摘要算法,即使在短消息上也会有很高的冲突率(Adler 32被认真考虑),因此给定组件散列的唯一概率很低.我们希望,我们施加的额外结构为我们提供了足够的额外信息,以改善匹配行为(即,降低误报率/假阴性率).
对于与摘要大小相同的消息,我不相信哈希值是不可靠的.如果它们是,那么它们将是双射的,这将缺少哈希点.这表明它们对于小于摘要的消息也不是不可取的.如果你想鼓励碰撞,我建议你使用你喜欢的任何哈希函数,然后扔掉它,直到它碰撞到足够的.
例如,扔掉159位SHA-1哈希会给你一个相当高的冲突率.你可能不想扔那么多.
但是,你想要实现的目标本质上是可疑的.您希望能够告诉您网址是您的网址之一,而不是它是哪一个.这意味着您希望您的网址相互冲突,但不希望您的网址与您的网址冲突.哈希函数不会为您执行此操作.相反,因为碰撞将是随机的,因为有更多的URL不是你的(我假设！),任何给定的碰撞级别将导致对URL是否是你的一个或者不是你的URL的混淆.你的哪一个.
相反,如何在启动时将URL列表发送到插件,然后让它只返回一个位,指示它是否正在访问列表中的URL？如果您不想显式发送URL,请发送哈希值(不尝试最大化冲突).如果您想节省空间,请发送Bloom filter.