PKI & Certificates

What is Public Key Infrastructure?

If you have ever used the Internet to make a purchase from a secure site you have already used certificates and PKI. In fact more and more web sites are requiring secure connections. So what is PKI and how do these certificates help secure our information?

PKI Theory

Public Key Infrastructure, PKI for short, is the way that web sites secure information so that you know that no one is listening in on your private communications, and you know that no one has changed that data while it was enroute to the web site you intended to receive it and back. But how does this work? How do two 'people' who have never met trust that the information they exchange, in public view and through unknown intermediaries, is secure? The low-level details involve a bit of modulo math, which I won't get into here, but to understand the idea and gain an understanding of the processes involved, no math is required at all!

The first thing we need to be aware of is a digital key. Like the keys you are already familiar with, those little metal protrusions that grant access to our homes, offices, and vehicles, digital keys secure access to things by hiding the information being secured. In order to render information secure a key is used to 'lock' that data, referred to as encrypting, and in order to view that secured information a key is used to 'unlock' that data, referred to as decrypting. This act of encrypting and decrypting information is analogous with locking and unlocking a door. When locked the contents are secured, and when unlocked the contents are available to all.

So we have a fairly basic idea of a key, in computer security parlance what we would call a symmetric key because the same key is used to lock and unlock data, similar to how physical keys work, but our key analogy only goes so far because when securing an area with a physical key you must physically provide the key to grant others access. In other words, to conduct a transaction online using symmetric keys, you would first have to physically meet a representative from that site and provide them with a key, repeating this for each 'entity' you conducted business with online. Obviously this is untenable for online transactions, and e-commerce would be a much different place than it is today if that were required. So we must come up with another way, and what we ended up doing was to extend our idea of how a key works.

Enter the asymmetric key. Unlike a symmetric key, where the same key is used to encrypt and decrypt, an asymmetric key uses a key-pair where each key can encrypt (lock) data that only the other can decrypt (unlock). In other words if I had a key-pair of keys A and B, A could encrypt data that only B could decrypt and B could encrypt data that only A could decrypt. If a key were used to decrypt anything other than something which its opposing pair had encrypted the underlying data would remain concealed

Here I will borrow a little notation from math to illustrate the above paragraph. Let's say P is our unencrypted information, we'll call this plain-text. C_a and C_b is our encrypted information, indicating which key encrypted it, we'll call this cipher-text. We'll show encryption as A(P) or B(P) and we'll show decryption as A(C_b) or B(C_a).
These are the relationships between keys:

  • A(P)=C_a
  • B(P)=C_b
  • A(C_b)=P
  • B(C_a)=P

All this leads to the fundamental relationships:

  • A(B(P))=P
  • B(A(P))=P

Anything else, say A(A(P)), produces unusable garbage; the lock remains intact since the data remains hidden.

When using asymmetric keys we refer to one as a public key and one as a private key. The idea is that we can keep the private key secret and distribute the public key to anyone we would like to communicate with. Information sent to us can be encrypted with the public key and secured until decrypted by the private key, which only you have. When you want to send data to someone you encrypt it with your private key, and only those with the public key can decrypt it. This solves half of our problem. It properly secures all information sent to us, but does not secure the data we send to others, since anyone with the public key could see that information. Note that it does protect that information from being modified, since after modification it could not be encrypted by a nefarious party using your private key, thus only the original message you sent could be decrypted properly by the public key you distributed. This issue of securing information you send is overcome two ways. The first is to use two key pairs, one for each side. Each side provides the other with their public key, and use the other side's public key to encrypt data sent. In this case all data sent can only be decrypted using the private key held by the opposing member. Note that this is referred to as bidirectional authentication. The other strategy is to have the side with the public key generate a symmetric key (recall symmetric keys use the same key to encrypt and decrypt), encrypt that with the public key and send it. The opposing side uses its private key to decrypt the symmetric key and that symmetric key is used for all further communications. In practice, both strategies may be employed. The key here is to recognize that if someone can encrypt a known value with their private key, anyone with the public key could decrypt that, verify that it matches the known value and be assured that the value could only come from someone holding the private key.

So how do certificates fit into PKI? Certificates are the mechanism used to exchange keys and prove authenticity. There are many different types of certificates, used for securing different types of information, but they all basically work the same:

  1. They hold some relatively small piece of critical data, typically a key
  2. They contain identifying information about who they were issued to
  3. They can sign and are typically themselves signed

So certificates are being used to hold keys. The private key held by the owner is stored in one, a private cert, the public key associated with that private key is also stored in one, a public cert. It is that public cert that is distributed to the public to disseminate a public key.

The identifying information indicates who owns the private key associated with that public key held in the public cert.

The signing is the primary technical part of the cert and the meat of the functionality. The signature is what proves ownership. Recall that with asymmetric keys, if we have a known value that is encrypted, and we can decrypt it using a public key and get that known value as a result, we know the value was encrypted using the private key. Knowing this, all I have to do to verify that someone holds a private key associated with a particular public key is to give them a random value to encrypt with their private key and send me that encrypted version, and if I can decrypt it with the public key and get that same random value back I know they are holding the private key. This act of encrypting a known value with a private key is signing. Signature verification is the act of decrypting with the public key and comparing to the original known value.

Note that this relies on two assumptions:

  1. The private key has not been compromised, so the only person in possession of it is the owner
  2. The random value you send to be encrypted with the private key is sufficiently random so as to assure that it does not match past values encrypted by the private key owner

The first assumption is standard for all encryption, compromise of private key data invalidates the strategy in all cases. The second is overcome by using sufficiently large range of cryptographic random values.

This is only half of the puzzle of verifying a web site, however. We need to be able to ensure that the private key is owned by the entity it is supposed to be owned by. For instance, just because someone has a private key that says it is owned by, doesn't mean they are associated with my site. Anyone can make a certificate that says it's owned by, and if they provide a public certificate to you, they would be the ones with the corresponding public key. So our task is not done, we still can't prove identity, we can only prove who holds a private key associated with a particular public key (held in a certificate). This is where Certificate Authorities (CA's) and certificate chaining come in to play.

What are Certificate Authorities and Certificate Chaining?

Certificate authorities (CA) are organizations who issues certificates to individuals and organizations whom they have verified the identity of. As with certificates there are different types of CAs, but for our purposes here we're going to talk about public CAs. We call them public because they have paid the major computer operating system and browser vendors (like Microsoft, Apple, and Google) to include their public certificates, what we call a Root CA Certificate, in those vendors software. The result is that those public CAs correct public keys are already there on your computer, and explicitly trusted. These public CAs act as a baseline for trust, they are organizations which you can prove the identity of from day one on just about every modern computing device.

The next, and final, piece of the puzzle involved in proving identity, certificate chains, require a brief side journey into something called hashing. Hashing, in this context, is the idea of a series of math operations which produce a result from an initial input value where it is not possible to find the initial input value by knowing the result. In math terms these are referred to as one-way functions. Hashing also produces a result that is effectively unique. Hashing is a deep mathematical topic, and a deeper understanding isn't required for the topic at hand. Just understand the one-way nature of a hash, and that in the context of modern security algorithms the results for a given initial input value are effectively unique. With this basic understanding of hashing, we are prepared to understand the topic of certificate chaining.

So we now have a mechanism, signatures, to prove who holds a private key associated with a public key we have, and we have a baseline of trusted certificates holding public keys for CAs that our software developers already verified as authentic for us. The last step to accomplish that is to leverage those public CAs to prove who we are. This is accomplished by a certificate chain, which is really just a chain of signatures starting with that Root CA Certificate that is already on your device. It's created slightly differently from other certificates in the chain, using the following steps:

  1. The CA created a public/private key-pair (asymmetric)
  2. The CA generates a certificate with their identifying information, such as company name, address, and web site and stores the public key in it
  3. The CA generates a hash result value from their public cert, encrypts it with their private key, and attaches it to the certificate as the signature

To validate the signature all that is required is to decrypt the signature with the public key, hash the public cert, and compare the results of both. Remember, we trust these root CA certificates not because of the signatures but because our OS and browser vendors verified them for us.

Now, when someone out there, like your online merchant, wants to prove who they are they can go to the CAs, go through a process to verify their identity, and the CA will issue them a certificate. They will chain the certificate they create for the online merchant to their Root CA cert via signature, using the following steps:

  1. The online merchant will generate a public/private key-pair (asymmetric)
  2. The online merchant will generate a Certificate Signing Request (CSR) containing their identification details such as name, web site, etc, and attach the public key
  3. The online merchant will sign the CSR using a hash of their public cert and send it to the CA
  4. The CA will go through a process to confirm the identity of the entity requesting the certificate and if confirmed they will use the identifying information to generate the requested certificate
  5. The CA will sign the generated certificate with the private key from their root CA certificate, using the hash of the merchant's public cert

This now forms a cert chain, the online merchants certificate linked to the CAs root cert. When visitors go to the online merchants web site and are presented with the certificate they can verify it as follows:

  1. Look at who signed the merchant's certificate and compare to the root CA certs, if no match is found the online merchant's cert is considered untrusted (typically resulting in a warning about the site being insecure)
  2. Use the CA's public key to decrypt the signature on the merchant's cert and compared to the hash of the merchant's cert, if they match we know that the CA verified the identity of the merchant's web site, and you have reasonable assurance that the merchant you are talking to is the one you intended to talk to

There can be any number of certificates in the signing chain. The first is always considered the root, and is always self-signed. The last is the certificate issued to individual entities, in our example an online merchant's web site, called leaf certificates. Everything in between are considered intermediate CAs, or sub CAs, and are called branch certificates. This is a tree analogy, roots, branches, and leaves. The process for verification is the same, find the root and confirm it is explicitly trusted then walk up the signatures and confirm that each public key decrypts the correct hash results matching the certificate hash itself. This not only confirms that the signature is indeed associated with that certificate (made by someone holding the private key), but prevents modification of the certificate, since such modification would alter the results of hashing. Any failure to match the hashes up the chain is a failure to verify (validate) the certificate.

A certificate, from its own perspective, is the subject or child. The CA certificate that signs it is the issuer, authority, or parent. A self-signed (root) certificate is both the parent/child and subject/issuer/authority. All other certificates form a hierarchy with the leaf certificates having no children.