Slashdot Mirror
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."
When you've got nothing on the line, you're not going to be as careful about cryptography as someone who does.
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.....
Prediction for end of Universe #42: Fencepost error in Quantum_bogosort.cpp
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.
There is the remote chance that several keys will have the same "short" Key ID. The "long" Key ID decreases the risk of a collision, but can be more unwieldy to use.
Considering that certain versions of the GnuPG man page actually explicitly cover this, I'd say this is a non-story. Just use the long key ID if you're worried.
With 32-bit short keys, there is a time complexity of 2^32.
That is only if you need to match one specific key.
To just get a match between two 32-bit keys, you on average need to generate less than 80000 keys.
But this is irrelevant, because the short ID isn't meant for positive authentication. It's a negative indicator - if the short key doesn't match, you don't need to check further, but if it does match, you do. Anyone who uses it for positive authentication deserves what they get.
It has been known for many years that two OpenPGP keys might have the same key ID. After all, a 36-bit hash of a 1024-bit or 4096-bit key cannot be unique.
However, no key fingerprint collision is yet known when the key-type and key-length are both the same. That is why, when verifying the ownership of a key, the owner is supposed to supply the type (RSA vs DH/DSS), the key-length (not the key ID length), and the key fingerprint (128 bits for RSA and 160 bits for DH/DSS).
In Laroia's case, neither the key-types nor the key-lengths were the same for the two keys that had the same key ID.
Note: I indicate "no key fingerprint collision is yet known". Such a collision is mathematically possible, but it is extremely difficult (not impossible) to contrive.
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.
http://www.red-bean.com/kfogel
Which surprises you most?
1. That GPG developers and users have ignored the well-known problem (in security circles) of the Birthday Paradox? ;)
- or -
2. That there are > ~45k GPG users such that this even is more likely than not to occur.
Seriously though, a 1 in 65536 chance of a collision doesn't seem acceptable to me.
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.
make imaginary.friends COUNT=100 VISIBLE=false
If you read the bug report, you'll see that the whole issue is that GPG doesn't exhibit the behaviour you describe!
Imho, the reprehensible behaviors of our governments over the last decade has made encrypting our communications a moral imperative. I have "nothing on the line" personally, but..
There are many activists in the world doing important things to undermine harmful sources of authority. And my own usage of cryptography helps prevent governments and corporations from identifying the interesting traffic quite so easily.
If you have an Android device, then you should check out the Guardian Project.
The Christian religion has been and still is the principal enemy of moral progress in the world. -- Bertrand Russell
This was actually a preimage attack -- that is, I intentionally created a collision for 0x70096AD1.
No birthday paradox required. I looped through the entire key space. It takes, as written in the article, less than a few hours on a regular netbook.
|/usr/games/fortune
... and nobody cares, because anyone with a clue already knew this, and it has zero effect on the effectiveness of GnuPG.
Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun