Public Key Cryptography designates the class of cryptographic algorithms that includes asymmetric encryption (and its cousin key exchange) and digital signatures. In these algorithms, there are two operations that correspond to each other (encrypt -> decrypt, or sign -> verify) with the characteristic that one of the operations can be done by everybody while the other is mathematically restricted to the owner of a specific secret. The public operation (encrypting a message, verifying a signature) uses a public parameter called a public key; the corresponding private operation (decrypting that which was encrypted, signing that which can be verified) uses a corresponding private parameter called a private key. The public and private key come from a common underlying mathematical object, and are called together a public/private key pair. The magic of asymmetric cryptography is that while the public and private parts of a key pair correspond to each other, the public part can be made, indeed, public, and this does not reveal the private part. A private key can be computed from a public key only through a computation that is way too expensive to be envisioned with existing technology.
To make the story short, if you know the public key of some entity (a server, a human user...) then you can establish a secured data tunnel with that entity (e.g. with SSL/TLS in a connected context, or encrypting emails with S/MIME).
The problem, now, is one of key distribution. When you want to connect to a server called www.example.com
, how do you make sure that the public key you are about to use really belongs to that server ? By "belong", we mean that the corresponding private key is under control of that server (and nobody else).
Public Key Infrastructures are a solution for that problem. Basically:
- The goal of a PKI is to provide to users some verifiable guarantee as to the ownership of public keys.
- The means of a PKI are digital signatures.
In that sense, a PKI is a support system for usage of public key cryptography, and it itself uses public key cryptography.
The core concept of a PKI is that of a certificate. A certificate contains an identity (say, a server name) and a public key, which is purported to belong to the designated entity (that named server). The whole is signed by a Certification Authority. The CA is supposed to "make sure" in some way that the public key is really owned by the named entity, and then issues (i.e. signs) the certificate; the CA also has its own public/private key pair. That way, users (say, Web browsers) that see the certificate and know the CA public key can verify the signature on the certificate, thus gain confidence in the certificate contents, and that way learn the mapping between the designated entity (the server whose name is in the certificate) and its public key.
Take five minutes to grasp the fine details of that mechanism. A signature, by itself, does not make something trustworthy. When a message M is signed and the signature is successfully verified with public key Kp, then cryptography tells you that the message M is exactly as it was, down to the last bit, when the owner of the corresponding private key Ks computed that signature. This does not automatically tell you that the contents of M are true. What the certificate does is that it moves the key distribution problem: initially your problem was that of knowing the server's public key; now it is one of knowing the CA's public key, with the additional issue that you also have to trust that CA.
How can PKI help, then ? The important point is about numbers. A given CA may issue certificates for millions of servers. Thus, by action of the CA, the key distribution problem has been modified in two ways:
From "knowing the public keys of hundreds of millions of server certificates", it has been reduced to "knowing the public keys of a thousand or so of CA".
Conversely, an additional trust requirement has arisen: you not only need to know the CA keys, but also you need to trust them: the CA must be honest (it won't knowingly sign a certificate with a wrong name/key association) and also competent (it won't unknowingly sign a certificate with a fake name/key association).
The PKI becomes a true infrastructure when recursion is applied: the public keys of CA are themselves stored in certificates signed by some über-CA. This further reduces the number of keys that need to be known a priori by users; and this also increases the trust issue. Indeed, if CA2 signs a certificate for CA1, and CA1 signs a certificate for server S, then the end user who wants to validate that server S must trust CA2 for being honest, and competent, and also for somehow taking care not to issue a certificate to incompetent or dishonest CA. Here:
- CA1 says: "the public key of server S is xxx". CA1 does not say "server S is honest and trustworthy".
- CA2 says: "the public key of CA1 is yyy AND that CA is trustworthy".
If you iterate the process you end up with a handful of root CA (called "trust anchors" in X.509 terminology) that are known a priori by end users (they are included in your OS / browser), and that are considered trustworthy at all meta-levels. I.e. we trust a root CA for properly identifying intermediate CA and for being able to verify their trustworthiness, including their ability to themselves delegate such trustworthiness.
Whether the hundred or so of root CA that Microsoft found fit to include by default in Windows are that much trustworthy is an open question. The whole PKI structure holds due to the following characteristics:
PKI depth is limited. A certificate chain from a root CA down to an SSL server certificate will include 3 or 4 certificates at most.
CA are very jealous of their power and won't issue certificates to just any wannabe intermediate CA. Whether that "CA power" is delegated is specified in the certificate. When a CA issues a certificate to a sub-CA, with that specific mark, it does so only within a heavy context (contracts, insurances, audits, and lots of dollars). Ultimately, trust is ensured through fear. Offending CA are severely punished.
Nobody really has interest in breaking the system, since there is no readily available substitute.
Note that, down the chain, the server S is verified to really own a specific public key, but nobody says that the server is honest. When you connect to https://www.wewillgraballyourmoney.com/
and see the iconic green padlock, the whole PKI guarantees you that you are really talking to that specific server; it does not tell you that sending them your credit card number would be a good idea.
Moreover, all of this is association between the server name as it appears in the target URL and a public key. This does not extend to the name intended by the user, as that name lives only in the user's brain. If the user wants to connect to www.paypal.com
but really follows a URL to www.paaypaal.com
, then the PKI and the browser will in no way be able to notice that the user really wanted to talk to PayPal, and not another server with a roughly similar (but not identical) name.
The main use case for a PKI is distributing public keys for lots of entities. In the case of Web browsers and SSL, the browser user must be able to check that the server he tries to talk to is indeed the one he believes it to be; this must work for hundreds of millions of servers, some of which having come to existence after the browser was written and deployed. Reducing that problem to knowing a hundred root CA keys makes it manageable, since one can indeed include a hundred public keys in a Web browser (that's a million times easier than including a hundred million public keys in a Web browser).
Client certificates are a SSL-specific feature. In all of the above we talked about a SSL client (Web browser) trying to authenticate a SSL server (Web server with HTTPS). SSL additionally supports the other direction: a SSL server who wants to make sure that it talks to a specific, named client. The same mechanism can be used, with certificates.
An important point to notice is that the server certificate and the client certificate live in different worlds. The server certificate is validated by the client. The client certificate is validated by the server. Both validations are independent of each other; they are performed by distinct entities, and may use distinct root CA.
The main reason why SSL servers have certificates is because clients cannot possibly know beforehand the public keys of all servers: there are too many of them, and new ones are created with every passing minute. On the other hand, when a server wants to authenticate a client, this is because that client is a registered user. Usually, servers know all their users, which is why most can use a simpler password-based authentication mechanism. SSL client certificates are thus rather rare in practice, because the main advantage of certificates (authenticating entities without prior knowledge) is not a feature that most servers want.