如何确定哈希函数是否安全？

Question

我正在做一个计算机安全方面的测试，我遇到了这个问题，我不知道如何正确地攻击。我应该在纸面上使用哈希函数，还是有一种更普遍的方法来做出这类安全判断？

问题如下：

设$M = B_1，.，B_n$是由512位的$n$块组成的消息。设$H$为函数$H(M)=(B_1+B_2) \oplus B_3)+B_4 \oplus B_5)...B_n$，其中$+$为加法模2^{512}$，$\oplus$为位异或。$H$是一个安全的哈希函数吗？

对于每一项要求：

1. 预像电阻(或单向)
2. 第二预像电阻(或弱碰撞阻力)
3. 防撞(或强碰撞)

如果它坚持或否定它，那就去激励它。

将$D$设为具有$n \leq 4$ (即。所有小于2兆比特的消息)。对于$H$中的消息，$D$会产生比SHA-256更多的冲突吗？

Answer 1

解决此类问题的最佳方法是从<#>assuming开始，即存在一个简单的解决方案。

1. 因为这是一个教科书上的问题，所以它可能有一个相对简单的解决方案，您应该能够根据您所学到的知识找出答案。
2. 即使不是这样，在花时间在任何更复杂的事情上之前，至少应该尝试寻找简单的解决方案。

因此，您应该假设，一方面，如果您的散列函数不能满足问题所询问的三个安全属性中的一个，那么应该有一个非常简单的例子，说明该属性被违反了。另一方面，如果它确实满足了它们的要求，那么就应该有一些相当简单的方法来证明这一点，或者至少将其简化为一些被广泛接受的假设(例如，“如果有人能够打破这个哈希，那么他们也可以破坏SHA-256")。

考虑到这一点，让我们仔细看看您的散列函数。它被指定为接受一系列$n$输入块，这些块根据涉及加法(模$2^{512}$)和位异或的特定表达式组合：

$$H(B_1，\dots，B_n) =(B_1+ B_2) \oplus B_3) + B_4) \oplus B_5) + \dots$$

我们怎么简化呢？嗯，块越少，表达式就越简单。因此，让我们首先考虑最简单的情况，即$n=1$。只有一个输入块，您的哈希函数如下所示：

$$H(B_1) = B_1$$

现在，考虑被问到的三个安全属性，看看是否可以找到单个块的反例：

1. 图像前电阻:如果给定一个值$X$，您能找到单个块消息$M = B_1$，这样$H(M) = X$吗？
2. 第二个预图像电阻:如果给定单个块消息$M = B_1$，您能找到另一个单块消息$M‘= B_1’\ne B_1$，使$H(M) = H(M')$吗？
3. 抗碰撞性:你能找到两个单块消息$M = B_1$和$M‘= B_1’\ne B_1$，例如$H(M) = H(M')$吗？

希望你至少能回答以上三个问题中的一个。(我不会破坏哪一个。)事实上，再多考虑一下，你就会发现，对于单块消息，其他两个问题的答案肯定是“否”。

不过，我们还没完成呢。如果我们考虑由两个块组成的消息呢？然后哈希函数将如下所示：

$$H( B_1，B_2) =B_1+ B_2$$

当然，$+$表示加法模$2^{512}$。考虑到这一点，让我们再考虑一下这三个问题。(当然，您不需要重新考虑上面已经找到的单一块反例。)

1. 图像前电阻:如果给定一个512位值$X$，您能找到一个双块消息$M = (B_1，B_2)$，这样$H(M) = X$吗？
2. 第二个预图像电阻:如果给一个双块消息$M = (B_1，B_2)$，你能找到另一个双块消息$M‘= (B_1'，B_2') \ne M$，使得$H(M) = H(M')$吗？
3. 碰撞阻力:你能找到任何双块消息$M = (B_1，B_2)$和$M‘= (B_1'，B_2') \ne M$，使得$H(M) = H(M')$？

如果在考虑了两个区块的情况后，你对这三个问题中的一些问题的回答仍然是“否”，那么现在可能是时候开始考虑一下，你是否应该开始考虑一下，对于一个和两个块案件，你得出“不”答案的方式是否可以推广到任意数量的区块。或者你可以花一些时间来考虑三个块的情况，如果你认为答案是肯定的话。

但事实上，在这种情况下，这不应该是必要的；仅仅考虑一分为二的情况就足以给出这个散列的所有三个问题的明确答案。

Ps。至于关于最后碰撞次数的额外问题，首先要注意的是，这个问题(或你对它的转录)显然有一些排字:四个512位块计算到2048位或2 _kilo_bits，而不是2兆位！

在任何情况下，我们当然不知道SHA-256在这组输入上有多少次碰撞，因为输入空间太大，无法用蛮力来计算它们，任何确定确切数字的方法都要比蛮力快得多，这就需要破坏SHA-256，或者至少要让人担心地接近它。

但是，您应该能够为SHA-256或任何其他具有256位输出大小的哈希值的输入空间提供一个下限，只需使用简单的算术。(广义针孔原理在这里可能很有用。)您的哈希函数$H$非常简单，您可以计算它在输入空间$D$上的确切碰撞次数，并将其与下限进行比较。

事实上，对于是/否的答案，你甚至不需要计算碰撞的实际数量。您真正需要做的就是考虑到您的函数$H$得到的512个位哈希的理论下限有多近，然后考虑如何使哈希输出更长/更短会影响下界。

(另外，是的，你会得到的结果似乎违反了直觉。它真正证明的是，碰撞的总数并不一定与实际找到碰撞的难度相关。)