11
$\begingroup$

I fully realize that MD5 should not be used in any new project, but in my particular situation I have severe CPU performance issues, so MD5 is convenient. I have read a lot about MD5 security for this project, and I know it is broken in several ways: extending a file while having the same MD5 hash, and generating two different files with the same MD5 hash, for instance.

In my particular instance, I have a Merkle tree. The root is validated with SHA256, but for performance reasons the internal nodes use MD5. The key point is that in my application the MD5 hashing is done over fixed length blocks. For instance, leaf nodes are MD5 over a 4096 bytes block. Internal nodes are MD5 over a 16384 bytes block.

So, my question is: Given a known block and its MD5 hash, is there an attack to generate a different block of the same length with the same MD5 hash?

I don't want to generate two 4096 bytes blocks with the same hash. I want to know if, when given a 4096 bytes block, can one replace it with a different 4096 bytes block with the same MD5.

Improve this question
$\endgroup$
8
  • $\begingroup$ I think that the questions is clear enough: can I generate a 4096 bytes block, given a know 4096 bytes block and its MD5 hash, that has the same MD5 hash? :) $\endgroup$
    – jcea
    Commented Feb 3, 2014 at 16:53
  • $\begingroup$ On '09, the best answer to a question regarding MD5 pre-image resistance was that it is not considered safe to use MD5 for such use. Collision resistance is worse. If you merely want a good non-cryptographic hash with convenient 128-bit digest size, MD5 may meet your needs. $\endgroup$
    – user4982
    Commented Feb 3, 2014 at 17:16
  • $\begingroup$ I need crypto strength. Being able to forge a 4096 bytes block with given MD5 would be catastrophic. $\endgroup$
    – jcea
    Commented Feb 3, 2014 at 17:47
  • 1
    $\begingroup$ If performance is a concern, why not use blake2b? It's faster than MD5, and even natively supports tree hashing. $\endgroup$
    – Stephen Touset
    Commented Feb 4, 2014 at 0:52
  • 1
    $\begingroup$ The source code for blake2b is short, freely available, and easily embedded in any project. $\endgroup$
    – Stephen Touset
    Commented Feb 4, 2014 at 16:17

1 Answer 1

Reset to default
18
$\begingroup$

Right now, the best published attack against MD5's preimage resistance (first preimage, actually, but it applies to second preimage resistance as well) finds preimages in cost $2^{123.4}$ average cost, which is slightly better than the generic attack (average cost of $2^{128}$), but still way beyond the technologically feasible. The attack rebuilds the preimage as a two-block value (128 bytes) and can be adjusted to any larger length.

Therefore:

  • There is no practical attack against your 4096-byte hash tree nodes yet.
  • But the fact that they have a fixed 4096-byte length does not appear to improve the situation.

Still, the foundation of the security of MD5 appears somewhat flimsy, so it is not recommended (at all) for new systems. If you have severe CPU constraints, then you might want to consider the SHA-3 candidates. The 14 "round 2" candidate functions have been quite thoroughly investigated, and no break has been found in any of them; in that respect, they are all stronger than MD5, and arguably stronger than SHA-1, which has a known collision attack (but no known preimage attack). Some of them are quite fast, and competitive with MD5. Depending on your architecture (8-bit CPU, small 32-bit ARM, big modern 64-bit PC with AES-NI opcodes...), you would be most interested in BMW, ECHO, Shabal and Skein. "The" SHA-3 (Keccak) is not as fast as these (except on dedicated FPGA / ASIC).

It is usually best, for public relations, if you use a standard, recommended function. However, if you decide otherwise, using a function which has survived some scrutiny by cryptographers with no known weakness is arguably better than using a function with big weaknesses.

Improve this answer
$\endgroup$
11
  • $\begingroup$ As I commented above, I would explicitly mention blake2b as a solid choice. It was a SHA-3 finalist, IIRC was the fastest amongst them, and natively supports a tree hashing mode. $\endgroup$
    – Stephen Touset
    Commented Feb 4, 2014 at 0:55
  • 1
    $\begingroup$ Actually BLAKE was the SHA-3 finalist; BLAKE2 (both 'b' and 's' variants) are an ulterior proposal. But yes, this is a valid idea, on the basis that "it cannot be worse than MD5 for security". $\endgroup$
    – Thomas Pornin
    Commented Feb 4, 2014 at 1:04
  • 1
    $\begingroup$ This project will be deployed on low power ARMv6 with no SIMD extensions. So the consensus so far is to use any fast SHA-3 finalist instead of MD5, even if currently there is no practical second preimage attack on standard MD5. I will think about it. Implications are profound: need to deploy extra libraries, validation, policy against "unknown algorithms", performance, and future maintenance... Thanks for the suggestions. Will keep the question open for a few days, just in case. Still open to new info/suggestions/advices. $\endgroup$
    – jcea
    Commented Feb 4, 2014 at 1:25
  • $\begingroup$ @jcea: On ARMv6, BLAKE2s is likely much faster than BLAKE2b. If you want to use something that is famous then even SHA-1 would be better pick (in security sense) than MD5? However, in new systems (standard compliance) I would go with SHA-2/Keccak, or (speed) BALKE2s or one of options mentioned by T. Pornin. $\endgroup$
    – user4982
    Commented Feb 4, 2014 at 15:02
  • 1
    $\begingroup$ On a 32-bit ARMv6 without SIMD extensions, the fastest of the 14 "round 2" SHA-3 candidates would be Shabal, as seen in this report (disclaimer: I wrote that report, and I one of the inventors of Shabal; however, Shabal was designed to be fast on small 32-bit CPU, and it shows). Though Shabal is faster than the "finalist BLAKE", a later derivative like BLAKE2 should be competitive. As for all performance matters, this should be measured rather than speculated on. $\endgroup$
    – Thomas Pornin
    Commented Feb 4, 2014 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.