GnuPG Short ID Collision Has Occurred. 110
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."
Let's face it (Score:5, Insightful)
Re:Let's face it (Score:5, Insightful)
Re: (Score:3, Interesting)
Re:Let's face it (Score:5, Insightful)
While I agree with the sentiment, what is possible for one person to know is wildly different for different people. While many of us here know a great deal about how a lot of technology works, many more people out there in the world just don't have the aptitude for it but know and understand all sorts of other things that we're not easily able to wrap our heads around.
Re: (Score:3, Interesting)
there is far too much data to decode the matrix my friend. this is why we have specialists!. want to trust your mechanic with pulling your teeth out?
Re:Let's face it (Score:5, Insightful)
Exactly! If I sell you a television, I don't expect users to know exactly how the television works. Most won't (especially children). The users of the television aren't specialists and aren't expected to know how it works, just how to use it.
Those who specialize in making televisions are expected to know how it works and they're expected to deliver a product that works as expected. If it fails by design, the user doesn't care why, and it's the manufacturer's responsibility to make sure that their product works right.
Likewise, it's the cryptographer's responsibility to deliver a secure product. The user mostly just needs to know how to use it correctly, but the cryptographer needs to work out the details of ensuring it's secure and saying, "here is your product, if you use it correctly, it's secure". and if it's not, then it's the cryptographer's job to fix that.
Re:Let's face it (Score:5, Funny)
Dude you just missed a really good opportunity for a car analogy!
Re: (Score:2)
Re:Let's face it (Score:5, Funny)
want to trust your mechanic with pulling your teeth out?
Not again.
Re: (Score:2)
Re: (Score:2)
Even worse, do you want your proctologist pulling your teeth? ewwwww!!!!
Re: (Score:2)
Like girls?
You insensitive clod! (Score:2, Funny)
The world around me is bounded by the extent of my mom's basement!
Re: (Score:1)
Do you know everything about baseball? How about your car engine? Or professional wrestling?
Non-technical users don't learn about computers because they couldn't care less about how they work. That knowledge wouldn't have any effect in their lives that they'd consider valuable. They have their own interests, like you do.
Re: (Score:2)
Do you know everything about baseball?
Yes, it's like rounders played by grown men instead of primary school girls. I'm not really interested in either.
How about your car engine?
Which car? What type of engine? Are you including all the electrical and hydraulic subsystems in that? The answer is yes, anyway.
Or professional wrestling?
I wouldn't say everything. It's more fun taking part than watching, that's all you need to know.
Re: (Score:2)
Ignore the other losers that responded "I don't care about it". The whole point is there may be others that would find cyrptogrophy to be "boring" or "Not interesting".
I, on the other hand, am actively trying to learn everything about baseball, my car's engine, and pro wrestling. They are interesting, everything is. Unfortunately that kinda limits my time for investigating them, so I don't know everything about them, but research them when I am presented an opportunity to. I know a lo about cryptography b
Re: (Score:1)
Re: (Score:2)
I agree, because the state of the art isn't fool proof yet. Until everyone on the street can encrypt and decrypt messages safely and securely, you'll have to know how it works.
On a side note, Cell phones might be a good example of a mature encryption system, except its not end to end or very secure. But people don't have to know about GSM encryption or keys or anything else. They are just protected in the transmission of their call from their handset to the carrier. Of course the encryption's been broken fo
Re: (Score:2)
I am of the opinion that one should know as much as possible about the world that surrounds them, including how things work.. It's not so difficult to learn. I love learning.
I feel exactly the same way and don't understand how on earth anyone can NOT want to learn about everything around them but unfortunately that is not how the vast majority of people operate... Sadly...
Re: (Score:3)
I feel exactly the same way and don't understand how on earth anyone can NOT want to learn about everything around them
Opportunity cost and lack of personal interest. Every hour you spend learning something is an hour you can't spend learning something else, or I dunno, just relaxing and having fun or something.
And personally, I really don't want to learn all the intricate details of how my car works, but I spend a lot of time learning about how computing technology works, keeping up with interesting physics, etc. Yet if some mechanic screwed me over because of my lack of knowledge, I'd get pretty annoyed if some gearhead b
Re: (Score:2)
I am of the opinion that one should know as much as possible about the world that surrounds them, including how things work.. It's not so difficult to learn. I love learning.
I agree, but what about those that disagree? Many people have no interest in learning how things work, and just want them TO work. When it is reasonably possible, shouldn't things "work" well enough out of the box that they don't have to think about them. If for no other reason than to protect the rest of us from what could happen du
Re: (Score:1)
Re: (Score:2)
Re:Let's face it (Score:5, Insightful)
If they use it, it's part of a package that uses it, and they will never see the short ID.
And anyone who uses it for real protection would never base their acceptance of a key on the short ID anyhow.
So the submission is, while technically correct, likely of little to no consequence.
It's a bit like saying that dirvers' licenses now are insecure as IDs because they contain a line stating the eye colour, and it has been found that by wearing coloured contacts, one can make a false positive ID. The observation is correct, but the conclusion is not.
tl;dr: The short ID is one of many factors to assist in verifying a key. It should never be used alone, and isn't "broken" because multiple keys can match it.
Re:Let's face it (Score:4)
Re: (Score:2)
If they use it, it's part of a package that uses it, and they will never see the short ID.
Debian users see the short IDs all the time, at least, I do. I have to manually add apt keys all the time.
Re: (Score:2)
Yeah, maybe that will teach Debian developers to distribute more data than the key ID.
Probably other people behave the same way: "Want my key? Here is my ID." That is why this is bad. The GP analogy to drivers licenses would be good if the photo was too hard to look at, and people relied on the eye color on their daily tasks.
Re: (Score:2)
Re: (Score:2)
And anyone who uses it for real protection would never base their acceptance of a key on the short ID anyhow.
I wonder what Manning would have done. Someone who doesn't even know how to turn off the logging feature in his IM client...
Re: (Score:2)
tl;dr
Re: (Score:2)
In the case of crypto they really might someone ignorant of cryptographic principles could easily do somethIng like create a known plaintext or similar that makes the key vulnerable to attack. No matter how simple and solid the software is some understanding is needed.
Re: (Score:2)
Hum... A crypto system for general use should survive known plaintext attacks.
cryptography as protest (Score:3)
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 [guardianproject.info].
Re: (Score:2)
That being said, a collision on a short key ID is not quite as critical as one might think. It happens fairly frequently just on its own, and this is just a technique of forcing it to happen. There is a bug in GPG that causes it to import the collided key under some circumstances, but one would still need to someone trick a person into signing the key (or trick several people) for that t
This is an example of the strength of the protocol (Score:2, Interesting)
8 hex digits means 8*4= 32 bits. It has taken until now to produce a single collision in something with a 32 bit key? Wow, that's great!
And even now, it has been done by tweaking two different versions.
So, yes, it's probably time to use a larger short representation. Maybe go to base-32 or -64 instead of base 16. But the protocol is nothing short of amazing.
Above post is ignorant (Score:5, Informative)
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.....
Re:Above post is ignorant (Score:5, Funny)
Who the fuck do you think you are? Some of us are trying to get page hits by posting dumb stories on Slashdot here!
Re: (Score:1)
Re: (Score:1, Offtopic)
And that matters, why?
Re: (Score:1)
GMGruman, is that you?
Re: (Score:1, Funny)
Now, now, be fair, we DID have a "BITCOIN IS STILL ALIVE AND WILL RULE THE WORLD ALREADY zomg modern money is teh evilz" article just a few days ago, so we're definitely getting back on track.
Re: (Score:1)
Fine time for me to run out of mod points... +1 to you... though also have to start adding in the "eBook/evil-Amazon" ones too now, as I've noticed a lot of eBook related stories lately.
The "Ask Slashdot" ones are the most annoying though.... may as well be "It hurts when I breathe, what should I oh wonderful master?"
Re: (Score:1, Funny)
let me see...
windows 7 is a fair operating systems, real people couldn't care less between what run their smart phones unless it's iOS, linux year of the desktop must have been the last one because this year graphic cards have no drivers.
Re: (Score:2)
Re: (Score:1)
This didn't happen by chance, though. He generated a script that kept generating keys until the key Id's matched an existing one.
With 32-bit short keys, there is a time complexity of 2^32. This is a preimage attack.
To make it unfeasbile to do they could go with 128-bit short keys.
Re:This is an example of the strength of the proto (Score:5, Insightful)
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 [wikipedia.org].
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.
Re: (Score:3)
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.
Re: (Score:3)
Re: (Score:2)
Exactly - and some people have "vanity" short keys, and have had since 1999, including generating their own collisions...
http://subkeys.pgp.net:11371/pks/lookup?search=0xDEADBEEF [pgp.net]
Re: (Score:1)
Re: (Score:1)
Expired certificate on bug report host's server? (Score:2)
How seriously do you really take security if you let your certificate expire like this? Is g10code.com legitimate?
So? (Score:5, Informative)
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? (Score:5, Informative)
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. (Score:4, Informative)
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.
Re: (Score:2)
Ah okay, I didn't read the bug report. That is indeed a bug, but it isn't a security vulnerability.
Re: (Score:2)
It is a vulnerability. What you mean is that it's not a design error.
The semantics here are actually important ;-)
Re: (Score:2)
It isn't a security vulnerability for the same reason that key id collisions aren't vulnerabilities. If I enter a long fingerprint and get two keys, one of which matches only the short id, that is a user interface bug. It isn't a security issue because I should never trust a key I pulled from the cloud unless a) the web of trust tells me it's okay (which means it has checked the full public key), or b) I subsequently check the full fingerprint in my local database.
I suppose you could expect GPG to verify it
Re: (Score:2)
It does, however, mean that the Internet is filled with guides that advertise an insecure practice that offers an attack vector:
http://blog.edseek.com/archives/2007/03/17/apt-key-gpg-key-import-on-ubuntu-and-debian/ [edseek.com]
Every time I've asked for the key to an unofficial repository, I've been given the short ID, and both the Ubuntu and Debian community seem to suggest this as the way to import the key.
Re: (Score:2)
Yeah, I agree with the Anonymous Coward who replied earlier. This isn't bad practice per se -- using the key id is the standard way to import a key. Importing by fingerprint doesn't make you any more secure because you haven't verified the fingerprint. That guide you linked to is inherently insecure because it isn't asking you to verify the key (and it isn't claiming to be secure against a fraudulent key).
The fingerprint is used when you are about to sign a key -- then you need to make sure that it actually
A collision in a 32 bit key space? Unpossible! (Score:5, Insightful)
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 [spywarewarrior.com] actually explicitly cover this, I'd say this is a non-story. Just use the long key ID if you're worried.
Re: (Score:3, Insightful)
The a commenter in the bug report explains the importance of this:
Even when you give gpg a long key-id (or even the full fingerprint) the program (which has no "plans for a new release") truncates and uses the short key-id.
So even if you say "gpg, look up this [long key-id]" it truncates silently.
See an example here:
https://bugs.g10code.com/gnupg/msg4026 [g10code.com]
Why do I care? (Score:1)
I read the whole thing, hoping to figure out why I care. Looks like there's a bug in Gnu PG, if you know someone's short key you can possibly do something or other, possibly replace their key with yours in some way. Surely it wouldn't authenticate, or it should at least say the message came from someone else if you check someone's signature. Is there any actual problem here?
TL;DR, your blog sucks.
Shamir Discreet Logarithmic Hash Anyone? (Score:1)
http://www.senderek.com/SDLH/ [senderek.com]
http://senderek.com/SDLH/discrete-logarithm-hash-for-RSA-signatures.ps [senderek.com]
http://www.senderek.com/pcp/pcp-security.html [senderek.com]
http://www.mit.edu:8008/bloom-picayune/crypto/13190 [mit.edu] {link appears dead/down :(}
[Relevant text from above link copied from the Pure Crypto Project Site link above]
Shamir's discrete logarithm hash function (SDLH)
The SDLH is base on a simple idea that once the message is converted into a long integer a hash of the message can be computed as follows:
hash(x) = g ^ x (mod
Re: (Score:2)
That analysis doesn't apply because n in this instance is no greater than 2^32 in order to ensure than the ID is no more than 32-bits. That fails to meet the criteria Shamir stated "given, that both p and q are large primes which are being kept secret so that factoring n = p*q is computationally infeasible."
Therefore, 32-bit hashes are not "provably collision resistant". See my post [slashdot.org] for the actual likelihood of collisions.
This well-known but not a problem (Score:3)
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.
Re: (Score:2)
Bit reduction in hashes is vital for many of their uses and that will result in collisions.
There are lots of silly assumptions about crypto that just aren't true. For example thinking that there is a 1:1 mapping of keys. As far as I know, all public / private key crypto not 1:1 but is 1:N with where one private key can have more than one public key and it may be N:M. Since someone is going to argue the point... here is some RSA code [abnormal.com]
Re: (Score:2)
Which surprises you most? (Score:5, Insightful)
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.
Re: (Score:3)
Do you really think that the developers of the world's foremost free encryption tool, the same one used by virtually all Linux distributions for package security, would have been too stupid to consider the birthday paradox? Read my post [slashdot.org] for an explanation of why this is not a problem.
Also, it isn't a one in 65536 chance (16-bits), it's a one in 4,294,967,296 chance (32-bits). Still, that is a very small number in cryptography, so I agree with you on this: with so many people using GPG, there are probably al
Re: (Score:2)
Note, the probability of a collision is approximately 1-exp(-n^2 / (2*N)) where n is the number of samples, and N is the state space.
Basically, if n is roughly sqrt(N), you are quite likely to have a collision. If n is way less than sqrt(N), you are fine. This is why Git works, with its 160 bit space - you'd need somewhere near 2^80 entries to have a high probability of a collision. One billion (2^30) entries a second, 2^25 seconds a year for a a thousand (2^10) years is 2^65 ... leaving you with about a 1-
Hey Stupid (Score:2)
Hey Stupid v2.0 (Score:1)
Actually, yes he did, but you would have to understand English well to know what I'm saying. He implied that you'd have to be stupid to think that the GnuPG developers were that stupid. In the English language, which is clearly not your first language, we ask a question when we are not sure what someone is saying (i.e. implying): Are you saying
Fingerprint (Score:2)
And that's why the fingerprint's used to actually check which key is what.
The short keyid has always been a short hand for the sake of simplicity, aka, if it doesn't match, it's wrong (that always works).
For performing true verification, fingerprint, always. If you check the key signing parties, they always check fingerprints too. For that reason.
Re: (Score:2)
For performing true verification, fingerprint, always.
Unless you get the person who owns the key to give you the fingerprint directly, that's still not a "true" verification. The place you got the fingerprint from might be compromised.
A "web of trust" is likewise not much of a safeguard - all a malicious user needs to do is get one account into the web, by acting like a good boy with that one account - then he can in turn add thousands of other sleeper accounts that one day will verify the malicious key.
For "true" verification, you either need a direct signer
Re: (Score:2)
That's why we rarely use keys we really trust... That means, in practice we put different tresholds of trustness on keys that will have different uses. E.g. for running software on a machine the keys comming with the install media is enough to trust them, but for banking it may not be.
Also, this is why SSL stil relies on paid certificates.
Why is this news? (Score:2)
See: "0xDEADBEEF"
News flash (Score:2)
Collisions in a 32-bit space.... (Score:4, Informative)
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.
Fetch the full fingerprint, not the keyID (Score:1)
gpg --recv-keys 0xE4F0EDDF374F2C50D473 5EC097833DC998EF9A49
and not just:
gpg --recv-keys 0x98EF9A49
Doing the former, gpg will then download all keys with fingerprint ending by 98EF9A49, and check which one matches the fingerprint. Bonus point: on top of fetching my key, you'll be doing a fingerprint verification (which is needed anyway) by copying entirely with your keyboard.
Re: (Score:3)
If you read the bug report, you'll see that the whole issue is that GPG doesn't exhibit the behaviour you describe!
Re: (Score:2)
32-bit (Score:2)
If 32-bit keys were as secure as the 1024 or 4096 bit keys they're derived from, we wouldn't need the 1024/4096 bit keys.
Using a 32-bit short ID is and has always been less secure.
Nothing to see here, move along.
How is this news? (Score:1)
ANY hashing algorithm which generates hash values which are shorter than the original input value is GUARANTEED to have collisions. This is basic mathematics; you can't have a smaller set which has a 1:1 correspondence with a larger set.
and no, I'm not a mathematician, but I did actually stay awake in a few math classes, which the original poster apparently did not...