×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

GnuPG Short ID Collision Has Occurred.

Unknown Lamer posted more than 2 years ago | from the 32-bits-ought-be-enough-for-anyone dept.

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

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

110 comments

Let's face it (4, Insightful)

2.7182 (819680) | more than 2 years ago | (#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 (5, Insightful)

Anonymous Coward | more than 2 years ago | (#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:Let's face it (3, Interesting)

ptx0 (1471517) | more than 2 years ago | (#38499876)

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 (5, Insightful)

Anonymous Coward | more than 2 years ago | (#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:Let's face it (3, Interesting)

Anonymous Coward | more than 2 years ago | (#38500002)

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 (5, Insightful)

Anonymous Coward | more than 2 years ago | (#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.

Re:Let's face it (0)

Anonymous Coward | more than 2 years ago | (#38503010)

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 (1)

Algae_94 (2017070) | more than 2 years ago | (#38506130)

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 (5, Funny)

PPH (736903) | more than 2 years ago | (#38500112)

want to trust your mechanic with pulling your teeth out?

Not again.

Re:Let's face it (2)

crutchy (1949900) | more than 2 years ago | (#38500622)

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 (1)

Jumperalex (185007) | more than 2 years ago | (#38502394)

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

Re:Let's face it (0)

Anonymous Coward | more than 2 years ago | (#38506444)

It's better than what he was doing to my ass.

You insensitive clod! (1, Funny)

PPH (736903) | more than 2 years ago | (#38500118)

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

Re:Let's face it (2)

bonch (38532) | more than 2 years ago | (#38500156)

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 (-1, Flamebait)

viperidaenz (2515578) | more than 2 years ago | (#38500406)

Do you know everything about baseball? No. I don't want to know anything about the worlds most boring sport. Now Blernsball on the other hand...

How about your car engine? Yes

Or professional wrestling? Its scripted. thats all I need to know

Re:Let's face it (1)

Gordonjcp (186804) | more than 2 years ago | (#38501090)

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 (1)

Bill, Shooter of Bul (629286) | more than 2 years ago | (#38502446)

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.

Re:Let's face it (2)

drussell (132373) | more than 2 years ago | (#38500632)

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 (2)

Raenex (947668) | more than 2 years ago | (#38502492)

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 (-1)

Anonymous Coward | more than 2 years ago | (#38500640)

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'm a moocher you insensitive clod. I demand you do the thinking and learning for me. It's my constitutional right.

Re:Let's face it (0)

Anonymous Coward | more than 2 years ago | (#38504464)

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 (1)

Pharmboy (216950) | more than 2 years ago | (#38505950)

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.

Re:Let's face it (1)

deniable (76198) | more than 2 years ago | (#38500014)

But how many people actually use GPG? The non-technical users just don't seem to bother.

Re:Let's face it (4, Insightful)

arth1 (260657) | more than 2 years ago | (#38500070)

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 (3)

ewanm89 (1052822) | more than 2 years ago | (#38500978)

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 (1)

drinkypoo (153816) | more than 2 years ago | (#38501220)

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:Let's face it (1)

marcosdumay (620877) | more than 2 years ago | (#38503730)

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:Let's face it (1)

Zero__Kelvin (151819) | more than 2 years ago | (#38506930)

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.

Re:Let's face it (1)

tenco (773732) | more than 2 years ago | (#38501692)

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 (1)

DarkOx (621550) | more than 2 years ago | (#38501676)

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.

cryptography as protest (2)

Weezul (52464) | more than 2 years ago | (#38502146)

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:Let's face it (1)

betterunixthanunix (980855) | more than 2 years ago | (#38502400)

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.

This is an example of the strength of the protocol (1, Interesting)

robbak (775424) | more than 2 years ago | (#38499810)

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 (5, Informative)

robbak (775424) | more than 2 years ago | (#38499846)

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 (5, Funny)

gparent (1242548) | more than 2 years ago | (#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!

Re:Above post is ignorant (-1)

Anonymous Coward | more than 2 years ago | (#38499904)

Speaking of dumb stories, we haven't had a "3D printing will change the world!" hype-fest or a "the species must colonize the galaxy!" liturgy lately.

Re:Above post is ignorant (1, Funny)

Anonymous Coward | more than 2 years ago | (#38500226)

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 (0)

bonch (38532) | more than 2 years ago | (#38500176)

If that's the goal, just select one of the following story templates:

- Google And Android Are Awesome
- Apple Sucks
- Arbitrary Linux News
- Something Advocating Piracy
- Daily Bitching About Patents
- Ask Slashdot: "It's still 1997 in my house and I've never heard of Google so I'm asking this question"
- Filler Technology Story That Only Gets 50 Comments

Re:Above post is ignorant (0)

inflex (123318) | more than 2 years ago | (#38500984)

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 (-1)

Anonymous Coward | more than 2 years ago | (#38501092)

He forgot the "Bitcoin is Awesome" and "Windows Sucks" templates.

I just can't lose!? (Re:Above post is ignorant) (-1, Offtopic)

robbak (775424) | more than 2 years ago | (#38500578)

Hmm. I make a dumb post, it gets modded up once. I make a post that corrects my dumb post, and it gets modded +5. Just how does one LOSE karma around here?

Re:I just can't lose!? (Re:Above post is ignorant) (1, Funny)

Anonymous Coward | more than 2 years ago | (#38500654)

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:I just can't lose!? (Re:Above post is ignorant) (-1)

Anonymous Coward | more than 2 years ago | (#38501856)

I have a much higher threshold to mod down.

I'm busy spending my points. TTYL

Re:Above post is ignorant (0)

Anonymous Coward | more than 2 years ago | (#38500638)

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 (0)

Anonymous Coward | more than 2 years ago | (#38501486)

Indeed - thanks to the birthday paradox it only takes 92683 hashes to probably get a collision somewhere.

Re:Above post is ignorant (1)

TheRaven64 (641858) | more than 2 years ago | (#38501530)

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.

Re:This is an example of the strength of the proto (1)

Anonymous Coward | more than 2 years ago | (#38499898)

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 (5, Insightful)

arth1 (260657) | more than 2 years ago | (#38500130)

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:This is an example of the strength of the proto (2)

paulproteus (112149) | more than 2 years ago | (#38504926)

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:This is an example of the strength of the proto (2)

Zero__Kelvin (151819) | more than 2 years ago | (#38507184)

... and nobody cares, because anyone with a clue already knew this, and it has zero effect on the effectiveness of GnuPG.

Expired certificate on bug report host's server? (1)

OverTheGeicoE (1743174) | more than 2 years ago | (#38499812)

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

Re:Expired certificate on bug report host's server (0)

Anonymous Coward | more than 2 years ago | (#38499884)

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

According to Perspectives [perspectives-project.org] , it's been consistent for the past 176 days [networknotary.org] . Good enough for me.

Re:Expired certificate on bug report host's server (0)

Anonymous Coward | more than 2 years ago | (#38499968)

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

What is this? Outlook?

So? (5, Informative)

cloudmaster (10662) | more than 2 years ago | (#38499854)

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? (5, Informative)

mgiuca (1040724) | more than 2 years ago | (#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.

Thanks for clarifying -- I should have researched. (3, Informative)

kfogel (1041) | more than 2 years ago | (#38500180)

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:Thanks for clarifying -- I should have research (1)

mgiuca (1040724) | more than 2 years ago | (#38500296)

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

Re:Thanks for clarifying -- I should have research (1)

kangsterizer (1698322) | more than 2 years ago | (#38500404)

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

The semantics here are actually important ;-)

Re:Thanks for clarifying -- I should have research (1)

mgiuca (1040724) | more than 2 years ago | (#38500524)

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:So? (1)

impaledsunset (1337701) | more than 2 years ago | (#38500992)

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:So? (0)

Anonymous Coward | more than 2 years ago | (#38501056)

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? (1)

mgiuca (1040724) | more than 2 years ago | (#38501840)

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.

A collision in a 32 bit key space? Unpossible! (4, Insightful)

zill (1690130) | more than 2 years ago | (#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:A collision in a 32 bit key space? Unpossible! (0)

Anonymous Coward | more than 2 years ago | (#38499974)

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! (3, Insightful)

Anonymous Coward | more than 2 years ago | (#38499998)

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]

GnuPG Short ID Collision Has Occurred. (-1)

Anonymous Coward | more than 2 years ago | (#38499980)

Are you saying 'never heard of quantum computing/encryption' ! seriously ????

Why do I care? (0)

b4dc0d3r (1268512) | more than 2 years ago | (#38499982)

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? (1)

Anonymous Coward | more than 2 years ago | (#38500086)

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 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? (1)

gstrickler (920733) | more than 2 years ago | (#38500538)

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 (2)

DERoss (1919496) | more than 2 years ago | (#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.

Re:This well-known but not a problem (1)

thogard (43403) | more than 2 years ago | (#38500576)

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:This well-known but not a problem (1)

ewanm89 (1052822) | more than 2 years ago | (#38501104)

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

Which surprises you most? (4, Insightful)

dfay (75405) | more than 2 years ago | (#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.

Re:Which surprises you most? (2)

mgiuca (1040724) | more than 2 years ago | (#38500318)

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 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? (0, Informative)

Anonymous Coward | more than 2 years ago | (#38501200)

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? (1)

wisty (1335733) | more than 2 years ago | (#38504354)

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.

Hey Stupid (1)

Zero__Kelvin (151819) | more than 2 years ago | (#38507254)

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.

Re:Which surprises you most? (0)

Anonymous Coward | more than 2 years ago | (#38502042)

Dur CS 201 is tough.

frist 5top (-1)

Anonymous Coward | more than 2 years ago | (#38500336)

FreeBSD at about 80 share. FrreBSD is a child knows fucking numbers,

Fingerprint (1)

kangsterizer (1698322) | more than 2 years ago | (#38500394)

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 (1)

arth1 (260657) | more than 2 years ago | (#38501230)

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 (1)

marcosdumay (620877) | more than 2 years ago | (#38503894)

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.

Collisions in a 32-bit space.... (3, Informative)

gstrickler (920733) | more than 2 years ago | (#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.

Fetch the full fingerprint, not the keyID (0)

GPLHost-Thomas (1330431) | more than 2 years ago | (#38500710)

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 (2)

Ragzouken (943900) | more than 2 years ago | (#38501760)

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 (1)

GPLHost-Thomas (1330431) | more than 2 years ago | (#38503946)

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.

32-bit (1)

mwvdlee (775178) | more than 2 years ago | (#38501014)

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.

only after it happens (0)

Anonymous Coward | more than 2 years ago | (#38501976)

[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]

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...