在MD5转换中是否存在一个固定点，即是否存在x使得md5(x) == x？
7个回答
143
由于MD5校验和是128位长，因此任何固定点也必须是128位长。假设任何字符串的MD5校验和在所有可能的校验和中均匀分布，则任何给定的128位字符串是一个固定点的概率为1/2128。
因此，没有128位字符串是固定点的概率是(1 - 1/2128)2128，因此存在固定点的概率为1 - (1 - 1/2128)2128。
由于当n趋近于无穷大时(1 - 1/n)n的极限为1/e，而2128显然是一个非常大的数字，因此这个概率几乎等于1 - 1/e ≈ 63.21%。
当然，实际上并没有涉及到随机性-要么有一个固定点，要么没有。但是，我们可以63.21%地确信存在一个固定点。(此外，请注意，这个数字不取决于键空间的大小-如果MD5校验和是32位或1024位，答案将是相同的，只要它大于约4或5位)。
- Adam Rosenfield
5
11你能否做出这样的假设：任意字符串的 MD5 哈希值在所有可能的哈希值中均匀分布？ - Ori Pessach
13是的。大数和模数形成了一个粗略的随机分布。如果不是这样，就会产生不断的碰撞。MD5算法的特性强制其输出随机分布。 - Stefan Kendall
2我以你的答案为基础，写了这个答案：http://security.stackexchange.com/questions/3851/can-a-file-contain-its-md5sum-inside-it/5609#5609 - CesarB
1这里，给你一个金徽章。 - Dennis
除了 md5 是确定性的，而不是随机的。 - PyRulez
16
我的暴力尝试找到了12个前缀和12个后缀匹配。
前缀12： 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762
后缀12： df12c1434cec7850a7900ce027af4b78 -> b2f6053087022898fe920ce027af4b78
博客文章: https://plus.google.com/103541237243849171137/posts/SRxXrTMdrFN
- Thomas Egense
5
1链接无法使用。Google Plus已于四月关闭。 - Typewar
抱歉...我没有保存博客文章，而且我的Google+备份也无法工作。但这是我的Github项目：https://github.com/thomasegense/MD5FixPointSearch - Thomas Egense
你确定这个前缀是正确的吗：12: 54db1011d76dc70a0a9df3ff3e0b390f -> 54db1011d76d137956603122ad86d762？
我使用了
md5sum Linux 命令，但得到了不同的结果。 - ThunderPhoenix不确定你是否正确使用了md5sum。您也可以在此在线确认：http://onlinemd5.com/ - Thomas Egense
3请确保输入字符串没有尾随换行符："echo -n"54db1011d76dc70a0a9df3ff3e0b390f" | md5sum" - Laszlo Treszkai
11
由于哈希是不可逆的，要破解它将会非常困难。唯一的方法是计算哈希函数在每一个可能的输出值上的结果，并查看是否与给定的哈希值匹配。
具体来说，MD5哈希值由16个字节组成，这意味着有2^(16*8) = 3.4 * 10 ^ 38 种组合方式。如果在16字节值上计算哈希值需要1毫秒，那么需要10790283070806014188970529154.99年才能计算出所有这些哈希值。
- Kibbee
5
2如果你必须尝试每一个，那么这是正确的。但是，你只需要尝试每个可能的输入来验证是否存在固定点。如果存在固定点（Adam Rosenfield的答案表明可能存在），那么只需要一个幸运的猜测就足够了。 - Naaff
该函数是不可逆的，这意味着它没有数学上的反函数，但这仅意味着对于给定的输出可能有多个输入。一般来说，对于给定的输出，输入空间将是无限的，但如果您知道它起始为128位值，则可以缩小可能性。如果您不将该函数视为黑盒子，而是阅读规范并应用一些数学思维，那么就有“倒推”的机会。 - rndmcnlly
2@Naaff: “只需尝试每个可能的输入”-这比尝试每个哈希更容易，为什么？恰恰相反，因为几个可能的输入可能哈希到相同的输出。 - Piskvor left the building
1@Piskvor：你误解了Naaff的意思（我也花了一分钟才明白）。更清晰的表达方式应该是“只有在没有固定点的情况下，你才需要尝试每个可能的输入（来自2^128空间）”。换句话说，只有在之前的尝试都失败了，你才需要尝试每一个可能性。所以需要1.08e28年，或者一个幸运的猜测！ - P Daddy
1如果计算哈希值需要1毫秒。现代GPU可以每秒计算数十亿个哈希值，比这快得多。但是，仍然需要很长时间。 - markasoftware
1
虽然我没有一个肯定的答案，但我的猜测是“是”，而且可能有2^32个这样的固定点（对于位串解释，而不是字符串解释）。我正在积极地研究这个问题，因为它似乎是一个很棒、简洁的难题，需要很多创造力（如果你不想马上采用暴力搜索的话）。
我的方法是：把它当作一个数学问题。我们有128个布尔变量和128个方程式，描述输出与输入（应该匹配）之间的关系。通过插入算法和填充位表中的所有常量，我的希望是这些方程可以被大大简化，从而得到一个针对128位输入情况优化的算法。这些简化后的方程可以在一些好的语言中编程以进行高效的搜索，或者再次抽象处理，逐位分配，注意矛盾。你只需要看到几位输出就知道它不匹配输入了！
- rndmcnlly
1
1这真的很有趣，请在您走下这条路时分享您的进展？ - user230910
-1
可能是可以找到的，但需要的时间比我们现在有的时间长，或者需要妥协MD5。
- Glomek
3
7它还没有被破解。他们只能在合理的时间内生成两个等于相同哈希值的字符串。要生成一个与特定哈希值相等的字符串仍然非常困难。 - Kibbee
9不确定如何寻找一个MD5会妥协其安全性，就像如果我告诉你MD5（“The quick brown fox jumps over the lazy dog”）= 9e107d9d372bb6826bd81d3542a419d6也不会妥协该算法一样。 - Kip
5固定点可能会在数学上提供一些杠杆作用，从而导致对MD5更全面的违规行为。我不确定 Glomek 能否真正证明“可能性”，我会毫不含糊地接受“可能性”。 - Jonathan Leffler
-8
有两种解释方式，如果可以选择其中任意一种，则找到固定点的概率增加至81.5％。
- 解释1：MD5输出的MD5值是否与其输入的二进制匹配？
- 解释2：MD5输出的MD5值是否与其输入的十六进制匹配？
- Joshua
5
13MD5算法本身与十六进制无关，它操作的是字节并生成字节，因此我认为后一种解释是无效的。 - Nick Johnson
无论在解释1下是否存在固定点，仍可能（或不可能）在解释2下存在。然而，如果您有兴趣探索这个问题，解释1似乎是一个更好的起点，因为您不必对大小写和字符编码做出各种任意决定。此外，二进制情况具有较少的位数！ - rndmcnlly
5你对十六进制的真正含义存在误解。你可以用十六进制表示二进制，就像你可以用十进制、八进制或三进制表示一样。它是一个数字，并且有不同的表现形式。所以，解释1和2是同样的事情。你考虑的是字符串表示，但这根本不是相同的十六进制，而是完全不同的二进制值。事实上，你可以在不同的字符集中有许多不同的十六进制字符串。128位哈希值可以表示为“hex”字符串，但它并不等于该字符串。该字符串不是相同的二进制数据。 - defines
达斯汀，解释2确实意味着显示字符串的MD5。 - Joshua
5然而，这个想法存在一个严重问题，即它直接依赖于您的字符编码。不同的编码方案将导致完全不同的结果集。甚至有一个整个项目和一篇文章基于对MD5操作方式的误解来揭穿这个想法。http://acodingfool.typepad.com/blog/2009/05/the-kembler-identity.html - defines
-23
严格来说，由于MD5的输入长度为512位，输出长度为128位，按定义来说这是不可能的。
- Ori Pessach
6
4不，1个字节字符串的MD5存在。 - Joshua
8输入可以是任何大小。如果输入少于512个字节，则进行填充，但较小的输入仍然可接受。根据维基百科的描述：“MD5将可变长度的消息处理成为128位固定长度的输出。输入消息被分成512位块（16个32位小端整数）；消息被填充以使其长度可被512整除。” - Naaff
那么你是假设，比如说，0000000001 = 1？我认为这个问题最多只能说是规定不清。 - Ori Pessach
11MD5的输入可以是128位。如果MD5想要对这个输入进行填充，那么这是MD5的事情。输入仍然被定义清楚。同样地，输出是一个明确定义的128位。如果（明确定义的）输入和（明确定义的）输出都相同，则MD5（x）= x。 - Naaff
但是在转换本身的上下文中，填充并没有被很好地定义。谁说你不能用全1或随机选择的重复位模式进行填充呢？嗯，RFC这么说，但只是在将函数从512位数字扩展到128位数字以生成任意长（或短）输入的128位数字的情况下。它只是进一步说明了问题规范性的差异。 - Ori Pessach
2@Joshua，一个空字符串（即0字节）的MD5是否存在？ - Kip
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
md5(x) == x，因为md5(x)本身就是128位长。因此，如果在128位域上的md5算法中存在一个固定点，那么无论输入大小如何，都会在md5中存在一个固定点。 - the paul1-(1/e)*(1/e) ≈ 86.47%。 - Dušan