ciphergoth | PKI deserves to die

In response http://www2.cio.com/research/security/edit/a05232002.html

From: Carl Ellison <cme@acm.org>
Subject: Re: PKI: Only Mostly Dead

Scott,

as far as I'm concerned PKI is not only dying, it deserves to die
much more quickly. That's because when it works, it still doesn't
work.

See the two papers to which I contributed at last month's PKI
Research Workshop http://www.cs.dartmouth.edu/~pki02/

Look especially at what we call the John Wilson problem. In a
nutshell, if you bind a name to a key, even if you do that always
accurately and even if your certificates interoperate with my
software, you have done nothing for me if there are more than about
1000 certified people in the world. That's because there are too
many John Wilsons. I can't tell them apart by name, when you lump
them all together into one big pool (the pool of all people the CA
certifies -- e.g., a big one like VeriSign -- or a little one like
Intel Corporation with only 70,000 and 8 John Wilsons). If I can't
tell them apart (and people can't -- for which we have definite
proof), then I am forced to make a guess as to which one is the right
one -- if the right one is represented at all -- and when I'm handed
a certificate saying that this S/MIME message or HTTPS page came from
John Wilson, I'm not given the list of all John Wilsons, so I don't
even get to compare them to see which one looks like the closest
match.

PKI deserves to die not because of vendor greed, although there is
plenty of that, but because the original idea was wrong. When you
bind a person's name to a public key you have not identified the key
in a way that is useful to me. That's because if I know the name of
the keyholder, I still don't know who the keyholder is.

- Carl

P.S. I strongly recommend your reading those papers in the preprints
available at the PKI Workshop web site.
+------------------------------------------------------------------+
|Carl M. Ellison         cme@acm.org     http://world.std.com/~cme |
|    PGP: 08FF BA05 599B 49D2  23C6 6FFD 36BA D342                 |
+--Officer, officer, arrest that man. He's whistling a dirty song.-+

Flat | Top-Level Comments Only

From:

ciphergoth.livejournal.com

Are key fingerprints guaranteed unique?

Short answer: yes, effectively as unique as public keys. The difficulty of generating a collision by the most effective attack known is around 2^80 (for modern 160-bit fingerprints anyway), which is beyond anyone's reach at the moment. The difficulty of finding another key that has the same fingerprint as a specific key is believed to be 2^160.

From:

djm4

That's not the point. I'm not talking about deliberately attempting to create a key with the same fingerprint as another one, I'm talking about it happening by accident. If it can happen by accident (no matter how small the chances are), then a public key fingerprint is not suitable as a unique index in the way that an e-mail address - guaranteed to be unique by the way e-mail addresses are constructed - is suitable.

From:

ciphergoth.livejournal.com

I understand why you might feel this way, but accepting a negligible probability of failure is pretty much an inevitable part of using cryptography at all. You just get used to thinking of "fails with negligible probability" as the same as "flawless".

From:

djm4

...a negligible probability of failure is pretty much an inevitable part of using cryptography at all.

Well, yes, I get that, but it doesn't mean that I have to accept an unnecessary probability of failure.

There are several ways of generating a unique index that are flawless (or, at any rate, flawless as long as the system works, which I realise is a pretty big 'if', but it's a different question). E-mail addresses are unique. An auto-incremented integer is unique. Network card Mac addresses are unique. None of these systems have to accept 'well, theoretically the system could generate two or more identical IDs, but it's highly unlikely' - if they're working properly, they can't generate identical IDs.

So why should I accept even a negligible probability of failure when I don't have to?

From:

ukfetish.livejournal.com

> Network card Mac addresses are unique.

I seem to remember reading somewhere that a few manufacturers had screwed this one up, using the same pool of numbers as each other for quite a while for some reason. It didn't show up for a while because companies tend to buy cards all from one manufacturer...

Regards,
Denny

From:

ciphergoth.livejournal.com

if they're working properly

I think you just destroyed your own argument. The practical probability of collison so vastly swamps the theoretical one in both systems, that adding complexity to the system to avoid a negligible probability of failure is the Wrong Way to Go.

There are for example Ethernet cards with colliding MAC addresses, because the manufacturers made mistakes.

Really, preferring a system with zero probability of failure over one with a negligible probability will take you the wrong way in security terms.

From:

djm4

Point taken, but I'm still not convinced. What's wrong with using a key fingerprint coupled to (say) an e-mail address?

From:

djm4

Just to reply to my own point - I think that one thing that bothers me is that it's perfectly valid for two public keys to have the same fingerprint. The only thing it screws up is the unique index in a database that has nothing directly to do with PGP itself. There's no immediate requirement for one or other person using the keys to change.

Whereas if two people get accidentally allocated the same e-mail address, then that actually buggers up mail delivery on the Internet a bit. E-mail delivery for one or both people will, in principle, be broken until one or other of them gives up the e-mail address.

I don't like the idea of creating a system that by implication invalidates something that would have been valid before (two keys with identical fingerprints). I'd far rather base it around something that's aleady invalid (fingerprint and e-mail pairs that are identical).

Did that make any sort of sense?

From:

ciphergoth.livejournal.com

I'll have to explain this to you in the pub sometime. I see why you feel this way, but you're not thinking like a cryptographer...

From:

djm4

Well, no, I wouldn't be, would I? ;-)

From:

ukfetish.livejournal.com

How much does one have to drink before one starts to think like a cryptographer then? ;)

~D.

From:

ukfetish.livejournal.com

I think it might help here to expand 2^80 so that people can see how it relates to the number of people who might be creating these fingerprints. If 2^80 is significantly bigger than the total pool of fingerprint makers then using 'negligible chance of failure' and 'flawless' in the same context would make sense to me. If 2^80 is within an order of magnitude of the number of possible fingerprint makers, then it's not what I'd call a safe risk to take...

Does that make sense? I'm speaking from a position of complete ignorance (but considerable interest) here :)

Okay, I just worked out what 2^80 is :) I'd say 1,208,925,819,614,629,174,706,176 is a fair bit larger than the total pool of email users for the foreseeable future. I'm with the 'negligible chance' vote here *laugh*

Regards,
Denny

From:

djm4

Thank you, I do know how small a number the reciprocal of 2^80 is. I'm still stumped as to why I should accept even this probability when I can reduce it to a theoretical probability of zero with very little effort.

From:

ukfetish.livejournal.com

> Thank you, I do know how small a number the reciprocal of 2^80 is.

Good for you - I didn't.

Therefore I worked it out and posted it for the benefit of any slow types like myself who are very interested and trying hard to follow the conversation. I find it easier to gain an emotional appreciation of the expanded form of the number than I do to gain any feel for the exponent form (or whatever that notation is called).

I'm with you in that I don't understand what's wrong with using an email address as the unique identifier, but I guess I'll just keep reading the arguments until the light dawns on me (possibly).

Regards,
Denny

From:

ciphergoth.livejournal.com

It's better than that. If A is the number of identifiers in use, and B is the size of the identifier pool, the probability of collision is on the order of A^2/2B (where A and B are large, and A^2 << B). So if you assume that everyone on the planet (6E9) has a million public keys, then the probability of collision somewhere in that entire keyspace is under 1 in 40 million billion.