Forgot your password?
typodupeerror
Privacy Encryption Security

GnuPG Short ID Collision Has Occurred. 110

Posted by Unknown Lamer
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."
This discussion has been archived. No new comments can be posted.

GnuPG Short ID Collision Has Occurred.

Comments Filter:
  • Let's face it (Score:5, Insightful)

    by 2.7182 (819680) on Tuesday December 27, 2011 @12:18AM (#38499772)
    When you've got nothing on the line, you're not going to be as careful about cryptography as someone who does.
    • Re:Let's face it (Score:5, Insightful)

      by Anonymous Coward on Tuesday December 27, 2011 @12:34AM (#38499844)
      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.
      • Re: (Score:3, Interesting)

        by ptx0 (1471517)
        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.
        • Re:Let's face it (Score:5, Insightful)

          by Anonymous Coward on Tuesday December 27, 2011 @01:09AM (#38499986)

          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)

            by Anonymous Coward

            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)

              by Anonymous Coward on Tuesday December 27, 2011 @01:24AM (#38500042)

              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.

            • by PPH (736903) on Tuesday December 27, 2011 @01:42AM (#38500112)

              want to trust your mechanic with pulling your teeth out?

              Not again.

              • by crutchy (1949900)
                while i agree that a lot of arguments are regurgitated on /. its a shame that a lot of arguments need to be regurgitated. the grandparent is right about the need for specialists. if gnupg doesn't work as advertised, it shouldn't be relied on. this concept isn't rocket science, but some people are just that thick.
            • Even worse, do you want your proctologist pulling your teeth? ewwwww!!!!

          • Like girls?

        • The world around me is bounded by the extent of my mom's basement!

        • by bonch (38532) *

          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.

          • by Gordonjcp (186804)

            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.

          • 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

            • by ptx0 (1471517)
              I guess my point was that if your communications are sensitive enough to warrant cryptography, you should probably at least know the basics about how keys work.
              • 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

        • by drussell (132373)

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

          • by Raenex (947668)

            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

        • by Pharmboy (216950)

          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

          • by ptx0 (1471517)
            My point is a bit more relevant when dealing with a crypto situation directly, because in my world (and the idealist world of accountability) it would make more sense that, if your communications are sensitive enough to warrant cryptography that you should know the very basics about how keys work. I still learnt how to drive a car before taking it for the first spin. If I were to do anything more advanced with the car, you can damn well bet that I will be learning all that I can about it. I'd complain some
      • by deniable (76198)
        But how many people actually use GPG? The non-technical users just don't seem to bother.
        • Re:Let's face it (Score:5, Insightful)

          by arth1 (260657) on Tuesday December 27, 2011 @01:29AM (#38500070) Homepage Journal

          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.

          • by ewanm89 (1052822) on Tuesday December 27, 2011 @05:24AM (#38500978) Homepage
            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.
          • by drinkypoo (153816)

            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.

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

              • This whole thing is much ado about nothing. The correct drivers license analogy is exactly the way it really works. A cop pulls you over and you forgot your license (the complete key), but you give your name (e.g. Bob Smith) for him to run (you are too drunk to recall your SSN and your DOB in this case.) He runs the name and finds three hits. The first two don't match your face. The third one does, so he knows he has the right guy and now knows your DOB and SSN. He then knows exactly who he is pulling
          • by tenco (773732)

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

      • by DarkOx (621550)

        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.

    • 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].

    • Some GPG users do have something on the line -- they might be trying to protect themselves from a hostile government.

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

    • by robbak (775424) on Tuesday December 27, 2011 @12:34AM (#38499846) Homepage

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

      • by gparent (1242548) on Tuesday December 27, 2011 @12:40AM (#38499870)

        Who the fuck do you think you are? Some of us are trying to get page hits by posting dumb stories on Slashdot here!

        • by deniable (76198)
          He must be new around here.
        • GMGruman, is that you?

      • There is a difference between accidental and crafted collisions. Having a collision in a hash between two random documents is not nearly as big a security problem as having a collision in a hash between one chosen document and one constructed one.
    • by Anonymous Coward

      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.

      • by arth1 (260657) on Tuesday December 27, 2011 @01:49AM (#38500130) Homepage Journal

        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.

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

          • ... and nobody cares, because anyone with a clue already knew this, and it has zero effect on the effectiveness of GnuPG.
        • 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]

          pub 1024D/DEADBEEF 2001-01-21 Imad R. Faiad
          Preston Wilson <pres@palmjunkie.com>

          pub 2048R/DEADBEEF 1999-08-03 Imad R. Faiad

          pub 1024D/DEADBEEF 1999-04-28 Imad R. Faiad

    • by thesh0ck (1983948)
      8 hex digits is 64 bits.
  • How seriously do you really take security if you let your certificate expire like this? Is g10code.com legitimate?

  • So? (Score:5, Informative)

    by cloudmaster (10662) on Tuesday December 27, 2011 @12:37AM (#38499854) Homepage Journal

    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)

      by mgiuca (1040724) on Tuesday December 27, 2011 @01:27AM (#38500058)

      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.

      • by kfogel (1041) on Tuesday December 27, 2011 @02:03AM (#38500180) Homepage

        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.

        • by mgiuca (1040724)

          Ah okay, I didn't read the bug report. That is indeed a bug, but it isn't a security vulnerability.

          • It is a vulnerability. What you mean is that it's not a design error.

            The semantics here are actually important ;-)

            • by mgiuca (1040724)

              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

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

        • by mgiuca (1040724)

          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

  • by zill (1690130) on Tuesday December 27, 2011 @12:44AM (#38499886)
    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 [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)

      by Anonymous Coward

      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]

  • TL;DR: This now gives two results: gpg --recv-key 70096AD1

    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.

  • by Anonymous Coward

    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

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

  • by DERoss (1919496) on Tuesday December 27, 2011 @01:50AM (#38500132)

    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.

    • by thogard (43403)

      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]

  • by dfay (75405) on Tuesday December 27, 2011 @02:24AM (#38500276)

    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.

    • by mgiuca (1040724)

      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

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

    • by arth1 (260657)

      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

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

  • See: "0xDEADBEEF"

  • Hash function produces same output from different inputs. More at 11
  • by gstrickler (920733) on Tuesday December 27, 2011 @03:12AM (#38500450)

    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.

  • Moral of this? To fetch my key, use:
    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.
    • by Ragzouken (943900)

      If you read the bug report, you'll see that the whole issue is that GPG doesn't exhibit the behaviour you describe!

      • This is *NOT* a bug. You should *always* check the full fingerprint. If it happens that gpg fetches 2 keys at the same time instead of just one, then it's not a big deal, since I'm going to check the full of the fingerprint anyway. People just should be aware of what's going on, and that's why asheesh made this blog post. Note that he has done this "trick" to brute-force the GPG UUID a long time ago (he told me about this at last debconf11 last summer), but it's nice that he gets exposure through Slashdot.
  • 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.

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

Forty two.

Working...