Practical Exploits of Broken MD5 Algorithm

jose parinas writes "A practical sample of an MD5 exploit can be found, with source code included,in codeproject, a site for .Net programmers. The intent of the demos is to demonstrate a very specific type of attack that exploits the inherent trust of an MD5 hash. It's sort of a semi-social engineering attack. At Microsoft, the MD5 hash functions are banned. The main problem is that the attack is directed to the distribution of software process, as you can understand reading the paper, Considered Harmful Someday. Some open source programs, like RPM, use MD5, and in many open source distributions MD5 is used as check sum."

Comments

Checksums are always going to be vulnerable

[LiquidCoooled]

If you contract your file from x bytes down to a fixed size, no matter what algorithm you use, you will always have collisions.

Unless you start to give your hash keys as the same size as the original file, there is not anything that can be done about it, ever.

Re:Checksums are always going to be vulnerable

[Ckwop]

If you contract your file from x bytes down to a fixed size, no matter what algorithm you use, you will always have collisions. Unless you start to give your hash keys as the same size as the original file, there is not anything that can be done about it, ever.

While this technical correct it is slightly misleading. The aim of a hash function is to make it has hard as possible to find a collision. For an n-bit has it takes roughly 2^(n/2) operations to find a collision. Any attack faster than this is considered a break of the hash function. It typically takes less than five minutes to break MD5 so it is horribly broken.

While removing the possibility of collision all together is provably impossible you can design a hash function for which finding a collision is computationally infeasible. The standard size to achieve this today is 256-bits and the better designed functions like Whirlpool use this hash length.

Simon

Re:Checksums are always going to be vulnerable

[Anonymous Coward]

This completely misses the point of cryptographic hashes.

The point is that it is supposed to be difficult to find another data set which hashes to the same value without doing a brute-force search. Of course you will get collisions, but the changes are (supposed to be) 1 in 2^80 with MD5 or 1 in 2^128 with SHA-1.

The exploits mentioned above are that the algorithms (MD5 and to some extent SHA-1) have been broken to allow you to construct a piece of data which hashes to the same value as the original. This is VERY different from the fact that you get collisions.

Re:Checksums are always going to be vulnerable

[LentoMan]

Use of two or more different checksums algorithms would make it substantially harder to create a file with a fake hash.

Re:Checksums are always going to be vulnerable

[ceeam]

(sigh) Insightful, my ass... Checksums are NOT reversible. The main trick here is to replace one file with another and leave the hash/checksum the same by patching the fake file. (For practically every file format there exists a spare space where this patching could be done.)

Re:Checksums are always going to be vulnerable

[gowen]

It typically takes less than five minutes to break MD5 so it is horribly broken.

But all that enables you to do is replace an MD5'd file with garbage that happens to have the same MD5 sum. It's hard to deliver a payload when you're limited to tricking a target into downloading what would be (essentially) a random string of ones and zeroes.

Re:Checksums are always going to be vulnerable

[Ckwop]

But all that enables you to do is replace an MD5'd file with garbage that happens to have the same MD5 sum. It's hard to deliver a payload when you're limited to tricking a target into downloading what would be (essentially) a random string of ones and zeroes.

At Toorcon this year, Dan Kaminsky showed how to generate two valid, nicely rendered, html files with the same hash . Basically, he injects javascript into the page to remove the rubbish at the begining of the file. But how often to do you view the source of a page you're visiting. It'd be hard for a layperson to notice this. Make no mistake about it, the collision attack is very dangerous.

Simon

Re:Checksums are always going to be vulnerable

[m50d]

No, it wouldn't, *sigh*. Stop posting this, I'm tired of correcting it.

As another reply said, however, doubling the bit count would improve security. But, a simple double-MD5 would have exactly the same problems. Therefore, the solution is to use a longer and more secure hash, like, for example, SHA-256.

Re:Checksums are always going to be vulnerable

[MaGogue]

You almost got it right. The reverse problem of a checksum is to produce the original file that will give the checksum.

Actually, the functions are called hash functions, and they can be written as:
H(file) = h
H() is the hash function, h is the hash value (checksum) the reverse would be RH()
RH(h) = file
Now we can of course prove that reverse is not a unique function, since any fixed-length h has a limited number of possible values, whereas file can be of any length.
Therefore, reverse has many possible solutions, and in a simple case like the real checksum of bits (having two values 1 and 0) has a simple reverse algorithm, too. Given the value of h, produce the file == easy.
Complex hash functions like MD5 have the interesting property of difficulty of reversion : it is difficult to even produce any file that will compute to any given MD5 value, hence it is difficult to fake it.
It has been known all along that reverse is possible, and has many solutions, but it was thought they are too difficult to find. Now it has turned out that some can be, and were, found.

Re:Checksums are always going to be vulnerable

[Pieroxy]

It doesn't seem to make it any easier to take an arbitrary original and just magic up another file which has the same hash.

Yes it does.

Re:Checksums are always going to be vulnerable

[ocelotbob]

I think you're missing what the OP is saying here. The OP is suggesting to use something like MD5+SHA1, algorithms with different techniques for generating hashes so that you decrease the probability of creating a collision that works for both, not using something like double MD5

Re:Checksums are always going to be vulnerable

[Anonymous Coward]

No, it doesn't.

You linked an example which takes a document A, and produces two documents A1 and A2 where

A1 looks like A, but A2 does not look like A
and MD5(A1) = MD5(A2)

BUT, critically, MD5(A1) is not MD5(A)

So neither of the documents created is an imposter. Arbitrary payloads are still protected by MD5. If you don't agree, simply reply with a link to a file that has the MD5 hash 7a0a25a5c71fa2639a41ee743aa5e2b7

No-one can do this yet, and they may never be able to do it. But MD5 has failed one of its original design requirements and that's why people should stop using it and divert resources to ensuring that its replacements are safer.

Re:Checksums are always going to be vulnerable

[Tony Hoyle]

Using multiple hashes is a known way to increase security (some protocols use it) - it *does* work because the number of potential collisions is reduced - if you can create a collission with the MD5 (far from simple, in fact) it's extremely unlikely to *also* collide with the SHA1 hash - the number of plaintexts where they both collide is significantly lower.

Re:Checksums are always going to be vulnerable

[baadger]

No it doesn't.

The Wang vector pair floating about at the moment, when prepended to 2 useable files will produce a MD5 collision of the said files. BUT - as a result of doing this you are also going to corrupt these files and make them unuseable (executeables, MP3's etc, obviously not text documents).

All the proof-of-concept article shows is the two attack vectors by Wang in use with 3 simple programs. You will notice the "md5extractor", which needs to be in place to remove the arbitrary vector data before the evil good.exe becomes dangerous. This exact procedure doesn't apply to most software distribution actually, how are you going to get the extractor on the victims computer in the first place?

This could be a problem is somebody can produce an attack vector pair that does produce a valid executeable/PE header or and MP3 header. But these have structure and leave much less room for the vector, may place restrictions on the payload, and might not even be possible.

The webpage thing described in the comment you link to is pretty harmless. Who the hell usines a MD5 hash on a HTML documents? Misleading documentation? Browser exploits? Unlikely.

The fact remains if you were to try and use this method you would really be doing, and what you will have to do, is nothing more than trick the user by normal means (human failure).

Coincedentally, for use in authentication you would be a fool NOT to be running sanity checks on input anyway. For use in authentication, salted and sanity checked input to MD5 should is still very very safe.

I can't see a reason why P2P applications implemented for networks using MD5 file verification can't start popping off bytes at the beginning of downloads (the first block) and try it with another payload to detect and reject people using this type of multicollision attack. In addition these applications could check for valid MP3, AVI, JPEG, headers etc.

The author of the "MD5 - Someday to be considered harmful" paper is correct. MD5 is risky for some purposes, P2P networks still using MD5 without any smarts may be ruined, but the hash far from dead if used carefully backed up by other checks. What makes people think moving to SHA-1 or Whirlpool is going to solve these problems (OK with SHA-1 different types of attacks) in the longer term?

Relying on the hash mechanism alone is just a bad habit to get into. People are switching because it's just best to play it safe when people (myself included) don't understand the full significance of the attacks produced this year.

Re:Checksums are always going to be vulnerable

[ajs]

You are looking at this incorrectly. The problem is that, given file A, which has hash X, if it is possible to create file B which has hash X in a non-exaustive way, then the hash is weak. Most such techniques work well regardless of file B being a from-scratch random pile of data or a combination of well-formed data plus random data. So, for example, you might have an RPM with 3 files in it. Add a fourth file, and start permuting to find your similar hash.

Now, as you point out, we're not yet to the point that this is trivial with MD5 (it has always been possible, just not practical). So, the only valid thing to do is to move to something more secure as soon as possible so that when we finally do discover a trivial exploit for MD5, we no longer care as much about it. This also helps us by forcing software vendors and projects to re-consider how they use hashing, and to make it easier to modularly replace the hashing functions they use. You will note that all of the oldest such software has already had to do this, and thus the task will be easier for them.

Re:Checksums are always going to be vulnerable

[RAMMS EIN]

``If you contract your file from x bytes down to a fixed size, no matter what algorithm you use, you will always have collisions.''

Yes.

``Unless you start to give your hash keys as the same size as the original file, there is not anything that can be done about it, ever.''

No. If I run deflate or some other compression algorithm on a file, chances are it will come out smaller. Still, the compressed file maps one to one with the original.

Re:Checksums are always going to be vulnerable

[evilviper]

But all that enables you to do is replace an MD5'd file with garbage that happens to have the same MD5 sum.

It's not nearly as scary as swaping one document for another, or one binary for another, but it's still quite useful.

Think of P2P networks. Gnutella uses SHA1 hashes to verify files, file mirrors, and the final downloaded file. If some RIAA employees could find the SHA1 hash of a very popular song, and generate junk with the same hash, they could have people downloading their junk (pardon the pun) and the P2P app wouldn't know it was corrupt, and wouldn't have any way to avoid the junk file.

So if you need a freely available hash algorithm

[MadMoses]

...better use Tiger or Whirlpool (based on AES). AFAIK there are no known vulnerabilities or attacks for these two yet.

hashtrust

[gcnaddict]

Now we know why people distribute modified game ISOs on the net and check it with md5 :P In all technicality, couldnt this mean that someone could land a virus on someone else's machine because the person trusted the hash?

Re:hashtrust

[SillyNickName4me]

Any practical use of hash algorithms is extremely easy to fool with social engineering. All you have to do is get someone to trust your hash..

Re:hashtrust

[Anonymous Coward]

No, it's extremely hard. Probability of collision AND valid code is too damn low. Although this article proves that, with little social engineering, you can "emulate" (or cheat) a valid-code collision.

No, it looks quite feasible.

You need two ISOs, to each of which you have added a different block of random bytes that happen to hash to the same MD5, and you have also modified the game's setup program so that, depending on which block of bytes is there, it either installs the game normally, or it installs the game and a rootkit. You then start sharing the "good" ISO on a P2P network. It gets a bunch of downloads, a whole load of people add comments that say "works fine! no viruses!", and then you start sharing the evil version instead. Nobody can see any difference - but now some of the people downloading it are going to get owned.

With little social engineering indeed. In fact, it barely takes any at all.

But...

[Auraiken]

Isn't this the problem with all algorithms? Only way to know if something is something... is to see something instead of its checksum?
As for md5... with only 32bits, it should've came up with repetitive hashes in end anyways?

I guess since the article explains some issues against md5 security, the only answer would be to trust the source that is supplying the hash in the first place? Coming down to the fact that a system is only as secure as its user?

M$ Antihash

[CDMA_Demo]

At Microsoft, the MD5 hash functions are banned.

they use crc instead!

Re:M$ Antihash

[DrSkwid]

and your point is ?

you'll be telling me Huffman encoding is dangerous next !

A quick note

[Darren Winsper]

This seems to work on the assumption that you want to do some harm with a program you created yourself, you can't actually take a random RPM and turn it into an evil RPM with the same MD5. So, yes, it's bad, but it's not as bad as you might think.

Re:A quick note

[commodoresloat]

you can't actually take a random RPM and turn it into an evil RPM

Sure you can; all you need to do is set the evil bit.

Re:A quick note

[provolt]

The signature doesn't do anything to solve the problem. If I create an evil tarball that has the same hash as the good tarball, the signature will verify properly for both files. When you download the file, you won't know if it's the good or evil one.

GPG signs the hash. With a strong hash function, it's as good as signing the tarball. With a weak hash functions, one signature would match for many files.

H(x) == H(y) - H(x + q) == H(y + q) ?

[strcmp]

There is a known result about MD5 hash function, is this: If MD5(x) == MD5(y) then MD5(x+q) == MD5(y+q) So, if you have a pair of messages, x and y, with the same MD5 value, you can append a payload q, and the MD5 value keeps the same, the size of q is arbitrary.

Considering this is such a "well known" result, you would think that MD5 should have been abandoned long ago. Is this true for other popular hash functions?

Re:H(x) == H(y) - H(x + q) == H(y + q) ?

[igb]

It's almost universal to use the byte count as part of the checking of equivalence, either by storing it as a distinct item or by using it as inital or final salt to the calculation of the hash.

ian

Re:H(x) == H(y) - H(x + q) == H(y + q) ?

[Ckwop]

Is this true for other popular hash functions?

No it is not. The newer hashes, such as Whirlpool, do not have this problem. You're correct in saying this is a "well known result" and every cryptographer worth his salt says that this fact constitutes a break of the algorithm. We've known since the middle of the nineties that breaking MD5 was within reach. The fact there has been so much inertia in getting people to change is quite incredible really.

At Toorcon this year, Dan Kaminsky showed a way to create two different webpages that render properly in a browser but have the same MD5 hash. Anybody who thinks this attack is theortical and ignorable is grossly mistaken.

Simon

Not a problem for software distribution..

[hhghghghh]

This isn't a problem for software distribution, really, since the good.bin file needs to start with a vector designed to enable a collision. A good-faith programmer wouldn't include that vector.

It is a problem for stuff like contracts; you draw up two versions of a contract, a good one and an evil one, let someone sign the good one, and later keep them to the clauses in the evil one.

So while there IS a very big problem, the example is a bit contrived.

Re:Not a problem for software distribution..

[provolt]

This is certainly a problem with software distribution. Here's an example of why. The good-faith programmer creates good.bin. A Bad-faith programmer creates bad.bin with the same hash. All the bad-faith programmer has to do is find a way to swap bad.bin in for good.bin (hacking, misrepresentation, etc).

Now everyone who gets bad.bin will hash the data, verify the signature and see that the signature verifies. When the signature verifies, everyone believes bad.bin is really good.bin.

Re:So if you need a freely available hash algorith

[thomasdn]

AFAIK there are no known vulnerabilities or attacks for these two yet

I am no cryptography expert so I can not read and understand those algorithms. But the fact that there are no known vilnerabilities for an algorithm doesn't make it secure.
Maybe they are just not used as much as other well known algorithms. And therefore nobody has found vulnerabilities for them yet?

Yadda Yadda

[Effugas]

Two pages, same hashes, etc. (This is the guy who wrote the MD5 someday paper.)

http://www.doxpara.com/t1.html
http://www.doxpara.com/t2.html

Re:Yadda Yadda

[Jerf]

Mods, parent is not insightful, parent is wrong. And it's not hard to understand why the parent has a hard time seeing how MD5 is involved when they have an incorrect idea of how it works.

As a bit of a hint to NightHwk1, extremely carefully check the first bytes of those two pages. They are indeed not identical and do indeed hash to the same MD5 value.

The rest of the "trick" of course hinges on the fact that a single bit change to a Turing Machine can completely alter the resulting output. "Trick" is put in quotes because that isn't really a "trick", it's a fundamental truth about computing and is the reason why twiddling even a few bits in an MD5-hashed block (which is all this break seems to be able to do) is such a big deal. This is how they demonstrate it constructively, since most people aren't programmers and won't understand that.

Actually RPM uses MD5 and SHA1

[seifried]

RPM uses both MD5 and SHA1, the chances of finding a collision that satisfies both hashes is small, even if both MD5 and SHA1 are compromised since the hash the data differently.

rpm -Kvv xorg-x11-libs-6.8.2-37.FC4.49.2.i386.rpm
D: Expected size: 2655615 = lead(96)+sigs(344)+pad(0)+data(2655175)
D: Actual size: 2655615
D: opening db index /var/lib/rpm/Packages rdonly mode=0x0
D: locked db index /var/lib/rpm/Packages
D: opening db index /var/lib/rpm/Pubkeys rdonly mode=0x0
D: read h# 278 Header sanity check: OK
D: ========== DSA pubkey id b44269d0 4f2a6fd2 (h#278)
./updates-released/packages/xorg-x11-libs-6.8.2-37 .FC4.49.2.i386.rpm:
Header V3 DSA signature: OK, key ID 4f2a6fd2
Header SHA1 digest: OK (f37bf5cb97db696f14133b90e23f2455b9f94587)
MD5 digest: OK (8eda29837b6992876bd867df03b3b8af)
V3 DSA signature: OK, key ID 4f2a6fd2
D: closed db index /var/lib/rpm/Pubkeys
D: closed db index /var/lib/rpm/Packages
D: May free Score board((nil))

Re:filesystems...

[ArsenneLupin]

Reiserfs (and lots of other filesystems ... and lots of other system components in general) might use hash functions to speed up lookups. These hash functions however do not need to be cryptographically secure. The hash (which is usually very short, so much that brute force would be feasible) is only used as an index into an array of "buckets". Each bucket may contain multiple files, and the system still uses a bit-by-bit comparison on the full names to find the correct entry.

The point is to reduce the set among which to do an exhaustive search (one small hash bucket versus all known files on the system), and not to verify some kind of signature.

Any successful attack on the hash would only be useful to make the system slow and unefficient (by making an excessive number of files end up in one bucket), but cannot corrupt it.

Re:File Integrity Checkers ?

[ArsenneLupin]

So the next time someone installs a root kit, he just needs to do it in a way TFA points out.

Wouldn't work. TFA points out a way to generate to packages, a good one, and an evil twin. Both are constructed by the algorithm.

It does not however show how to make an evil twin for an existing package. This considerably lessens its danger.

Think about it: the only guy who could pull this off would be the original author. But then, the original author could achieve that same goal much more easily than by "breaking" MD5.

Re:So if you need a freely available hash algorith

[MadMoses]

Misunderstandment. I never made a statement about MD5 not being "free". But MD5 is vulnerable, that's why I pointed out some alternatives.

Speaking of hashing algorithms...

[scovetta]

The NIST is having a two-day workshop in Gaitherburg, Maryland (USA) on October 31-Nov 1. Xiaoyun Wang will be giving a keynote speech, and there'll be plenty of technical material to go around. The workshop website is: www.csrc.nist.gov/pki/HashWorkshop/program.htm. I don't work for NIST or anything, but I thought this was interesting and they haven't really done a good job getting the word out about this conference.

Don't panic yet

[Anonymous Coward]

While this is a very serious attack, it doesn't yet mean that every use of MD5 is totally unsafe.

It is feasible now to generate 2 different pieces of data with the same MD5 hash. As many file formats allow one to embed invisible 'junk', it is possible to create a 'good' version and an 'evil' version with the same MD5 hash.

BUT it is NOT (yet) feasible to create a piece of data with a given MD5 hash. This means that if you can not modify the 'good' version, you can't create a matching 'evil' version.

An example of where the usage of MD5 isn't broken are *nix passwords. Your password is hashed with MD5 (a salt is added to your password too, but that's not important here), and that hash value is stored. Anyone who can supply a password (doesn't have to be the same one!) which has the same MD5 hash, is allowed access.

So if it would be feasible to generate data with a given MD5 hash, one could easily generate a matching password, when given the MD5 hash (which you can often easily acquire, especially in NIS/yp environments). But luckily, this is not possible ... yet :-)

So you'd better start protecting those hashes (that's what a shadow password file does), en better yet, move to a better algorithm. Like the Blowfish algorithm that OpenBSD has been using for years now.

Re:Don't panic yet

[Haeleth]

An example of where the usage of MD5 isn't broken are *nix passwords. Your password is hashed with MD5 (a salt is added to your password too, but that's not important here)

Actually, the salt is extremely important. A large proportion of unsalted MD5 passwords can be cracked trivially by looking them up in pregenerated databases. MD5 alone is broken for passwords - it's only the salt that makes MD5 passwords still "good enough" for use on low-security machines... for the time being.

Why it IS a problem

[Moraelin]

The problem is that a broken algorithm just makes that piece of social engineering a lot easier.

If I just told you you can download the latest auto-installer of the latest WoW patch from www.i-pwn-ur-puter.ru instead through the slow Blizzard installer, you might think "uh, wtf, I think I'll play it safe anyway and get it directly from Blizzard. I trust them more than I trust a warez and script-kiddie site."

Now picture that I tell you "and here's a link to the MD5 sum on Blizzard's site. You can check for yourself that the the file on our site is the original file and it hasn't been tampered with." In fact, I would even _urge_ you to make a habit to check all your downloads against the original MD5 sums, for your own good.

It already looks a lot safer and more legitimate. Well, maybe not to _you_, but to a lot of people it does.

That's the whole problem. That false sense of security makes the "if we can convince you to run our insecure extractor code" part a helluva lot easier.

Re:Why it IS a problem

[archeopterix]

Now picture that I tell you "and here's a link to the MD5 sum on Blizzard's site. You can check for yourself that the the file on our site is the original file and it hasn't been tampered with." In fact, I would even _urge_ you to make a habit to check all your downloads against the original MD5 sums, for your own good.

It already looks a lot safer and more legitimate. Well, maybe not to _you_, but to a lot of people it does.

That's the whole problem. That false sense of security makes the "if we can convince you to run our insecure extractor code" part a helluva lot easier.

The scheme described in the article enables you to: take a good file and generate:

A. Another "good" file (one that generates the same exec while extracting).
B. A "bad" file.
Such that hash(A)=hash(B)

For this scheme to work, you would first have to convince Blizzard to use your "good" file A for distribution (more exactly: computing the published hash). Hey Blizzard, I have a file that extracts the same files as your distribution, only has a different hash value, why don't you replace your file with my file? "Helluva lot" easier than just convincing them to distribute your "bad" file? I don't think so.

Re:So if you need a freely available hash algorith

[commodoresloat]

...better use Tiger

Once again, OSX proves to be more secure!

*ducks*

On Slashdot..

[Anonymous Coward]

surprisingly many stories hashes to the same value..

Re:So if you need a freely available hash algorith

[poopdeville]

I am no cryptography expert so I can not read and understand those algorithms. But the fact that there are no known vilnerabilities for an algorithm doesn't make it secure. Maybe they are just not used as much as other well known algorithms. And therefore nobody has found vulnerabilities for them yet?

This is a complicated issue. Generally, the security offered by an encryption algorithm isn't measured by its popular usage, but by the amount of time qualified professional cryptographyers/mathematicians/hackers have studied it without finding a critical vulnerability. My claim is probably too broad: there is no magical formula that determines how secure an algorithm is. But in depth work by professionals does endear confidence in an algorithm.

As a general rule of thumb, it is wise to use an algorithm that has been seriously studied for 10-20 years. At this point, it is modern enough to withstand modern brute force attacks, and (hopefully) understood well enough to ensure that there are no structural vulnerabilities. If it is much older than that and still studied, it is likely because a flaw has been found and people are trying to push it as far as it goes.

TCP

[RAMMS EIN]

And to think that they're still working on getting MD5 digests in TCP packets...the algorithm could be as useless as the checksums they currently use by the time this change would have become widely accepted (now it's probably never going to happen).

Re:TCP

[tomstdenis]

It's ok as a checksum [e.g. non-malicious modification].

If you need say authentication you need a MAC anyways. As far as I know HMAC-MD5 is not immediately attackable by the known attacks [though I wouldn't use it anyways].

Tom

Re:File Integrity Checkers ?

[Shano]

Not necessarily - it depends on how much the author is trusted to begin with. Certain types of software are very closely checked by the open source community, and any trojan will be discovered if it exists in the package.

Say I write a bit of security software (for which most people take the time to compare checksums). As a relative nobody, lots of people are going to scrutinise the source code before using it. Any new release will also be checked. Only after it's been scrutinised and built up a reasonable userbase is it worth switching it for the evil version - otherwise, the evil version would be discovered early and nobody would use it.

Someone like Schneier could probably release a trojan directly and people would install it without thinking (I trust he's too responsible for that, though). For the rest of us, this gives a feasible way to sneak in evil code without anyone checking it.

Ahem...

[tomstdenis]

said this before...

Dan Kaminsky is actually the dude who came up with the Stripwire idea. ... LAST YEAR.

Tom

Re:compressed content safe (?)

[Shano]

Lots of file types allow for arbitrary junk at certain places.

For example, a very basic form of steganography: cat a .zip file to the end of a .gif file. The result is a valid file that can be displayed as an image (which ignores trailing junk), and decompressed with zip (which ignores leading junk).

Most file formats I've written don't care about junk at the end of the file. It'll be stripped off if you load and then save, but the program won't notice or complain. One program even preserves records it doesn't recognise (which could be secret messages, or just random crap).

There are some limitations to this attack

[GekkePrutser]

As far as I know, the technique used for finding these MD5 collisions, cannot be performed with a GIVEN hash. So it's not possible to create, say, a copy of an already available RPM, add malicious code to it, and easily find some data to add to it to generate the same hash. This is not possible.

The only thing the current 'crack' does is create two RANDOM input files that generate the same hashed output. So it's only useful for someone who can control both the 'original' and the 'malicious' version of the data which is being protected by an MD5 hash.

So the dangers here are kind of limited though you could still do a lot of damage with it.

Merkle Damgard: Why len(x) and len(y) matter

[0ptix]

AFAIK this is an attack on the underlying Merkel-Damgard paradigm which both SHA-1 and MD5 (amoungst others) employ. The paradigm goes as follows:

                                      IV | Intialisation vector of n-bits
                                  MB_i | Message Black i of n-bits
                                  HB_i | Hashblock i of n-bits
f:(IV , MB_i) -> HB_i | is the underlying compression function which takes both an IV and a message block as input and outputs a hashblock.

First the orginal messaage is split up (and padded if need be) into n-bit blocks. Then f is applied with an IV and MB_1 as input resulting in HB_1. f is then applied iteratively each time tacking the next message block as input while using the previouse hash block as the IV input.

f(IV, MB_1) = HB_1
f(HB_1, MB_2) = HB_2 ...
f(HB_s-1, MB_s) = HB_s = H(Message)

Merkle and Damgard proved that the over all construction is collision resistent given that the compression function f is collision resistant.

As the parent post pointed out though the last block had better include the over all message length. If this is not the case then by extendeing 2 different but colliding messages x,y with the same plain text q the input to the compression function becomes identical since H(x) = H(y) = IV input for f. If on the other hand the length of the orginal message is included in the last block then even though the IV input for f is the same for f(H(x),q_1) and for f(H(y),q_1)..., the final message block (q_s) will again be different resulting in a different final hash block.

If on the other hand len(x) = len(y) then the problem persists since both IV and message blocks will be the same when the final iteration of the algorithm is reached.

Infact this attack is even stronger since by the same reasoning one can see that to produce H(x+q) all one needs is to know is H(x) (and len(x) if that is included in the last message block). No other information is needed about the orginal message x! H(x) is simply inserted as the IV for f when hashing q and so the iteration is "jump started" just where x finishes. (If the length is included in the last block then all that need be used is len(x)+len(q).)

Disclaimer: Not to 100% sure about all this though so please feel free to correct me if i'm wrong... :-)

Banning MD5 is stupid and small minded

[ivan256]

It's dumb to ban MD5. It is still, and will continue to be a useful tool in situations where a cursory comparison is needed for reasons other than security. It would be silly, stupid even, to use a larger hash that requires more (slower) computation in these situations. Banning MD5 can mean one of two things: Either it's a stupid publicity stunt that will result in slower code overall, or that Microsoft doesn't trust it's developers to be smart enough to know when a particular hash is appropriate.

RPM is still relatively safe...

[PAjamian]

RPM only uses MD5 to check for corruption of the type you might find during download. RPM actually uses GPG or PGP to sign the generated RPMs for security, and GPG is (afaik) capable of using nearly any hashing algorythm including ones that are yet to be invented. So as far as security is concerned RPM doesn't use MD5 but rather uses whatever hashing algorythm the GPG key that signed the RPM was generated with.

Whirlpool is not based on AES

[Paul Crowley]

Whirlpool is not "based on AES". It shares a few similiarities (and a designer) but it is a distinct algorithm in its own right. It has a larger block size, different S-boxes, a different linear component, a different key schedule and so on.

I would interpret "based on AES" as meaning it actually uses AES itself (perhaps in tandem Davis-Meyer mode or similar).

I like Whirlpool but it's not fast. I think Tiger is quite a bit faster.

Bernstein's cache timing attacks, and the ever-growing gap between processor speeds and memory access times, mean that table-based primitives (which both of these are) are going out of style.

replace both the "Evil file" AND the extractor ?

[Jedi_Gunsmith]

I just read the article, and i was thinking :If we can replace the extractor, then why bother creating an evil file with the same checksum ? The extractor can do the "evil patch" at extraction. The method in this article isn't very usefull for evil purposes.

About this attack

[Ernesto Alvarez]

I've been reading the posts in this thread and I've noticed that there are two types of posters here: the ones who got it 100% right, and the clueless ones (there appear to be little or no posters in the middle ground).

Now, the clueless ones are thinking of lots of "attacks" using this vulnerability, some of them really wrong. Since this has the potential of getting lots of people to do stupid things (like not trusting MD5 when they should), let's talk a little bit about the vulnerability and its effects.

First of all: this is not new. There was an article here explaining the same attack a few months ago (about x.509 certificate collisions and how to fake postscript orders, if you know what I am refering to, please post a link).

The attack goes like this:

You have a block B1 that is known to collide with another block B2.
You have some custom made code that looks like this:

-----BEGIN SNEAKY CODE---------------
If DATA[1] = DATA[2] then
do something good
else
do something bad
end
DATA[1]
DATA[2]
-----END SNEAKY CODE-----------------

The trick is that since there's a collision between B1 and B2 and MD5 makes the hash by reading sequentially, the hash for the whole program will be the same whether you fill DATA[1] and DATA[2] with B1 or B2 (in any combination). Since the code is DESIGNED to do different things depending on the collision area, by changing the contents of DATA[1] and DATA[2] you can have programs that do "good" or "bad" things, with the same hash. Please note it's been DESIGNED with that in mind.

From now on I'll talk on absolute terms, while in reality there is a very small probability of things being right for an attack without being planned that way, so keep in mind that before saying "but that's not the whole truth.....".

Now let's discuss what's possible to do and what's not:

1.Oh no! Now, someone will create a virus that has the same hash than my favorite app!

False: the app (or installer) would have to have been designed with that "feature" in advance.

2.MD5 is worthless and should not be used anymore.

False: MD5 is useless in the situation presented above. There are some very good uses of MD5 that are safe (like access control: this attack does nothing practical to you salted MD5 shadow file). MD5 should probably be watched for other undesirable properties, though. An alternate cryptographically secure function should be kept in reserve.

3.I'll use another hash function, I'll be invulnerable to this attack.

(somewhat) False: You'll be invulnerable until someone finds ONE collision in your new hash function (it might take a long time but....). Then you'll be vulnerable again. But now we all know what can be done with ONE collision. What you're thinking is probably good, but it's no silver bullet.

4.Microsoft will forbid the use of MD5 and DES, and use SHA-1 and AES. We should do the same.

(somewhat) True: Not for the reasons you're thinking though. If MS is really doing this, this attack is a lame excuse to do it. MD5 is still useable for some things, and SHA-1 is not much better than MD5 in the things related to this attack. IIRC these collisions were found using an attack derived from an attack on SHA-1. Right now, SHA-1 collisions can be found in 2^63 operations (and the clock is ticking). We should probably consider using a new hash function someday, but leave the decision to the cryptologists. About AES, it's about time. DES can be brute forced in reasonable time, and that's been like that for a few years. 3DES is slow. That's the reason for the AES contest, we should use since we have it.

5.Someone could distribute some sort of binary and the switch it so it does lots of damage to unsuspecting people.

True: That's exactly what the attack is about. Maybe you were wrong to trust [insert a name here].

6.Who should be doing what and when?

If you work in crypto, you probably k