与此处最受赞成的答案所强调的相反,由大(可能无限)输入大小和固定输出大小之间的差异引起的密码散列函数的非注入性(即有几个字符串散列到相同的值)不是重要的一点——实际上,我们更喜欢那些冲突尽可能少发生的哈希函数。
考虑这个函数(在 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 也不应该出现这种情况。
加密哈希函数的重要假设是:
- 很难找到任何产生给定哈希的字符串(原像电阻)
- 很难找到任何不同的字符串产生与给定字符串相同的哈希(第二原像电阻)
- 很难找到任何一对具有相同哈希的字符串(抗碰撞)
显然我的simple_hash
功能不满足这些条件。(实际上,如果我们将输入空间限制为“16 字节字符串”,那么我的函数就会变成单射的,因此甚至可以证明是抗第二原像和抗碰撞的。)
现在存在针对 MD5 的冲突攻击(例如,可以产生一对字符串,即使具有给定的相同前缀,具有相同的散列,有相当多的工作,但并非不可能做很多工作),所以你不应该使用MD5 对于任何关键的东西。目前还没有原像攻击,但攻击会变得更好。
要回答实际问题:
这些函数是什么使生成的字符串无法回溯?
MD5(以及其他基于 Merkle-Damgard 结构的散列函数)有效地做的是应用加密算法,将消息作为密钥,将某个固定值作为“纯文本”,使用生成的密文作为散列。(在此之前,输入被填充并分割成块,每个块用于加密前一个块的输出,与输入进行异或以防止反向计算。)
现代加密算法(包括散列函数中使用的算法)的制作方式使得很难恢复密钥,即使在明文和密文(甚至当对手选择其中之一时)也是如此。他们通常通过执行大量位混洗操作来做到这一点,每个输出位由每个关键位(几次)以及每个输入位确定。这样,如果您知道完整的密钥以及输入或输出,您就可以轻松地追溯内部发生的事情。
对于类似 MD5 的散列函数和原像攻击(使用单块散列字符串,以使事情更容易),您只有加密函数的输入和输出,但没有密钥(这就是您要寻找的)。