Slashdot Mirror

← Back to Stories (view on slashdot.org)

GnuPG Short ID Collision Has Occurred.

Posted by Unknown on from the 32-bits-ought-be-enough-for-anyone dept.

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."

20 of 110 comments (clear)

  1. Let's face it by 2.7182 · · Score: 4, Insightful

    When you've got nothing on the line, you're not going to be as careful about cryptography as someone who does.

    1. Re:Let's face it by Anonymous Coward · · Score: 5, Insightful

      This is always true, but I think the main point here is that the defaults for GnuPG should not leave users vulnerable to imposters, especially since non-technical users may not realize it would even be an issue. Not everyone who makes the good decision to encrypt critical communications needs to know how it works.

    2. Re:Let's face it by ptx0 · · Score: 3, Interesting

      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.

    3. Re:Let's face it by Anonymous Coward · · 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.

    4. Re:Let's face it by Anonymous Coward · · 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?

    5. Re:Let's face it by Anonymous Coward · · 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.

    6. Re:Let's face it by arth1 · · Score: 4, 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.

    7. Re:Let's face it by PPH · · Score: 5, Funny

      want to trust your mechanic with pulling your teeth out?

      Not again.

      --
      Have gnu, will travel.
    8. Re:Let's face it by ewanm89 · · Score: 3

      Yeah, it was never meant to uniquely identify a key, just find the key easily using it as the field to populate hash tables. There is only one thing that uniquely identifies a key, the whole damn key.

    9. Re:Let's face it by AmiMoJo · · Score: 4, Funny

      Dude you just missed a really good opportunity for a car analogy!

      --
      const int one = 65536; (Silvermoon, Texture.cs)
      SJW, n: "Someone I don't like, and by the way I'm a fuckwit" - AC
  2. Above post is ignorant by robbak · · 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.....

    --
    Prediction for end of Universe #42: Fencepost error in Quantum_bogosort.cpp
    1. Re:Above post is ignorant by gparent · · 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!

  3. So? by cloudmaster · · 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.

    1. Re:So? by mgiuca · · 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.

  4. A collision in a 32 bit key space? Unpossible! by zill · · Score: 4, Insightful
    I'm shocked, shocked to find collisions going on in here!

    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.

    1. Re:A collision in a 32 bit key space? Unpossible! by Anonymous Coward · · 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

  5. Re:This is an example of the strength of the proto by arth1 · · 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.

    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.

  6. Thanks for clarifying -- I should have researched. by kfogel · · Score: 3, 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.

    --
    http://www.red-bean.com/kfogel
  7. Which surprises you most? by dfay · · Score: 4, 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.

  8. Collisions in a 32-bit space.... by gstrickler · · Score: 3, 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.

    --
    make imaginary.friends COUNT=100 VISIBLE=false