可以多快找到MD5碰撞 [英] How fast can a MD5 collision be found

问题描述

如果我有16字节和16字节数据的盐，有多快可以找到另外16字节的数据，以便MD5（盐+数据）== MD5（盐+其他数据）？



我不希望答案准确到纳秒，只是估计几秒钟，几个小时，几个文明。

If I have a salt of 16bytes and 16bytes of data, how fast can one find another 16bytes of data so that MD5(salt + data) == MD5(salt + other data)?

I don't expect an answer accurate to the nanosecond, just an estimation like "a few seconds", "a few hours", "a few civilizations".

推荐答案

正如Sergay所说，这取决于你的系统和代码。例如，我有Ronald Rivest的代码，用直写C编写，在X纳秒内散列1个块。由于我没有做任何基准测试，我无法告诉你X的价值。我使用Microsoft Visual C ++ 6.0将其编译成我每天使用的DLL，并且它针对标准C运行时的多线程DLL实现运行图书馆。如果我针对静态多线程CRT进行编译，我期望获得稍微不同（可能更好）的时间，如果我针对静态链接的单线程CRT（LIBC.LIB）进行编译，那么时间肯定会（略微）更好。如果我使用GCC编译器来编译和链接相同的代码，我可能得到可测量的不同结果。



以上仅涵盖了相同源代码的潜在变异来源，用相同的编程语言编写。如果你在C编程语言中包含MD5算法的其他实现，或者完全改变编程语言，它会变得更加混乱。例如，我希望相同算法的Visual Basic实现运行得更慢，即使它忠实于Rivest博士的算法。对于C＃，JavaScript或其他已实现MD5算法的语言的端口也是如此。



样本大小为16字节这很不切实际。真实世界的明文更像数千甚至数百万字节，例如邮件正文或可执行代码和程序文件的静态数据。



另一个考虑因素是样本大小对结果哈希的内容几乎没有影响，因为MD5哈希总是长128位（32字节）。



此外，如果你将测试用例限制在16字节的明文中，那么很容易计算出只有128种可能的组合（每字节8位乘以16字节）。

As Sergay said, it depends on your system and code. For instance, I have Ronald Rivest's code, written in straight C, that hashes 1 block in X nanoseconds. Since I haven't done any benchmarks, I can't tell you the value of X. I used Microsoft Visual C++ 6.0 to compile it into the DLL that I use daily, and it runs against the multithreaded DLL implementation of the Standard C runtime library. I would expect to get marginally different (probably better) times if I compiled against the static multithreaded CRT, and the times would certainly be (slightly) better if I compiled against the statically linked single threaded CRT (LIBC.LIB). I might get measurably different results if I used the GCC compiler to compile and link the same code.

The above only covers the potential sources of variation given the same source code, written in the same programming language. It gets even more muddy if you include other implementations of the MD5 algorithm, either in the C programming language, or change the programming language entirely. For example, I would expect a Visual Basic implementation of the same algorithm to run more slowly, even if it was faithful to Dr. Rivest's algorithm. The same would be true of a port to C#, JavaScript, or any number of other languages in which the MD5 algorithm has been implemented.

A sample size of 16 bytes is pretty unrealistic. Real world plaintext is more like thousands, or even millions, of bytes, such as the body of a mail message or the executable code and static data of a program file.

Another consideration is that sample size has little bearing on the content of the resultant hash, since the MD5 hash is always 128 bits (32 bytes) long.

Moreover, if you confine your test cases to plaintexts of 16 bytes, it's fairly easy to work out that there are only 128 possible combinations (8 bits per byte times 16 bytes).

答案：非常慢因为它不只是发现碰撞而是使用原像。

Answer : very slowly as it's not just about finding collision but working with preimage.

这篇关于可以多快找到MD5碰撞的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！