Meaningful MD5 Collisions 312
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'."
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:no help (Score:2)
Up to recently nobody has found a collision in 128 bit hashes like MD5. 128 allows for roughly 3x10^38 different hashes. SHA-256 allows for roughly 10^77 different hashes, which is close to number of atoms in the observable universe (estimated to be between 4×10^78 and 6×10^79).
So, unless you present the algorithm with a lot of different input you'll never find a collision.
It is probably safe to say that nobody will *ever* be able to find (or generate) *any* collision in SHA-256 and higher.
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.
Re:Common sense (Score:2)
Re:Common sense (Score:2)
While you are right that you always will have collissions they say that they can find it in a reasonable time.
What is interesting though is that in their example they have control of both documents and they may use that to find a collision.
This means that they may have a harder time to find a collision for an arbitrary document. If that is the case i don't know. I'm just speculating.
Re:Common sense (Score:2, Insightful)
Your common sense seems a little ridiculous. Are we saying that all documents have to be reduced to text before applying our encryption? What about nontextual documents, like, say, process flowcharts, spreadsheets, powerpoint slides, multimedia?
There are a lot of formats out there that allow additions of random undisplayed information, and so I presume that many of these formats are vulnerable to these attacks.
I wonder how long it will take before there are exploits out there that take advantage of these techniques... Of course, I also wonder how many there already are...
Oh well. The key concept behind security is, has been, and always will be trust. You should always ask yourself when you receive something from someone else how much you trust the source, and act accordingly.
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
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).
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)
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. In a calm constructive way of course.
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 identical to the original. Some of these have already been demonstrated.
While this collision will be a big deal for signing documents, it shouldn't have any effect on web security (Digest Authentication, for one, uses MD5 pretty extensively). The lesson: While MD5 is still reasonably difficult to collide, the time to find collisions (~5 hours) on a normal PC means that malicious uses are now practical.
I'm not entirely sure what the implications are -- would it be suitable to sign documents using multiple cryptographic functions (such as a signature containing SHA, MD5, and CRC32 hashes, along with the original filesize)? Maybe perform a simple, arbitrary transformation on the text content and use that to generate a seperate, complimentary MD5 or SHA hash?
Jasin NataelRe: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 here is that it is possible, probably in several good ways, to generate a couple of different files that have the same hash and also have meaningful data in them. The attacks found that generate seemingly random data with the same hashes can be used in ways that will let them apply to non-random, purposefully designed data.
The example they use is where some secretary gets her boss to sign a document, and then uses his signature on another document which gives her access she shouldn't have. It's a way to forge a digital signature on a document by having them sign another one that you specially crafted.
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 and kernel.org with microsoft.com in the above text.
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)
Re:These are important attacks.. (Score:2, Insightful)
Re:These are important attacks.. (Score:2)
A crafty employer would make the 'normal' document match the draconian one by adding crap to it, making the draconian document appear to be the original. Who'd have to explain things then?
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 simply remove it, then the jury might be less inclined to believe you.
Doubtful this sort of thing could happen with employment. A government contract on the other hand
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.
Re:These are important attacks.. (Score:2)
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.
I think that's insufficient to be able to mount the attack.
To do what these guys did, you need a format that can:
MP3s don't meet these criteria, nor do JPEG images. HTML files do, if you allow for Javascript or the like. I think "plain" HTML is inadequate.
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.
Given HTML e-mail, plus Javascript, yes. OTOH, interpreting Javascript in e-mails is a bad idea anyway.
Re:These are important attacks.. (Score:2)
There's plenty of scope for changing the files, we only need to select roughly 128-bits in each file to message about with to drive a collision.
I agree with your suggestion to use Javascript over HTML to "disguise" the change.
Simon.
Re:These are important attacks.. (Score:2)
Well, you can have two MP3s that sound the same even though they're different and you can have two jpegs that look the same even though they're different.
But you can't practically generate two MP3s or JPEGs that have *meaningful* differences, yet hash to the same value.
Re:These are important attacks.. (Score:2)
That's pretty irrelevent though as the whole point of this hack is that you change the sound or the image anyway, then add the extra data to make it hash correctly to a specified hash
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 OpenOffice.org, the default settings are to warn you when you open a document containing any macro code -- but the user can have turned off this feature.
I don't know about MS Office's binary format.
OpenOffice.org documents are simply Zip files of XML. (Yes, try renaming your OOo document's extention to ".zip" and unzipping it.) I know for a fact that I can take an OOo document written on Windows, move it to Linux, unzip it, and then re-zip it (using the "zip" command line tool) to get a smaller better compressed, but otherwise identical OOo document that opens in all versions of OOo. It may be possible to construct an OOo document that is a Zip, but where one or more zip file entries are completely UN-compressed, and therefore, where this technique could be used.
Re:These are important attacks.. (Score:2)
You don't even need JavaScript. A browser that implements some subset of CSS or even tables is enough. It's easy to hide content from a skimming reader, let alone the technically challenged.
You *might* be able to do it with CSS, but not tables. Hiding content isn't enough, you need to be able to dynamically select different content based on the result of a calculation on the hidden "random" junk. CSS allows you to use the functions in the XPath specification in some limited ways, so you might be able to finagle something. Plain tables aren't enough.
The junk would be obvious (Score:2)
A novice might miss it, but a trained eye could easily see the garbage.
What worries me more is executeables where you're depending on the hash to match. If the file sizes are approximately the same, it would be very easy to trick someone into running something that is actually something else.
Re:The junk would be obvious (Score:2)
Lets imagine a more devious employer. What if the junk was on the legitimate document? The employer has you sign the one with junk, and then when it goes to court, the employer claims that YOU generated a hash collision to write yourself an easier/better contract.
It works both ways. The junk could be on either document, and both parties have motives to forge a document.
Re:The junk would be obvious (Score:2)
Since this is an attack in which you create two documents, the party which created the document must be the would-be forger. I think your evil employer would have a hard time convincing the court that I wrote the document they had me sign.
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 party is involved who is naive to the document Bob signed and his intents.) This is effectively the scenario suggested in TFA, and because there is no alternate version of the document, Bob has no recourse (unlike the parent poster's suggestion).
To exploit this hole in MD5 (SHA-1, or whichever hashing function you like), you need to create two completely different documents, not two which are different versions of the same thing and can be compared by humans. That's the real hole: these documents need to be printed out (or rendered on a screen) and interpreted by humans who assume that the rendering process is trustworthy because it is complete and veracious. If humans natively read PostScript with the same ease we read English, for example, this kind of exploit wouldn't be possible.
Re:These are important attacks.. (Score:2)
I'm curious, do you get to take classes in that or is it graduate work? I'm currently in my undergrad at a school that doesn't have any cryptology courses. When I graduate in December I'll be heading off to the Navy to (hopefully) do crypto, but I wonder where civilian cryptology programs are.
Re:These are important attacks.. (Score:2)
This should be obvious to anyone. Any reasonably fast and efficient hash or encryption algorithm can be brute forced given enough time on a sufficiently large parallel machine. This means 1) Any truly effective hash or encryption must be slow, even on the latest hardware, and 2) any algorithm is reasonably secure today won't be secure against a dedicated attack by somebody with sufficient resources 10 years from now. Given the constantly advancing state of the art, any usable algorithm will eventually be broken; nothing can stay encrypted forever.
Re:These are important attacks.. (Score:2)
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's say you are going to transmit an n-bit message. Even if you don't transmit any information, an attacker knows that there are 2^n possible messages that you could transmit. If we assume that your message is compressed as much as possible, then before you transmit the message, all 2^n messages are equally likely (from an attacker's point of view).
So, you have n bits of data. We'll call this message P (the plaintext). Now, let's say you generate another n-bit random message, called K (the key). Finally, you xor P and K together to produce C (the ciphertext), which is also an n-bit message.
The theory behind the one-time pad says that if and only if there are at least 2^n equally-likely possibilities for K, then someone who only knows C cannot learn anything about P.
We can express this a different way. Let's say you have an invertible function, C = f(P), and:
Note that the function f is just a generic representation of the one-time pad algorithm and the key K, so similarly, we cam say that an attacker who knows nothing about the function f cannot learn anything about P from only C.
And that's the problem: every time you transmit a message (P) that isn't *completely* random, you give the attacker a little information about f, unless you completely change f every time you transmit a new message. This why you can never re-use a key in the one-time-pad system.
So let's say you have a key, K, that has fewer than 2^n equally-likely possibilities. Then, there are fewer than 2^n possible functions f. If there are still 2^n possible values for P, then an attacker can learn some information about P from C. So, if you don't want that to happen, you need to have 2^n possible functions for f.
So, you have 2^n equally-likely functions for f, and you need to use a different one for every message. In order to let the recipient know which function to use each time you transmit a message, you have to transmit at least n bits of information to the recipient. I think you can see where this is going...
If you were going to write an algorithm to implement the function f, the optimally-compressed description of the algorithm would have to be at least n bits long, and would need to be replaced for every new message that you send. It doesn't matter if f is an algorithm based on a DVD library, or a really complicated program. In order for the one-time pad to work (an attacker learns nothing about P from C), you need make sure that there are at least an additional n bits of information that the attacker knows nothing about.
So in your example, you'd still need to send a new 4GB (optimally-compressed) version of rand() for every 4GB message you send.
Nice try, though. Keep it up!
Re:These are important attacks.. (Score:2, Insightful)
Steps:
1. Write a very useful tool
2. Compile it
3. Tamper the file to get two almost identical versions, one exploitable, the other "secure"
4. Release the source and the secure binary
5. Wait for the tool to achieve widespread adoption based on its "security"
6. Overwrite the secure version with the exploitable one on your server and log the IPs of the people downloading it
7. Wait a little more
8. Use the exploit and gain access to the exploitable machines
9. Once you are in charge overwrite the exploitable version of the tool with the "secure" one - tripwire should not detect this
10. Party
Re:These are important attacks.. (Score:2)
Factor in the fact that it take 2^64 time to *brute-force* a collision in MD5 and the fact that we now have an attack that can find any collision in minutes on a laptop then I'd say it's pretty reasonable that someone can do it.
Simon.
Re:These are important attacks.. (Score:2)
Given that restriction, you then need to be able to generate a collision. And not just any collision, but a *specific* collision that has your malware or subtle contract alterations or whatever in it. Hashing is used as verification, so simple corruption is useless.
The flaws being found are not totally irrelevent, by any means, but they're theoretical mathematical attacks on hashing. The practical security of hashing as verification is not especially weakend.
Re:These are important attacks.. (Score:2)
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: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.
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)
Obvious solution (Score:2)
There are 2 reasons people do this. 1) decryption takes longer than computing a checksum. and 2) this would force everyone to decrypt the file in order to use it. Only paranoid people and those who realize bits get corrupted bother to verify checksums now.
Reliable solutions are entirely available, people just need to start using them. BTW, I'm no expert but I think there are simpler ways than that suggested above.
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 responsible for redistributing the software have bad intentions?
Re:What are the alternatives? (Score:2)
This generates a detatched signature named "THEFILE.asc".
The
'gpg --verify THEFILE.asc'
This method is already in pretty widespread use for open source software distribution. For example, Slackware has used for all official packages since 8.1.
Re:What are the alternatives? (Score:2)
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.
Re:Explanation of the attack (Score:2)
Nevertheless, it's a good way to shut the mouths of the ones who say that hash function attacks are still theoretical...
Re:Explanation of the attack -- enforcement issues (Score:2, Interesting)
It is an interesting attack, and IANAL, but I'd be curious about the legal ramifications. If I slip a carbon (ah... the way-back machine) in a stack of papers and ask someone to sign the top one without thus informing them, I think my stealth probably invalidates the additional document(s).
You could argue that there's a noticeable difference between pen and carbon -- making the copy hard to enforce -- but I'd argue the digital version is even easier: at least in the PS example, both "copies" of the document need to be present to preserve the hash.
In normal (pen/paper) signature situations, I get a copy of what I signed. The same ought to apply to digital sigs, resulting in a simple legal challenge to the validity of the document.
Not exactly useful for fraud... (Score:5, Insightful)
It's been around long enough... (Score:2)
Of course, MD5 passwords are probably still safe, for now (between maximum password lengths and the fact that this attack will have a hard time actually doing that), but it's only a matter of time.
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
Possible solution (Score:2, Insightful)
Is the answer then to create a hash that is in fact the sum of two distinct hashing alogrithms? For example, use MD5 and SHA1. Since the alogrithms use different methods, the set of collisions from one would not overlap the set from the second (or rather the overlap would be vanishingly small). And if the overlap was larger than you wanted - just keep adding different hash alogrithms until you are satisfied.
I realise that the computations involved aren't cheap, but it becomes a trade-off between security and speed - the more sure, the more time it will take.
Weak + weak = weak (Score:2)
Strong hash functions are difficult to design, and require a lot of research and testing.
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.
Re:Possible solution (Score:2, Informative)
You are assuming that I read hashing alogrithm threads, which I don't. If there is a reason why this wouldn't work, then please enlighten me.
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.
Re:7 bits difference (Score:2)
I don't that is exactly true.
From http://www.schneier.com/blog/archives/2005/02/sha
"collisions in the the full SHA-1 in 2**69 hash operations, much less than the brute-force attack of 2**80 operations based on the hash length."
2**69 is still a very large number, so you probably shouldn't be worried just yet. It isn't quite the same as the bit trick for MD5. If anyone knows of a bigger weakness in SHA-1, I would be interested to know.
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:2)
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...
You only need as much random data as fits in the size of the hash signature. I.e. for MD5, 128 bits is enough for at least 1 collision.
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.
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.
Re:So you're saying I shouldn't implement MD5 ... (Score:2)
I suspect that in the near future, signing will be done using two different hashes to seriously restrict the collision space.
Re:So you're saying I shouldn't implement MD5 ... (Score:2)
You could reasonably choose SHA256 or Whirlpool for some of those user-selectable hashes. SHA256 still has some safety margin against the new attacks and Whirlpool is a different kind of design.
Relative Resources: The Attackers' Advantage (Score:5, Interesting)
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].
It was only a matter of time (Score:2)
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:2)
Re:The provided exploit documents can be edited! (Score:2)
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!
No. The whole point of hashing that it is extremely difficult to figure out what *exactly corresponding edits* are, so the provided exploit documents cannot be edited. This is why these two postscript files are noteworthy: they are different, yet they hash to the same thing. Since the two postscripts are different, changing the same letter in both will NOT result in the same hash.
You still have to use the attack from Wang and Yu [WY05], so having these postscript files makes no difference to an attacker. Unless he happens to deal with Alice and Caesar, of course.
Re:The provided exploit documents can be edited! (Score:2)
Actually the textual part of both is the same, they just found some PS magic to choose between two 'sub-documents' in the same PS. Indeed one can trivially show that modifying both files will result in a collision since both files contain the text of both messages.
OTOH, in the real world, one would be hard pressed to change the contents of an existing document.
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.
what'd i tell ya'all (Score:2)
This has a solution (Score:2, Informative)
See http://en.wikipedia.org/wiki/Birthday_paradox [wikipedia.org] for details.
Basically if you have enough documents you will be able to find two with the same hash. Not to be mistaken with the difficulty of finding a document with the same hash as a GIVEN document. This cannot be avoided regardless of the hash.
To foil a birthday attack, NEVER agree to sign a given document. One must ALWAYS add some random junk to the document (clear text or hidden). This should be implemented in sofetware that helps in signing, but if the option isn't given, you can add a clear text "random" string.
Yossi
Re:huh? (Score:2, Funny)
Re:huh? (Score:2)
Re:huh? (Score:2)
I would have thought that with a name like yours, the answer would be obvious.
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.
Re:do you know how big 2^128 is? (Score:5, Funny)
Pfft, let me show you my porn collection.
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 one the birthday paradox works in your favor and you only need on average 2^80 trials for brute force. Wang has lowered that number to 2^64, which is uncomfortably small by today's standards and reckless by tomorrow's. SHA-256 produces a 256-bit hash: you do the math.
The big worry is that cryptographic attacks tend to inspire research that finds better attacks. There's an unquantifiable but real risk that SHA-1 could collapse altogether.
The crypto geeks are speulating that these weaknesses are inherent in any hash algorithm that can be calculated incrementally. Right now the output after block N of input depends only on blocks 1..N of input. If the intermediate result for block N depended on blocks N+1..EOF then the current attacks wouldn't work. Neither would hashing an input stream. Such a change would destroy the ability to hash a file in parallel with reading it.
Re:do you know how big 2^128 is? (Score:2)
Re:Speaking of 128 bit collisions, UUIDs and GUIDs (Score:2)
The GUID (as called by Microsoft) has it's history in the UUID, which was first "invented" by OSF as part of it's big DCE specs (long before Microsoft adopted the format and gave it a spiffy new name).
The UUID and GUID look alike, but the UUID was constructed in a much different manner than GUIDs seem to be nowdays. GUIDs are basically 128-bits of random data (usually made by passing pseudo-random seeds through a hash). UUIDs on the other hand contained structured data too in addition to randomness, to try to prevent accidental reuse. For instance the rightmost 48 bits come from the Ethernet MAC address if available. Other bits contained date/time information, process/thread ids, etc.
There was an expired Draft RFC [ietf.org] written in February 1998 which explained a lot of the technical details of GUIDs and UUIDs (surprisingly authored by Microsoft). You may still be able to find copies of it out on the net (the filename was "draft-leach-uuids-guids-01.txt")
Re:First post (Score:2)
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.
Re:Security Through Obscurity (Score:2, Informative)
Your ignorance is so appalling that I have a hard time deciding where to start.
First - this is about digital signatures, not about encryption - sharing the documents (by sending them over electronic media or otherwise) is needed.
Second - obfuscated algorithms ??? Open any book on encryption to learn that the strongest encryption algorhitms rely on completely documented algorhitms - security through obscurity is so 80's...
My suggestion - try to have something worth saying before making suggestions.
Happy Posting.
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 things, the need to hide is temporary. If the hidden thing stays hidden as long as it needs to stay hidden, there is nothing wrong with it.
Know the limitations on the technology you use, and know the parties with which you exchange information. Those two rules alone, if followed, will probably provide more than adequate real-world defense. Perfect? No. Good enough. Statistically, yes.
Re:big oops (Score:2, Informative)
Another solution that should work quite well is to combine hashes: (md5+sha1) is definitely much stronger as you would need to find a collision that works for both algorithms at the same time.
Possible, but not likely.
Re:Misuse of MD5? (Score:2)
Well, that's impossible - but that's not even the point. The entire point of hashing algorithms is that they are one way, so you're not (supposed to be) able to retrieve the original.
But anyway, their 2-way equivalent is encryption, not compression. The idea of strong hashing algorithms (like MD5 was thought to be before it was broken) is that it's computationally infeasible to find a collision, so yes, one of its uses is to authenticate data. For a quick check for bit errors, that's what weak hashing mechanisms such as CRC are for.
Re:Just use multiple hash methods (Score:2, Informative)
Not impossible, just less probable. Combining algorithms effectively increases the size of your fingerprint. The probability of a duplicate is a function of original data size and its proportion to the fingerprint data size. The closer those two data sizes are, the lower the probability of duplicates.
It may seem difficult to pull off now, but eventually someone will make a nice, clever script to do it and then the script-kiddies will have a field day.