为什么MD5哈希值不可逆?

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

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

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

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

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

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

回答(16)

3 years ago

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

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

3 years ago

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

3 years ago

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

考虑这个函数(用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的任何类型都不可能 .

The important assumptions for a cryptographic hash function are:

  • 很难找到产生给定散列的任何字符串(前映像素阻力)

  • 很难找到任何不同的字符串产生与给定字符串相同的散列(第二个preimage抵抗)

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

显然我的 simple_hash 函数既不满足这些条件 . (实际上,如果我们将输入空间限制在"16-byte strings",那么我的函数就会变成单射,因此甚至可以证明第二次前像素抗性和抗冲突性 . )

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

To answer the actual question:

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

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

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

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

3 years ago

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

3 years ago

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

例如 . ,

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

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

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

3 years ago

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

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

3 years ago

哈希冲突比你想象的要可能得多 . 看一下birthday paradox以更好地理解为什么会这样 .

3 years ago

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

加密哈希函数用于检查数据完整性或数字签名(为了效率而签名的哈希) . 因此,更改原始文档应该意味着原始哈希与更改的文档不匹配 .

有时使用这些标准:

  • Preimage抵抗:对于给定的散列函数和给定的散列,应该很难找到具有该函数的给定散列的输入 .

  • 第二个preimage抵抗:对于给定的散列函数和输入,应该很难找到具有相同散列的第二个不同的输入 .

  • 碰撞阻力:对于给定的函数,应该很难找到具有相同散列的两个不同输入 .

选择这些标准使得难以找到与给定散列匹配的文档,否则可以通过用散列匹配的原语替换原始文档来伪造文档 . (即使更换是胡言乱语,仅仅更换原件可能会导致中断 . )

3号意味着2号 .

至于MD5,它已被证明是有缺陷的:How to break MD5 and other hash functions .

3 years ago

但这就是彩虹表发挥作用的地方 . 基本上只是大量的值被散列,然后将结果保存到磁盘 . 然后反转位“只是”在一个非常大的表中进行查找 .

显然,这仅适用于所有可能输入值的子集,但如果您知道输入值的边界,则可以计算它 .

3 years ago

中国科学家发现了一种称为“选择前缀冲突”的方式,可以在两个不同的字符串之间产生冲突 .

这是一个例子:http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5.exe.zip
源代码:http://www.win.tue.nl/hashclash/fastcoll_v1.0.0.5_source.zip

3 years ago

正如大多数人已经说过MD5是为可变长度数据流而设计的,这些数据流被散列为固定长度的数据块,因此许多输入数据流共享单个散列 .

但是,如果您确实需要从校验和中找出原始数据,例如,如果您有密码的哈希并需要查找原始数据密码,通常谷歌(或任何你喜欢的搜索者)的答案通常更快,而不是蛮力 . 我已经使用这种方法成功找到了一些密码 .

3 years ago

根据定义Hash(加密哈希)函数:不应该是可逆的;不应该有冲突(最不可能) .

回答你的问题:这是单向哈希 . 输入(与长度无关)将产生固定大小的输出(它将基于算法(MD5的512位边界)填充) . 信息被压缩(丢失)并且实际上不可能从反向变换生成 .

关于MD5的其他信息:它容易受到冲突的影响 . 最近经历了这篇文章,http://www.win.tue.nl/hashclash/Nostradamus/

打开加密哈希实现(MD5和SHA)的源代码可以在Mozilla代码中找到 . (freebl库) .

3 years ago

现在,为所有可能的字符串预先计算MD5哈希值或任何其他哈希值,并存储以便于访问 . 虽然理论上MD5不可逆,但使用这样的数据库,您可能会发现哪个文本产生了特定的哈希值 .

例如,在http://gdataonline.com/seekhash.php尝试以下哈希代码,找出我用来计算哈希值的文本

aea23489ce3aa9b6406ebb28e0cda430

3 years ago

f(x)= 1是不可逆的 . 散列函数不是不可逆转的 .

这实际上是 required ,以便他们履行其确定某人是否拥有散列数据的未损坏副本的功能 . 这带来了对暴力攻击的敏感性,这些攻击目前非常强大,特别是对抗MD5 .

在这里和其他地方,有数学知识但很少有密文知识的人也会感到困惑 . 几个密码只是简单地用密钥流对数据进行异或,因此您可以说密文对应于该长度的所有明文,因为您可以使用任何密钥流 .

然而,这忽略了种子 password 产生的合理明文比种子 Wsg5Nm^bkI4EgxUOhpAjTmTjO0F!VkWvysS6EEMsIJiTZcvsh@WI$IH$TYqiWvK!%&Ue&nk55ak%BX%9!NnG%32ftud%YkBO$U6o 产生的更明显更可能达到任何人声称第二种可能性被嘲笑的程度 .

同样地,如果你试图在两个潜在的密码 passwordWsg5Nm^bkI4EgxUO 之间做出决定,那么就像一些数学家会让你相信的那样难 .

3 years ago

了解所有投票最多的答案意味着什么的最好方法是实际尝试恢复MD5算法 . 我记得几年前我试图恢复 MD5crypt 算法,不是为了恢复原始消息,因为它显然是不可能的,而只是生成一条消息,它会产生与原始散列相同的散列 . 至少在理论上,这将为我提供一种方法来登录到存储用户的Linux设备:使用生成的消息(密码)而不是使用原始消息(密码)在/ etc / passwd文件中使用密码 . 由于两个消息都具有相同的结果散列,因此系统会将我的密码(从原始散列生成)识别为有效 . 那根本不起作用 . 几周之后,如果我没记错的话,在最初的消息中使用 salt 会杀了我 . 我不仅要生成一个有效的初始消息,而且还要生成一个盐渍的有效初始消息,这是我永远无法做到的 . 但是我从这个实验中得到的知识很好 .

3 years ago

我喜欢各种各样的论点 . 很明显,散列值的真正 Value 在于为密码等字符串提供人类难以理解的占位符 . 它没有特定的增强安全性优势 . 假设攻击者获得了带有哈希密码的表的访问权限,他/她可以:

  • 哈希他/她自己选择的密码,如果他/她具有对表的编写/编辑权限,则将结果放在密码表中 .

  • 生成常用密码的散列值,并在密码表中测试是否存在类似的散列值 .

在这种情况下,弱密码不能仅仅通过哈希来保护 .