MD5 - Not as safe as once believed

[thehorse13]

There is an interesting paper on altering files without changing the MD5 hash. Even more interesting, a tool that can be used for POC.

This information was passed to me through a mailing list and I think that it is an interesting read. Many of us here should pay attention to this paper and as a side note, I am glad to see that others in the security field feel the same way that I do about MD5.

*Snip*

The full details may be acquired at the following link:

http://www.doxpara.com/md5_someday.pdf

A tool, Stripwire, has been assembled to demonstrate some of the attacks
described in the paper. It may be acquired at the following address:

http://www.doxpara.com/stripwire-1.1.tar.gz

Incidentally, the expectations management is by no means accidental --
the paper's titled "MD5 To Be Considered Harmful Someday" for a reason.
Some people have said there's no applied implications to Joux and Wang's
research. They're wrong; arbitrary payloads can be successfully
integrated into a hash collision. But the attacks are not wildly
practical, and in most cases exposure remains thankfully limited, for
now. But the risks are real enough that responsible engineers should
take note: This is not merely an academic threat, systems designed with
MD5 now need to take far more care than they would if they were
employing an unbroken hashing algorithm, and the problems are only going
to get worse.

Some highlights from the paper:

* The attack itself is pretty limited -- essentially, we can create
"doppelganger" blocks (my term) anywhere inside a file that may be
swapped out, one for another, without altering the final MD5 hash. This
lets us create any number of binary-inequal files with the same md5sum.

* MD5 uses an appendable cascade construction -- in other words, if you
happen to find yourself with two files that MD5 to the same hash, an
arbitrary payload can be applied to both files and they'll still have
the same hash. This leads to...

* Attacks are possible using only the proof of concept test vectors
released by Wang -- the actual attack is not necessary.

* Stripwire emits two binary packages. They both contain an arbitrary
payload, but the payload is encrypted with AES. Only one of the
packages ("Fire") is decryptable and thus dangerous; the other ("Ice")
shields its data behind AES. Both files share the same MD5 hash.

* Digital Signature systems are vulnerable, as they almost always sign a
hashed representation of data rather than the data itself.

* This is an excellent vector for malicious developers to get unsafe
code past a group of auditors, perhaps to acquire a required third party
signature. Alternatively, build tools themselves could be compromised
to embed safe versions of dangerous payloads in each build. At some
later point, the embedded payload could be safely "activated", without
the MD5 changing. This has implications for Tripwire, DRM, and several
package management architectures.

* HMAC's invulnerability has been slightly overstated. It's definitely
possible, given the key, to create two datasets with the same HMAC.
Attacker possession of the key violates MAC presumptions, so the impact
of this is particularly questionable.

* Very interesting possibilities open up once the full attack is made
available -- among other things, we can create self-decrypting
executables (fire.exe and ice.exe) that exhibit differential behavior
based on their internal colliding payloads. They'll still have the same
MD5 hash.

* Several doppelgangers may (relatively quickly, as per Joux) be
computed within a single multicollision-friendly block. As such, the
particular selection of doppelganger sets within a file can itself be
made to represent data. It's relatively straightforward to embed a 128
bit signature inside an arbitrary file, in such a way that no matter the
value of the signature, a constant MD5 hash is maintained. This is
curiously steganographic.

* Many popular P2P networks (and innumerable distributed content
databases) use MD5 hashes as both a reliable search handle and a
mechanism to ensure file integrity. This makes them blind to any
signature embedded within MD5 collisions. We can use this blindness to
track MP3 audio data as it propagates from a custom P2P node.
"Strikeback" capacity against executable trafficking is even more
pronounced -- it's possible to create application installers that
self-modify with host identifying characteristics but still successfully
retransmit on P2P networks under the global search hash.

[gore]

Another reason why Blowfish is better at everything

[thehorse13]

This paper pretty much sums up why we don't use tripwire at our shop. I pissed and moaned about it and eventually got my way when I asked who would assume responsibility when I prove that I can indeed modify filez and keep the MD5 hash the same.

[Striek]

We discussed this with a professor of mine. It was the first thing he told us when we came back to school in September - "MD5 has been cracked."

For some reason though, he still insists on MD5 sums for all evidence we collect during investigations, and hasn't covered any methods on migrating to a more secure hash algorithm. I have migrated all my tools to use the SHA1 checksum, mostly because it's also a part of the coreutils package and is *almost* as universally available and recognizeable as MD5. I stopped using MD5 in September.

It would be quite interesting to demonstrate realistically how this new technique could be used. I'm going to have to try it once I'm done this semester.

My advice for everyone is to just use SHA1; it's as readily available as MD5, and hasn't been cracked yet,

Can't Tripwire be set up with a different hashing algorithm? I moved my Aide to SHA1 in October.

[Soda_Popinsky]

Originally posted here by thehorse13
This paper pretty much sums up why we don't use tripwire at our shop. I pissed and moaned about it and eventually got my way when I asked who would assume responsibility when I prove that I can indeed modify filez and keep the MD5 hash the same.

Then what was your alternative to tripwire / MD5?

I am glad to see that others in the security field feel the same way that I do about MD5.

What was your beef with MD5 to begin with?

[thehorse13]

We do have a solution that is similar to tripwire/MD5. However, the details cannot be posted in public.

My beef with MD5 has always been the same. The hash cannot guarantee integrity. The paper I have attached provides a POC very similar to the internal POC done here almost 6 months ago. Because of the huge amount of policy and red tape in place here, anything that introduces a hole in an otherwise air tight case is a baaaaaad thing.

[gore]

Originally posted here by thehorse13
We do have a solution that is similar to tripwire/MD5. However, the details cannot be posted in public.

DUN DUN DUN DUN DUN DUN DUN DUN DUN DUN DUN DUN DO DO DO, DO DO DO,

007, Horsey, The Horsey.

LOL

OK I'm done. lol

Anyway, depending on the box, I suually use Blowfish, but I really like SUSE Linux as it comes with Encryption which allows 4096 bit, and that is on this box, which is used for an FTP server.

Guess Quantum encryption is the next step huh

One time keypads would work well, and are almost un-crackable when used properly, but who uses them properly? Remember the Russians? "Well hey since keys are hard to come by why not everyone use the SAME key??? As long as the same one gets used only once per office it should be OK right?"

Obviously not, lol.

I should come up with my own encryption standard. Gore138 or something. Un-crackable because whenever a crack is attempted it auto self destructs and takes the machine with it lol. Buahahaha.


I'm sure 4096 bit has been cracked by someone and that there is something higher, but really, is my cooking recipe THAT important? Maybe if I owned Kraft a recipe would need it.

[phishphreek]

Originally posted here by gore

I'm sure 4096 bit has been cracked by someone and that there is something higher, but really, is my cooking recipe THAT important? Maybe if I owned Kraft a recipe would need it.

Thats silly... Kraft puts their recipes on the back of the box!
Or, you can just get it from their site...

http://www.kraftfoods.com/kf/

Duh!

[thehorse13]

Seriously though. MD5 collisions are pretty scary (limited output yet infinite input). To better understand my issue, let's say that you have some PWs that are hashed and you are able to mod a PW to match the original MD5 hash, the new PW you set will work so you no longer have to brute force or crack PWs that are MD5 hashed. This is only one example of collisions (other algorythms have the same issue) but think of what will happen when exploits/softwarez come out that allow for quick controlled collisions. Time to look into other algos as Striek suggests.

For those who scoff at such notions, keep in mind what platforms use this exact model for passwords. Our good friends at Cisco and just about every *nix OS on the planet.

[Striek]

the new PW you set will work so you no longer have to brute force or crack PWs that are MD5 hashed

The scary part is that you wouldn't need to set a new password. Two (or as many as you can find) password will soon be able to open the same account. It's only a matter of time now, and that time seems a lot shorter than it did 6 months ago.

SHA1 can't be too far off either. It's time to include stronger algorithms for general distribution.