Certificate Authority, Web of Trust, Or. . . ?

Developer.com content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.

Wow, four more days and we’re done with 2000. Turns out the millennium bug was a bit of a non-event. I wonder if any of the survival nuts have come out of their shelters yet. Well, this was supposed to be the year of PKI, at least according to the ads I saw in magazines. Unfortunately, it seems that many readers weren’t paying attention to the ads, and while PKI has continued to grow, it hasn’t taken the market by storm.

There are many issues retarding the growth of PKI, not the least of which was the RSA patent. Fortunately, this has now expired in the US, meaning companies can use it in commercial products without having to pay a license fee. Of course, most companies will still end up paying a large sum of money for an RSA implementation; B-Safe from the RSA company is quite popular and far from cheap. Even ignoring this the simple fact, the fact remains that good programmers who know PKI do not come cheap. But I think the problems are more deep-seated than that.

Certificate Authorities (CAs)

The conventional thinking goes something like this:

We need to authenticate users (internal or otherwise) and organizations (again internal or otherwise), so we will set up a trusted third party or internal organization that will be the CA. This CA will buy a whole bunch of nifty hardware and software that can be used to create and sign digital certificates (usually X.509-based). People and organizations will then go to the CA, prove their identity, hand over their public key and get it signed by one of the CA’s keys. The CA’s public keys will also be made available, sometimes built into software directly (as in the case of WWW browsers) so that people can authenticate the digital signature on the certificate they are given by someone trying to communicate with them.

Well, this is all fine and dandy in theory, but in the real world it gets horribly complex and prone to error. Several assumptions must be made for this process to work:

• The CA is trustworthy

• The CA is secure and the CA’s keys are secure

• The process used to prove identity is secure

• The process used to send a certificate to the CA for signing is secure

And this is just to get certificates out in the real world. Once you want to actually verify a certificate, you need to ensure:

• The CA’s keys are properly distributed

• The software checking the signature is secure

• The certificate you are checking has not been revoked

And these are only the major problems (I’ve been conveniently ignoring many of the smaller ones). If any link in this security chain is broken or mishandled, the entire process is useless. Add to this a number of other problems:

X.509 certificates can only be signed by one entity, so you need one certificate for each organization you deal with (one for your company, one for personal use, etc.) as the integration between CAs is extremely limited currently. You must store these keys securely, which means you can’t just keep the certificates on your hard drive. What happens when you need to use them while on the road, issues like the certificate being stolen aside? The certificates must then be portable, meaning a smartcard — too bad many smartcards and readers are incompatible.

Once you have decided on a set of compatible smartcards and readers, you must then check that the certificate someone hands you for a transaction hasn’t been revoked. This involves going to the CA’s site and asking. But what happens if the site is down? Do you refuse the order for a $3000 computer? Even if all this works, how do you know you are dealing with the right entity? There are many John Smiths in the world; which one are you talking to? Identifying features such as physical addresses, phone numbers and email addresses are prone to change. Perhaps in future some sort of hash value of a biometric value will be used, but this is quite a ways off.

Even when everything goes perfectly, what do you when someone disputes a charge? They claim that their smartcard was stolen and the password guessed — they did not order 12 months of hot-raunchy-naked-monkeys.com. Or worse yet, someone just took out a $200,000 bank loan for a house in your name, signing it with your electronic certificate. There is no real established process yet for dealing with this, unlike with, say, credit cards or debit cards — who themselves took some time to work out a set of rules, which generally put the merchants and customers at a severe disadvantage.

Assuming everything works perfectly, you need to reissue certificates every so often: one year seems to be a popular option, meaning you have to go through the whole identity proof again.

Web of Trust

Well, perhaps we can solve some of these problems with a PGP-style web of trust. PGP and GnuPG have some significant advantages over X.509 certificates. A single key can have multiple identities; for example, I can create a PGP key with "Kurt Seifried, seifried@seifried.org" as the primary identity (this is my "permanent" email address, a poor unique identifier but a little better than nothing), and a secondary ID of "Kurt Seifried, seifried@securityportal.com" (my current job-related email address).

This key could then be signed by my mother (Alice). If my cousin (Bob) has a copy of Alice’s public key, he could then choose to trust my key (Bob trusts Alice, Alice appears to trust Kurt, so Bob can trust Kurt, right?). If you can’t see the obvious problem with this, then here’s another example: I trust President Bush not to lie, you trust me not to lie, so when I say, "Bush said we’re going to feed the poor, cut taxes and buy Jamaica," do you believe that statement? Probably not. So if PGP/GnuPG go with large central authorities to sign keys, we have all the problems of a CA. If we go with a distributed model (web of trust) we have a new set of problems:

• How many keys can one individual properly sign? That is, how many people can they meet, prove identities to and then sign the keys of? I’m guessing 1000 at most, per year, for any normal individual.

• How do we check for key revocation? Someone has to run a large central database(s) for this to work properly.

So if we assume that everyone on the Internet uses PGP (100 million people), that means you are likely 2-3 "steps" from a key. That is to say, it’s unlikely that you have met the person and signed their key. There is a 1% chance that someone whose key you signed has signed their key, but it’s much more likely that you signed someone’s key who signed someone else’s key who signed the key you just received (OK, the math is off a bit, but you get the idea). Since most users will not go to great lengths to get their keys signed, it is much more likely that any keys you encounter will be signed by people far removed from you in the web of trust.

Summary

With all these problems, it’s little wonder PKI hasn’t taken off. Even companies that take the time and money to deploy PKI often make mistakes that could potentially invalidate the entire process, and some of these mistakes can be very subtle. Even if the whole PKI process goes perfectly, you have to deal with regular expiration of certificates, revoked certificates, and so on. Even if this goes well, you have to deal with people claiming they didn’t make transactions (or did make a transaction): how do you handle this? Add the problems of actual identity, and you have an extremely messy solution that has no hope of delivering what many vendors will happily promise their customers.

Who knows, maybe 2001 will be the real year of PKI.

About the Author

Kurt Seifried (seifried@securityportal.com) is a security analyst and the author of the Linux Administrators Security Guide, a source of natural fiber and Linux security, part of a complete breakfast.