In section 7.2 we saw that a drawback of symmetric key cryptography was the need for the two communicating parties to have agreed upon their secret key ahead of time. With public key cryptography, this a priori agreement on a secret value is not needed. However, as we saw in our discussion of authentication protocol ap5.0 in Section 7.3, public key encryption has its own difficulties, in particular the problem of obtaining someone's true public key. Both of these problems – determining a shared key for symmetric key cryptography, and securely obtaining the public key for public key cryptography – can be solved using a trusted intermediary. For symmetric key cryptograghy , the trusted intermediary is called a Key Distribution Center (KDC), which is a single, trusted network entity with whom one has established a shared secret key. We will see that one can use the KDC to obtain the shared keys needed to communicate securely with all other network entities. For public key cryptography, the trusted intermediary is called a Certification Authority (CA). A certification authority certifies that a public key belongs to a particular entity (a person or a network entity). For a certified public key, if one can safely trust the CA that the certified the key, then one can be sure about to whom the public key belongs. Once a public key is certified, then it can be distributed from just about anywhere, including a public key server, a personal Web page or a diskette.
Suppose once again that Bob and Alice want to communicate using symmetric key cryptography. They have never met (perhaps they just met in an on-line chat room) and thus have not established a shared secret key in advance. How can they now agree on a secret key, given that they can only communicate with each other over the network? A solution often adopted in practice is to use a trusted Key Distribution Center (KDC).
The KDC is a server that shares a different secret symmetric key with each registered user. This key might be manually installed at the server when a user first registers. The KDC knows the secret key of each user and each user can communicate securely with the KDC using this key. Let's see how knowledge of this one key allows a user to securely obtain a key for communicating with any other registered user. Suppose that Alice and Bob are users of the KDC; they only know their individual key, KA-KDC and KB-KDC, respectively, for communicating securely with the KDC. Alice takes the first step, and they proceed as illustrated in Figure 7.5-1.
Figure 7.5-1: Setting up a one-time session key using a Key Distribution Center
Using KA-KDC to encrypt her communication with the KDC, Alice sends a message to the KDC saying she (A) wants to communicate with Bob (B). We denote this message, KA-KDC (A,B) . As part of this exchange, Alice should authenticate the KDC (see homework problems), e.g., using an authentication protocol (e.g., our protocol ap4.0) and the shared key KA-KDC .
The KDC, knowing KA-KDC , decrypts KA-KDC (A,B) . The KDC then authenticates Alice. The KDC then generates a random number, R1. This is the shared key value that Alice and Bob will use to perform symmetric encryption when they communicate with each other. This key is referred to as a one-time session key (see section 7.5.3 below), as Alice and Bob will use this key for only this one session that they are currently setting up. The KDC now needs to inform Alice and Bob of the value of R1. The KDC thus sends back an encrypted message to Alice containing the following:
R1, the one-time session key that Alice and Bob will use to communicate;
a pair of values: A, and R1, encrypted by the KDC using Bob's key, KB-KDC . We denote this KB-KDC(A,R1). It is important to note that KDC is sending Alice not only the value of R1 for her own use, but also an encrypted version of R1 and Alice's name encrypted using Bob's key. Alice can't decrypt this pair of values in the message (she doesn't know Bob's encryption key), but then she doesn't really need to. We'll see shortly that Alice will simply forward this encrypted pair of values to Bob (who can decrypt them).
These items are put into a message and encrypted using Alice's shared key. The message from the KDC to Alice is thus KA-KDC(R1,KB-KDC(R1)).
Alice receives the message from the KDC, verifies the nonce, extracts R1 from the message and saves it. Alice now knows the one-time session key, R1. Alice also extracts KB-KDC(A,R1) and forwards this to Bob.
Bob decrypts the received message, KB-KDC(A,R1), using KB-KDC and extracts A and R1. Bob now knows the one-time session key, R1, and the person with whom he is sharing this key, A. Of course, he takes care to authenticate Alice using R1 before proceeding any further.
Kerberos [RFC 1510, Neuman 1994] is an authentication service developed at MIT that uses symmetric key encryption techniques and a Key Distribution Center. Although it is conceptually the same as the generic KDC we described in section 7.5.1, its vocabulary is slightly different. Kerberos also contains several nice variations and extensions of the basic KDC mechanisms. Kerberos was designed to authenticate users accessing network servers and was initially targeted for use within a single administrative domain such as a campus or company. Thus, Kerberos is framed in the language of users who want to access network services (servers) using application-level network programs such as Telnet (for remote login) and NFS (for access to remote files), rather than than human-to-human conversants who want to authenticate themselves to each other, as in our examples above. Nonetheless, the key (pun intended) underlying techniques remains the same.
The Kerberos Authentication Server (AS) plays the role of the KDC. The AS is the repository of not only the secret keys of all users (so that each user can communicate securely with the AS) but also information about which users have access privileges to which services on which network servers. When Alice wants to access a service on Bob (who we now think of as a server), the protocol closely follows our example in Figure 7.5-1:
Alice contacts the Kerberos AS, indicating that she wants to use Bob. All communication between Alice and the AS is encrypted using a secret key that is shared between Alice and the AS. In Kerberos, Alice first provides her name and password to her local host. Alice's local host and the AS then determine the one-time secret session key for encrypting communication between Alice and the AS.
The AS authenticates Alice, checks that she has access privileges to Bob, and generates a one-time symmetric session key, R1, for communication between Alice and Bob. The Authentication Server (in Kerberos parlance, now referred to as the Ticket Granting Server) sends Alice the value of R1, and also a ticket to Bob's services. The ticket contains Alice's name, the one-time session key, R1, and an expiration time, all encrypted using Bob's secret key (known only by Bob and the AS), as in Figure 7.5-1. Alice's ticket is valid only until its expiration time, and will be rejected by Bob is presented after that time. For Kerberos V4, the maximum lifetime of a ticket is about 21 hours. In Kerberos V5, the lifetime must expire before the end of year 9999 - a definite Y10K problem!
Alice then sends her ticket to Bob. She also sends along an R1-encrypted timestamp that is used as a nonce. Bob decrypts the ticket using his secret key, obtains the session key, decrypts the timestamp using the just-learned session key. Bob sends back the timestamp value plus one (in Kerberos V5) or simply the timestamp itself (in Kerberos V5).
The most recent version of Kerberos (V5) provides support for multiple Authentication Servers, delegation of access rights, and renewable tickets. [Kaufman 95] [RFC 1510] provide ample details.
One of the principle features of public key encryption is that it is possible for two entities to exchange secret messages without having to exchange secret keys. For example, when Alice wants to send a secret message to Bob, she simply encrypts the message with Bob's public key and sends the encrypted message to Bob; she doesn't need to know Bob's secret (i.e., private) key, nor does Bob need to know her secrect key. Thus, public key cryptography obviates the need for KDC infrastructure, such as Kerberos.
Of course, with public key encryption, the communicating entities still have to exchange public keys. A user can make its public key pubicly available in many ways, e.g., by posting the key on the user's personal Web page, placing the key in a public key server, or by sending the key to a correspondent by e-mail. A Web commerce site can place its public key on its server in a manner that browsers automatically download the public key when connecting to the site. Routers can place their public keys on public key servers, thereby allowing other browsers and network entities to retrieve them.
There is, however, a subtle, yet critical, problem with public key cryptography. To gain insight to this problem, let's consider an Internet commerce example. Suppose that Alice is in the pizza delivery business and she accepts orders over the Internet. Bob, a pizza lover, sends Alice a plaintext message which includes his home address and the type of pizza he wants. In this message, Bob also includes a digital signature (e.g.,, an encrypted message digest for the original plaintext message). As discussed in Section 7.4, Alice can obtain Bob's public key (from his personal Web page, a public key server, or from an e-mail message) and verify the digital signature. In this manner Alice makes sure that Bob (rather than some adolescent prankster) indeed made the order.
This all sounds fine until clever Trudy comes along. As shown in Figure 7.5-2, Trudy decides to play a prank. Trudy sends a message to Alice in which she says she is Bob, gives Bob's home address, and orders a pizza. She also attaches a digital signature, but she attaches the signature by signing the message digest with her (i.e., Trudy's) private key. Trudy also masquerades as Bob by sending Alice Trudy's public key but saying that it belongs to Bob. In this example, also will apply Trudy's public key (thinking that it is Bob's) to the digital signature and conclude that the plaintext message was indeed created by Bob. Bob will be very surprised when the delivery person brings to his home a pizza with everything on it! Here, as in the flawed authentication scenario in Figure 7.3-7, the man-in-the-middle attack is the room cause of our difficulties.
Figure 7.5-2: Trudy masquerades as Bob using public key cryptography.
We see from this example that in order for public key cryptography to be useful, entities (users, browsers, routers, etc.) need to know for sure that they have the public key of the entity with which they are communicating. For example, when Alice is communicating with Bob using public key cryptography, she needs to know for sure that the public key that is supposed to be Bob's is indeed Bob's.
Binding a public key to a particular entity is typically done by a certification authority (CA), which validates identities and issue certificates. A CA has the following roles:
First to verify that entity (a person, a router, etc) is who it says it is. There are no mandated procedures for how certification is done. When dealing with a CA, one must trust the CA to have performed a suitably rigorous identity verification. For example, if Trudy were able to walk into Fly-by-Night Certificate Authority and simply announce "I am Alice" and receive keys associated with the identity of "Alice," then one shouldn't put much faith in public keys offered by the Fly-by-Night Certificate Authority. On the other hand, one might (or might not!) be more willing to trust a CA that is part of a federal- or state-sponsored program (e.g., [Utah 1999]). One can trust the "identify" associated with a public key only to the extent that one can trust a CA and its identity verification techniques. What a tangled web of trust we spin!
Once the CA verifies the entity of the entity, the CA creates a certificate that binds the public key of the identiy to the identity. The certificate contains the public key and identifying information about the owner of the public key (for example a human name or an IP address). The certificate is digitally signed by the CA. These steps are shown in Figure 7.5-3.
Figure 7.5-3: Bob obtains a certificate from the certification authority.
Let us now see how certificates can be used to combat pizza-ordering pranksters, like Trudy, and other undesirables. When Alice recieves Bob's order, she gets Bob's certificate, which may be on his Web page, in an e-mail message or in a certificate server. Alice uses the CA's public key to verify that the public key in the certificate is indeed Bob's. If we assume that the public key of the CA itself is known to all (for example, it could published in a trusted, public, and well-known place, such as The New York Times, so that it is known to all and can not be spoofed), then Alice can be sure that she is indeed dealing with Bob.
Both the International Telecommunication Union and the IETF
have developed standards for Certification Authorities. ITU X.509
[ITU 1993] specifies an authentication
service as well as a specific syntax for certificates. RFC 1422
[RFC 1422] describes CA-based key
management for use with secure Internet e-mail. It is compatible
with X.509 but goes beyond X.509 by establishing procedures and
conventions for a key management architecture. Figure 7.5-4
describes some of the important field in a certificate.
|version||version number of X.509 specification|
|serial number||CA-issued unique identifier for a certificate|
|signature||specifies the algorithm used by Ca to "sign" this certificate|
|issuer name||identity of CA issuing this certificate, in
Distinguished Name(DN) [RFC 1779] format
|validity period||start and end of period of validity for certificate|
|subject name||identity of entity whose public key is associated with
certificate, in DN format
|subject public key||the subject's public key as well as an indication of
the public key
algorithm (and algorithm parameters) to be used with this key
With the recent boom in electronic commerce and the consequent widespread need for secure transactions, there has been increased interest in Certification Authorities. Among the companies providing CA services are Cybertrust [Cybertrust 1990] Verisign [Verisign 1999] and Netscape [Netscape 1999].
A certificate issued by the US Postal Service, as viewed through a Netscape browser, is shown in Figure 7.5-5.
Figure 7.5-5: A US Postal Service issued certificate
We have seen above that a one-time session key is generated by a KDC for use in symmetric key encryption of a single session between two parties. By using the one-time session keys from the KDC, a user is freed from having to establish a priori its own shared key for each and every network entity with whom it wishes to communicate. Instead, a user need only have one shared secret key for communicating with the KDC, and will receive one-time session keys from the KDC for all of its communication with other network entities.
One time session keys are also used in public key cryptography. Recall from our discussion in section 7.2.2, that a public key encryption technique such as RSA is orders of magnitude more computationally expensive that a symmetric key system such as DES. Thus, public key systems are often used for authentication purposes. Once two parties have authenticated each other, they then use public-key-encrypted communication to agree on a shared one-time symmetric session key. This symmetric session key is then used to encrypt the remainder of the communication using a more efficient symmetric encryption technique, such as DES.