This lesson is mostly a lab: X.509 Certificates Lab
The lab and the instructor demos that proceed it all revolve around a very basic, profound problem — public key encryption provides us with tools that guarantee confidential, authenticated between owners of public keys. What it doesn't provide is a way of guaranteeing that the entity behind that public key is who we think it is. That's what X.509 certificates (and other similar systems) are for.

Man-in-the-middle attacks

Man-in-the-middle is a form of attack that can be carried out in a variety of scenarios. We will describe it in terms of attacking RSA, though this is just one kind of man-in-the-middle attack.

RSA guarantees us the following: you can carry on communication with the owner of public key Kpub and be sure that:

  1. messages you receive can only be read by you, and can only have come form the owner of Kpub
  2. messages you send can only be read by the owner of Kpub, and the owner of Kpub will know that they could only have come form you.
With the usual Alice and Bob scenario, Alice's public key KApub is out there on the Internet, as is Bob's public key KBpub. Alice "owns" KApub because she alone has the matching private key KApriv. Similarly, Bob "owns" KBpub because he alone has the matching private key KBpriv. This is illustrated by the diagram to the right. Following our usual plan, Alice sends Bob the plaintext message msg by:

plaintext — encrypt with KApriv → ciphertext1 — encrypt with KBpub → ciphertext2

... and she sends him ciphertext2. This works great, as long as Alice is really sure that KBpub belongs to the person she knows as "Bob". When that's no longer true, things get ugly.

Suppose we have our usual enemy Eve throwing a public key KA'pub up on the Internet and claiming it's Alice's public key, and throwing a public key KB'pub up on the Internet and claiming it's Bob's public key. The diagram to the left illustrates this. Now Alice thinks she's encrypting her message with Bob's public key, but the public key KB'pub she uses really belongs to Eve. Eve then decrypts and reads the message, perhaps modifying it a bit, and then encrypts it using the real Bob's public key. The real Bob receives the message none the wiser.

What if Alice encrypts with her private key KApriv first, and then with the key KB'pub she thinks belongs to Bob? Then Eve decrypts with her key KB'priv followed by Alice's public key KApub and she has the plaintext message from Alice. Once again, she reads the message or changes it. Then Eve encrypts with her fake key KA'priv first, and then with Bob's public key KBpub. Bob is able to decrypt the plaintext message. Because doing so required KA'pub, the key he believes to be Alice's public key, he thinks this message really must've come from Alice, and that nobody could have read it but himself.

This is called a Man-in-the-middle Attack. Eve, obviously, is the "man-in-the-middle" here. Eve needs to pull off some kind of misdirection to make Alice believe KB'pub really belongs to Bob, and to make Bob believe KA'pub really belong to Alice. But we've seen how to trick people with spam e-mails, misleading links, and convincing copies of webpages, which are a few possible ways to do this.

Identity and web servers

At first blush, the fact that Man-in-the-middle attacks work seems to indicate that RSA (or public key cryptography in general) has failed us. After all, wasn't it supposed to provide a guarantee that if Alice sends Bob a message, Bob can be sure that message really did come from Alice? In fact, this is not what RSA/Asymmetric Encryption guarantee. If Bob decrypts with his private key followed by the public key Kpub, he is only guaranteed that the message was really sent by the owner of Kpub. He has no guarantee of the identity of the owner of Kpub! So RSA has worked perfectly. It's provided exactly the guarantee it said it would provide. But we need something more in order to be safe from Man-in-the-middle attacks. What we need is a way to match public keys with identities.

xkcd.com/1121/

It's important to note that this is not merely a technical problem. What constitutes "identity" is a social problem, and maybe even a philosophical, problem. However, once we've decided what identity means, at least in a limited context, we need technical tools to help bind identities to public keys — a "public key infrastructure" (PKI). The particular system we will look at is based on X.509 Certificates, and it's responsible for mapping identities to public keys in, for example, web browsing with HTTPS.

Let's consider the problem of Man-in-the-middle Attacks on secure web communications, i.e. when using HTTPS. A man-in-the-middle attack would look like this: you want to check your balance at the Navy Federal Credit Union, so you enter the URL www.navyfcu.org in your browser's address bar. RSA is used to provide secure communications between your browser and the webserver (actually, it's only used at the beginning in order to agree on a secret key for that session, after which symmetric encryption is used). A Man-in-the-middle attack would mean that the public key your browser thought belonged to www.navyfcu.org actually belongs to some bad guy. So what does "identity" mean in this context? You think you're communicating with Navy Federal Credit Union. Your browser thinks it's communicating with www.navyfcu.org. RSA thinks it's communicating with public key (4f32 .... 7e). So there are different notions of who exactly we're communicating with.

  1. RSA is responsible for secure, authenticated communication with public key (4f32 .... 7e).
  2. The X.509 Certificate system is responsible for certifying that the public key (4f32 .... 7e) really belongs to domain name www.navyfcu.org.
  3. The user is responsible for knowing that the domain name www.navyfcu.org really belongs to the Navy Federal Credit Union.
In other words, X.509 Certificates certify the mapping of domain names to public keys.

CAC Cards and DoD PKI

Your CAC is a perfect real-world example that brings together a lot of what we talk about in the Models & Tools section of SI110: Pillars of IA (Confidentiality, Authentication, and Non-Repudiation), Asymmetric Cryptography, identity and X.509.

Anyone who receives a CAC must sign* a DD Form 2842:

"You have been authorized to receive one or more private and public key pairs and associated certificates.

"The certificates and private keys will be issued on a Common Access Card (CAC).

"A private key enables you to digitally sign documents and messages and identify yourself to gain access to systems. You may have another private key to decrypt data such as encrypted messages.

"People and electronic systems inside and outside the DoD will use public keys associated with your private keys to verify your digital signature, or to verify your identity when you attempt to authenticate to systems, or to encrypt data sent to you.

*Note: the DD2842 itself can be digitally signed!

X.509 Certificates ... a matter of trust

X.509 is a standard for a Public Key Infrastructure. An X.509 Certificate is a file that a user or a program can use to verify that public key K really belongs to identity I. A Photo ID like a passport does a similar thing for you: it certifies that your name really belongs to your face. Provided a person assures himself that your passport is valid, i.e. not fake, he'll probably believe that your name really does belong to your face. That belief is based on trust: a trust that the U. S. government probably wouldn't issue that passport to you unless the name in the passport was really yours. X.509 certificates work the same way, they are issued by a certificate authority, and if you trust that certificate authority and you assure yourself of the validity of the certificate, then you trust that public key K really belongs to identity I.

Conceptually, a certificate has three pieces of information:

Certificate authorities have certificates as well, and you need that certificate in order to to verify that a certificate is valid. So a participant in this system keeps on hand the certificates of one or more certificate authorities it trusts. When a certificate is received for some entity with whom he wants to communicate, he looks at the issuer's identity: if that matches the common name of one of the authorities he trusts, he'll take the certificate for the authority and use it to verify the new certificate.

A look at how, in principle, a certificate system works

Let's add a new actor to our Alice/Bob/Eve play. Suppose with have a fourth party named Cedric, who is trusted by both Alice and Bob. Cedric has the public/private key-pair KCpub/KCpriv, and Alice and Bob both know his public key. Suppose Alice presented Cedric with her name "Alice" and public key KApub, in such a way that Cedric was satisfied that he was really dealing with Alice. Cedric could make a certificate by encrypting the string Alice:KApub with his private key, KCpriv. Alice could send Bob this certificate before they start encrypted communication. Bob would decrypt with Cedric's public key KCpub, and get the name Alice and the public key KApub. Because Bob knows that KCpub really belongs to Cedric, he knows that the certificate really was created by Cedric — because it takes Cedric's private key to create something decryptable with his public key. Moreover, since Bob trusts Cedric, he now believes that the key KApub belongs to the identity "Alice".

Certificates at the Naval Academy

When you install a browser on your computer, that browser comes pre-installed with a fairly large number of certificate authorities that it trusts. A wary user might want to winnow that down to only the certificate authorities that are absolutely necessary — i.e. minimize trust. So what authorities does someone at USNA need to trust? Or at least, which authorities are we expected to trust? The interactive SI110 resource
Certificates at USNA
shows you what the certificate chain looks like for resources Navy Knowledge Online, BUPERS Online, Mids, our CAC cards, and gozer.usna.edu (the authentication server for our gmail accounts). If you trust DoD Root CA 2 as DoD employees are supposed to, you will automatically trust the certificate for mids, for example, because it is signed by DOD CA-27, which your browser will trust because it is signed by DoD Root CA 2, which you trust. In other words, your browser will trust any certificate that "chains" back to the DoD Root CA 2 certificate.

The Lab

The X.509 Certificates Lab is designed to make this discussion concrete. You get to see how X.509 certificates are used in HTTPS communication to verify the identities of the webservers we communicate with. Going through the activity, you will see what a real X.509 certificate looks like. You will see where the browser keeps its list of trusted authorities, and you will even see how certificates foil an attempted man-in-the-middle attack.

DoD PKI Infrastructure
The Department of Defence has its own Certificate Authorities. You can view and download them at DoD's PKI management site: https://crl.gds.disa.mil/. The DoD PKI is managed by DISA (Defence Information Systems Agency).
The Flame Malware: forging certificates
Our discussion of certificates is centered around verifying the identity of a webserver. Certificates can be used to verify identities in other scenarios. An important one is to identify the source of software (programs) and software updates. For instance, Windows has a mechanism to automatically pull updates (usually bug fixes!) over the internet and install them on your machine. It's pretty darn important that you (or your computer, at any rate) can be certain that the update really came from Microsoft. So the update comes with a certificate that proves that it's authentic.

In the Summer of 2012 a new piece of malware (malicious software, about which we will have much to say later!) was discovered on hundreds of machines in the mideast, and given the name Flame. Security experts speculate that it was produced by either the government of the U.S. or of Israel. One of the many fascinating aspects of Flame is the way it gets onto hosts in the first place. Basically, it pretends to be a genuine Microsft software update, so your computer willingly installs it. Now, to do that, Flame needed a valid certificate that "proved" it really came from Microsoft. So the authors of Flame forged a certificate by taking an actual valid certificate, and modifying it. But this isn't supposed to be possible! A certificate is protected from modification by a hash that cannot be changed. If the certificate data is modified, the hash value calculated by your computer, and that unchangable hash value won't match. The only way around this is to find a way to modify the certificate without changing the hash value — which is referred to as generating a hash "collision". Well, that's what the Flame authors managed to do! The Flame authors showed us not only that MD5 is "broken", in the sense that collisions can be found (which was already known), but that it's possible to modify data to read more or less however you want and still get an MD5 collision. That was impressive!

When Certificate Authorities Go Bad
When we install a certificate authority's certificate in our browser, we are saying "I trust the indentiy of any server with a certificate signed by you". That's a big deal! Of course that means you trust the certificate authority to be honest (to do thorough background checks, refuse bribes, etc), but it also means you trust them to keep their systems secure. When a certificate authority you trust gets hacked, the attacker can issue fraudulent certificates ... which you will trust! So when a certificate authority gets hacked, everyone pretty much loses confidence in them, and confidence is really the only thing a certificate authority sells.

In 2011, Dutch certificate authority DigiNotar was hacked, and the attacker issued a large number of fradulent certificates, including certificates that would allow him to pretend to be google! Shortly after the security breach became public, DigiNotar filed for bankruptcy. The Wired Fall 2011 article is a concise and easily readable description.