‘Multiple Collisions attack on MD5 and other Hashing Algorithms’

Summary

Presented below are two papers discussing a Collision attack that affects several hash algorithms, including MD5. The collision allows an attacker to change a very small amount of data in file without changing its signature. This collision attack might someday introduce a weakness in MD5 as a hashing algorithm.

The first paper by Xiaoyun Wang et al. provides the theoretical basis for the attack. The second paper by Dan Kaminsky provides a practical approach to the attack and provide some Proof of Concept code.’

Credit:

‘The papers can be found at: Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD and MD5 To Be Considered Harmful Someday


Details

Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD:
The full paper can be found at: http://eprint.iacr.org/2004/199/

Abstract:
MD5 is the hash function designed by Ron Rivest as a strengthened version of MD4 [8]. The presented attack can find many real collisions which are composed of two 1024-bit messages with the original initial value 0 IV of MD5.

HAVAL is a hashing algorithm that can compress messages of any length in 3,4 or 5 passes and produce a fingerprint of length 128, 160, 192 or 224 bits. Attack on a reduced version for HAVAL was given by P. R. Kasselman and W T Penzhorn, which consists of last rounds for HAVAL-128. The attack break the full HAVAL-128 with only about the 26 HAVAL computations. Two examples of collisions of HAVAL-128 are given in the document, where specific conditions are filled.

MD5 To Be Considered Harmful Someday:
The full paper can be found at: http://www.doxpara.com/md5_someday.pdf

Abstract:
Joux and Wang’s multi-collision attack has yielded collisions for several one-way hash algorithms. Of these, MD5 is the most problematic due to its heavy deployment, but there exists a perception that the flaws identified have no applied implications. We show that the append-ability of Merkle-Damgard allows us to add any payload to the proof-of-concept hashes released by Wang et al. We then demonstrate a tool, Stripwire, that uses this capability to create two files one which executes an arbitrary sequence of commands, the other which hides those commands with the strength of AES both with the same MD5 hash. We show how this affects file-oriented system auditors such as Tripwire, but point out that the failure is nowhere near as catastrophic as it appears at first glance. We examine how this failure affects HMAC and Digital Signatures within Digital Rights Management (DRM) systems, and how the full attack expands into an unusual pseudosteganographic strikeback methodology against peer to peer networks.

Introduction:
The modern application of cryptographic principles is actually quite primitive not in its complexity, but in the way the complexity has been managed. Independent primitives such as hashes and ciphers completely specify the behavior of a limited set of aggressively audited algorithms. Each trusted implementation is chosen to be entirely functionally equivalent to one another; choosing one over another is to have no impact on what the user (legitimate or otherwise) can do. Deviations between the chosen algorithms are limited to speed of operation, some mild key and block size constraints, and a vaguely understood security level of the underlying mathematics. It is this last fear that even after all our auditing, something will still get through that drives adherence to the primitive specification. If everything implements the same specification, we can swap out a broken implementation for a correct one. But just because we can do something doesn’t mean we will. Joux and Wang have made it plainly clear that MD5 has serious problems. This shouldn’t come as much surprise; Dobbertin’s work almost a decade ago made it clear that this was coming. Yet even now there are those who have hinted that there isn’t any applied risk and that the vulnerabilities are purely theoretical. Outside of FIPS s unwillingness to certify MD5 there is no apparent push to migrate away from MD5 as we once did for its predecessor, MD4.

The attacks discovered are indeed obscure. But completely theoretical? No. Even given what little data has been released code implementing the attack isn’t even public yet sufficient information has been released to piece together a rudimentary proof of concept tool that demonstrates, at minimum, that the selection of MD5 exposes new and potentially deeply undesirable functionality above and beyond what the one-way hash primitive specifies.

The tool, Stripwire, implements some of the attacks described herein. That being said, this paper is not a smoking gun indictment of MD5. The author taken great pains to include the caveats of each vulnerability, as it is far too easy to overestimate the risks described in this paper. It is for that reason I am not saying today , or any day now . The title states someday for a reason. There are dots going back ten years as to the risk of MD5. Here are a few more, in the hopes that they will start to be connected.’

Categories: Reviews