GnuPG Short ID Collision Has Occurred.

kfogel writes "Asheesh Laroia now has two GPG different keys with the same short ID (70096AD1) circulating on keyservers. One of them is an older 1024-bit DSA key, the other is a newer 4096-bit RSA key. Oops. Asheesh argues that GPG's short IDs are too short to be the default anymore — collisions are too easy to create: he did it on purpose and openly, but others could do it on purpose and secretly. More discussion (and a patch by dkg) are in this bug report."

Comments

Above post is ignorant

[robbak]

Having done the most basic of research, I have found out that GNUpg short collisions are everyday events. Which makes me wonder what the point of the article was.....

So?

[cloudmaster]

Doesn't this just make it more annoying to do searches, since that key (really a "key name") isn't unique? The encryption/decryption/signing uses the whole big key, right? So this would strike me as a client problem whose impact is limited to being able to verify a signature or decrypt something encrypted. It's seemingly more a nuisance than an actual security problem; you shouldn't be trusting keys from unknown sources, and it's easy enough to revoke and reissue keys if you end up having a conflicting index.

Re:So?

[mgiuca]

This. There is no problem here. The system is explicitly designed for the key id to be collidable. That is precisely why there is such a thing as a key fingerprint. The 32-bit key ID was never intended to be used to verify the validity of a key, merely for quickly identifying a key. The worst that can happen if two keys have the same ID is you are presented with two keys and have to look more closely to decide which one you want. The 180-bit fingerprint is used to verify a key and should be resistant to collisions for many many years.

The only problem is if people are using key IDs for verification, in which case it is a user error. Therefore, the lesson of this story is that if you want to know whether a key matches the one you were expecting, you need to look at the whole fingerprint, NOT the key id. That is why when you sign someone's key, they give you the fingerprint, not just the id.

Thanks for clarifying -- I should have researched.

[kfogel]

I should have done that research before posting -- thank you for clarifying the situation.

There is still a bug here, in that (according to the linked bug ticket) even if one *requests* a key using a longer ID, from a keyserver that can handle the request, GPG transforms it to the short ID and then returns you all the keys that match. That seems like non-optimal behavior, given that the user asked carefully, and the server could have answered, if only GPG would transmit the true request.

However, that's a slightly different problem from what I originally posted, so I'm glad you replied.

Collisions in a 32-bit space....

[gstrickler]

Collisions of random numbers with approximately equal distribution across the sample space are variations of the classic "birthday problem". And, with a 32-bit sample space, you have a 50% chance of a collision with slightly fewer than 77,500 entries.

I tried calculating it for a 64-bit hash, but the online calculator I used using was apparently using a linear calculation and didn't validate the input. It timed out after about 15 minutes. Oops, sorry I hammered the server. Maybe next time he'll validate the input and maybe even use a more efficient algorithm.

So, lets just say it'll take ~ (77500^2) *.8 ~ 4.8E9 IDs for a 64-bit hash to have a 50% chance of a collision. Take it up to 80 or more bits and the likelihood of a collision becomes very small even if everyone on the planet has an ID.

Re:Which surprises you most?

[Anonymous Coward]

Paragraph 1: "You'd have to be stupid not to understand the birthday paradox."

Paragraph 2: "I don't understand the birthday paradox."