用_brute force_破坏单向哈希属性与证明碰撞之间的区别

Question

对于任何哈希函数，无论从概念上还是其他方面，上述两个操作之间有什么区别。我已经通过以下方式解决了这个问题：

H=hash(someplaintext)
n=0
while 1:
    if hash(str(n))==H:
        print n
    n+=1

可以通过这种方式证明这两个属性，是否有问题？忽略效率，内存使用率或任何此类属性。请严格根据正确性回答我的问题

Answer 1

“单向”表示给定一个函数输出，除非尝试了很多潜在的输入并很幸运，否则您找不到匹配的输入。冲突是关于找到产生相同输出的两个不同输入，而在所述输出上没有任何预定义的约束。

好的（加密）哈希函数应具有三个经典属性：

• 抵抗原像：给定x，找到m使得h（m）= x应该是不可行的。
• 对第二原像的抵抗力：给定m，找到m与m不同应该是不可行的，这样h（m）= h（m'）。
• 耐碰撞：找到m和m'彼此不同，以使h（m）= h（m'）应该是不可行的。

这可以看作是攻击者面临的三个挑战，按照难度的降低排序。对于原像，我给您一个输出，然后挑战您找到一个匹配的输入。对于第二张原图，我给您一个输入（并暗含相应的输出），并挑战您查找另一个匹配的输入。对于碰撞，这就像第二次原像挑战，只是我不需要您找到特定的输出；任何人都会做。或者，换句话说：对第二个原像的挑战就像对碰撞的挑战，在碰撞中，攻击者无法自由选择一个冲突消息。

在不利用哈希函数本身的任何弱点的情况下，对于具有n位输出的哈希函数，查找原像，第二原像和碰撞的通用方法的成本约为2 ⁿ（对于原像和第二原像）和2 ^{n / 2}（用于碰撞）。因此，查找冲突非常容易。对于原像，您只需尝试输入即可，直到您感到幸运为止（这就是您所说的“蛮力”）；每次尝试都有2 ^-n的成功几率。对于碰撞，这与生日攻击有关：基本上，一旦您累积了sqrt（2 ⁿ） 在输入/输出对中，其中两个对具有相同输出的可能性上升很快。

就生日而言，这意味着如果您随机选择20个人，他们中的两个人生日相同的可能性就很高-但您无法选择哪一天或哪一天。另一方面，如果您想找到一个生日与您相同的人，那么您将必须平均抽样365个人。