暴力破解嵌入式 MD5sum 的时间复杂度
我长期以来一直想回答的一个问题 - 查找包含静态嵌入的相同 MD5（例如作为字符串）的已编译二进制文件的 MD5sum 的时间复杂度是多少？
编辑：如果这还不清楚。我正在寻找具有时间复杂度的答案及其解释。
A question I've been meaning to have answered for a long time - What would be the time complexity of finding an MD5sum of a compiled binary that contains that same MD5 statically embedded in it, say, as a string?
Edit: If this wasn't already clear. I am looking for an answer with the time complexity and an explanation of it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
这可以在常数时间内解决。
包含所有可能的 MD5 摘要的文件包含该文件的摘要。
This can be solved in constant time.
The file that contains all possible MD5 digests contains the digest of that file.
与暴力破解几乎相同：计算 md5sum 很简单，但制作一个文件来匹配已知的 md5sum 却很困难。
在最好的情况下，您正在寻找一个原像，该原像将为您提供已知的哈希值（可能通过将数据添加到二进制文件中）。
Pretty much the same as brute force: computing a md5sum is trivial, but making a file to match a known md5sum is hard.
You are, in the best case, looking for a preimage that will give you a known hash (possibly by adding data into the binary).
这确实很难，因为 MD5 具有良好的分布。暴力破解的最佳选择是向文件添加一些哈希值，并将无意义的数据附加到二进制文件的末尾，直到二进制文件具有与嵌入的哈希值相同的哈希值。
另一方面，如果您想检查您的二进制文件是否完整且未经修改，您最好将二进制文件分为 3 部分：哈希值之前的二进制文件部分、哈希值本身和哈希值之后的部分。连接第一部分和最后一部分，计算 md5 哈希并将其嵌入到二进制文件中。
像这样（示例）：
It is really hard since MD5 has a good distribution. Your best bet by bruteforcing is adding some hash to your file and appending meaningless data to the end of the binary until the binary has the same hash as the one embedded.
On the other hand if you want to check whether your binary is intact and unmodified you'd be better off by splitting your binary in 3 parts: The part of the binary before the hash, the hash itself and the part after the hash. Concatenate the first and the last part, compute the md5 hash and embed it into the binary.
Like this (example):
你想要做的事情需要哈希算法存在缺陷。事实上，MD5 不是很安全，所以这可能是可能的。但我不认为任何已知的弱点可以帮助你完成你想做的事情。即使原像攻击也无济于事，它需要是“选择的前缀原像攻击”。
所以我想（今天）唯一可行的方法是使用暴力。
如果您正在寻找一种为二进制文件“添加安全性”的方法，请截断哈希值，然后使用暴力破解。
What you want to do would require a flaw in the hash algorithm. And in fact, MD5 isn't very secure, so it might be possible. But I don't see how any of the known weaknesses could help in what you want to do. Even a preimage attack wouldn't help, it would need to be a 'chosen prefix preimage attack'.
So I guess the only feasible way (today) would be to use brute force.
If you are looking a way to 'add security' to a binary, truncate the hash, and then use brute force.
这也要看具体情况。如果给出了二进制文件，并且只需要在某个地方插入 md5，则答案可以是：0。因为有可能（并且我假设在几乎所有这样的情况下）没有插入的 md5产生相同的 md5。
如果您有可能修改更多的二进制文件（例如，通过可以用任意数字填充的填充空间），唯一可行的方法是暴力破解。
That also depends on the circumstands. If the binary is given, and just the md5 must be inserted at some place, the answer can be: 0. Because it may be possible (and I would assume it maybe in almost all cases like this) that there is no md5 which inserted yields the same md5.
In case you have the possibility to modify more of the binary (e.g. by having padding space which you can fill with arbitrary numbers), the only feasible approach is brute force.
为了实现这一点，您必须找到碰撞。这可以使用针对 md5 的前缀攻击来完成。请记住，这是可能的，因为 md5 非常损坏。此攻击的时间复杂度为 2^24.1，现代桌面可以承受。
In order to accomplish this you must find a collision. This can be done using the prefixing attack against md5. Keep in mind this is only possible because md5 is very broken. This attack has a time complexity of 2^24.1, which is within reach of a modern desktop.