抗碰撞函数H‘= h1(h2())的组合是否具有抗碰撞能力？

Question

假设有两个抗碰撞散列函数h_1和h_2，其输出大小分别为n_1和n_2。

H'(x) = h_1(h_2(x))是否能抵抗n_1和n_2之间的不同关系？

这在过去几天里一直困扰着我和我的同事，因为两种不同的方法相互矛盾：

第一种方法：

基于碰撞抗力的定义，H'有一个n_1长度的输出，所以如果我们能找到比\mathcal O(2^{n_1/2})更小的攻击，那么它就不具有抗碰撞能力。

我们要\mathcal O(2^{n_2/2}) < \mathcal O(2^{n_1/2}) \implies \ldots \implies n_2 < n_1

因此，如果n_2 < n_1, H'不具有抗碰撞能力，而在其他情况下则是如此

第二种方法：

让我们假设H'不具有抗碰撞能力。

在此基础上，x_1和x_2的存在不同，使得H'(x_1) = H'(x_2)即：

h_1(h_2(x_1)) = h_1(h_2(x_2))

如果是h_2(x_1) = h_2(x_2)，但h_2具有抗碰撞能力，也可能发生这种情况

如果h_1(A) = h_1(B) A = h_2(x_1)和B = h_2(x_2)但h_1具有抗碰撞能力，也可能发生这种情况。

我们已经证明了H'是抗碰撞的，n_1和n_2的关系并不重要.

Answer 1

我有机会问我的教授，他期待第一个解决方案，因为第二个假设n_1 = n_2 (我仍然不知道为什么或在哪里这样做)。

他还解释说：

• 一个1,000位的n_2然后转换为2位的n_1被认为是抗碰撞的，因为你利用了2位提供的全部安全性，也就是说你得到了你“支付”的2位的所有值。
• 相反，一个500位的n_2然后转换为1000位的n_1并不被认为是抗碰撞的，因为您“支付”了1000位的安全性，并且只使用了500位。

这确实帮助我以直观和合乎逻辑的方式理解了这个概念。

Answer 2

这在过去的几天里一直困扰着我和我的同事，因为两种不同的方法相互矛盾。

原因是这两种方法假设了不同的“抗碰撞”定义；这两种定义不是等价的；也就是说，我们可以找到满足一个定义而不是另一个定义的函数。

第一次尝试使用的定义是“没有冲突查找附加，比\mathcal{O}(2^{n/2})操作花费的更少；因为n是固定的，所以我们用它来表示‘攻击需要c2^{n/2}操作，对于一些距离1不远的c，以及一些合理的操作定义(在本例中，是哈希函数计算)。

这个定义的问题是，它导致了一些荒谬的结论，例如，根据这个定义，截断为8位的SHA-256是“抗碰撞的”。在另一个方向上，奶昔256的1k字节输出并不是“抗碰撞”，因为您可以发现与2^{8192/2}哈希值相比要少得多的冲突。

相反，方法2使用的定义是“如果我们找不到冲突，哈希函数是冲突的抵抗”。正式表达这一点有点棘手(因为，只要允许输入比输出长，就一定会发生冲突，我们只是不知道它们是什么)，也因为这是相对于我们所拥有的计算资源(现在，SHA-256截断为200位是抗碰撞的；随着我们获得更多的计算能力，可能还不到20年)；另一方面，它更接近于我们所拥有的“抗碰撞”的直观概念。

有了这个定义，方法2可以被改写为‘如果我们假设H'不具有冲突抵抗力，那么我们就知道x \ne y和H'(x) = H'(y)，那么要么h_2(x) = h_2(y) (因此h_2不具有冲突抗性，就像我们所知道的冲突那样)，要么h_2(x) \ne h_2(y)，在这种情况下我们有h_1(u) = h_1(v) for u = h_2(x), v = h_2(y), u \ne v (因此h_1是不冲突的，因为我们知道冲突)。