[cryptography] Near-collisions and ECC public keys

Florian Weimer fw at deneb.enyo.de
Tue Dec 30 07:41:20 EST 2014


> On Mon, Dec 29, 2014 at 8:18 AM, Florian Weimer <fw at deneb.enyo.de> wrote:
>> To check an OpenPGP fingerprint for correctness, it is sufficient (for
>> practical purposes) to compare the leading and trailing eight
>> hexadecimal digits, and perhaps a few digits in the middle.
>
> It is, only if you prefer these odds...
> 16^16/2^64 = 1.00
> 16^19/2^76 = 1.00

Huh?

> I believe collisions in the former are already well known.

Producing a colliding pair isn't *that* hard (it's been done for the
key ID part in V4 keys), but computing a partial 64-bit collision for
a specific key is still expected to be quite expensive.

(The chosen-prefix collisions for MD5 should completely break V3
certification signatures, but I don't think anything has been
published yet.)


More information about the cryptography mailing list