Re: [Haifux] MD5 collisions
Hello Muli (and welcome back). When and where are these lectures going to take place? Thanks, Eli Muli Ben-Yehuda wrote: On Tue, Aug 17, 2004 at 11:57:45AM +0200, Eli Billauer wrote: (and sorry for not coming yesterday. I really wanted to hear the combined lecture, but was under the impression that it's only next week :((( ) We'll be giving the same talk at Telux and at IBM HRL. You're welcome to come to either... Cheers, Muli -- Web: http://www.billauer.co.il
Re: [Haifux] MD5 collisions
On Wed, Aug 18, 2004 at 11:46:29AM +0200, Eli Billauer wrote: Hello Muli (and welcome back). Thank you When and where are these lectures going to take place? Telux: Sept 5. See http://www.cs.tau.ac.il/telux/ IBM HRL: Sept 7. Contact me offlist for details. Cheers, Muli -- Muli Ben-Yehuda http://www.mulix.org | http://mulix.livejournal.com/ signature.asc Description: Digital signature
Re: [Haifux] MD5 collisions
Orr Dunkelman wrote: This is true, but has no meaning. A paper to be presented tomorrow in Santa Barbara by Antoine Joux (who found the collision in SHA-0), explains that to attack such a scheme: h(x) = SHA-1(x) || MD5(x) is as hard as breaking the harder between the two (under birthday attacks). So a generic attack of finding collisions in SHA-1(x)||MD5(x) requires only 2^80 computations (and not 2^160 as one might expect). Also, it is very likely that if the SHA-1 results will be obtained in similar methods to the ones of MD5, then his ideas will be applicable also for the new attacks. The paper was pretty scarce on details. What is the attack method? Also, I wrote a newbie friendly explanation of what happens there in my blog. http://www.israblog.co.il/35850. Shachar -- Shachar Shemesh Lingnu Open Source Consulting ltd. http://www.lingnu.com/ -- Haifa Linux Club Mailing List (http://www.haifux.org) To unsub send an empty message to [EMAIL PROTECTED]
Re: [Haifux] MD5 collisions
Hi, On 08/18/2004 04:01 PM, Shachar Shemesh wrote: Also, I wrote a newbie friendly explanation of what happens there in my blog. http://www.israblog.co.il/35850. ... which includes: , , , . , . , , , . ,. As far as I can tell, the current attacks only let you choose an arbitrary prefix and obtain two messages, having the same hash, that are random-looking except for both having the chosen prefix. How is this sufficient for performing the cheating you describe? Also, in regard to your taxonomy, one can also distinguish between finding a preimage given a hash, and finding a *second* preimage of the hash of a given message. In general the latter may be easier. For example, consider the Rabin one-way function (i.e., squaring modulo a nasty prime); we don't know how to efficiency compute the modular square root of a given number, but given one square root it only takes one keystroke to find another one. Of course, that's not a secure hash function for quite a few other reasons, but it's quite thinkable that some common hash functions have similar properties. Eran -- Haifa Linux Club Mailing List (http://www.haifux.org) To unsub send an empty message to [EMAIL PROTECTED]
Re: [Haifux] MD5 collisions
Hello Orr all, any proof-of-concept code to try out? (and sorry for not coming yesterday. I really wanted to hear the combined lecture, but was under the impression that it's only next week :((( ) Eli Orr Dunkelman wrote: A recent research found how to produce collisions in MD5 (from md5sum) in a small amount of time (1 hour + 5 minutes). -- Web: http://www.billauer.co.il -- Haifa Linux Club Mailing List (http://www.haifux.org) To unsub send an empty message to [EMAIL PROTECTED]
Re: [Haifux] MD5 collisions
http://eprint.iacr.org/2004/199 paper. The code exist The technique is quite blurry in the 4-page paper... On Tue, 17 Aug 2004, Eli Billauer wrote: Hello Orr all, any proof-of-concept code to try out? (and sorry for not coming yesterday. I really wanted to hear the combined lecture, but was under the impression that it's only next week :((( ) Eli Orr Dunkelman wrote: A recent research found how to produce collisions in MD5 (from md5sum) in a small amount of time (1 hour + 5 minutes). -- Orr Dunkelman, [EMAIL PROTECTED] Any human thing supposed to be complete, must for that reason infallibly be faulty -- Herman Melville, Moby Dick. Spammers: http://vipe.technion.ac.il/~orrd/spam.html GPG fingerprint: C2D5 C6D6 9A24 9A95 C5B3 2023 6CAB 4A7C B73F D0AA (This key will never sign Emails, only other PGP keys.) -- Haifa Linux Club Mailing List (http://www.haifux.org) To unsub send an empty message to [EMAIL PROTECTED]
Re: [Haifux] MD5 collisions
AFAIK (from a person who heard their technique) it is easy to tweak an ISO. C code might be a bit harder, but it looks a bit technical in nature to solve the problem as well. On Tue, 17 Aug 2004, Eli Billauer wrote: Orr Dunkelman wrote: http://eprint.iacr.org/2004/199 paper. The code exist The technique is quite blurry in the 4-page paper... Blurry indeed. And I'm sure the code exists, but the question is whether one can try it...? It's always sad to find out that a security measure fails, but is it time to panic yet? For example, if MD5 is used to hash C code or tarballs, how possible is it to create an alternative, legal C code or tarball with the same MD5? As for CD ISO images: Is it possible to create, say, 600 MB of any data I want, and then use the rest of the data space (unallocated as far as the CD concerns) to get the MD5 to what I want? This would be a real danger. My point is: It's quite easy to tell everyone not to use a technique because someone has found some problem with it, but before the mess begins: How real is the threat? Eli -- Orr Dunkelman, [EMAIL PROTECTED] Any human thing supposed to be complete, must for that reason infallibly be faulty -- Herman Melville, Moby Dick. Spammers: http://vipe.technion.ac.il/~orrd/spam.html GPG fingerprint: C2D5 C6D6 9A24 9A95 C5B3 2023 6CAB 4A7C B73F D0AA (This key will never sign Emails, only other PGP keys.) -- Haifa Linux Club Mailing List (http://www.haifux.org) To unsub send an empty message to [EMAIL PROTECTED]
Re: [Haifux] MD5 collisions
On Tue, Aug 17, 2004 at 11:22:27AM +0300, Orr Dunkelman wrote: I'm sad to announce that MD5 is no longer considered secure. Eeek. Any inside info on the SHA-1 break rumored? (http://www.freedom-to-tinker.com/archives/000661.html) Cheers, Muli -- Muli Ben-Yehuda http://www.mulix.org | http://mulix.livejournal.com/ signature.asc Description: Digital signature
Re: [Haifux] MD5 collisions
AFAIK, Eli (my advisor) is working for quite some time on this. I hope he'll succeed. When this happens - use tiger. On Tue, 17 Aug 2004, Muli Ben-Yehuda wrote: On Tue, Aug 17, 2004 at 11:22:27AM +0300, Orr Dunkelman wrote: I'm sad to announce that MD5 is no longer considered secure. Eeek. Any inside info on the SHA-1 break rumored? (http://www.freedom-to-tinker.com/archives/000661.html) Cheers, Muli -- Orr Dunkelman, [EMAIL PROTECTED] Any human thing supposed to be complete, must for that reason infallibly be faulty -- Herman Melville, Moby Dick. Spammers: http://vipe.technion.ac.il/~orrd/spam.html GPG fingerprint: C2D5 C6D6 9A24 9A95 C5B3 2023 6CAB 4A7C B73F D0AA (This key will never sign Emails, only other PGP keys.) -- Haifa Linux Club Mailing List (http://www.haifux.org) To unsub send an empty message to [EMAIL PROTECTED]
Re: [Haifux] MD5 collisions
On Tue, Aug 17, 2004 at 11:57:45AM +0200, Eli Billauer wrote: (and sorry for not coming yesterday. I really wanted to hear the combined lecture, but was under the impression that it's only next week :((( ) We'll be giving the same talk at Telux and at IBM HRL. You're welcome to come to either... Cheers, Muli -- Muli Ben-Yehuda http://www.mulix.org | http://mulix.livejournal.com/ signature.asc Description: Digital signature
Re: [Haifux] MD5 collisions
Orr Dunkelman wrote: I'm sad to announce that MD5 is no longer considered secure. A recent research found how to produce collisions in MD5 (from md5sum) in a small amount of time (1 hour + 5 minutes). I read that to say attacker can find two messages, A and B, that have the same hash. Now, the questions: 1. Do A and B have to follow some mathematical rule? I.e. - is it possible to say This particular A cannot be the result of this attack? 2. Does the attack still apply if one of them is chosen in advance? I.e. - is it possible for you to compute an identical hash to one that matches a message I already wrote? If you try to recall the old days when you were a mere BA student and learned Crypto, one of the homework exercises of the course was along the following line: 1. Read the specs for Sha1 2. Show that any two messages that have the following structure have the same SHA1 hash. (You gotta love studying with Eli Biham :-) That attack, in and on itself, was not sufficient to say that SHA1 is broken, because the chances your original message follow that format is not high. Is this attack of a different nature? Shachar -- Shachar Shemesh Lingnu Open Source Consulting ltd. http://www.lingnu.com/ -- Haifa Linux Club Mailing List (http://www.haifux.org) To unsub send an empty message to [EMAIL PROTECTED]
Re: [Haifux] MD5 collisions
I read that to say attacker can find two messages, A and B, that have the same hash. Now, the questions: 1. Do A and B have to follow some mathematical rule? I.e. - is it possible to say This particular A cannot be the result of this attack? Currently yes. but soon not. It's only a technical matter to be solved. 2. Does the attack still apply if one of them is chosen in advance? I.e. - is it possible for you to compute an identical hash to one that matches a message I already wrote? Currently no. In the near future my guess would be yes. If you try to recall the old days when you were a mere BA student and learned Crypto, one of the homework exercises of the course was along the following line: 1. Read the specs for Sha1 2. Show that any two messages that have the following structure have the same SHA1 hash. (You gotta love studying with Eli Biham :-) I don't recall such an exercise. I recall an exercise where we were requested to forge DSA signatures That attack, in and on itself, was not sufficient to say that SHA1 is broken, because the chances your original message follow that format is not high. Is this attack of a different nature? yes. There are REAL collisions. Shachar -- Orr Dunkelman, [EMAIL PROTECTED] Any human thing supposed to be complete, must for that reason infallibly be faulty -- Herman Melville, Moby Dick. Spammers: http://vipe.technion.ac.il/~orrd/spam.html GPG fingerprint: C2D5 C6D6 9A24 9A95 C5B3 2023 6CAB 4A7C B73F D0AA (This key will never sign Emails, only other PGP keys.) -- Haifa Linux Club Mailing List (http://www.haifux.org) To unsub send an empty message to [EMAIL PROTECTED]
