finding key pairs with colliding fingerprints (Re: How thorough are the hash breaks, anyway?)

[Adam Back]

You would have to either:

- search for candidate collisions amongst public keys you know the
private key for (bit more expensive)

- factorize the public key after you found a collision

the 2nd one isn't as hard as it sounds because the public key would be
essentially random and have non-negligible chance of finding trivial
factors.  (Not a secure backdoor, but still create a pretty good mess
in DoS terms if such a key pair were published).

The latter approach is what I used to create a sample dead-fingerprint
attack on a PGP 2.x fingerprints.

http://cypherpunks.venona.com/date/1997/06/msg00523.html

(No need to find hash collision even tho' md5 because it has another
bug: the serialization has multiple candidate inputs).  So I just
searched through the candidate inputs for one I can factor in a few
minutes.

Adam

On Fri, Aug 27, 2004 at 12:22:26AM +0100, Ian Grigg wrote:
> Correct me if I'm wrong ... but once finding
> a hash collision on a public key, you'd also
> need to find a matching private key, right?
> 
> >If someone finds a collision for microsoft's windows update cert (or a
> >number of other possibilities), and the fan is well and truly buried
> >in it.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com