为什么MD5哈希值不可逆？

我一直想知道的一个概念是使用加密哈希函数和值.我知道这些函数可以生成一个唯一且几乎不可能反转的哈希值,但这是我一直想知道的:

如果在我的服务器上,在PHP中我生成:

md5("stackoverflow.com") = "d0cc85b26f2ceb8714b978e07def4f6e"

通过MD5函数运行相同的字符串时,您在PHP安装上获得相同的结果.正在使用一个过程从一些起始值产生一些值.

这是不是意味着有一些方法来解构正在发生的事情并扭转哈希值？

这些函数是什么使得结果字符串无法回溯？

1> Cody Brociou..：

---

输入材料可以是无限长度,其输出始终为128位长.这意味着无限数量的输入字符串将生成相同的输出.

如果您选择一个随机数并将其除以2但只记下余数,则分别得到0或1 - 偶数或奇数.是否可以取0或1并获得原始数字？

---

moocha:Injective意味着1到1.MD5肯定不是1比1,因为域大于范围.值得注意的另一点是,给定一个MD5校验和,很难找到一个哈希值的字符串.可能值得补充澄清的答案.

---

使用生成唯一值的哈希函数是不可能的.您将无限数量的值映射到有限数量的值,这可以保证冲突.

---

我建议你的答案没有解决关键问题.正如biozinc所提到的,对于安全密码哈希来说,重要的是你找不到任何创建输出的输入,而不是你找不到原始输入.在这方面,MD5不一定是安全的(http://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities).

---

也就是说,数字 - >余数和字符串 - > md5都不是"内射函数".

2> Autodidact..：

---

如果MD5等散列函数是可逆的,那么它将成为数据压缩算法历史上的一个分水岭事件!很容易看出,如果MD5是可逆的,那么任意大小的任意数据块都可以用128位表示,而不会丢失任何信息.因此,无论原始消息的大小如何,您都能够从128位数重建原始消息.

---

@Colin Pickard:我们不会再*下载*linux发行版,我们将*写下来*.:)

---

想想下载linux发行版有多快,如果你能得到md5而不是:)

---

很好地说.:)

3> Paŭlo Eberma..：

---

与此处最受欢迎的答案强调的相反,由大(可能无限)输入大小和固定输出大小之间的差异引起的加密散列函数的非内射性(即,有几个字符串散列到相同值)不是重要的一点 - 实际上,我们更喜欢散列函数,尽管这些碰撞很少发生.

考虑这个函数(用PHP表示法,作为问题):

function simple_hash($input) {
     return bin2hex(substr(str_pad($input, 16), 0, 16));
}

如果字符串太短,则会附加一些空格,然后获取字符串的前16个字节,然后将其编码为十六进制.它具有与MD5散列相同的输出大小(32个十六进制字符,如果我们省略bin2hex部分则为16个字节).

print simple_hash("stackoverflow.com");

这将输出:

737461636b6f766572666c6f772e636f6d

此函数也具有与Cody对MD5的答案所突出显示的相同的非注入性:我们可以传入任何大小的字符串(只要它们适合我们的计​​算机),并且它将仅输出32个十六进制数字.当然它不能是单射的.

但是在这种情况下,找到一个映射到相同哈希的字符串是很简单的(只需应用hex2bin你的哈希值,你就可以了).如果您的原始字符串长度为16(如我们的示例所示),您甚至会获得此原始字符串.即使你知道输入的长度非常短(除了通过尝试所有可能的输入,直到找到匹配的输入,例如蛮力攻击),MD5的任何类型都不可能.

加密哈希函数的重要假设是:

很难找到产生给定散列的任何字符串(preimage resistance)

很难找到任何不同的字符串产生与给定字符串相同的哈希值(第二个原像素阻力)

很难找到任何具有相同散列的字符串对(抗冲击性)

显然我的simple_hash功能既不符合这些条件.(实际上,如果我们将输入空间限制为"16字节字符串",那么我的函数就变得是单射的,因此甚至可以证明第二前像素抗性和抗冲突性.)

现在存在针对MD5的冲突攻击(例如,有可能产生一对字符串,即使具有相同的前缀,具有相同的散列,具有相当多的工作,但并非不可能的大量工作),因此您不应该使用MD5对于任何关键的事情.还没有一个原像攻击,但攻击会变得更好.

回答实际问题:

这些函数是什么使得结果字符串无法回溯？

MD5(以及Merkle-Damgard构造的其他哈希函数)有效地做的是应用加密算法,将消息作为关键字,将一些固定值作为"纯文本",使用生成的密文作为哈希.(在此之前,输入被填充并分成块,每个块用于加密前一个块的输出,与其输入进行异或,以防止反向计算.)

现代加密算法(包括散列函数中使用的算法)的制作方式使得难以恢复密钥,即使给出了明文和密文(或者甚至在对手选择其中之一时).它们通常通过以每个输出位由每个密钥位(几次)以及每个输入位确定的方式进行大量的位混洗操作来完成此操作.这样,如果您知道完整的密钥以及输入或输出,您只能轻松地回溯内部发生的事情.

对于类似MD5的散列函数和前映像攻击(使用单块散列字符串,为了简化操作),您只能输入和输出加密函数,但不能输入密钥(这就是您要查找的内容).

---

是的,我知道这是一个很晚的答案,但接受的答案不应该让这样站着.

4> Federico A. ..：

---

Cody Brocious的答案是正确的.严格来说,您不能"反转"散列函数,因为许多字符串都映射到相同的散列.但是,请注意,要么找到一个映射到给定哈希的字符串,要么找到两个映射到相同哈希的字符串(即冲突),这将是密码分析师的重大突破.这两个问题的最大困难是良好的哈希函数在密码学中有用的原因.

5> Trevel..：

---

MD5不会创建唯一的哈希值; MD5的目标是快速生成一个值,该值根据对源的微小变化而显着变化.

例如,

"hello" -> "1ab53"
"Hello" -> "993LB"
"ZR#!RELSIEKF" -> "1ab53"

(显然这不是实际的MD5加密)

大多数哈希(如果不是全部)也是非独特的; 相反,它们足够独特,所以碰撞是非常不可能的,但仍然可能.

6> nbevans..：

---

考虑哈希算法的一个好方法是考虑在Photoshop中调整图像大小......假设你有一个5000x5000像素的图像,然后你将它的大小调整为32x32.你所拥有的仍然是原始图像的一种表现形式,但它要小得多,并且有效地"抛弃"图像数据的某些部分,使其适合较小的尺寸.因此,如果您要将32x32图像重新调整为5000x5000,那么您所得到的就是模糊不清.然而,因为32x32图像不是那么大,理论上可以想象另一个图像可以缩小尺寸以产生完全相同的像素!

这只是一个类比,但它有助于理解哈希正在做什么.

---

虽然图像大小调整是一个有损的过程,但仍然很容易生成原始5000×5000大小的图像,这将(当再次应用缩小功能时)减少到相同的32×32图像.找到这样的前像应该是**硬**以获得良好的散列函数.