hash - 通过_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 成功的概率。对于碰撞，这与 birthday attack 有关: 基本上，一旦你积累了大约 sqrt(2ⁿ) 对输入/输出，其中两个具有相同输出的对的概率上升得非常快。

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