hash - 哈希 : doesn't it reduces entropy? 上的多次迭代

Question

我看到在很多地方(包括堆栈)都推荐了这种技术，我无法忘记这会减少熵!毕竟，您正在再次散列一些已经散列并且有碰撞机会的东西。碰撞机会超过碰撞机会会不会导致更多的碰撞机会？经过研究，似乎我错了，但为什么呢？

Answer 1

由于您标记了 md5，我将以此为例。来自 wikipedia :

if two prefixes with the same hash can be constructed, a common suffix can be added to both to make the collision more likely to be accepted as valid data by the application using it. Furthermore, current collision-finding techniques allow to specify an arbitrary prefix: an attacker can create two colliding files that both begin with the same content. All the attacker needs to generate two colliding files is a template file with a 128-byte block of data, aligned on a 64-byte boundary that can be changed freely by the collision-finding algorithm. An example MD5 collision, with the two messages differing in 6 bits, is:

然后他们给出的示例明文长度为 256 字节。由于碰撞攻击依赖于 128 字节的数据块，而哈希摘要只有 128 位，因此在第一次迭代之后碰撞攻击成功的风险确实没有增加——也就是说，你真的不能影响超出第一个哈希值的冲突可能性。

还要考虑散列的熵是前面提到的 128 位。即使考虑到总碰撞机会仅为 2^20.96(同样来自 wikipedia)，也需要大量迭代才能导致两个输入发生碰撞。我认为你成为受害者的第一眼推理是:

任意两个任意输入都有碰撞几率 x%。

第一个散列的输出本身就是两个这样的输入。

因此，每次迭代都会将碰撞几率增加 x%。

这可以很容易地被反例证明。再次考虑 MD5:

两个输入发生冲突的几率是 1:2^21(从维基百科对 MD5 的密码学分析中采取最坏的情况)

再次散列会导致相同可能性的碰撞复合，因此第二轮碰撞的几率是 1:2^20

因此，对于散列次数等于摘要熵的任何两个输入，保证会发生冲突。

MD5 任何两个输入连续 128 次，你会发现这不是真的。您可能不会在它们之间找到一个重复的散列 - 毕竟，您只创建了 2^128 个可能的散列值中的 256 个，剩下 2^120 个可能性。每轮之间发生碰撞的概率是independent所有其他回合。

有两种方法可以理解为什么会这样。首先是每次迭代本质上都是试图击中一个移动的目标。我认为您可以基于生日悖论构建一个证明，即哈希的迭代次数少得惊人，您可能会看到一个输入的一个哈希摘要与另一个输入的哈希摘要匹配。但它们几乎肯定会发生在迭代的不同步骤。一旦发生这种情况，它们在同一次迭代中永远不会有相同的输出，因为哈希算法本身是确定性的。

另一种方法是意识到哈希函数在运行时实际上增加了熵。考虑一个空字符串和任何其他输入一样有一个 128 位的摘要；如果在算法步骤中不添加熵，就不会发生这种情况。这实际上是加密散列函数的必要组成部分:必须销毁数据，否则可以从摘要中恢复输入。对于比摘要长的输入，是的，整体上会丢失熵；它必须是为了适应摘要长度。但也增加了一些熵。

我没有其他哈希算法的确切数字，但我认为我提出的所有观点都可以推广到其他哈希函数和单向/映射函数。