GnuPG Short ID Collision Has Occurred.

Let's face it by 2.7182 · 2011-12-26 16:18 · 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.

Re:Let's face it by Anonymous Coward · 2011-12-26 16:34 · 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.
Re:Let's face it by ptx0 · 2011-12-26 16:42 · 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.
Re:Let's face it by Anonymous Coward · 2011-12-26 17:09 · 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:Let's face it by Anonymous Coward · 2011-12-26 17:14 · 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 by deniable · 2011-12-26 17:17 · Score: 1

But how many people actually use GPG? The non-technical users just don't seem to bother.
Re:Let's face it by Anonymous Coward · 2011-12-26 17:24 · 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 by arth1 · 2011-12-26 17:29 · 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.
Re:Let's face it by PPH · 2011-12-26 17:42 · Score: 5, Funny

want to trust your mechanic with pulling your teeth out?
Not again.

--
Have gnu, will travel.
Re:Let's face it by bonch · 2011-12-26 17:54 · 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:Let's face it by crutchy · 2011-12-26 20:06 · Score: 2

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.
Re:Let's face it by drussell · 2011-12-26 20:08 · 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:Let's face it by ewanm89 · 2011-12-26 21:24 · 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.
Re:Let's face it by Gordonjcp · 2011-12-26 21:50 · Score: 1

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:Let's face it by drinkypoo · 2011-12-26 22:28 · Score: 1

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.

--
"You're right," Fisheye says. "I should have set it on 'whip' or 'chop.'"
Re:Let's face it by AmiMoJo · 2011-12-26 23:09 · 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
Re:Let's face it by DarkOx · 2011-12-27 00:18 · Score: 1

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.

--
Repeal the 17th Amendment TODAY! Also Please Read http://www.gnu.org/philosophy/right-to-read.html
Re:Let's face it by tenco · 2011-12-27 00:22 · Score: 1

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:Let's face it by Anonymous Coward · 2011-12-27 02:19 · Score: 0

This is slashdot, we don't need a tldr for 5 sentences.
Re:Let's face it by Jumperalex · 2011-12-27 02:21 · Score: 1

Even worse, do you want your proctologist pulling your teeth? ewwwww!!!!

--
If you can't be good, be good at it!
Re:Let's face it by betterunixthanunix · 2011-12-27 02:22 · Score: 1

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 to be of any use.

--
Palm trees and 8
Re:Let's face it by Bill,+Shooter+of+Bul · 2011-12-27 02:29 · Score: 1

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 because the tools are still immature, requiring a bit more understanding of how they work. Like cars were in 1905.

--
Well.. maybe. Or Maybe not. But Definitely not sort of.
Re:Let's face it by Raenex · 2011-12-27 02:36 · Score: 2

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 bashed me about what a dumb idiot I was.
Re:Let's face it by Anonymous Coward · 2011-12-27 03:26 · Score: 0

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.
Regarding TV, thats why they call it the "idiot box". :)
Re:Let's face it by SteveFoerster · 2011-12-27 04:20 · Score: 1

tl;dr

--
Space game using normal deck of cards: http://BattleCards.org
Re:Let's face it by marcosdumay · 2011-12-27 04:32 · Score: 1

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.

--
Rethinking email
Re:Let's face it by marcosdumay · 2011-12-27 04:34 · Score: 1

Hum... A crypto system for general use should survive known plaintext attacks.

--
Rethinking email
Re:Let's face it by Anonymous Coward · 2011-12-27 05:34 · Score: 0

Yeah it's a fucking awesome way to be a jerk of all trades and spread yourself thin instead of mastering one or two things. Since we live forever and all.
Re:Let's face it by Christian+Smith · 2011-12-27 07:43 · Score: 1

Like girls?
Re:Let's face it by Pharmboy · 2011-12-27 07:45 · Score: 1

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 due to their lack of desire to become experts.
And the same could be said of your car. I completely understand how an Otto engine works, and can literally draw you a diagram of it. As a direct comparison, should we say that everyone *should* understand how an Otto engine works, and maybe even understand how to at least change their oil, rotate their tires and do basic electronic diagnosis of their car before we let them get a license?
And yes, for once, this a car analogy that actually fits.

--
Tequila: It's not just for breakfast anymore!
Re:Let's face it by Algae_94 · 2011-12-27 07:59 · Score: 1

Exactly, It's one thing to learn and understand the concept of how something works, but another to know the exact implementation. Understanding cryptography is an important bit of knowledge, but knowing the ins and outs of every implementation of it is a bit excessive.
Re:Let's face it by Anonymous Coward · 2011-12-27 08:23 · Score: 0

It's better than what he was doing to my ass.
Re:Let's face it by Zero__Kelvin · 2011-12-27 08:59 · Score: 1

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 out of the car and beating to a pulp with his billy club prior to fabricating a charge of Assault and Battery on a Police Officer.

--
Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun
Re:Let's face it by Anonymous Coward · 2011-12-27 12:26 · Score: 0

I hope that person would be you, but being such a cynical dumb ass.
Re:Let's face it by ptx0 · 2011-12-27 20:01 · Score: 1

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.
Re:Let's face it by ptx0 · 2011-12-27 20:06 · Score: 1

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 about laziness and apathy but I can't be arsed..
Re:Let's face it by Bill,+Shooter+of+Bul · 2011-12-28 02:31 · Score: 1

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 for a while, and government agencies just tap into the carrier itself to listen. But secure decryption should be so pervasive and easy to use that it requires nothing of the end user.

--
Well.. maybe. Or Maybe not. But Definitely not sort of.

This is an example of the strength of the protocol by robbak · 2011-12-26 16:27 · Score: 1, 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.

--
Prediction for end of Universe #42: Fencepost error in Quantum_bogosort.cpp

Expired certificate on bug report host's server? by OverTheGeicoE · 2011-12-26 16:28 · Score: 1

How seriously do you really take security if you let your certificate expire like this? Is g10code.com legitimate?

Above post is ignorant by robbak · 2011-12-26 16:34 · 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

Re:Above post is ignorant by gparent · 2011-12-26 16:40 · 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:Above post is ignorant by deniable · 2011-12-26 17:19 · Score: 0

He must be new around here.
Re:Above post is ignorant by Anonymous Coward · 2011-12-26 18:14 · 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:Above post is ignorant by Bill+Currie · 2011-12-26 19:34 · Score: 1, Offtopic

And that matters, why?

--
Bill - aka taniwha
--
Leave others their otherness. -- Aratak
Re:Above post is ignorant by Anonymous Coward · 2011-12-26 20:10 · Score: 0

i am not using this stuff, but if i had to guess, its not the fact that collisions happend, but the fact, that you can actually artificially create one and abuse it.
Re:Above post is ignorant by inflex · 2011-12-26 21:25 · Score: 0

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:Above post is ignorant by Anonymous Coward · 2011-12-26 23:30 · Score: 0

Indeed - thanks to the birthday paradox it only takes 92683 hashes to probably get a collision somewhere.
Re:Above post is ignorant by TheRaven64 · 2011-12-26 23:41 · Score: 1

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.

--
I am TheRaven on Soylent News
Re:Above post is ignorant by The+Other+White+Meat · 2011-12-27 11:39 · Score: 1

GMGruman, is that you?

--

--- Generation X: The first generation to have SIG lines inferior to their parents... ---
Re:Above post is ignorant by Anonymous Coward · 2011-12-28 06:30 · Score: 0

lol -1 fucking troll

So? by cloudmaster · 2011-12-26 16:37 · 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? by mgiuca · 2011-12-26 17:27 · 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.
Re:So? by impaledsunset · 2011-12-26 21:27 · Score: 1

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/
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:So? by Anonymous Coward · 2011-12-26 21:42 · Score: 0

The way the whole GPG model works is based on a web of trust, though. Even if someone were to generate a collission, their key is unlikely to be trusted by other legit developers or the real project, which should ultimately be traceable to someone with whom you've already established an in-person key exchange. If you're just downloading a key and not checking in to the whole remaining trust chain, you're only getting the possibility of encryption - not source validation. GPG - much like SSL and any other public key infrastructure - doesn't fully work if you only have one key and no way to verify a chain of trust.
So there's really the same attack vector even if this is solved.
Re:So? by mgiuca · 2011-12-27 00:55 · Score: 1

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 belongs to its supposed owner. Having said all that, perhaps if you trust the site telling you to install a key, then it would add some extra verification to tell you to check the fingerprint.

Re:Expired certificate on bug report host's server by Anonymous Coward · 2011-12-26 16:44 · Score: 0

Eep. Well, it expired 3 days ago. But yeah.

According to Perspectives, it's been consistent for the past 176 days. Good enough for me.

A collision in a 32 bit key space? Unpossible! by zill · 2011-12-26 16:44 · 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.

Re:A collision in a 32 bit key space? Unpossible! by Anonymous Coward · 2011-12-26 17:07 · Score: 0

Maybe read the bug report comments a little closer. The point is that explicitly telling gpg to import from the keyserver keys based on their long ids, defaults to searching on their short ids. The patch fixes the gpg/keyserver interaction. The existence of collisions on short ids are not the issue.
Also, werner is a tool.
Re:A collision in a 32 bit key space? Unpossible! by Anonymous Coward · 2011-12-26 17:14 · 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

Re:This is an example of the strength of the proto by Anonymous Coward · 2011-12-26 16:46 · 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:Expired certificate on bug report host's server by Anonymous Coward · 2011-12-26 17:06 · Score: 0

Or if your bug tracker comments are top-posted....

What is this? Outlook?

Why do I care? by b4dc0d3r · 2011-12-26 17:09 · Score: 0

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.

Shamir Discreet Logarithmic Hash Anyone? by Anonymous Coward · 2011-12-26 17:34 · Score: 1

http://www.senderek.com/SDLH/

http://senderek.com/SDLH/discrete-logarithm-hash-for-RSA-signatures.ps

http://www.senderek.com/pcp/pcp-security.html

http://www.mit.edu:8008/bloom-picayune/crypto/13190 {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 p*q)
given, that both p and q are large primes which are being kept secret so that factoring n = p*q is computationally infeasible.
This hash function is provably collision-resistant, I quote the prove Ronald L. Rivest presented in his posting:

Adi Shamir once proposed the following hash function:

Let n = p*q be the product of two large primes, such that
factoring n is believed to be infeasible.

Let g be an element of maximum order in Z_n^* (i.e. an
element of order lambda(n) = lcm(p-1,q-1)).

Assume that n and g are fixed and public; p and q are secret.

Let x be an input to be hashed, interpreted as a
non-negative integer. (Of arbitrary length; this may be
considerably larger than n.)

Define hash(x) = g^x (mod n).

Then this hash function is provably collision-resistant, since
the ability to find a collision means that you have an x and
an x' such that

hash(x) = hash(x')

which implies that

x - x' = k * lambda(n)

for some k. That is a collision implies that you can find a
multiple of lambda(n). Being able to find a multiple of lambda(n)
means that you can factor n.

I would suggest this meets the specs of your query above.

Cheers,
Ron Rivest

Ronald L. Rivest
Room 324, 200 Technology Square, Cambridge MA 02139
Tel 617-253-5880, Fax 617-258-9738, Email

There are a number of issues to be addressed, especially when the SDLH is being used together with the RSA signature scheme and a full analysis of the SDLH's security can be found in the paper "A Discrete Logarithm Hash Function for RSA Signatures". The analysis shows, that SDLH can safely be used together with RSA once certain conditions are met with regard to the selection of the user's key material. For details I like to refer to the paper about SDLH.

CAPTCHA: revolter {Well, cryptography can be used to secure communications between individuals during a revolt....}

Re:Shamir Discreet Logarithmic Hash Anyone? by gstrickler · 2011-12-26 19:38 · Score: 1

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 for the actual likelihood of collisions.

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

You insensitive clod! by PPH · 2011-12-26 17:45 · Score: 1, Funny

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

--
Have gnu, will travel.

Re:This is an example of the strength of the proto by arth1 · 2011-12-26 17:49 · 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.

This well-known but not a problem by DERoss · 2011-12-26 17:50 · Score: 2

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:This well-known but not a problem by thogard · 2011-12-26 19:49 · Score: 1

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
Re:This well-known but not a problem by ewanm89 · 2011-12-26 21:55 · Score: 1

depends on the algorithm, most are actually 1:1, makes life simpler for all.

Thanks for clarifying -- I should have researched. by kfogel · 2011-12-26 18:03 · 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

Which surprises you most? by dfay · 2011-12-26 18:24 · 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.

Re:Which surprises you most? by mgiuca · 2011-12-26 18:36 · Score: 2

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 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 already key ID collisions happening all the time. It just isn't an issue because the system is designed with the expectation that key IDs would collide.
Re:Which surprises you most? by Anonymous Coward · 2011-12-26 22:20 · Score: 0, Informative

Paragraph 1: "You'd have to be stupid not to understand the birthday paradox."
Paragraph 2: "I don't understand the birthday paradox."
Re:Which surprises you most? by Anonymous Coward · 2011-12-27 01:26 · Score: 0

Dur CS 201 is tough.
Re:Which surprises you most? by wisty · 2011-12-27 05:24 · Score: 1

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-exp(-2^130/2^161) = 1-exp(-2^-31), which isn't one in a million.
But with a few thousand keys, you'll be on very thin ice with a 2^32 keyspace.

Re:Thanks for clarifying -- I should have research by mgiuca · 2011-12-26 18:30 · Score: 1

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

Fingerprint by kangsterizer · 2011-12-26 18:56 · Score: 1

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:Fingerprint by arth1 · 2011-12-26 22:29 · Score: 1

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 you trust and is only one step (not two or more) away.
Or have keys delivered in person, or at the very least in a sealed package.
Re:Fingerprint by marcosdumay · 2011-12-27 04:44 · Score: 1

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.

--
Rethinking email

Why is this news? by Swampash · 2011-12-26 18:56 · Score: 1

See: "0xDEADBEEF"

Re:Thanks for clarifying -- I should have research by kangsterizer · 2011-12-26 18:57 · Score: 1

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

The semantics here are actually important ;-)

News flash by viperidaenz · 2011-12-26 19:06 · Score: 1

Hash function produces same output from different inputs. More at 11

Collisions in a 32-bit space.... by gstrickler · 2011-12-26 19:12 · 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

Re:Thanks for clarifying -- I should have research by mgiuca · 2011-12-26 19:35 · Score: 1

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 for you after typing in the long fingerprint, then I guess it's severe. I just wouldn't trust a key unless I looked at the fingerprint in my local database.

Re:I just can't lose!? (Re:Above post is ignorant) by Anonymous Coward · 2011-12-26 20:17 · 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.

Fetch the full fingerprint, not the keyID by GPLHost-Thomas · 2011-12-26 20:28 · Score: 0

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.

Re:Fetch the full fingerprint, not the keyID by Ragzouken · 2011-12-27 00:39 · Score: 2

If you read the bug report, you'll see that the whole issue is that GPG doesn't exhibit the behaviour you describe!
Re:Fetch the full fingerprint, not the keyID by GPLHost-Thomas · 2011-12-27 04:49 · Score: 1

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.

Re:This is an example of the strength of the proto by thesh0ck · 2011-12-26 20:32 · Score: 1

8 hex digits is 64 bits.

Re:This is an example of the strength of the proto by thesh0ck · 2011-12-26 20:35 · Score: 1

nm.. its late... not thinking.

32-bit by mwvdlee · 2011-12-26 21:32 · Score: 1

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.

--
Slashdot social media options: AIM, ICQ, Yahoo, Jabber and Mobile Text. Why no MySpace?

only after it happens by Anonymous Coward · 2011-12-27 01:18 · Score: 0

[rant]
This is a bit OT, but I wanted to make the point that people suddenly care about collision problems in hashes only after the fact.
In git, for example, each unique commit and its history are identified with a SHA-1 hash that depends on the whole history of the project up to that commit.
What happens in the extremely rare and improbable case (or maliciously constructed case) where two SHA-1 hashes collide?
Depending on exactly where and when the collision occurs, the repository can fall apart, and nothing works anymore (tested).
Every single comment about this issue on the mailing list has been ridiculed. "It will never happen! Stop worrying!"
The day it happens, suddenly they will realize: hey, we should have dealt with the failure case after all, to at least leave the repository in a consistent state.
Only after the fact. Before that, you are an idiot.
[/rant]

cryptography as protest by Weezul · 2011-12-27 01:43 · Score: 2

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

Re:This is an example of the strength of the proto by paulproteus · 2011-12-27 06:12 · Score: 2

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

Re:This is an example of the strength of the proto by Zero__Kelvin · 2011-12-27 09:18 · Score: 2

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

Hey Stupid by Zero__Kelvin · 2011-12-27 09:23 · Score: 1

He didn't say "You'd have to be stupid not to understand the birthday paradox", he said that you'd have to be stupid to think that the GnuPG developers don't understand it.

--
Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun

Re:Hey Stupid by Anonymous Coward · 2011-12-27 11:40 · Score: 0

Actually, no he didn't. He said the GPG developers would have to be stupid not to understand it. But that was a really good effort, so you should feel proud for trying.

How is this news? by The+Other+White+Meat · 2011-12-27 11:36 · 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...

--

--- Generation X: The first generation to have SIG lines inferior to their parents... ---

Hey Stupid v2.0 by Zero__Kelvin · 2011-12-27 12:02 · Score: 0

Dear Stupid and Cowardly:

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 ..., and it is therefore common to say that someone is saying something when they have not explicitly stated something, but rather implied it. Still, your effort to condescend was valiant, and you should feel proud for trying!

--
Guns don't kill people; Physics kills people! - John Lithgow as Dick Solomon on Third Rock From The Sun

Re:This is an example of the strength of the proto by stoborrobots · 2012-01-08 17:17 · Score: 1

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

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 Preston Wilson <pres@palmjunkie.com>

--
"Go to CNN [for a] spell-checked, fact-checked summary" -- CmdrTaco

Slashdot Mirror

GnuPG Short ID Collision Has Occurred.

110 comments