A beginner's guide to Public Key Infrastructure

PKI can help keep your network secure, but it can be a hard concept to understand. Brien Posey explains how it works.

A few months ago, I attended a conference. A security related session had just ended, when a fellow attendee that was sitting next to me asked me if I understood what the speaker was talking about. When I answered yes, the man asked me to explain it to him in laymen's terms. After talking to him for a few minutes, I realized that although he had worked with computers for a few years, he did not really understand public key infrastructure (PKI). He told me that he had tried to read about it on a few occasions, but that all of the books or Web sites that he found on the subject either assume that you already know all about PKI or they use so many big words that they are hard for a beginner to understand. I thought about his statement and realized that he was right. I have never seen anything on PKI that was geared toward a novice. I decided right then that I wanted to be the one to write a beginner's guide to PKI.

Before I Begin

Before I get started, I just want to point out that this is article is intended to be an introduction to PKI. There is no way that I could possibly cover the topic thoroughly without writing a good sized book.

What is PKI?

As you've probably already figured out, PKI stands for Public Key Infrastructure. PKI has lots of different uses, but it is used primarily for encrypting and / or signing data. Encrypting data refers to scrambling it in a way that makes it unreadable except to authorized persons.

Signing data basically refers to authenticating it. A good example of this is signing an E-mail message. If an E-mail message contains a valid digital signature, it proves two things. First, it proves that the message has not been tampered with in transit. Second, it proves that the message is from the person that it claims to be from. E-mail messages are not the only thing that can be signed though.

You've probably seen device driver's or applications that contain a digital signature from the manufacturer. Such digital signatures prove that the code was really developed by the company that it claims to be from. I will talk a lot more about digital signatures later on.

The Anatomy of PKI

PKI is based on a mechanism called a digital certificate. Digital certificates are sometimes also referred to as X.509 certificates or simply as certificates. Think of a certificate as a virtual ID card.

In the real world, people use ID cards such as a driver's license, passport, or an employee ID badge to prove their identity. A certificate does the same basic thing in the electronic world, but with one big difference. Certificates are not just issued to people (users, administrators, etc.). Certificates can also be issued to computers, software packages, or to just about anything else that you may need to prove the identity of.

Certificates are very useful in high security situations. For example, suppose that you needed to securely transmit data from a Windows XP workstation to a Windows 2003 Server in your company. How do you really know that you are transmitting the data to the actual server and not to an imposter? One way of insuring the integrity of the transaction is to use digital certificates to prove the identities of both machines. In fact, digital certificates are one of the underlying requirements of the IPSec protocol that is designed to securely transmit data over Windows networks.

OK, so a secure session can be established because two machines are able to present each other with certificates. You might be wondering though, what makes the certificates so trustworthy. These days, if you want to leave the country, you pretty much have to have a passport regardless of where you are going.

A few years ago though, you could travel to Canada, Mexico, or to some of the Caribbean islands and use a birth certificate and a driver's license instead of a passport. That being the case, let's imagine that these forms of ID are still accepted and that you wanted to travel to the Bahamas. When you arrive at the airport in Nassau, you give the immigration officer your driver's license. The officer has absolutely no idea who you are, but he knows that your driver's license has your name on it, along with your picture. The fact that you hand the officer a plastic card with a name and picture on it means nothing to him. However, your license was issued by government agency. Of course the Bahamas is a foreign country and the officer may or may not have ever heard of your state. What matters to him though is that the Federal Government of the United States trusts the state to use due diligence in proving your identity before they issue a license.

So what does this have to do with digital certificates? Let's go back to my earlier example in which a Windows XP machine needed to prove its identity to a server. Think of the process of the Windows XP machine presenting the server with its digital certificate as being similar to giving the immigration officer a driver's license. The certificate itself proves nothing to the server. However, if the certificate was issued by a source that the server knows and trusts then the server will accept the machine's certificate as proof of its identity.

This raises the question of where do certificates come from and how do machines decide whether or not to trust them? Well, there are a number of places that certificates can come from. One source is from third party certificate authorities, such as VeriSign. Windows is configured by default to trust anything with a valid VeriSign certificate. There are a few other third party certificate authorities that are also trusted by default.

Windows 2000 Server and Windows Server 2003 also allow you to create your own certificate authority. Sometimes it's more practical and a lot less expensive to just create your own certificate authority and allow it to issue certificates on an as needed basis, according to your corporate security policy.

Certificates and PKI

So far I have talked a lot about certificates, but you may be wondering what certificates have to do with PKI. PKI works by assigning a user a pair of keys. These keys are generated by running a mathematical process against the user's certificate. The keys themselves are nothing more than a very long alpha-numeric string.

One of the keys is designated as the user's private key, while the other is designated as the user's public key. The idea is that only the user who owns the keys has the private key, but the user's public key can be freely given to anyone. Normally, a certificate authority or a key management server passes out public keys whenever they are requested, but public keys could really be distributed by any means.

Suppose for a moment that a user needed to encrypt a file. The user would use their private key to encrypt the file. Once the file is encrypted, only the public key can decrypt it. At first, this probably doesn't sound very secure since anyone in the world can have the user's public key just by asking for it. However, there is one detail that you need to consider. The user's public key can only decrypt files, it can not be used to encrypt anything. Furthermore, it can only decrypt items that have been encrypted using the corresponding private key. Therefore, if a public key is used to decrypt a file, it absolutely guarantees that the person who encrypted it was the owner of the corresponding private key (assuming that the private key hasn't been stolen). For example, if I encrypted a file with my private key, and you used my public key to open it, then you can be sure that I was the person who encrypted the file.

This concept is very important when it comes to producing and authenticating digital signatures. To see how this concept works, let's pretend that I need to send you an E-mail message and that because of the sensitivity of the message, you need to be absolutely sure that the message came from me and not from someone pretending to be me. For this example, we will also pretend that the message does not need to be encrypted. You just need to be able to verify the identity of the person who sent the message (me) and verify that the message was not intercepted and altered in transit. This is what a digital signature does for E-mail in the real world. The example below is simplified, but accurately illustrates how a digital signature works.

I would start out by typing the message. For simplicity's sake, let's assume that the message says: The check is in the mail. The first thing that the E-mail program that I am using would have to do is to produce a non reversible hash of the message. A hash is nothing more than a mathematical computation based on the contents of the message. In the real world, hashes are very complex, but for the sake of demonstration, I will pretend that we are creating a hash by adding together the ASCII values of each character in the message (including spaces and punctuation). The hash would look something like this:

The check is in the mail.

84 + 104 + 101 + 32 + 99 + 104 + 101 + 99 + 107 + 32 + 105 + 115 + 32 + 105 + 110 + 32 + 116 + 104 + 101 + 32 + 109 + 97 + 105 + 108 + 46 =Â 2180

Assuming that I have added the numbers correctly, the sum of the ASCII values used to construct the message is 2180. As you may recall from the previous paragraph, I said that we needed to use a non-reversible hash. The reason why the hash is non-reversible is because there is no way that you can look at the number 2180 and see that the message was "The check is in the mail". You could theoretically run a brute force attack against the number 2180 and look at all of the different combinations of ASCII values that add up to this number in an effort to get the original message, but there are some problems with that.

First, there would be a huge number of ASCII strings that add together to produce the correct value. I won't claim to be enough of a mathematician to tell you how many possible strings there are, but it's a bunch. The second problem is knowing the algorithm that was used to produce the hash. In this case, I used an extremely simple algorithm, but in real life the algorithms are much more complex and are not highly publicized. The third problem is picking out which of the results is the original message.

You could use a dictionary program to filter out junk strings and leave only those messages that contain real words, but then anagrams become a problem. Anagrams refer to being able to change the order of the letters in a phrase to spell out something different. For example, if you were to change the order of the letters in the word "dog" you could produce the word "god". Both words would both produce the same hash value using the algorithm above. My point is that for all practical purposes, the hash value is non-reversible.

Once my E-mail client has produced the hash, it appends the hash to the end of the message. The idea is that when the recipient receives the message, the recipient's computer calculates the message's hash by using the same algorithm that my machine used to produce the hash in the first place. If the recipient calculates the same value as the hash value that is appended to the end of the message, then the recipient can be sure that the message has not been altered in transit, and all is right with the world, right?

Not so fast� There is absolutely nothing stopping a hacker from intercepting the message, changing the message's contents, and then changing the hash to reflect the message's new contents. Besides, I haven't done anything to prove my identity to the message's recipient.

This is where PKI comes into play. We have calculated a hash value that the recipient should be able to use to verify that the message hasn't been modified in route, but presently there is nothing stopping a hacker from modifying the hash value along with the message. Suppose however that I used my private key to encrypt the hash value before I transmitted the message.

If I did this, then anybody can read the hash value because it can be decrypted with my public key and my public key is freely available to anyone who asks for it. Keep in mind though that the only things that my public key can only decrypt things that were encrypted by my private key. Therefore, when the recipient receives the E-mail message, they use my public key to decrypt the hash value. If they are able to do this successfully, then they know beyond a shadow of a doubt that I am the one who encrypted the hash value. They can then compute a hash of the message for themselves. If their computed hash value matches the now decrypted hash value that is appended to the message, then the recipient knows for certain that I am the one who sent the message and that the message has not been tampered with.

To put it simply, I have digitally signed the message. In the real world, the algorithms used to create digital signatures are more complex, but the process is very similar to what I have just shown you. Furthermore, this process isn't just used to sign E-mail messages. The process can be used to sign software packages or just about anything else.