The Role of Cryptography in Security

Asymmetric Ciphers

Asymmetric ciphers provide the same two functions as symmetric ciphers: message encryption and message decryption. There are two major differences, however. First, the key value used in message decryption is different than the key value used for message encryption. Second, asymmetric ciphers are thousands of times slower than symmetric key ciphers. But asymmetric ciphers offer a phenomenal advantage in secure communications over symmetric ciphers.

To explain this advantage, let's review the earlier example of using a symmetric cipher. Alice encrypts a message using key K and sends it to Bob. When Bob receives the encrypted message, he uses key K to decrypt the encrypted message and recover the original message. This scenario introduces the question of how Alice sends the key value used to encrypt the message to Bob. The answer is that Alice must use a separate communication channel, one that is known to be secure (that is, no one can listen in on the communication), when she sends the key value to Bob.

The requirement for a separate, secure channel for key exchanges using symmetric ciphers invites even more questions. First, if a separate, secure channel exists, why not send the original message over that? The usual answer is that the secure channel has limited bandwidth, such as a secure phone line or a trusted courier. Second, how long can Alice and Bob assume that their key value has not been compromised (that is, become known to someone other than themselves ) and when should they exchange a fresh key value? Dealing with these questions and issues falls within the realm of key management.

Key management is the single most vexing problem in using cryptography. Key management involves not only the secure distribution of key values to all communication parties, but also management of the lifetime of the keys, determination of what actions to take if a key is compromised, and so on. Alice and Bob's key management needs may not be too complicated; they could exchange a password over the phone (if they were certain that no one was listening in) or via registered mail. But suppose Alice needed to securely communicate not just with Bob but with hundreds of other people. She would need to exchange (via trusted phone or registered mail) a key value with each of these people and manage this list of keys, including keeping track of when to exchange a fresh key, handling key compromises, handling key mismatches (when the receiver cannot decrypt the message because he has the wrong key), and so on. Of course, these issues would apply not just to Alice but to Bob and everyone else; they all would need to exchange keys and endure these key management headaches (there actually exists an ANSI standard (X9.17) [ANSIX9.17] on key management for DES.)

To make matters worse , if Alice needs to send a message to hundreds of people, she will have to encrypt each message with its own key value. For example, to send an announcement to 200 people, Alice would need to encrypt the message 200 times, one encryption for each recipient. Obviously, symmetric ciphers for secure communications require quite a bit of overhead.

The major advantage of the asymmetric cipher is that it uses two key values instead of one: one for message encryption and one for message decryption. The two keys are created during the same process and are known as a key pair. The one for message encryption is known as the public key; the one for message decryption is known as the private key. Messages encrypted with the public key can only be decrypted with its associated private key. The private key is kept secret by the owner and shared with no one. The public key, on the other hand, may be given out over an unsecured communication channel or published in a directory.

Using the earlier example of Alice needing to send Bob a confidential document via e-mail, we can show how the exchange works with an asymmetric cipher. First, Bob e- mails Alice his public key. Alice then encrypts the document with Bob's public key, and sends the encrypted message via e-mail to Bob. Because any message encrypted with Bob's public key can only be decrypted with Bob's private key, the message is secure from prying eyes, even if those prying eyes know Bob's public key. When Bob receives the encrypted message, he decrypts it using his private key and recovers the original document.

Figure 2-2 illustrates the process of encrypting and decrypting with the public and private keys.

If Bob needs to send some edits on the document back to Alice, he can do so by having Alice send him her public key; he then encrypts the edited document using Alice's public key and e-mails the secured document back to Alice. Again, the message is secure from eavesdroppers, because only Alice's private key can decrypt the message, and only Alice has her private key.

Note the very important difference between using an asymmetric cipher and a symmetric cipher: No separate, secure channel is needed for Alice and Bob to exchange a key value to be used to secure the message. This solves the major problem of key management with symmetric ciphers: getting the key value communicated to the other party. With asymmetric ciphers, the key value used to send someone a message is published for all to see. This also solves another symmetric key management headache: having to exchange a key value with each party with whom one wishes to communicate. Anyone who wants to send a secure message to Alice uses Alice's public key.

Recall that one of the differences between asymmetric and symmetric ciphers is that asymmetric ciphers are much slower, up to thousands of times slower [WeiDai02]. This issue is resolved in practice by using the asymmetric cipher to communicate an ephemeral symmetric key value and then using a symmetric cipher and the ephemeral key to encrypt the actual message. The symmetric key is referred to as ephemeral (meaning to last for a brief time) because it is only used once, for that exchange. It is not persisted or reused, the way traditional symmetric key mechanisms require. Going back to the earlier example of Alice e-mailing a confidential document to Bob, Alice would first create an ephemeral key value to encrypt the document with a symmetric cipher. Then she would create another message, encrypting the ephemeral key value with Bob's public key, and then send both messages to Bob. Upon receipt, Bob would first decrypt the ephemeral key value with his private key and then decrypt the secured document with the ephemeral key value (using the symmetric cipher) to recover the original document.

Figure 2-4 depicts using a combination of asymmetric and symmetric ciphers.

Some examples of asymmetric ciphers are RSA, Elgamal, and ECC (elliptic-curve cryptography). RSA is by far the most popular in use today. Elgamal is another popular asymmetric cipher. It was developed in 1985 by Taher Elgamal and is based on the Diffie-Hellman key exchange, which allows two parties to communicate publicly yet derive a secret key value known only to them [Diffie-Hellman].

Diffie-Hellman, developed by Whitfield Diffie and Martin Hellman in 1976, is considered the first asymmetric cipher, though the concept of an asymmetric cipher may have been invented in the U. K. six years earlier. Diffie-Hellman is different from RSA in that it is not an encryption method; it creates a secure numeric value that can be used as a symmetric key. In a Diffie-Hellman exchange, the sender and receiver each generate a random number (kept private) and value derived from the random number (made public). The two parties then exchange the public values. The power behind the Diffie-Hellman algorithm is its ability to generate a shared secret. Once the public values have been exchanged, each party can then use its private number and the other's public value to generate a symmetric key, known as the shared secret, which is identical to the other's. This key can then be used to encrypt data using a symmetric cipher. One advantage Diffie-Hellman has over RSA is that every time keys are exchanged, a new set of values is used. With RSA, if an attacker managed to capture your private key, they could decrypt all your future messages as well as any message exchange captured in the past. However, RSA keys can be authenticated (as with X.509 certificates), preventing man-in-the-middle attacks, to which a Diffie-Hellman exchange is susceptible.

Digital Signature

Digital signatures are used to guarantee the integrity of the message sent to a recipient by representing the identity of the message sender. This is done by signing the message using a digital signature, which is the unique by-product of asymmetric ciphers. Although the public key of an asymmetric cipher generally performs message encryption and the private key generally performs message decryption, the reverse is also possible. The private key can be used to encrypt a message, which would require the public key to decrypt it. So, Alice could encrypt a message using her private key, and that message could be decrypted by anyone with access to Alice's public key. Obviously, this behavior does not secure the message; by definition, anyone has access to Alice's public key (it could be posted in a directory) so anyone can decrypt it. However, Alice's private key, by definition, is known to no one but Alice; therefore, a message that is decrypted with Alice's public key could not have come from anyone but Alice. This is the idea behind digital signatures.

Digital signatures are the only mechanisms that make it possible to ascertain the source of a message using an asymmetric cipher. Encrypting a message with a private key is a form of digital signature. However, as we discussed before, asymmetric ciphers are quite slow. Alice could use the technique presented in the previous section of creating an ephemeral key to encrypt the message, and then encrypt the ephemeral key with her private key. But encrypting the message is a wasted effort, because anyone can decrypt it. Besides, the point of the exercise is not to secure the message but to prove it came from Alice.

The solution is to perform a one-way hash function on the message, and encrypt the hash value with the private key. For example, Alice wants to confirm a contract with Bob. Alice can edit the contract's dotted line with "I agree," then perform an MD5 hash on the documents, encrypt the MD5 hash value with her private key, and send the document with the encrypted hash value (the digital signature) to Bob. Bob can verify that Alice has agreed to the documents by checking the digital signature; he also performs an MD5 hash on the document, and then he decrypts the digital signature with Alice's public key. If the MD5 hash value computed from the document contents equals the decrypted digital signature, then Bob has verified that it was Alice who digitally signed the document.

Figure 2-5 shows how a digital signature is created.

Figure 2-6 shows the process of verifying a digital signature.

Moreover, Alice cannot say that she never signed the document; she cannot refute the signature, because only she holds the private key that could have produced the digital signature. This ensures non- repudiation .

Digital Certificates

A digital certificate is a document that uniquely identifies information about a party. It contains a party's public key plus other identification information that is digitally signed and issued by a trusted third party, also referred to as a Certificate Authority (CA) . A digital certificate is also known as an X.509 certificate and is commonly used to solve problems associated with key management.

As explained earlier in this chapter, the advent of asymmetric ciphers has greatly reduced the problem of key management. Instead of requiring that each party exchange a different key value with every other party with whom they wish to communicate over separate, secure communication channels, one simply exchanges public keys with the other parties or posts public keys in a directory.

However, another problem arises: How is one sure that the public key really belongs to Alice? In other words, how is the identity of the public key's owner verified ? Within a controlled environment, such as within a company, a central directory may have security controls that ensure that the identities of public keys' owners have been verified by the company. But what if Alice runs a commerce Web site, and Bob wishes to securely send Alice his credit card number. Alice may send Bob her public key, but Mary (an adversary sitting on the communication between Alice and Bob) may intercept the communication and substitute her public key in place of Alice's. When Bob sends his credit card number using the received public key, he is unwittingly handing it to Mary, not Alice.

One method to verify Alice's public key is to call Alice and ask her directly to verify her public key, but because public keys are large (typically 1024 bits, or 128 bytes), for Alice to recite her public key value would prove too cumbersome and is prone to error. Alice could also verify her public key fingerprint , which is the output of a hash function performed on her public key. If one uses the MD5 hash function for this purpose, the hash value is 128 bits or 16 bytes, which would be a little more manageable.

But suppose Bob does not know Alice personally and therefore could not ascertain her identity with a phone call? Bob needs a trusted third party to vouch for Alice's public key. This need is met, in part, by a digital certificate.

For example, assume Charlie is a third party that both Alice and Bob trust. Alice sends Charlie her public key, plus other identifying information such as her name , address, and Web site URL. Charlie verifies Alice's public key, perhaps by calling her on the phone and having her recite her public key fingerprint. Then Charlie creates a document that includes Alice's public key and identification, and digitally signs it using his private key, and sends it back to Alice. This signed document is the digital certificate of Alice's public key and identification, vouched for by Charlie.

Now, when Bob goes to Alice's Web site and wants to securely send his credit card number, Alice sends Bob her digital certificate. Bob verifies Charlie's signature on the certificate using Charlie's public key (assume Bob has already verified Charlie's public key), and if the signature is good, Bob can be assured that, according to Charlie, the public key within the certificate is associated with the identification within the certificatenamely, Alice's name, address, and Web site URL. Bob can encrypt his credit card number using the public key with confidence that only Alice can decrypt it.

Figure 2-7 illustrates how a digital certificate is used to verify Alice's identity.

Suppose Mary (an adversary) decides to intercept the communication between Alice and Bob, and replaces Alice's public key with her own within the digital certificate. When Bob verifies Charlie's signature, the verification will fail because the contents of the certificate has changed. Recall that to check a digital signature, one decrypts the signature with the signer's public key, and the result should equal the output of the hash function performed on the document. Because the document has changed, the hash value will not be the same as the one Charlie encrypted with his private key.

Figure 2-8 shows what happens if an adversary (Mary) tries to alter Alice's certificate.

Verification of a digital certificate can also be a multilevel process; this is known as verifying a certificate chain . In the previous example, it was assumed that Bob had already verified Charlie's public key. Let's now assume that Bob does not know Charlie or Alice but does have in his possession the pre-verified public key of Victor, and that Charlie has obtained a digital certificate from Victor. When Bob needs to secure information being sent to Alice, Alice sends Bob not only her digital certificate signed by Charlie, but Charlie's certificate signed by Victor. Bob verifies Charlie's signature on Alice's certificate using Charlie's public key, and then verifies Victor's signature on Charlie's public key using Victor's public key. If all signatures are good, Bob can be assured that Victor vouches for Charlie and that Charlie vouches for Alice.

In practice, Victor's public key will be distributed as a certificate that was self-signed. A self-signed certificate is known as a root certificate. So in the example, there are really three certificates involved: Alice's certificate signed by Charlie, Charlie's certificate signed by Victor, and Victor's certificate, also signed by Victor. These three certificates make up the certificate chain.

Figure 2-9 shows how certificates can be chained together to verify identity.

In this example, Victor acts as a CA. He is in the business of being a trusted authority who verifies an individual's identification, verifies that individual's public key, and binds them together in a document that he digitally signs. CAs play an important part in the issuance and revocation of digital certificates.

The Role of CA in Issuing Certificates

In a trusted communication using digital certificates, a CA plays the role of the entity that issues a public key certificate. The certificate is the CA's assertion that the public key contained in the certificate belongs to a specific person, associated organization, or server host. Other information related to the person noted in the certificate is also provided. The CA is obligated to verify the information when a user requests a certificate and sends a Certificate Signing Request (CSR) to the CA. After verifying the information, the CA signs the requests and returns a certificate to the user (usually in X.509 certificate format). It is important to note that the relying parties also trust the certificate information issued by the CA. The relying party can decrypt the CA's signature using the CA's public key, which assures the relying party that the certificate was issued by the CA mentioned in the certificate.

In order to trust a certificate, the relying party has to trust the root certificate in its hierarchical chain. The CA, therefore, provides the trusted root certificate, and the CA is responsible for verifying the identities (out-of- band ) of the certificates it signs. The reason digital certificates are so pervasive on the Web today is because many CA root certificates come bundled in the Web browsers. This eliminates the need for Web users to import and verify root certificates, though often this must be done with employees in organizations that have their own root certificates that are not bundled by default in the browsers. One of the most popular certificate authorities is VeriSign. Most of the secure Web sites on the Internet have their certificates verified (and signed) by VeriSign.

All Web browsers that support HTTPS employ the SSL (Secure Socket Layer) protocol, which in turn uses X.509 certificates. S/MIME (Secure MIME) and PEM (Privacy Enhanced Mail), both used to secure e-mail, also use X.509 certificates. Along with the public key and identification information, X.509 certificates include validity dates that indicate from what point in time the certificate is valid and when it expires . Other information is included as well; see [RFC2459]. The examples in this chapter have described the X.509 certificate structure, which is a hierarchical trust model; a signing authority signs each digital certificate once, and the top authority self-signs his certificate. Other certificate structures use different trust models; PGP (Pretty Good Privacy), which is another program used to secure e-mail, uses its own type of digital certificate that can be signed more than once. Trust models are discussed later in this chapter.

The Role of CA in Revocation of Certificates

The CA is also responsible for revoking the certificates if the CA discovers that the issued certificate is falsely verified or the identified user does not adhere to the CA- mandated policy requirements or has violated its policies. In addition, revoking certificates is also necessary for a variety of other reasons. A user may leave an organization, an organization with an SSL Web site might go out of business, or a private key may be compromised.

As part of the revocation process, the CA maintains the user certificate and its serial number as part of a certificate revocation list (CRL). The CRL is a list of certificates that are considered revoked, that are no longer valid, and that should not be trusted by any system or users. It is important to note that when a revoked certificate's expiration date occurs, the certificate will be automatically removed from the CRL.

Using Certificate Revocation Lists (CRL)

To verify a certificate, it is quite important to use the appropriate CRL to make sure the signer's certificate has not been revoked. CRLs are usually maintained as repositories identified with a URL for sites containing the latest CRLs. It is also possible to download CA-listed CRLs by subscribing to the repositories and creating an in-house CRL repository to make CRL searches for verifying the signer's information. Most Web servers and Web browsers provide a facility for verifying the certificates using CRLs.

Using the Online Certificate Status Protocol (OCSP)

Another alternative for verifying certificates using CA-maintained CRLs is the Online Certificate Status Protocol (OCSP) defined in RFC 2560 [RFC2560]. In this method, the CA publishes the revoked certificate lists to an OSCP-enabled directory. This could be done using a CRL or an LDAP update. The CA then maintains an OCSP responder application that will use the data in the OCSP directory to respond to a query for a particular certificate with a "good," "revoked," or "unknown" response. This allows CAs to create plug-ins for Web browsers that can automatically check for certificate revocations. Application developers can also write code to query the OSCP responder , because it is a standard protocol. The drawbacks to OSCP are that it does not allow for out-of-band verification and that it may be slow, because each response must be signed by the CA and the CA may get overwhelmed with requests as the number of users hitting it and the number of revoked certificates grows.