哈希算法的优势

语句“x hash function has been breaked”意味着hash函数算法存在缺陷,因此可以比通过野蛮变形更快地生成冲突。看看 this post by Bruce Schneier -他说,现在可以更快地产生一个sha-1碰撞,仅此而已。

所以是的,它们对于暴力变形都是同样不安全的,但这不是“x hash function has been breaked”语句所指的。

准确地说,一个哈希函数可以执行三次“攻击” H :

1. 预成像 :给定“输出” Y (正确大小的位序列,如MD5为128位),查找消息 米 (任意的位序列)这样 h(m)=y .

2. 第二个预映像 :给出消息 米 ,查找其他消息 M’ ,不同于 米 ,这样 h(m)=h(m') .

3. 碰撞 :查找两条消息 米 和 米 彼此不同,这样 h(m)=h(m') .

一个好的散列函数是一个尽可能抵抗这三种攻击的函数。那最好的是什么?它取决于哈希输出大小 n .

考虑一个理论上完美的散列函数,包含在一个黑匣子里;盒子里有一个侏儒、一些骰子和一本大书。当要求一个哈希值时,对于一个给定的输入消息,gnome使用骰子生成一个随机的输出,然后返回。但他也在他的大书中写下了信息和输出。如果再次向他请求相同消息的散列值,那么他将返回与以前相同的值。这个设置被理论家称为 随机预言机 . 随机预言者从不自相矛盾,但在向他提出精确的问题之前,你不知道它会在给定的问题(和输入信息)上回答什么。

如果随机Oracle输出长度为的字符串 n 比特,那么我们就可以及时找到预图像和第二个预图像。 O(2) ⁿ ) 和及时的碰撞 O(2) ^N/2 ) . 这里用对随机Oracle的请求来表示时间。preimages上的阻力很容易理解:攻击者只需尝试消息,直到Oracle输出预期值;他无法做得更好,因为即使是gnome也不知道他将获得什么新输入。由于甲骨文具有一致随机性,因此预期的试验次数为 二 ⁿ . 对第二个预成像的阻力沿着同一条线流动。对于碰撞,这与已知的 birthday paradox .

如果散列函数的电阻看起来与随机Oracle的电阻匹配,那么散列函数就被认为是安全的。它不能做得更好,我们要求它也不会变得更糟。

当有人提出一种方法来查找preimages、第二个preimages或冲突时,散列函数就被称为“中断”,其成功率高于处理随机Oracle的通用方法。据说沙-1是因为一种寻找碰撞的方法而被破坏的,花费大约 二 ^六十一 ,被发现(sha-1有160位输出,因此应该能够抵抗高达约 二 ^八十 )请注意,完整的方法没有运行,即我们没有实际的冲突。 二 ^六十一 仍然很高,在可行的边缘(它需要数千台机器,运行数月或数年)。但是 二 ^六十一 如果小于50万倍 二 ^八十 所以这是一个休息。

有时会发现“中断”,因为攻击的成本非常高(例如,成本上的攻击) 二 ^{一百一十二} 理论阻力为 二 ^{一百六十八} )然后我们讨论一个“学术性”突破:比预期的阻力更快,但使用地球技术仍然完全无法挽回。

注意,并非所有哈希函数的使用都依赖于对碰撞的抵抗。实际上,大多数用法依赖于对预图像或第二预图像的抵抗。对于这些攻击,sha-1目前和新的一样好,它的 二 ^一百六十 抵抗力。

相反,即使是一个输出为128位的完美哈希函数也应该被认为是弱的,至少对于抗碰撞性来说是这样:一般攻击,工作系数为 二 ^六十四 在技术可行的范围内。这就是为什么新的哈希标准使用更大的输出(例如,sha-2从224位输出开始)。足够大的输出可以抵御一般攻击。

现代密码的措施是什么 哈希算法用于防止 碰撞攻击?

密码学家Bart Preneel的博士论文是对这一主题的一个很好的概述: Analysis and Design of Cryptographic Hash Functions .

你可能对 provably secure cryptographic hash functions 存在,但目前认为不实际。

MD5不是 collision resistant . 维基百科的定义是:

碰撞阻力 是加密哈希函数的属性:a 哈希函数具有抗冲突性 如果很难找到两个输入 散列到相同的输出;也就是说,两个 输入A和B,以便 H(a)= H(b) .

MD5生成一个128位散列,现在可以在几秒钟内中断。

现代密码散列算法使用什么措施 防止碰撞攻击?

防止这种情况的一种方法是增加哈希结果的大小(以位为单位的输出大小)。允许 时间 让密码学家调查漏洞。我这么做已经很久了……但总而言之,是的——)

我只有部分答案。=)

根据我目前的理解,对于所有哈希结果,从数据d中获得某个哈希h(d)的机会是相等的。

这不是真的。散列的目的是每次都为一些数据D获得相同的散列h(d)。因此,该算法可能没有产生哈希的任何“机会”。哈希算法面临的困境是,从D计算h(d)应该是容易的,但从H(d)计算有效d应该是困难的。

如果从h(d)计算d的速度比蛮力更快,则认为算法“不具有密码安全性”。

很容易看出,并不是所有的哈希算法都必须同样不安全,方法是使用返回数据前几个位的哈希函数。无论您使用的位数是多少,查找冲突都很简单。

是的,“密码破译”就是这个意思。恐怕我不是专家,所以我不能回答第二个问题。