▶ 8.6 Publishing Public Keys
We get the most benefit out of public-key cryptography if we publish and share public keys. This allows anyone to pick up a public key and encrypt a message to someone else. Attackers can’t use the public key to decrypt the message, at least not without breaking the system.
On the other hand, key cracking isn’t the only risk. There is also a trick in which an attacker actively intercepts all traffic. This is often called a man-in-the-middle attack. It is also known as the bucket brigade attack. FIGURE 8.26 provides a diagram of the action. Here is how it works:
FIGURE 8.26 Eve performs a bucket brigade attack.
Bob wants to send another secret message to Alice, and Eve wants to intercept it. Eve took Alice’s USB drive and replaced the file titled “Alice’s Key.” It now contains Eve’s public key instead of Alice’s public key.
Bob retrieves the file titled “Alice’s Key.” He uses it to wrap the secret key that encrypts his message. He saves the wrapped key and his message in a file titled “To Alice.”
Later, before Alice returns, Eve takes the USB drive again. She retrieves the file titled “To Alice” and unwraps Bob’s secret encryption key using her private key; then she rewraps the key using Alice’s public key. She replaces the file on the USB drive.
When Alice returns, she uses her own private key to unwrap Bob’s secret key, then she decrypts and reads the message.
Meanwhile, Eve uses her own unwrapped copy of Bob’s secret key to decrypt and read the message herself.
Essentially, someone intercepts the public keys traveling in one direction and the secret messages traveling in the other. What Eve has done is distribute a forgery: The file claims to contain Alice’s public key, but in fact it contains Eve’s public key.
Eve’s success depends on tricking Bob into using Eve’s public key while thinking it is Alice’s public key. Once Bob has encrypted the message with Eve’s key, Eve must reencrypt it with Alice’s key. Otherwise, Alice won’t be able to read the message, uncovering Eve’s trick.
There are several different strategies for preventing such attacks or for reducing their risks. One approach might be to restrict distribution of public keys so that only authorized people get them. This eliminates many benefits of public-key cryptography. Another approach is to publish individual keys widely so that people can double-check their own copies for validity. This also isn’t practical, because public keys are enormous blocks of random-looking binary data. They won’t contain patterns or structures for people to recognize and remember.
8.6.1 Public-Key Certificates
The favored solution for authenticating public keys was first proposed by an MIT student in 1978. Undergraduate Loren Kohnfelder suggested that we embed public keys in specially constructed credentials called public-key certificates. We use digital signatures to verify a certificate’s integrity. FIGURE 8.27 shows the construction of a certificate.
At a minimum, a certificate contains three pieces of information:
FIGURE 8.27 Constructing a public-key certificate for Alice.
A public key (symbolized by the key marked “A”)
The name of the public key’s owner (“Alice”)
A digital signature that covers the name and the public key (symbolized by the seal with the initial “C” matching the signer’s key)
To construct a certificate, we calculate the hash over the owner’s name and public key, then we use a private key to construct the signature. Anyone with the appropriate public key may verify the certificate.
Although we can use a certificate containing the minimum amount of information, typical modern public-key certificates contain several additional fields. These fields help clarify how the certificate should be used and provide flexibility in creating and validating them. Additional fields generally include:
■ The name of the trusted person or entity who issued and signed the certificate, usually a certificate authority (CA) described later
■ A date range during which the certificate is valid
■ Specifications of the crypto algorithms used to sign the certificate
■ Indication of the certificate’s purpose and approved uses
Whether or not they know it, typical web surfers use public-key certificates constantly. Whenever a browser establishes a secure connection with a website, it uses a public-key certificate to verify the site’s identity and to retrieve the site’s public key. The browser then uses the key to establish a secure, encrypted connection. We explore this further in Chapter 13.
However, we don’t need networks to use certificates. A certificate allows us to authenticate a public key: to confirm that it belongs to a particular individual. We can perform such a test without a network connection.
Certificate Authorities
The certificate’s signature poses an important question: Who does sign a public-key certificate? The signature attests to the fact that the name and public key go together. The signer must be someone trustworthy enough to associate names and keys accurately. Often, the signer is a trusted third party, a person or organization whom we trust for certain things. For example, a bank is a trusted third party for handling various financial transactions. If a friend introduces us to someone new, the friend is acting as a trusted third party.
In the world of certificates, the trusted third party is often a CA. This is a person or entity that issues certificates on behalf of some organization. Inside a company, the CA could be a trustworthy administrator who issues certificates to employees. There are also commercial authorities that sell certificates for use in internet commerce.
As is often the case with crypto, public-key certificates replace one really difficult problem with, we hope, an easier problem. We no longer have to worry about authenticating the public keys we use; instead, we must ensure that we have the correct CA public keys to authenticate certificates.
Internet e-commerce sites use public-key certificates to authenticate their sites when establishing a secure web connection. The Netscape Navigator was the first browser to use public-key certificates. The Navigator relied on a single CA (RSA Data Security, Inc.) and included its public key in the browser’s executable code. Modern browsers contain an entire collection of keys, each belonging to a separate certificate authority. (See Chapter 13.)
At the very least, public-key owners can sign their own certificates. These are called self-signed certificates. If Bob receives a self-signed certificate directly from Alice, as opposed to retrieving it from an unattended USB drive, then the certificate is likely to be valid. Bob simply has to ensure that no one hacks his computer and messes with the collection of certificates.
Trusted third parties are an example of Transitive Trust. When we trust a signed certificate, we also trust the public key that validates the certificate. If the key comes from a trusted third party, then we trust that third party. We also trust the chain of software that provided us with the third party’s public key.
8.6.2 Chains of Certificates
Once we have a public key for a certificate authority, we can authenticate any certificate signed by that authority. However, the authority could get incredibly busy signing certificates, especially in an extremely large organization. We can spread the work out by allowing the authority to delegate its work to others. We do this by issuing certificates to these subsidiary certificate authorities.
For example, the company Amalgamated Widget distributes public-key certificates in this fashion. Each department has its own administrator who serves as a CA and issues certificates to people in that department. To establish the system, Amalgamated took the following steps:
Each CA generates its own public/private key pair.
The initial CA, or root certificate authority, signs a public-key certificate for each of the departmental CAs.
When someone wants a certificate, they ask the departmental CA to sign it. The departmental CA is usually an IT administrator.
When users send email, they sign it with their private key. In order to authenticate it, each email client in Amalgamated contains a copy of a single public key: the root CA’s public key. This key can’t authenticate individual user certificates by itself, because the root CA doesn’t sign every certificate. Instead, it lets us check the certificate that signed the certificate. We call this series of signed certificates a certificate chain.
If Alice receives an email from an official in human resources (HR), her email software authenticates the email by authenticating the certificate chain. This takes place by checking the following signatures:
■ The root CA signed the HR admin’s certificate.
■ The HR admin’s certificate signed the HR official’s certificate.
■ he HR official signed the email to Alice.
FIGURE 8.28 illustrates the process. Note that each certificate must identify the CA who signed it. We use that field to choose the right certificate for verifying the signature.
FIGURE 8.28 Checking a certificate chain.
The checking process starts at the lower left of the diagram and progresses through each digital signature:
■ The email is from the HR official. We retrieve the official’s public key from the official’s personal certificate.
■ We authenticate the email by checking its digital signature, using the official’s public key.
■ The official’s personal certificate was signed by the HR department’s admin. We retrieve the admin’s public key from the admin’s CA certificate.
■ We authenticate the official’s certificate by checking its digital signature, using the public key of the HR department’s admin.
■ The HR department admin’s CA certificate was signed by Amalgamated’s root CA. The root CA’s public key is built in to Amalgamated’s email application software.
■ We authenticate the admin’s CA certificate by checking its digital signature, using the root CA’s public key.
If any check fails, then we can’t authenticate the email. A failure may indicate that someone is using an expired certificate, or it may indicate a forgery.
Certificate Hierarchy
Public-key cryptography provides safe and convenient encryption, as long as we can trust the public keys we use. When we have a public-key infrastructure (PKI), we have the tools to validate public keys and to use them safely. The exact form of an effective infrastructure has produced a lot of debate over the years.
When public-key certificate systems were first proposed, many experts anticipated a single, global PKI. Individual public-key systems would be part of a giant hierarchy with a single root. All public-key software would carry a single, well-known public key belonging to a universal “root” certificate authority. All national, regional, corporate, and local authorities would have certificates signed by that universal authority. FIGURE 8.29 illustrates this structure.
FIGURE 8.29 A certificate hierarchy that spans multiple enterprises.
In practice, no single authority ever emerged. There were several reasons for this, including the fact that there was no real business, economic, or strategic benefit to adopting a single, universal root authority. Another problem was that different applications demanded different levels of assurance. Multimillion-dollar commercial transactions and logins to a personal blog site are both protected with the same public-key technology, but they don’t require the same level of caution (and expense) when issuing public-key certificates.
Today, there remains no single, universal root authority. Nonetheless, certificate hierarchies are alive and well. Many large-scale public-key systems use a certificate hierarchy. Internet web browsers contain a database of root public keys, and these often serve as the starting point for hierarchies of authorities.
Web of Trust
When Phil Zimmerman published the encryption program PGP in 1991, it was partially a political statement. Zimmerman believed that individual freedom would depend in the future on strong cryptography. He wanted cryptography available to the public at large, and usable in a grassroots manner. He didn’t want a system that relied on a centralized authority, like a certificate hierarchy with a single root, but he still needed a way to assure the identity of public keys.
To solve the problem, PGP implemented a web of trust. No single person was universally trusted to sign certificates. Instead, individual users made up their own minds about who they trusted to sign certificates. Each certificate could contain as many signatures as the owner desired. Each user would collect certificates from their friends and colleagues. They could then use those certificates to verify signatures on new certificates they receive (FIGURE 8.30).
FIGURE 8.30 A web of trust.
The technique relies on Transitive Trust to decide whether a certificate is valid or not. For example, Alice wants to encrypt information for Tina without meeting her in person. She has a copy of every signed certificate in Figure 8.30. Honest Abe signed Alice’s own certificate. Abe also signed Carl’s certificate, and Carl signed Tina’s. If Alice trusts Abe’s judgment, then she might accept Tina’s certificate, because Abe seems to trust Carl.
The certificate-signing process became a sort of social activity; crypto geeks would arrange “key-signing parties” or sign keys when thrown together in a social event. The practice waned after several years, as other assurance techniques replaced it. One alternative was for people to publish a “key fingerprint” that provided several bytes of the key in hexadecimal. Even these small portions of the key were random enough to make it unlikely that two people would have identical key fingerprints. Moreover, the mathematics of key construction make it impractical to try to create a key with a particular fingerprint. Thus, an attacker couldn’t try to masquerade by constructing a public key with a particular fingerprint.
Another alternative was to incorporate email addresses into the certificate process and to use them to increase assurance. The PGP Corporation, which now sells PGP as a commercial product, maintains a PGP key directory on the internet. When Bob submits his PGP key, the directory validates it by contacting him via the email address in his certificate. Once the email address is validated, the directory adds its own signature to the certificate. Anyone with the directory’s certificate can verify any certificate retrieved from the directory.
Self-Signed Certificates
As we described, anyone can produce a public-key certificate and sign it, yielding a self-signed certificate. Although these are convenient to construct, they are also easy for an attacker to forge. A self-signed certificate is useful only if it is going to be used over time for a series of transactions. As we perform these transactions successfully, we develop increased confidence in the certificate’s validity.
There are two cases in which a self-signed certificate provides useful assurance:
If the certificate contains other data that we can independently verify
If the certificate is used for a series of transactions
For example, the PGP Directory keeps a public collection of signed PGP certificates. It requires that all self-signed certificates contain an email address. The directory verifies the email address before concluding that the certificate is valid.
If we use a self-signed certificate for a few low-risk transactions, this increases our confidence in its accuracy. If we are sure that the certificate’s real owner is the one performing the transactions, then we can at least be confident that those sorts of transactions may take place reliably. On the other hand, we can’t assume that a self-signed certificate really belongs to 3M Corporation simply because the signer sells us Post-it® Notes.
Trickery with Certificates
Although public-key certificates provide strong cryptography to protect their information, attackers have found several ways to abuse certificates. Such attacks usually affect authenticated software updates (described in the next section) or secure connections to websites. We discuss these techniques in Section 15.2.3.
8.6.3 Authenticated Software Updates
Software updates pose a serious challenge. If we apply subverted updates to our operating system, we can install malicious software, back doors, and Trojan horses. Public-key cryptography provides an effective mechanism for authenticating software updates. FIGURE 8.31 illustrates the basic mechanism for signing and verifying a software update.
FIGURE 8.31 Procedure for verifying a software update.
If we trust the vendor to create reliable updates, then we can fully automate the update process. We create a set of processes that accept an update file from any user and apply the update. The processes use the vendor’s public key to authenticate the update. If the authentication succeeds, a process automatically applies those updates.
The mechanism requires the following components:
■ A public/private key pair that the software vendor uses to sign software update files
■ A software update package: trustworthy software that validates the digital signature on a software update file and, if the signature is valid, applies the updates
■ A copy of the vendor’s public key that resides inside the update package
■ A digital signature applied by the vendor to every software update file
The software update process further relies on the appropriate arrangement of processes inside the computer. FIGURE 8.32 illustrates one approach.
FIGURE 8.32 A set of processes for trusted software update.
We break the software update process into three steps. First, Bob or some other user retrieves the update file from a disk or the internet and starts the update. Second, the validation process copies the update software into a protected block of RAM and checks its digital signature. If the signature checks out, the update process runs, and updates the system files.
This is a simple example of an assured pipeline, a series of processes that use Least Privilege and Separation of Duty to perform a security-critical task in separate steps. Bob can start the update process, but his processes lack the rights to patch the system files directly. The validation process validates the authenticity and integrity of the update software before it allows it to execute. Once the process verifies that the update software comes from the vendor, the update process is allowed to run.