Re: MD5 collisions in one minute
On 3/17/06, Weger, B.M.M. de [EMAIL PROTECTED] wrote: You might be interested in knowing that my MSc student Marc Stevens has found a considerable speedup of MD5 collision generation. His improvements of Wang's method enables one to make MD5 collisions typically in one minute on a PC; sometimes it takes a few minutes, and sometimes only a few seconds. His paper (shortly to appear on the Cryptology ePrint Archive) can be found on http://www.win.tue.nl/hashclash/, where we've also made his software available (source code and a Win32 executable). Thanks for interesting info! btw, do you aware of another MD5 Collisions generating software (requiring ~45 minutes per collision) available at http://www.stachliu.com/collisions.html I did not find any references to it in Marc's website/paper. Max - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
In the light of day and less inebriated, I'd like to clarify some of what I wrote last night, and maybe expand a bit. My original account wasn't what I'd like to think of as a record for posterity. Greg. At 13:11 2004-08-18 +1000, Greg Rose wrote: Xiaoyun Wang was almost unintelligible. This was not meant as a criticism. It just meant you had to concentrate really hard. Her English is much better than my Chinese. But the attack works with any initial values, which means that they can take any prefix, and produce collisions between two different suffixes. The can produce the first collision for a given initial value in less than an hour, and then can crank them out at about one every 5 minutes. As mentioned previously, the idea is to produce a good partial collision with the first blocks input to the hash, and then from two similar starting points, find subsequent blocks that correct them back to the same output. So, for a given input chaining vector, it takes about an hour to get the partial collisions in the first input block. From there, they can compute subsequent second blocks to produce the collisions in a few minutes. Note that they did two entirely new collisions for MD5 overnight, communicating back to China, when they found out about the endianness problems. No-one can now argue that they can't find collisions at will. It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it. With further hindsight, and Phil Hawkes' help, I understand now. The technique needs to alternate between single bit (xor) differences and subtractive differences, with careful conditioning of the bits affected to make sure the right carries do, or don't, propagate. This is explained in Phil's upcoming paper about SHA-2 cancellations, which was presented later in the rump session. That should be on e-print in the next couple of days. The Chinese team is also writing a much more detailed paper, but it will take longer. There has been criticism about the Wang et. al paper that it doesn't explain how they get the collisions. That isn't right. Note that from the incorrect paper to the corrected one, the delta values didn't change. Basically, if you throw random numbers in as inputs, in pairs with the specified deltas, you should eventually be able to create your own MD5 collisions for fun or profit. How they got this insight, we'll have to wait for... but the method is already there. Greg. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
At 00:49 2004-08-19 +1000, Greg Rose wrote: There has been criticism about the Wang et. al paper that it doesn't explain how they get the collisions. That isn't right. Note that from the incorrect paper to the corrected one, the delta values didn't change. Basically, if you throw random numbers in as inputs, in pairs with the specified deltas, you should eventually be able to create your own MD5 collisions for fun or profit. This, too, is overly simplistic an explanation. Doing it like this would effectively multiply the work for the near-collision in the first block and the correction in the second block, which is not what you want. To be efficient, you need to divide-and-conquer; make random pairs of first blocks until you find a pair that have the right very small difference in their chaining outputs. Then, from those first blocks, try to find second blocks that work. This adds the amounts of work, rather than multiplying them. Apologies for any confusion. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: MD5 collisions?
At 12:04 2004-08-18 -0400, Whyte, William wrote: There has been criticism about the Wang et. al paper that it doesn't explain how they get the collisions. That isn't right. Note that from the incorrect paper to the corrected one, the delta values didn't change. Basically, if you throw random numbers in as inputs, in pairs with the specified deltas, you should eventually be able to create your own MD5 collisions for fun or profit. So this is big. This doesn't just break collision resistance, it breaks second preimage resistance. Is that right? If I've understood it correctly, the answer is sort of. For a given input, it seems that there is some non-trivial chance that the input+delta would produce the same hash, that is, a 2nd preimage. But the probability, for any single arbitrary message, might be quite low (especially since you'd have to multiply the probabilities of success for the first and second blocks; see my other message just before this one). But it seems to me that that probability would still be much better than the 2^-n that it should be for an n-bit hash. For example, the MD5 collision in 2^40 work is really two separate near-collisions, each taking a bit less than 2^40 work. If you apply the deltas to a random message M, both blocks at the same time, it seems to me that the probability of success is about 2^-80; it either works or it doesn't. But that 2^-80 is a much better chance than you would have had for two random messages (which is really message M and a random delta). But I could also be mistaken on this. Greg. Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
On Thu, 19 Aug 2004 00:49:17 +1000, Greg Rose [EMAIL PROTECTED] wrote: It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it. With further hindsight, and Phil Hawkes' help, I understand now. The technique needs to alternate between single bit (xor) differences and subtractive differences, with careful conditioning of the bits affected to make sure the right carries do, or don't, propagate. This is explained in Phil's upcoming paper about SHA-2 cancellations, which was presented later in the rump session. That should be on e-print in the next couple of days. The Chinese team is also writing a much more detailed paper, but it will take longer. There has been criticism about the Wang et. al paper that it doesn't explain how they get the collisions. That isn't right. Note that from the incorrect paper to the corrected one, the delta values didn't change. Basically, if you throw random numbers in as inputs, in pairs with the specified deltas, you should eventually be able to create your own MD5 collisions for fun or profit. How they got this insight, we'll have to wait for... but the method is already there. How likely is it that this attack could be extended to creating common-prefix collisions? This is equivalent to specifying two IVs for the two hashes. Looking at X.509 ASN.1, it seems like it would be pretty easy to construct a certificate request such that, if you could predict the certificate serial number you were to be issued, you could create a hash collision in an X.509 certificate: You would construct two strings, each the same length, an even multiple of 512 bits long, which contained the prefix of the certificate you were going to be issued and the prefix of the certificate you would like to claim to have been issued (P1 = authentic prefix, P2 = forged prefix). The trailing part of each prefix would be the first few bits of the value of n in the RSA key. These first few bits can be different in P1 and P2, and randomly selected, as long as they begin with a 1. Call the first few bits of n in P1 p1, and the first few bits of n in P2 p2. You would take IV1 = internal state of MD5 after hashing P1 and IV2 = internal state of MD5 after hashing P2. You can tweak the first few bits of n if you want IV1 and IV2 to have a particular relation, as long as it's not infeasible to find that relation. Then find two 1024-bit 2-block messages, M1, and M2, such that they create a collision. Define v1 = p1 concatentated with M1, and similarly for v2. Calculate D = abs(v1-v2). Factor D, finding a 1024-bit prime that evenly divides D (i). If you can't easily factor D, or it doesn't yield a 1024-bit prime factor, find another collision pair. Now construct the last bits of n (call them t), which will be used in both requests, such that n1 = v1 concatentated with k and n2 = v2 concatenated with k are both equal to i times j1 and j2 (each 1024-bit primes). I think it may be possible to acclerate it, but even if you just have to calculate collisions until it's true, you should be able to find a collision D and a value k that gives primes i, j1, and j2 once in every ~30 million collisions. (I'm taking a stab in the dark that values of D that have a single 1024-bit factor have 1/300 density, but this is demonstrably worst-case.) If you can find such a collision with 5 minutes of CPU time, the attack will take, at worst, 275 CPU-years. This is university-feasible. Of course, I don't have any idea how hard it is to extend the known attack with common IVs to one in which the IVs are not common. I'd recommend that anyone operating a CA choose serial numbers which are long unpredictable; if you want some structure, append a random 128 bit value to your structure. - Tim - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
Eric Rescorla wrote: Check out this ePrint paper, which claims to have collisions in MD5, MD4, HAVAL, and full RIPEMD. http://eprint.iacr.org/2004/199.pdf The authors claim that the MD5 attack took an hour for the first collision and 15 seconds to 5 minutes for subsequent attacks with the same first 512 bits. So what's the status?, the MD5 collisions has been confirmed by Eric Rescorla (taken the type into consideration), the MD4 by David Shaw, what about Haval and RipeMD?. I did a test on the RipeMD results and couldn't get the results written. Anybody else having the same problems? Any news on Antoine Joux and his attack on SHA-0? how did he create the collision previously announced on sci.crypt? Regards, Mads Rasmussen Open Communications Security - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: MD5 collisions?
At 14:12 2004-08-17 -0300, Mads Rasmussen wrote: Eric Rescorla wrote: Check out this ePrint paper, which claims to have collisions in MD5, MD4, HAVAL, and full RIPEMD. http://eprint.iacr.org/2004/199.pdf The authors claim that the MD5 attack took an hour for the first collision and 15 seconds to 5 minutes for subsequent attacks with the same first 512 bits. So what's the status?, the MD5 collisions has been confirmed by Eric Rescorla (taken the type into consideration), the MD4 by David Shaw, what about Haval and RipeMD?. I did a test on the RipeMD results and couldn't get the results written. Anybody else having the same problems? Any news on Antoine Joux and his attack on SHA-0? how did he create the collision previously announced on sci.crypt? Eli Biham -- has collisions on 34 (out of 80) rounds of SHA-1, but can extend that to probably 46. Still nowhere near a break. Antoine Joux -- his team announced the collision on SHA-0 earlier this week. There is concentration on the so-called IF function in the first 20 rounds... f(a,b,c) = (a b) ^ (~a c). That is, the bits of a choose whether to pass the bits from b, or c, to the result. The technique (and Eli's) depends on getting a near collision in the first block hashed, then using more near collisions to move the different bits around, finally using another near collision to converge after the fourth block hashed. This took 20 days on 160 Itanium processors. It was about 2^50 hash evaluations. Xiaoyun Wang was almost unintelligible. But the attack works with any initial values, which means that they can take any prefix, and produce collisions between two different suffixes. The can produce the first collision for a given initial value in less than an hour, and then can crank them out at about one every 5 minutes. It seems to be a straightforward differential cryptanalysis attack, so one wonders why no-one else came up with it. The attack on Haval takes about 64 tries. On MD4, about 4 tries. RIPE-MD, about 2 hours (but can improve it). SHA-0 about 2^40 (1000 times better than Joux). Xuejia Lai clarified that the paper on E-print has been updated with correct initial values. They were initially byte-reversed, which they blamed on Bruce Schneier. Greg. Regards, Mads Rasmussen Open Communications Security - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED] Greg RoseINTERNET: [EMAIL PROTECTED] Qualcomm Australia VOICE: +61-2-9817 4188 FAX: +61-2-9817 5199 Level 3, 230 Victoria Road, http://people.qualcomm.com/ggr/ Gladesville NSW 2111/232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
