7.5 Key Distribution and Certification

7.5.1 The Key Distribution Center

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, K_A-KDC and K_B-KDC, respectively, for communicating securely with the KDC.  Alice takes the first step, and they proceed  as illustrated in Figure 7.5-1.

• Using K_A-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, K_A-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 K_A-KDC .
• The KDC, knowing K_A-KDC , decrypts K_A-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, K_B-KDC . We denote this K_B-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 K_A-KDC(R1,K_B-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 K_B-KDC(A,R1) and forwards this to Bob.
• Bob decrypts the received message, K_B-KDC(A,R1), using K_B-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.

7.5.2 Kerberos

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).

7.5.3 Public Key Certification

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.

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.
 

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

7.5.4 One-Time Session Keys

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.
 

References