Slashdot Log In
Meaningful MD5 Collisions
Posted by
Zonk
on Fri Jun 10, 2005 02:38 PM
from the bam-crash-boom dept.
from the bam-crash-boom dept.
mrogers writes "Researchers at Ruhr-Universität Bochum have found a way to produce MD5 collisions between human-meaningful documents. This could be used to obtain a digital signature on one document and then transfer it to another. The same technique is theoretically applicable to other hash functions based on the Merkle-Damgård structure, such as SHA-1." From the article: "Recently, the world of cryptographic hash functions has turned into a mess. A lot of researchers announced algorithms ("attacks") to find collisions for common hash functions such as MD5 and SHA-1 (see [B+, WFLY, WY, WYY-a, WYY-b]). For cryptographers, these results are exciting - but many so-called 'practitioners' turned them down as 'practically irrelevant'."
Related Stories
[+]
SHA-1 Collisions for Meaningful Messages 128 comments
mrogers writes "Following on the heels of last year's collision search attack against SHA-1, researchers at the Crypto 2006 conference have announced a new attack that allows the attacker to choose part of the colliding messages. "Using the new method, it is possible, for example, to produce two HTML documents with a long nonsense part after the closing </html> tag, which, despite slight differences in the HTML part, thanks to the adapted appendage have the same hash value." A similar attack against MD5 was announced last year."
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Common sense (Score:3, Insightful)
Unless I'm missing something, all these guys are doing is using a format that can contain an infinite amount of extraneous information that has no effect on how it's ultimately rendered, so same thing can be done with a
no help (Score:2, Insightful)
Extracting the formatting and code from the document will just make it EASIER to create a duplication.
"Hello World!" might match with "Hello World!!!!!! this is extra stuff"
at least leaving the exact formatting instructions in gives you a chance that the collision which leaves a compatible file is much more difficult than the hash of the simple raw text.
Re:Common sense (Score:2, Informative)
It's an example of the hash collision weaknesses recently documented, giving a practical example of how it could be used for malicious purposes.
Traditionally we haven't had to worry about nonsensical things like applying the hash only to easily verifiable English text, because the hash is supposed to practically protect against intentional searches for collisions.
On the contrary... (Score:5, Insightful)
You may believe it's common sense, but to the average user, encrypting a simple letter like the memos used in the article expressed as a Word document is no different than encrypting a simple text email. Heck, many of these users probably have no idea that much of the plain-looking email they send and recieve is actually HTML, which is capable of hiding beneath its rendered surface all sorts of additional information.
When's the last time you saw an email program that read in a Word document, extracted just the plain text content, signed or encrypted it and then repackaged it into some new format in a cryptographically sound way that would automatically be reconstituted as a Word document on the other side? Most just have a handy "Sign" or "Encrypt" button that will happy accept
Parent
Re:Common sense (Score:4, Interesting)
So they are actually using a format that can contain an exact quantity of extraneous information that doesn't get rendered but entirely changes what does get rendered.
The same thing could be done with PDF or doc, and executables, but not anything compressed (it won't decompress at all if a block is changed) and not HTML without javascript (there's no way to test which block of junk is included and show different results based on that).
Parent
Re:Common sense (Score:3, Informative)
The files are the same size.
The cksum comand (which uses a 32 bit CRC) spits out the checksum and a file size. Why doesn't md5sum do the same thing?
It does - The file size is used as part of the MD5 hash. The MD5 algorithm hashes the file, then appends the file size and hashes that too. If it didn't do this then you could create an MD5 collision just by appending zeros to the file.
Wow...this is nerdy even for /. (Score:2)
Re:Wow...this is nerdy even for /. (Score:3, Funny)
I hope that clears things up.
Re:Wow...this is nerdy even for /. (Score:3, Informative)
Re:Wow...this is nerdy even for /. (Score:4, Informative)
Parent
Re:Wow...this is nerdy even for /. (Score:3, Insightful)
Not exactly. Not unless the attacker could choose the first text. The new attacks allow you to create two documents that collide, but don't (yet) allow you to take an arbitrary document and make another that collides with it.
That word "yet" is important. A lot of bright crypto people will now start working on "preimage" attacks and they've got some new tools to work with. Be afraid
Re:Wow...this is nerdy even for /. (Score:3, Interesting)
It bears mentioning that md5 doesn't account for the length of the file. So if someone were to try installing a backdoor into a program, and had a sophisticated enough piece of software using this method, comments, metadata, or other information could be used to 'pad out' the file to make it seem like the original -- even with source code files. Especially in the case of executables, they could just insert random crap at the end of an executable file, and make the md5 hash (and possibly the size) come out
Re:Wow...this is nerdy even for /. (Score:3, Informative)
Consider it to be an example... (Score:3, Informative)
Basically, they provided an example case where one of these recent methods to generate hash function collisions can be turned into a "real world" attack.
It's a very simple example case, but it demonstrates the point effectively. The point is that these recently discovered methods to generate collisions quickly are a real threat to any software using them as a method for digital signatures and such.
The real world application
Re:Wow...this is nerdy even for /. (Score:3, Insightful)
Before someone starts bitching about "lack of trust" in open source, please replace kernel with security update an
These are important attacks.. (Score:5, Insightful)
is at the very least misguided and at worst a shocking display of incompetence.
Stop the fixation with plain-text messages, most messages are not plain-text. Your average word document
contains loads of invisible data that doesn't get rendered. Pdf's contain "junk" data that doesn't get rendered either. Would
you notice a single bit difference in an MP3? Or a single pixel colour change in a jpeg? Hell, you can even do it in HTML <div style="visibility:hidden">Junk goes here</div>.
Mark my words, people will find in the next couple of months find two meaningful computer
documents that hash to the same value but are different byte-wise.
People undervalue these attacks because the attacker has to generate the collision before hand to use it.
To properly appreciate the power of these attacks consider the following senario.
Imagine we're agreeing a contract of employement and I'm your employer.
I give you the first word document that includes all the standard terms, however, I've also drafted
a Word document that contains a load of draconian clauses like banning you from working in any IT position five years
after leaving the company. By adding junk that doesn't render to both documents, I've managed to find to make the hash
of the two documents collide. Thinking I'm a nice employer, you sign the first document, which you do by signing the hash of
document. However, I now have your signature on BOTH documents. I now make sure the company IT system "forget" the first document
and I've successfully screwed you.
This is a human example, but there are other examples that apply in computer systems. The problem is that in many situations
the attacker can choose when you encrypt. Say you encrypt your e-mail conversation with your friend using S/MIME, many people click
"Reply" and the message body of the other persons method appears in the new message. Because of these attacks,
It's now no certainty that an attacker couldn't use this fact to construct collisions that an attacker could use.
As another security researcher said (paraphrased) It's like you're in building and you've just heard the fire alarm go off.
You can't see smoke but it's time to make your way calmly to the exit. That sums up the position with SHA-1 and MD5. Swap out the primitives
before you start seeing smoke.
It's not like we don't have alternatives anyway. Whirlpool uses the same wide-trail design principles has AES. It's slower than MD-5 or SHA-1 but it's much better designed. And beside, people would do well to realise you have to spend CPU cycles to get security.
Simon.
Re:These are important attacks.. (Score:2)
Er, only if you're stupid enough not to keep a copy of a document that you sign.
Re:These are important attacks.. (Score:4, Informative)
Parent
Re:These are important attacks.. (Score:5, Insightful)
Then you whip out the original document. Presto: both documents have the same signature. Now it's up to the party making the claim to prove which contract was signed. Impossible.
The reverse is also true: the programmer works on a super secret project. He signs a secrecy declaration. If he can apply the exact same signature to his lunch agreement, and walks out with the sourcecode, his employer is screwed, as per the example above.
Etc. An agreement is legally binding in any form. The only reason to have a signed copy of any agreement (digitally or paper) is to have proof of the agreement. If the signature is no longer proof, no agreement rises above verbal agreements, evidence wise.
Parent
Re:These are important attacks.. (Score:3, Insightful)
The "reasonable person" standard prevails. Remember, they have to explain the existence of that extra padding in the document. The jury, assuming it's composed of reasonable people
sorry, had to take a moment. my co-workers are no doubt wondering what the hysterical laughter was about
the jury is not likely to believe that you signed away your rights. Now if the employer's document specified a million-dollar signing bonus, then he pulled a switch on you to
Re:These are important attacks.. (Score:3, Informative)
Not quite, beacuse of reasonable doubt and the fact that the hypothetical employee would have copies of the document.
However, Alice can get Bob to sign an innocuous recommendation letter that in the hidden version is a power of attorney for Bob's bank accounts. Alice can then take the fraudulent letter to Bob's bank and with apparent legality, take all of his money. (The difference being that a third part
Re:These are important attacks.. (Score:3, Informative)
The collisions that have been found for MD5 are for pairs of documents that are the same size. The size constraint is not a problem.
Re:These are important attacks.. (Score:3, Informative)
What people don't realize is that MD5 _IS_ two hashes already! That's how it works!
To make it worse the hashes you mentioned MD5 and SHA-1 are based on exactly the same algorithm, so using it twice doesn't help you much.
Re:well... (Score:3, Insightful)
[Disclaimer: I'm not an expert at cryptography, but I like to think I understand it better than most non-mathematicians outside the field. It would be really nice if a crypto expert could clarify this, but I don't expect that to happen on Slashdot.]
You are correct that your scheme would add some security, but not nearly as much as our intuition might lead us to believe.
Let'
Re:These are important attacks.. (Score:3, Interesting)
Microsoft Office and OpenOffice.org documents both can contain executable content which can execute when the document is opened, and which can alter the contents of the document.
I am not very familiar with Microsoft Office, but in Op
Coral Cache QUICK! Before it gets /.'ed (Score:2)
A critical event... (Score:2)
What are the alternatives? (Score:2, Insightful)
Re:What are the alternatives? (Score:4, Informative)
Parent
Re:What are the alternatives? (Score:3, Informative)
Read about collision attacks versus preimage attacks here [cryptography.com].
Unless you're assuming that at least one of the people respon
Text of Letters (Score:3, Informative)
Julius. Caesar
Via Appia 1
Rome, The Roman Empire
Alice Falbala fulfilled all the requirements of the Roman Empire
intern position. She was excellent at translating roman into her gaul
native language, learned very rapidly, and worked with considerable
independence and confidence.
Her basic work habits such as punctuality, interpersonal deportment,
communication skills, and completing assigned and self-determined
goals were all excellent.
I recommend Alice for challenging positions in which creativity,
reliability, and language skills are required.
I highly recommend hiring her. If you'd like to discuss her attributes
in more detail, please don't hesitate to contact me.
Sincerely,
Julius Caesar
Julius. Caesar
Via Appia 1
Rome, The Roman Empire
May, 22, 2005
Order:
Alice Falbala is given full access to all confidential and secret
information about GAUL.
Sincerely,
Julius Caesar
Explanation of the attack (Score:5, Informative)
What these researchers did was not to improve the known attacks on MD5, but to demonstrate a clever way of turning the known attack, generally considered to be of theoretical interest only, into an attack that could potentially really be used.
The way they did it was to create a postscript document that actually contains two documents, one that the sender would be willing to sign and one that he presumably would not. The full text of both is contained in the file, but near the beginning of the file is a bit of code that compares two blocks of random-appearing bits, call them A and B. If A == B, the postscript interpreter will select the innocuous message and display that. If A != B, the interpreter will display the other message.
The researchers then generated a pair of blocks with the same MD5 hash. In one copy of the postscript file, they used one of these blocks as both A and B. In the other copy, they used one block as A and the other as B. Because every bit of both documents before and after the two blocks is identical, and because those blocks hash to the same value, the documents hash to the same value.
It's an interesting attack. It only applies to documents that are also programs, in some sense, but we use lots of document formats that fit that description.
A simple countermeasure that makes such an attack more difficult is to compress the documents before signing.
Not exactly useful for fraud... (Score:5, Insightful)
Parent
Kids in Finland don't agree (Score:5, Insightful)
"every time [some software engineer] says, 'nobody will go to the trouble of doing that,' there's some kid in Finland who will go to the trouble."
Taken from Kevin' Mitnik's "The Art of intrusion"
http://www.amazon.com/exec/obidos/tg/sim-explorer
7 bits difference (Score:3, Informative)
I guess it's obvious from looking at the ps file in text form, but if it's that easy to mangle postscript to display two different layers (or is it changing comments or pointers? I am not a binary postscript parser.) I still don't think it's time to throw md5 away yet. Six months.
What other hashing alternatives are there these days? SHA-1 apparently has the same kinds of weaknesses.
Perhaps its time for another layer of protection. (Score:3, Funny)
Okay, I'm impressed. (Score:5, Interesting)
I bet the random parts are REALLY BIG! I mean, you'd probably need a lot of random data before you could find a collision...
Then I downloaded the files...
There's almost nothing to them! I can't read PS, so I'm not sure how many of that handful of bytes at the beginning might be tweakable... but it's a lot less than I expected.
Collisions must be very easy to find! I am now offically very worried about this.
Re:Okay, I'm impressed. (Score:4, Informative)
That's actually not what they did. They generated two essentially random blobs of data that have the same hash. We'll call these X and Y. They then created a PostScript document containing BOTH messages, the one that Alice's boss would sign and the one he presumably would not sign. They inserted two copies of block X into one of these documents, and a one X and one Y into the other. The original document contained code that compared the two blocks, and if they were the same, caused one message to be rendered, or if they were different, caused the other message to be rendered. Thus both documents hash the same (since X hashes the same as Y), but you see different text when you view the files.
This sort of attack would only work on documents that can contain code of some sort. It would not work on text files.
Parent
So you're saying I shouldn't implement MD5 ... (Score:3, Interesting)
in my next big project?
In all seriousness, I believe Schneier's right. We need a competition for a new hash function [schneier.com].
Nah, let's just wait for 24 [techweb.com] to drop the words "MD5" before we know it's really bad.
Relative Resources: The Attackers' Advantage (Score:5, Interesting)
- Relative expected values of gian vs. loss: The attacker thinks "I know I can gain a #BIG_NUM million dollars" and devotes their full effort to the attack. The defender thinks "I'm safe, there's a low probability, and I'm sure I'll catch the problem before it becomes real money, " and does not not devote effort to security becuase a Gartner report told him it was over-hyped. Thus, the attacker's perceived expected value is much higher than the defenders perceived expected loss and each invests accordingly.
- Rising Complexity: As IT systems become more complex, they become less secure. Each new device, new networking protocol, new physical layer, new OS feature, new networked application provides new opportunities for the attacker and a dilution of security resources for defenders.
- Time: The attacker has the advantage of time. New algorithms, new mathematical theories, new exploits, and faster processors all favor the attacker. What once was supposed to take the age of the universe to crack can be decrypted with a quickly declining number of networked (even zombied) PCs.
- Curse of Compatibility: Because so much crypto and security is networking related, it is subject to implementation delays caused by the need to be compatible. Defenders continue to use old, vulnerable systems to maintain compatibility with key partners. Patches don't solve the problem because the patch itself can introduce incompatibilities that make defenders leary of applying the patch with a very real chance of causing problems to avoid a hypothetical security issue.
The bottom line is that the defender must protect all vulnerabilities while going about the day-to-day business of using the computer. In contrast, the attacker can devote full time to any weakness of their choice.From a prior discussion... (Score:4, Interesting)
There was talk about someone being able to foil P2P networks by seeding bad stuff through random data formulated to fit the MD5/SHA1 code from legitimate files shared on those networks. The consensus was that it was BS and that even if it weren't BS there could be updates to make such attacks more difficult or impossible to perform.
Am I missing something or are these two stories relevant to each other?
Works for certificates, too (Score:5, Interesting)
Here's a link to the paper: Lenstra et al [iacr.org].
The provided exploit documents can be edited! (Score:4, Insightful)
All you need to do is download the two postscript documents and do *exactly corresponding edits* in both of them, and you get two documents saying different things and still have the same md5sums!
I just tried exchanging Alice's name for my own, and surely it did work.
Now, if they released a pdf-file hack, I would be genuinely worried
Re:The provided exploit documents can be edited! (Score:5, Informative)
No, you have missed the point. Go back and rtfa again. The attack still works if you rename the documents to the same filename.
The difference lies in a generated "binary cookie" in the beginning of the postscript documents. This "cookie" makes the postscript intepreter either select to show document 'A' or 'B'. The "thing" with the cookies are that they are carefully selected to be md5-colliding. Result: both documents have the same md5sum.
You can change the rest of the documents freely if you make the same changes in both documents. The md5sum will change, but it will still be the same for both documents.
So. No. It is indeed a md5 collission attack.
Parent
do you know how big 2^128 is? (Score:5, Insightful)
2^128 is huge. It's larger by far than the number of all the files in all of the computers in the world. It larger than the number of stars in the universe. Chance collisions will not become an everyday occurance. No accidental collision has ever been found yet. Switching to larger keys will not change anything. Sure, they might make it slightly harder to make a deliberate collision (although I don't know for a fact that they make it harder at all, there were some reports of someone in Japan being able to create a collision by hand with only pencil and paper), but just wait 2 months and the computing power will catch up with that. It's not a matter of the size of the hash function.
Parent
Re:do you know how big 2^128 is? (Score:5, Funny)
Pfft, let me show you my porn collection.
Parent
Size matters (even now) (Score:3, Informative)
Switching to longer hash sizes (not keys) will help against the current generation of SHA attacks. The effect of the Wang attacks is to knock (if memory serves) 16 bits off the work factor to find a collision. In other words, finding a collision in SHA-1 is now 64K times easier than brute force. Make brute force harder and the attack gets harder.
Some numbers: SHA-1 produces a 160-bit hash. If you're trying to find a collision as oposed to generating on
Re:Security Through Obscurity (Score:4, Informative)
With cryptographic hashes, you're throwing away nearly all of the data to obtain a hash (a number) which represents the larger data set in such a way that (hopefully) the hash will never turn up again in practical usage. The article here indicates that there are ways being devised to force two data sets to have a hash collision while keeping the practical parts of the data sets the same.
As for accusing encryption of being "security through obscurity", you're misusing that term. If knowing the encryption algorithm allowed you instant access to all data encrypted with that algorithm, then yes, the only security present would be dependent upon the secrecy of the algorithm itself. But that's not the case here. Encryption typically works by public key exchange, meaning that a key (a number) used to encrypt messages is shared with the encrypting partner, while the key to decrypt and recover the data is kept private (is never transmitted). Recovering the private key through brute force is not a compromise of the algorithm itself - given enough time, any private key can be recovered, regardless of the algorithm, but by increasing the key size arbitrarily, the time taken to find that key can also be increased arbitrarily.
Parent
Re:Security Through Obscurity (Score:3, Informative)
I think that's a big shortsighted... I agree that if we let history take a crack at it, that any encryption put together by smart people will eventually be breakable by smart people.
However, most data that I deal with day-to-day is time relevant. Do I care if someone figures out my credit card number on an account I closed 5 years ago? Is it terrible if someone hacks an old email only to find out I was begging a professor for a passing grade in 1997?
Encryption is meant to hide things, and for many
That won't solve it (Score:4, Insightful)
Therefore, no matter how many algorithms you sum up using your described method, the number of collisions is still infinite in amount. It is not the algorithms that are flawed, rather, it is the fundamential concept of hashing that allows collisions to happen.
I would assume that the way to reduce the number of collisions is by increasing the length of the hash itself so as to increase the number of unique hashes.
Parent