Re: [cryptography] Near-collisions and ECC public keys
On Mon, Dec 29, 2014 at 8:18 AM, Florian Weimer f...@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.) ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
[cryptography] Near-collisions and ECC public keys
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. This is not true for raw RSA keys because weak keys are in close Hamming distance to any given reference key (I think, I haven't verified this). So you'd need to compare the full (n, e) pair, bit by bit, or compare a cryptographically strong digest of them (the OpenPGP approach, more or less). ECC public keys are small, and a digest will not provide much of a length reduction. But I wonder if the digest would still make sense to perturb the bits, so that it is not possible to create a near-collision. Do ECC public keys behave like RSA keys in this regard? Does this depend on the chosen encoding format? ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Near-collisions and ECC public keys
On Mon, Dec 29, 2014 at 8:18 AM, Florian Weimer f...@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 I believe collisions in the former are already well known. ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
