双重哈希是否具有抗碰撞性？

Question

双重哈希肯定比单层哈希提供更多安全性，但这是否意味着它更抗碰撞？用更数学化的方式来表达这个问题： 如果H是一个抗冲突哈希函数，那么对于某些x，H(H(x))仍然是抗冲突的吗？

- AverageJoe

Answer 1

事实上，对于碰撞抗性来说甚至可能更糟，因为内部H的输出是有限的。

例如，取一个从{0,1}ⁿ → {0,1}ⁿ映射的函数H。(我们将x限制在{0,1}ⁿ中以便更容易看到。)假设存在a、b来自{0,1}ⁿ，且c=H(a)=H(b)。这意味着H(c)=H(H(a))=H(H(b))。当你在第一次转换中发生碰撞时，你无法解决它。

如果在{0,1}ⁿ中没有碰撞，则第二个转换的表现方式相同。

由于我们通常将哈希函数描述为{0,1}^* → {0,1}ⁿ，因此在第一次转换中必定会出现碰撞，而第二次转换可能会使情况变得更糟。

- Artjom B.

Answer 2

原则上，结果哈希函数 H(H(x)) 的碰撞抗性要么不如，要么与哈希函数 H(x) 相同，因为：

1. 对于哈希函数 H(x)，假设每个 N 个唯一前像中有一个冲突。这意味着有两个哈希值相似，而 H(H(x)) 不会使它们不同。
2. 对于哈希函数 H(x)，假设每个 N 个唯一前像中有一个冲突。对于 H(H(x)) 也是如此，因为 H(H(x)) 只是 H(固定长度的字符串)。这增加了发生碰撞的可能性。

- yadab