This paper, for which there is more explanation at this site, will probably cause a great deal more gnashing of teeth in the crypto community. It shows how you can create a collision in MD5 even starting with different messages. To make their point more clearly, the authors create two certificates with the same signature that have different identifiers.
To be sure, this is a big advance from the current state of the art. Until now, all of the hash collision work started with two identical message beginnings and added two different middles. This paper shows that you can start with two different beginnings that are chosen by the attacker and still create a collision in a reasonable amount of effort.
However, it does not change the state of the world with respect to the safety of cryptography in day-to-day use. The authors are careful to call their work a "construction" instead of an "attack" because it is not clear that there is a practical negative use for the work. The paper lists some suggested areas for more research where target collisions might yield real attacks. It appears that, for now, this construction is only mountable on MD5 due to the amount of work required, although it is very likely that a similar construction would work against SHA-1 with a lot more effort.
A few conclusions I draw from the paper:
- Certificate authorities (CAs) should only be signing certificates with algorithms using SHA-1 (although we have already known that for a few years)
- CAs should be using serial numbers that include random values in order to thwart this and earlier collision constructions
- The standards community should be putting more effort into signing algorithms that allow the signer to add random values in the signature
The latter point is probably the most controversial. The cryptography community is focused on creating new hash functions that will be more resistant to collisions. Yet it is still not clear that the collision-resistance of a hash function means anything except when the hash is used in a signature. Therefore, fixing the signature functions might be the quickest and most effective way to avoid current and future collision-resistance problems. Shai Halevi and Hugo Krawczyk have begun this work; the rest of the community should start thinking about whether this is sufficient and, if so, how we can implement it.
Update 10/25/06: The paper is now available on the venerable Cryptology ePrint Archive . I am amazed at how little people seem to care about the announcement, given how so many people were falling all over themselves over earlier announcements that were much less threatening than this.Not that I think this is at all threatening in a practical sense, just that being able to create collisions based on different starting inputs is much more serious than needing to use the same inputs.
My feed