为什么一个好的哈希算法不允许攻击者找到两个产生相同哈希的消息?

我正在阅读维基百科,它说

加密散列函数是第三种加密算法 . 它们将任意长度的消息作为输入,并输出一个短的,固定长度的散列,可用于(例如)数字签名 . 对于良好的散列函数,攻击者无法找到两条产生相同散列的消息 .

但为什么?我的理解是你可以将长的Macbeth故事放入哈希函数中并从中获取X长哈希值 . 然后你可以放入Beowulf故事中再次获得另一个哈希值X long .

因此,由于此函数将事物的负载映射到较短的长度,因此必然存在重叠,就像我可能将Hobit的故事放入哈希函数并获得与Beowulf相同的输出,好吧,但这是 inevitable 对( ?)因为我们从输入产生较短的长度输出?即使找到输出,为什么会出现问题?

我可以想象,如果我将其反转并退出Hobit而不是Beowulf,那会很糟糕,但为什么它对攻击者有用呢?

最好,

回答(4)

2 years ago

是的,将长消息映射到较短的散列时,不可避免地会发生冲突,因为散列不能包含消息的所有可能值 . 出于同样的原因,你无法“反转”哈希来独特地生成Beowulf或霍比特人 - 但是如果你生成了所有可能的文本并过滤掉了那些具有你特定哈希值的文本,你就会找到这两个文本(在数十亿其他文本中) ) .

文章说攻击者应该很难 findconstruct 第二条消息与第一条消息具有相同的哈希值 . 加密哈希函数通常用作证明消息未被篡改的证据 - 如果即使单个数据位翻转,则哈希值也应完全不同 .

几年前,荷兰研究人员通过在美国总统大选中公布他们的"prediction"哈希来弥补MD5的弱点 . 当然,他们无法提前知道结果 - 但是凭借PS3的计算能力,他们为每个候选人构建了一个PDF文件,每个候选人具有相同的哈希值 . MD5的影响 - 已经在下降 - 作为数字签名的可靠算法变得更加可怕......

2 years ago

是的,当然会因为您描述的原因而发生碰撞 .

我想这句话应该是这样的:"For good hash functions, an attacker cannot find two messages that produce the same hash, except by brute-force" .

至于为什么......

散列算法通常用于身份验证 . 通过检查消息的散列,您可以(几乎)确定消息本身未被篡改 . 这依赖于找到两条生成相同哈希的消息是不可行的 .

如果散列算法允许相对容易地找到冲突,那么它对于认证变得无用,因为攻击者然后(理论上)可以篡改消息并且使得被篡改的消息生成与原始相同的散列 .

2 years ago

加密哈希用于身份验证 . 例如,对等协议严重依赖于它们 . 他们使用它们来确保恶意的对等方不能通过分发包含垃圾的数据包来破坏其他人的下载 . 描述下载的torrent文件包含每个块的哈希值 . 通过此检查,受害者对等方可以发现他已经处理了损坏的块并从其他人处再次下载 .

攻击者想用Hobbit取代Beowulf以增加撒克逊诗歌的可见度,但协议中使用的加密哈希不会让他失望 .

2 years ago

如果很容易发现冲突,那么攻击者就可以创建恶意数据,并简单地将其与虚拟数据一起添加,直到找到冲突为止 . 然后,哈希检查将传递恶意数据 . 这就是为什么碰撞只能通过蛮力进行,并尽可能少见 .

或者,冲突也是证书的问题 .