为什么MD5散列值不可逆？

Question

我一直想知道的一个概念是加密哈希函数和值的使用。我知道这些函数可以生成唯一且几乎不可能被反向的哈希值，但我一直在想：

如果在我的服务器上，在PHP中我产生了：

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

当你在PHP中运行相同的字符串通过MD5函数时，你会得到相同的结果。这个过程是从一些起始值产生某个值。

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

这些功能有什么特点使得生成的字符串不可能被追溯？

- barfoon

---

一个简单的不可逆值的例子是取模。例如，10 % 3 = 1，但你不能将1反转回10，因为它也可以是4。 - Gab Royer

如果您可以重构数据，那么您将拥有最有效的无损压缩算法 :) - Dan Diplo

Answer 1

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

如果你选择一个随机数并将其除以2但只写下余数，你将得到0或1--分别是偶数或奇数。能否从这个0或1中得到原始数字呢？

- Cody Brocious

---

换句话说，无论是数字转余数还是字符串转md5，都不是“单射函数”。 - Federico A. Ramponi

Moocha说：“Injective”意味着一一对应。MD5肯定不是一一对应的，因为定义域比值域更大。另一个值得注意的点是，给定一个MD5校验和，很难找到一个散列成它的字符串。为了澄清，可能值得将此添加到答案中。 - biozinc

没有一种哈希函数可以生成唯一的值。你要将无限数量的值映射到有限数量的值，这就保证会出现冲突。 - Serafina Brocious

我建议你的回答没有解决关键问题。正如biozinc所提到的，保证一个安全密码哈希的重点是不能找到任何输入来创建输出，而不是不能找到原始输入。因此，MD5并不一定像它本可以那样安全（http://en.wikipedia.org/wiki/MD5#Collision_vulnerabilities）。 - Mike Pelley

@DaveL.：他在非正式的语境中使用“无限”的意思是“无限制的”。 - David Schwartz

Answer 2

如果哈希函数（例如MD5）是可逆的，那么这将是数据压缩算法历史上的一个分水岭事件！很容易看出，如果MD5是可逆的，则任意大小的任意数据块可以用仅有的128位表示而不会丢失任何信息。因此，您可以从128位数字中重建原始消息，无论原始消息的大小如何。请注意保留HTML标记。

- SDX2000

---

如果你能够直接获取MD5值，下载Linux发行版会变得非常快速。 - Colin Pickard

@Colin Pickard: 我们将不再“下载”Linux发行版，而是需要“书写它们”。 :) - tzot

Answer 3

与此处最赞的答案强调的相反，密码哈希函数的非注入性（即存在多个字符串散列到同一值）由于大输入大小（可能为无限）和固定输出大小之间的差异所导致并不是重��� - 实际上，我们更喜欢尽可能少发生碰撞的哈希函数。

考虑以下函数（使用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

这个函数和MD5一样也有不可逆性，正如Cody的答案中所强调的：我们可以传入任意大小（只要它们适合我们的计算机），它只会输出32个十六进制数字。当然它不能是可逆的。

但在这种情况下，很容易找到一个映射到相同哈希的字符串（只需在哈希上应用hex2bin即可）。如果原始字符串的长度为16（如我们的示例），您甚至将获得此原始字符串。对于MD5来说，这种情况不可能发生，即使您知道输入的长度非常短（除非尝试所有可能的输入，直到找到一个匹配的输入，例如暴力攻击）。

密码哈希函数的重要假设包括：

• 很难找到任何产生给定哈希的字符串（预像阻力）
• 很难找到任何产生与给定字符串相同哈希的不同字符串（第二预像阻力）
• 很难找到任何具有相同哈希的字符串对（碰撞防止）

显然，我的simple_hash函数都没有满足这些条件。（实际上，如果我们将输入空间限制为“16字节字符串”，则我的函数变得可逆，因此甚至可以被证明具有第二预像防护和碰撞防护）。

现在已经存在针对MD5的碰撞攻击（例如，即使具有给定相同前缀，也可以生成具有相同哈希的一对字符串，但需要一些工作，但不是无法完成），因此您不应该将MD5用于任何关键任务。目前还没有预像攻击，但攻击会变得更好。

回答实际问题：

这些函数具有什么特点，使得结果字符串不可能被追溯？

MD5（以及其他基于Merkle-Damgard构造的哈希函数）有效地执行的操作是使用消息作为密钥和某个固定值作为“明文”应用加密算法，使用生成的密文作为哈希值。（在此之前，输入进行了填充并分成块，每个块都用于加密上一个块的输出，并与其输入做异或运算以防止反向计算。）

现代加密算法（包括用于哈希函数的算法）通常采用位混淆操作的方式来难以恢复密钥，即使给定明文和密文（或者即使对手选择其中之一）。他们这样做通常是通过以每个密钥位（多次）和每个输入位确定每个输出位的方式进行的。这样，只有在您知道完整密钥和输入或输出时才能轻松追溯发生了什么。

对于类似MD5的哈希函数及其预像攻击（使用单个块散列字符串，以简化事情），您仅具有加密函数的输入和输出，但没有密钥（这就是您要寻找的内容）。

- Paŭlo Ebermann

---

是的，我知道这是一个相当晚的回答，但接受的答案不应该保持原样。 - Paŭlo Ebermann

我认为你的批评有一定道理，但你没有回答实际问题：“是什么让这些函数生成的字符串不可能被追踪？” 你的回答关注了密码哈希应该具有的特性，但却没有解释它们如何被MD5实现。你可以在这里陈述计算MD5摘要的确切算法，以展示它是如何不可逆的，但其他答案也提供了一个更简单的解释，而不用深入细节。 - Sandeep Datta

2. 这些解释使用“数学”来展示一个基本问题，由于这个问题，这些操作会丢失信息并变得不可逆。

- Sandeep Datta

@SandeepDatta 我添加了一些关于这个的段落。 - Paŭlo Ebermann

虽然本帖中其他回答更加技术正确，但这个回答更为实用。非单射函数f(x)=1是不可逆的但不太有趣。哈希的实用性在于它具有预像阻力，在这种情况下，很难找到任何输入产生特定的输出。 - Justin J Stark

Answer 4

Cody Brocious的答案是正确的。严格来说，您不能“反转”哈希函数，因为许多字符串映射到相同的哈希值。 请注意，找到映射到给定哈希值的一个字符串或找到映射到相同哈希值的两个字符串（即冲突），对于密码分析员来说都将是重大突破。这两个问题的巨大困难正是为什么好的哈希函数在密码学中非常有用的原因。

- Federico Ramponi

Answer 5

MD5算法不能创建唯一的哈希值；MD5的目标是快速生成一个基于源代码微小更改而显著变化的值。

例如，

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

（显然这不是真正的MD5加密）

大部分哈希函数（如果不是全部）也都是非唯一的；而是足够唯一，因此冲突的可能性非常小，但仍然存在。

- Trevel

Answer 6

一种理解哈希算法的好方法是将其类比于在Photoshop中调整图像大小...假设您有一个5000x5000像素的图像，然后将其调整为仅为32x32。您拥有的仍然是原始图像的表示，但它要小得多，并且已经“抛弃”了某些图像数据的部分以使其适合较小的尺寸。因此，如果您将该32x32图像放大到5000x5000，您将得到模糊的混乱图像。但是，由于32x32图像并不是那么大，因此从理论上讲，另一幅图像可以被缩小以产生完全相同的像素！这只是一个比喻，但它有助于理解哈希正在做什么。

- Nathan Evans

---

尽管改变图像大小会损失部分信息，但很容易生成一个原始尺寸为5000 x 5000的图像，再次应用缩小函数后可缩小为相同的32 x 32图像。对于优秀的哈希函数而言，找到这样的预像应该是困难的。 - Paŭlo Ebermann

Answer 7

哈希碰撞比你想象的更有可能发生。查看生日悖论，以更深入地了解其中的原因。

- Gamic

---

有365个可能的生日值，介于2^8和2^9之间。128位哈希有2^128个可能的值——是其120倍。是的，碰撞比你想象的更有可能，但它们仍然是天文数字般的不可能。 - Tim Keating

你需要大约2^64个不同的值才能有很好的哈希碰撞机会。仍然相当多。 - Paŭlo Ebermann

Answer 8

由于可能的输入文件数量大于128位输出的数量，因此无法为每个可能的输入唯一分配MD5哈希值。

加密哈希函数用于检查数据完整性或数字签名（哈希值被签名以提高效率）。因此更改原始文档应意味着原始哈希值与更改后的文档不匹配。

有时使用以下标准：

1. 预像抗性：对于给定的哈希函数和给定的哈希值，很难找到一个具有该函数的给定哈希值的输入。
2. 第二原像抗性：对于给定的哈希函数和输入，很难找到一个第二个不同的输入，其哈希值相同。
3. 碰撞抗性：对于给定的哈希函数，很难找到两个不同的输入具有相同的哈希值。

选择这些标准是为了使查找与给定哈希值匹配的文档变得困难，否则可以通过替换原始文档与与哈希值匹配的文档来伪造文档。（即使替换是无意义的，仅替换原始文档也可能导致破坏。）

第3点蕴含第2点。

至于MD5，已经显示出存在漏洞：如何破解MD5和其他哈希函数。

- Geoglyph

Answer 9

但这就是彩虹表发挥作用的地方。基本上，它只是将大量值分别进行哈希，然后将结果保存到磁盘中。然后反转位“只是”在一个非常大的表中查找。

显然，这仅适用于所有可能输入值的子集，但如果您知道输入值的范围，则可能可以计算它。

- martinlund

---

啊，是的。我很喜欢读Jeff关于哈希表（http://www.codinghorror.com/blog/archives/000949.html）的文章，这个帖子对概念的理解有所帮助。 - barfoon

Answer 10

理解所有最被赞同的答案的最好方式是尝试恢复MD5算法。我记得几年前我曾尝试还原MD5crypt算法，不是为了恢复原始消息，因为这显然是不可能的，而只是为了生成一个与原始哈希相同的哈希值。至少在理论上，这将为我提供一种方法，使用生成的消息（密码）而不是使用原始消息来登录存储用户:密码的Linux设备中的/etc/passwd文件。由于两个消息将具有相同的结果哈希，系统将识别我的密码（从原始哈希生成）为有效密码。但这根本没有起作用。如果我没记错的话，经过几周的努力，初始消息中的盐杀死了我。我不仅需要生成一个有效的初始消息，还需要生成一个盐值有效的初始消息，但我从未能够做到。但我从这个实验中获得的知识很好。

- Vinicius

---

如果您能够以任何合理高效的方式生成一个产生给定MD5哈希值的输入，那将对加密社区来说是一件大事，并且应该予以发布。这完全独立于特定输入是否被盐处理。 - Dave L.