In this lesson, we will cover two topics that sound similar, but have very different purposes. Be careful and precise when using this terminology while being able to identify what these specific security tools provide. Digital Signatures are the result of a cryptographic transformation that provides a mechanism to verify the authenticity, integrity, and non-repudiation of a message. Digital Certificate (aka Certificate) is used to uniquely identify a public key and an owner that is authorized to use the key pair. We will discuss each of these in more detail in the lesson below.

Digital Signatures

Concerns About Trust: Man-in-the-middle attacks

The Problem. Asymmetric encryption is almost magical — you create security out of insecurity. However, there is still one weakness in the system that's fundamental: certifying the connection between a public key and its associated identity. 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 Rivest-Shamir-Adleman (RSA) public-key/asymmetric encryption, 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 K_pub and be sure that:

1. messages you receive can only be read by you, and can only have come from the owner of K_pub
2. messages you send can only be read by the owner of K_pub, and the owner of K_pub will know that they could only have come from you.

With the usual Alice and Bob scenario, Alice's public key K^A_pub is out there on the Internet, as is Bob's public key K^B_pub. Alice "owns" K^A_pub because she alone has the matching private key K^A_priv. Similarly, Bob "owns" K^B_pub because he alone has the matching private key K^B_priv. This is illustrated by the diagram to the right. Following our usual plan, Alice sends Bob the plaintext message msg by:

plaintext — encrypt with K^A_priv → ciphertext1 — encrypt with K^B_pub → ciphertext2

... and she sends him ciphertext2. This works great, as long as Alice is really sure that K^B_pub 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 K^A'_pub up on the Internet and claiming it's Alice's public key, and throwing a public key K^B'_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 K^B'_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 K^A_priv first, and then with the key K^B'_pub she thinks belongs to Bob? Then Eve decrypts with her key K^B'_priv followed by Alice's public key K^A_pub and she has the plaintext message from Alice. Once again, she reads the message or changes it. Then Eve encrypts with her fake key K^A'_priv first, and then with Bob's public key K^B_pub. Bob is able to decrypt the plaintext message. Because doing so required K^A'_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 K^B'_pub really belongs to Bob, and to make Bob believe K^A'_pub really belongs to Alice. But we've seen how to trick people with spam e-mails, misleading links, and convincing copies of web pages, which are a few possible ways to do this.

Digital Certificate Basics

Let's add a new actor to our Alice/Bob/Eve play. Suppose there is a fourth party named Cedric, who is trusted by both Alice and Bob. Cedric has the public/private key-pair K^C_pub/K^C_priv, and Alice and Bob both know his public key. Suppose Alice presented Cedric with her name "Alice" and public key K^A_pub, 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:K^A_pub with his private-signing key, K^C_priv. Alice could send Bob this certificate before they start encrypted communication. Bob would decrypt with Cedric's public-signing key K^C_pub, and get the name Alice and the public key K^A_pub. Because Bob knows that K^C_pub really belongs to Cedric, he knows that the certificate really was created by Cedric — because it takes Cedric's private-signing key to create something decryptable with his public-signing key. Moreover, since Bob trusts Cedric, he now believes that the key K^A_pub belongs to the identity "Alice".

Digital Certificates Standard - X.509

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:

• subject's identity — in fact there are several pieces of information identifying the subject, but a simple string called the common name (CN) is the crucial part. For a web server, the common name is the domain name.
• subject's public key — in the certificates we looked at this was an RSA key.
• issuer's identity — again, there are several pieces of information identifying the issuer, but a simple string called the common name (CN) is the crucial part.

The certificate binds an identity to the public key using the CA's digital signature, which can be verified, providing non-repudiation and integrity to the digital certificate.

Certificate authorities have certificates as well, and you need that certificate in order 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.

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 guarantees. If Bob decrypts with his private key followed by the public key K_pub, he is only guaranteed that the message was really sent by the owner of K_pub. He has no guarantee of the identity of the owner of K_pub! 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.

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 web server (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.

Certificates in the News

Read the following articles to learn more about the importance of Digital Certificates.

• Stealing the Crown Jewels - China's Hack of RSA Read the following Wired article to learn more about how Chinese spies were able to break into RSA and steal RSA's most guarded secrets.What's more RSA wasn't the end goal - customers all over the world used RSA's products, to include United States Government contractors, to secure access to their networks and products.The Full Story of the Stunning RSA Hack Can Finally Be Told
• When Certificate Authorities Go Bad
  When we install a certificate authority's certificate in our browser, we are saying "I trust the identity 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 fraudulent 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.

• The Flame Malware: forging certificates
  Our discussion of certificates is centered around verifying the identity of a web server. 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 Middle East, 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 Microsoft 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 unchangeable 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!

• Firefox Distrusts Major Certificate Authority
  In early 2018, Mozilla determined that Symantec, one of the oldest and largest Certificate Authorities, was not trustworthy and decided to slowly remove support for websites with certificates from them. Firefox slowly rolled out warnings and eventually removed the support entirely. This is significant because it affected a large number of sites; about 1% of the top million. Mozilla urged the operators of these websites to take action by obtaining new certificates so that they can still be accessed by Firefox users. This incident showcases how browsers are constantly evaluating their trust in Certificate Authorities.
• Cedric: CA's and the Internet's Relationship
  This Wired article illustrates the importance of Certificate Authorities and how the safe and efficient functioning of the internet depends on websites possessing proper certificates.
• Lenovo Laptops Pre-Loaded w/ Malicious Adware
  It was discovered in January 2015 that new Lenovo laptops were being shipped with pre-installed adware that hijacks encrypted web sessions, and may make their users vulnerable to HTTPS man-in-the-middle attacks. The software installs a self-signed root HTTPS certificate that can intercept encrypted traffic for every website a user visits. When a user visits an HTTPS site, the site certificate is signed and controlled by Superfish and falsely represents itself as the official website certificate. Lenovo has released a statement stating that while this adware was installed on laptops shipped between October-December 2014, it has since stopped pre-loading this particular software onto it's laptops. It should be noted that the USNA Class of 2016 was issued Lenovo laptops...presumably before this software was installed.

---

Supplemental Media:





What are Digital Signatures and How Do They Work?

---

Review Questions:

1. How are Digital Signatures and Digital Certificates different?
2. What problem do Digital Certificates address?
3. What part does trust play in our current Digital Certificates model?
4. What is a Digital Certificate composed of?
5. What role does a Certificate Authority provide in assured web browsing?
6. What is a Man-in-the-Middle attack?




References

Schneier, Bruce. 1996. "Applied Cryptography : Protocols, Algorithms, and Source Code in C". Wiley

Department of Defense. 2011. DoDI 8520.02: Public Key Infrastructure (PKI) and Public Key (PK) Enabling. Washington: May 24, 2011.

Department of the Navy Chief Information Officer. 2005. SECNAV M-5239.1: Department of the Navy Information Assurance Program. Washington: November 2005.

Rivest, Shamir, Adleman. 1978. “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." ACM 21, no. 2 (February): 120-126.

---