The following is a long ramble on how to make PKIX certificates more resistant to the recently-announced attacks on hash collisions. If that lead sentence does not interest you, I can assure you the rest of this posting will not either.
Some of what I say below may be wrong and/or incomplete. I fully intend to update this entry over time. Feel free to write me if you find something that needs to be changed.
Potential collision-reduction attacks on PKIX certificates
Some parts of the cryptography community have started to think about what it might mean if someone devises an effective collision attack on PKIX certificates where you can have two certificates with different identities that have the same hash value. In RFC 4270, which I blogged about the other day, Bruce Schneier and I describe a nice construction by Arjen Lenstra and Benne de Weger which allows an attacker to create two certificates that have the same hash; the certificates have the same identity but different public keys, starting with a Wang-style collision reduction. Lenstra and de Weger call this a "construction" instead of an "attack" because no one has come up with a believable attack scenario for it.
Many folks have told me that they are worried that this construction might be able to be extended to allow two certificates with different identities (and, of course, the same public key) to have the same hash value. This would clearly be a valuable, and therefore devastating, attack: the attacker could fool a CA into issuing a certificate for a "good" identity, and that certificate could be used with a "bad" identity as well.
Edited Dec. 5 based on a discussion with Eric Rescorla to show that the downside of the "Add unpredictability to the certificate serial number" option is not as bad as I had said at first.
Edited Dec. 9 based on a discussion with Hugo Krawczyk to add a short discussion of randomized hashes as alternative new hash functions.
More ...
Posted by lookit at December 3, 2005 09:58 PM