5.6: Security Protocols

In the previous sections we discovered a need for protecting a principal's password when authenticating to a remote service, a need for distributing keys securely, etc. Security protocols can achieve those objectives. A security protocol is an exchange of messages designed to allow mutually-distrustful parties to achieve an objective. Security protocols often use cryptographic techniques to achieve the objective. Other example objectives include electronic voting, postage stamps for email, anonymous email, and electronic cash for micropayments.

In a security protocol with two parties, the pattern is generally a back-and-forth pattern. Some security protocols involve more than two parties in which case the pattern may be more complicated. For example, key distribution usually involves at least three parties (two principals and a trusted third party). A credit-purchase on the Internet is likely to involve many more principals than three (a client, an Internet shop, a credit card company, and one or more trusted third parties) and thus require four or more messages.

The difference between the network protocols discussed in Chapter 1 and the security ones is that standard networking protocols assume that the communicating parties cooperate and trust each other. In designing security protocols, we instead assume that some parties in the protocol may be adversaries and also that there may be an outside party attacking the protocol.

Example: Key Distribution

To illustrate the need for security protocols, let’s study two protocols for key distribution. In Section 5.4.6, we have already seen that distributing keys is based on a name discovery protocol, which starts with trusted physical delivery. So, let's assume that Alice has met Charles in person, and Charles has met Bob in person. The question then is: is there a protocol such that Alice and Bob, who have never met, can exchange keys securely over an untrusted network? This section introduces the basic approach and subsequent sections work out the approach in detail.

The public-key case is simpler, so we treat it first. Alice and Bob already know Charles's public key (since they have met in person), and Charles knows each of Alice and Bob’s public keys. If Alice and Bob both trust Charles, then Alice and Bob can exchange keys through Charles.

Alice sends a message to Charles (it does not need to be either encrypted or signed), asking:

1. Alice ⇒ Charles: {"Please give me keys for Bob"}

The message content is the string "Please give me keys for Bob". The source address is "Alice" and the destination address is "Charles." When Charles receives this message from Alice, he cannot be certain that if the message came from Alice, since the source and destination fields of Chapter 1 are not authenticated.

For this message, Charles doesn't really care who sent it, so he replies:

2. Charles ⇒ Alice: {"To communicate with Bob, use public key KBpub."}Cpriv

The notation {M}k denotes signing a message M with key k . In this example, the message is signed with Charles's private authentication key. This signed message to Alice includes the content of the message as well as the authentication tag. When Alice receives this message, she can tell from the fact that this message verifies with Charles's public key that the message actually came from Charles.

Of course, these messages would normally not be written in English, but in some machine-readable semantically equivalent format. For expository and design purposes, however, it is useful to write down the meaning of each message in English. Writing down the meaning of a message in English helps make apparent oversights, such as omitting the name of the intended recipient. This method is an example of the design principle be explicit.

To illustrate that problems can be caused by of lack of explicitness, suppose that the previous message 2 were:

2'. Charles ⇒ Alice: {"Use public key KBpub."}Cpriv

If Alice receives this message, she can verify with Charles's public key that Charles sent the message, but Alice is unable to tell whose public key KBpub is. An adversary Lucifer, whom Charles has met but doesn't know is bad, might use this lack of explicitness as follows. First, Lucifer asks Charles for Lucifer's public key, and Charles replies:

2'. Charles ⇒ Lucifer: {"Use public key KLpub."}Cpriv

Lucifer saves the reply, which is signed by Charles. Later when Alice asks Charles for Bob's public key, Lucifer replaces Charles's response with the saved reply. Alice receives the message:

2'. Someone ⇒ Alice: {"Use public key KLpub."}Cpriv

From looking at the source address (Someone), she cannot be certain where message 2' came from. The source and destination fields of Chapter 1 are not authenticated, so Lucifer can replace the source address with Charles's source address. This change won't affect the routing of the message, since the destination address is the only address needed to route the message to Alice. Since the source address cannot be trusted, the message itself has to tell her where it came from, and message 2' says that it came from Charles because it is signed by Charles.

Believing that this message came from Charles, Alice will think that this message is Charles's response to her request for Bob's key. Thus, Alice will incorrectly conclude that KLpub is Bob's public key. If Lucifer can intercept Alice's subsequent messages to Bob, Lucifer can pretend to be Bob, since Alice believes that Bob's public key is KLpub and Lucifer has KLpriv. This attack would be impossible with message 2 because Alice would notice that it was Lucifer's key, rather than Bob's.

Returning to the correct protocol using message 2 rather than message 2', after receiving Charles's reply, Alice can then sign (with her own private key, which she already knows) and encrypt (with Bob's public key, which she just learned from Charles) any message that she wishes to send to Bob. The reply can be handled symmetrically, after Bob obtains Alice's public key from Charles in a similar manner.

Alice and Bob are trusting Charles to correctly distribute their public keys for them. Charles's message (2) must be signed, so that Alice knows that it really came from Charles, instead of being forged by an adversary. Since we presumed that Alice already had Charles's public key, she can verify Charles's signature on message 2.

Bob cannot send Alice his public key over an insecure channel, even if he signs it. The reason is that she cannot believe a message signed by an unknown key asserting its own identity. But a message like 2 that is signed by Charles can be believed by Alice, if she trusts Charles to be careful about such things. Such a message is called a certificate: it contains Bob's name and public key, certifying the binding between Bob and his key. Bob himself could have sent Alice the certificate Charles signed, if he had the foresight to have already obtained a copy of that certificate from Charles. In this protocol Charles plays the role of a certificate authority (CA). The idea of using the signature of a trusted authority to bind a public key to a principal identifier and calling the result a certificate was invented in Loren Kohnfelder's 1978 M.I.T. bachelor's thesis.

When shared-secret instead of public-key cryptography is being used, we assume that Alice and Charles have pre-established a shared-secret authentication key AkAC and a shared-secret encryption key EkAC, and that Bob and Charles have similarly pre-established a shared-secret authentication key AkBC and a shared-secret encryption key EkBC. Alice begins by sending a message to Charles (again, it does not need to be encrypted or signed):

1. Alice ⇒ Charles: {"Please give me keys for Bob"}

Since shared-secret keys must be kept confidential, Charles must both sign and encrypt the response, using the two shared-secret keys AkAC and EkAC . Charles would reply to Alice:

2. Charles ⇒ Alice: {"Use temporary authentication key AkAB and temporary encryption key EkAB to talk to Bob."} AkAC EkAC 

The notation {M}k denotes encrypting message M with encryption key k . In this example, the message from Charles to Alice is signed by the shared-secret authentication key AkAC and encrypted with the shared-secret encryption key EkAC .

The keys AkAB and EkAB in Charles's reply are newly-generated random shared-secret keys. If Charles would have replied with AkBC and EkBC instead of newly-generated keys, then Alice would be able to impersonate Bob to Charles, or Charles to Bob.

It is also important that message 2 is both authenticated with Charles's and Alice's shared key AkAC and encrypted with their shared EkAC. The kAC's are known only to Alice and Charles, so Alice can be confident that the message came from Charles and that only she and Charles know the kAB's. The next step is for Charles to tell Bob the keys:

3. Charles ⇒ Bob: {"Use the temporary keys AkAB and EkAB to talk to Alice."} AkBC EkBC

This message is both authenticated with key AkBC and encrypted with key EkBC, which are known only to Charles and Bob, so Bob can be confident that the message came from Charles and that no one else but Alice and Charles know the two kAB's.

From then on, Alice and Bob can communicate using the temporary key AkAB to authenticate and the temporary key EkAB to encrypt their messages. Charles should immediately erase any memory he has of the two temporary kAB keys. In such an arrangement, Charles is usually said to be acting as a key distribution center (or KDC). The idea of a shared-secret key distribution center was developed in classified military circles and first revealed to the public in a 1973 paper by Dennis Branstad.\(^*\) In the academic community it first showed up in a paper by Needham and Schroeder.\(^{**}\)

A common variation is for Charles to include message 3 to Bob as an attachment to his reply 2 to Alice; Alice can then forward this attachment to Bob along with her first real message to him. Since message 3 is both authenticated and encrypted, Alice is simply acting as an additional, more convenient forwarding point so that Bob does not have to match up messages arriving from different places. 

Not all key distribution and authentication protocols separate authentication and encryption (e.g., see Sidebar \(\PageIndex{1}\) about Kerberos); they instead accomplish authentication by using carefully-crafted encrypting, with just one shared key per participant. Although having fewer keys seems superficially simpler, it is then harder to establish the correctness of the protocols. It is simpler to use the divide-and-conquer strategy: the additional overhead of having two separate keys for authentication and encrypting is well worth the simplicity and ease of establishing correctness of the overall design.

Sidebar \(\PageIndex{1}\)

The Kerberos authentication system

Kerberos\(^1\) was developed in the late 1980s for project Athena, a network of engineering workstations and servers designed to support undergraduate education at M.I.T.\(^2\) The first version in widespread use was Version 4, which is described here in simplified form; newer versions of Kerberos improve and extend Version 4 in various ways, but the general approach hasn't changed much.

A Kerberos service implements a unique identifier name space, called a realm, in which each name of the name space is the principal identifier of either a network service or an individual user. Kerberos also allows a confederation of Kerberos services belonging to different organizations to implement a name space of realms. Principal names are of the form "[e-mail]", a principal identifier followed by the name of the realm to which that principal belongs. Kerberos principal identifiers are case-sensitive. Users and services are connected by an open, untrusted network. The goal of Kerberos is to provide two-way authentication between a user and a network service securely under the threat of adversaries.

A user authenticates the user's identity and logs on to a realm using a shared-secret protocol with the realm's Kerberos Key Distribution Service (KKDS). Kerberos derives the shared-secret key by cryptographically hashing a user-chosen password. During the name-discovery step (e.g., a physical rendezvous with its administrator), the Kerberos service learns the principal identifier for the user and the shared secret. When logging on, the user sends its principal identifier to KKDS and asks it for authentication information to talk to service S :

Alice ⇒ KDDS: {"[e-mail]", S, Tcurrent}

and the service responds with a ticket identifying the user:

KKDS ⇒ Alice: {Ktmp, S, Lifetime, Tcurrent, ticket}Kalice

The service encrypts this response with the user's shared secret. The verification step occurs when the user decrypts the encrypted response. If Tcurrent and S in the response match with the values in the request, then Kerberos considers the response authentic, and uses the information in the decrypted response to authenticate the user to S . If the user does not posses the key (the hashed password) that decrypts the response, the information inside the response is worthless.

The ticket is a kind of certificate; it binds the user name to a temporary key for use during one session with service S . Kerberos includes the following information in the ticket:

ticket = {Ktmp, "[e-mail]", S, Tcurrent, Lifetime}Ks

The temporary key Ktmp is to allow a user to establish a continued chain of authentication without having to go back to KKDS for each message exchange. The ticket contains a time stamp, the principal identifier of the user, the principal identifier of the service, and a second copy of the temporary key, all encrypted in the key shared between the KDDS and the service S (e.g., a network file service).\(^3\)

Kerberos includes in a request to a Kerberos-mediated network service the ticket identifying the user. When the service receives a request, it authenticates the ticket using the information in the ticket. It decrypts the ticket, checks that the timestamp inside is recent and that its own principal identifier is accurate. If the ticket passes these tests, the service believes that it has the authentic principal identifier of the requesting user and the Kerberos protocol is complete. Knowing the user's principal identifier, the service can then apply its own authorization system to establish that the user has permission to perform the requested operation.

A user can perform cross-realm authentication by applying the basic Kerberos protocol twice: first obtain a ticket from a local KDC for the other realm's KDC, and then using that ticket obtain a second ticket from the remote realm's KDC for a service in the remote realm. For cross-realm authentication to work, there are two prerequisites: (1) initialization: the two realms must have previously agreed upon a shared-secret key between the realms and (2) name discovery: the user and service must each know the other's principal identifier and realm name.

Versions 4 and 5 of Kerberos are in widespread use outside of M.I.T. (e.g., they were adopted by Microsoft). They are based on formerly classified key distribution principles first publicly described in a paper by Branstad and are strengthened versions of a protocol described by Needham and Schroeder (mentioned in the footnotes for Section 5.6.1). These protocols don't separate authentication from confidentiality. They instead rely on clever use of cryptographic operations to achieve both goals. As explained in Section 5.5.4, this property makes the protocols difficult to analyze.

---

\(^1\) S[teven] P. Miller, B. C[lifford] Neuman, J[effrey] I. Schiller, and J[erome] H. Saltzer. Kerberos authentication and authorization system. Section E.2.1 of Athena Technical Plan, M.I.T. Project Athena, October 27, 1988.

\(^2\) George A. Champine. M.I.T. Project Athena: A Model for Distributed Campus Computing. Digital Press, Bedford, Massachusetts, 1991. ISBN 1–55558–072–6. 282 pages.

\(^3\) This description is a simplified version of the Kerberos protocol. One important omission is that the ticket a user receives as a result of successfully logging in is actually one for a ticket-granting service (TGS), from which the user can obtain tickets for other services. TGS provides what is sometimes called a single login or single sign-on system, meaning that a user needs to present a password only once to use several different network services.

For performance reasons, computer systems typically use public-key systems for distributing and authenticating keys and shared-secret systems for sending messages in an authenticated and confidential manner. The operations in public-key systems (e.g., raising to an exponent) are more expensive to compute than the operations in shared-secret cryptography (e.g., table lookups and computing several XOR's). Thus, a session between two parties typically follows two steps:

1. At the start of the session use public-key cryptography to authenticate each party to the other and to exchange new, temporary, shared-secret keys;
2. Authenticate and encrypt subsequent messages in the session using the temporary shared-secret keys exchanged in step 1.

Using this approach, only the first few messages require computationally expensive operations, while all subsequent messages require only inexpensive operations.

One might wonder why it is not possible to the design the ultimate key distribution protocol once, get it right, and be done with it. In practice, there is no single protocol that will do. Some protocols are optimized to minimize the number of messages, others are optimized to minimize the cost of cryptographic operations, or to avoid the need to trust a third party. Yet others must work when the communicating parties are not both online at the same time (e.g., email), provide only one-way authentication, or require client anonymity. Some protocols, such as protocols for authenticating principals using passwords, require other properties than basic confidentiality and authentication: for example, such a protocol must ensure that the password is sent only once per session (see Section 5.3). 

---

\(^*\) Dennis K. Branstad. Security aspects of computer networks.American Institute of Aeronautics and Astronautics Computer Network Systems Conference, paper 73–427 (April, 1973).

\(^{**}\) Roger M. Needham and Michael D. Schroeder. Using encryption for authentication in large net­ works of computers. Communications of the ACM 21, 12 (December, 1978), pages 993–999.

 

Designing Security Protocols 

Security protocols are vulnerable to several attacks in addition to the ones described in Section 5.4.4 and Section 5.5.2 on the underlying cryptographic transformations. The new attacks to protect against fall in the following categories:

• Known-key attacks. An adversary obtains some key used previously and then uses this information to determine new keys.
• Replay attacks. An adversary records parts of a session and replays them later, hoping that the recipient treats the replayed messages as new messages. These replayed messages might trick the recipient into taking an unintended action or divulging useful information to the adversary.
• Impersonation attacks. An adversary impersonates one of the other principals in the protocol. A common version of this attack is the person-in-the-middle attack, where an adversary relays messages between two principals, impersonating each principal to the other, reading the messages as they go by.
• Reflection attacks. An adversary records parts of a session and replays it to the party that originally sent it. Protocols that use shared-secret keys are sometimes vulnerable to this special kind of replay attack.

The security requirements for a security protocol go beyond simple confidentiality and authentication. Consider a replay attack. Even though the adversary may not know what the replayed messages say (because they are encrypted), and even though the adversary may not be able to forge new legitimate messages (because the adversary doesn’t have the keys used to compute authentication tags), the adversary may be able to cause mischief or damage by replaying old messages. The (duplicate) replayed messages may well be accepted as genuine by the legitimate participants, since the authentication tag will verify correctly.

The participants are thus interested not only in confidentiality and authentication, but also in the three following properties:

• Freshness. Does this message belong to this instance of this protocol, or is it a replay from a previous run of this protocol?
• Explicitness. Is this message really a member of this run of the protocol, or is it copied from an run of another protocol with an entirely different function and different participants?
• Forward secrecy. Does this protocol guarantee that if a key is compromised that confidential information communicated in the past stays confidential? A protocol has forward secrecy if it doesn't reveal, even to its participants, any information from previous uses of that protocol.

We study techniques to ensure freshness and explicitness; forward secrecy can be accomplished by using different temporary keys in each protocol instance and changing keys periodically. A brief summary of standard approaches to ensure freshness and explicitness include:

• Ensure that each message contains a nonce (a value, perhaps a counter value, serial number, or a timestamp, that will never again be used for any other message in this protocol), and require that a reply to a message include the nonce of the message being replied to, as well as its own new nonce value. The receiver and sender of course have to remember previously used nonces to detect duplicates. The nonce technique provides freshness and helps foil replay attacks.
• Ensure that each message explicitly contain the name of the sender of the message and of the intended recipient of the message. Protocols that omit this information, and that use shared-secret keys for authentication, are sometimes vulnerable to reflection attacks, as we saw in the example protocol in Section 5.6.1 above. Including names provides explicitness and helps foil impersonation and reflection attacks.
• Ensure that each message specifies the security protocol being followed, the version number of that protocol, and the message number within this instance of that protocol. If such information is omitted, a message from one protocol may be replayed during another protocol and, if accepted as legitimate there, cause damage. Including all protocol context in the message provides explicitness and helps foil replay attacks.

The explicitness property is an example of the be explicit design principle: ensure that each message be totally explicit about what it means. If the content of a message is not completely explicit, but instead its interpretation depends on its context, an adversary might be able to trick a receiver into interpreting the message in a different context and break the protocol. Leaving the names of the participants out of the message is a violation of this principle.

When a protocol designer applies these techniques, the key-distribution protocol of Section 5.6.1 might look more like:

1. Alice ⇒ Charles: {"This is message number one of the "Get Public Key" protocol, version 1.0. This message is sent by Alice and intended for Charles. This message was sent at 11:03:04.114 on 3 March 1999. The nonce for this message is 1456255797824510. What is the public key of Bob?"}Apriv

2. Charles ⇒ Alice: {"This is message number two of the "Get Public Key" protocol, version 1.0. This message is sent by Charles and intended for Alice. This message was sent at 11:03:33.004 on 3 March 1999. This is a reply to the message with nonce 1456255797824510. The nonce for this message is 5762334091147624. Bob’s public key is (…)."}Cpriv

In addition, the protocol would specify how to marshal and unmarshal the different fields of the messages so that an adversary cannot trick the receiver into unmarshaling the message incorrectly.

In contrast to the public-key protocol described above, the first message in this protocol is signed. Charles can now verify that the information included in the message came indeed from Alice and hasn't been tampered with. Now Charles can, for example, log who is asking for Bob's public key.

This protocol is almost certainly overdesigned, but it is hard to be confident about what can safely be dropped from a protocol. It is surprisingly easy to underdesign a protocol and leave security loopholes. The protocol may still seem to "work OK" in the field, until the loophole is exploited by an adversary. Whether a protocol "seems to work OK" for the legitimate participants following the protocol is an altogether different question from whether an adversary can successfully attack the protocol. Testing the security of a protocol involves trying to attack it or trying to prove it secure, not just implementing it and seeing if the legitimate participants can successfully communicate with it. Applying the safety net approach to security protocols tells us to overdesign protocols instead of underdesign.

Some applications require properties beyond freshness, explicitness, and forward secrecy. For example, a service way want to make sure that a single client cannot flood the service with messages, overloading the service and making it unresponsive to legitimate clients. One approach to provide this property is for the service to make it expensive for the client to generate legitimate protocol messages. A service could achieve this by challenging the client to perform an expensive computation (e.g., computing the inverse of a cryptographic function) before accepting any messages from the client. Yet other applications may require that more than one party be involved (e.g., a voting application). As in designing cryptographic primitives, designing security protocols is difficult and should be left to experts. The rest of this section presents some common security protocol problems that appear in computer systems and shows how one can reason about them. Problem set 43 explores how to use the signing and encryption primitives to achieve some simple security objectives.

 

Authentication Protocols

To illustrate the issues in designing security protocols, we will look at two simple authentication protocols. The second protocol uses a challenge and a response, which is an idea found in many security protocols. These protocols also provide the motivation for other protocols that we will discuss in subsequent sections.

A simple example of an authentication protocol is the one for opening a garage door remotely while driving up to the garage. This application doesn't require strong security properties (the adversary can always open the garage with a crowbar) but must be low cost. We want a protocol that can be implemented inexpensively so that the remote can be small, cheap, and battery-powered. For example, we want a protocol that involves only one-way communication, so that the remote control needs only a transmitter. In addition, the protocol should avoid complex operations so that the remote control can use an inexpensive processor.

The parties in the protocol are the remote control, a receiving device (the receiver), and an adversary. The remote control uses a wireless radio to transmit "open" messages to a receiver, which opens the garage door if an authorized remote control sends the message. The goal of the adversary is to open the garage without the permission of the owner of the garage.

The adversary is able to listen, replay, and modify the messages that the remote control sends to the receiver over the wireless medium. Of course, the adversary can also try to modify the remote control, but we assume that stealing the remote control is at least as hard as breaking into the garage physically, in which case there isn't much need to also subvert the remote control protocol.

The basic idea behind the protocol is for the receiver and the remote control to share a secret. The remote control sends the secret to the receiver and if it matches the receiver's secret, then the receiver opens the garage. If the adversary doesn't know the secret, then the adversary cannot open the garage. Of course, if the secret is transmitted over the air in clear text, the adversary can easily learn the secret, so we need to refine this basic idea.

A lightweight but correct protocol is as follows. At initialization, the remote control and receiver agree on some random number, which functions as a shared-secret key, and a random number, which is an initial counter value. When the remote control is pressed, it sends the following message:

remote ⇒ receiver: {counter, HASH(key, counter)}

and increments the counter.

When receiving the message, the receiver performs the following operations:

1. verify hash: compute HASH(key, counter) and compare result with the one in message
2. if hash verifies, then increment counter and open garage. If not, do nothing.

Because the holder of the remote control may have pressed the remote while out of radio range of the receiver, the receiver generally tries successive values of counter between its previous values \(N\) and, e.g., \(N+100\) in step 1. If it finds that one of the values works, it resets the counter to that value and opens the garage.

This protocol meets our basic requirements. It doesn't involve two-way communication. It does involve computing a hash, but strong, inexpensive-to-compute hashes are readily available in the literature. Most important, the protocol is likely to provide a good enough level of security for this application.

The adversary cannot easily construct a message with the appropriate hash because the adversary doesn't know the shared-secret key. The adversary could try all possible values for the hash output (or all possible keys, if the keys are shorter than the hash output). If the hash output and key are sufficiently long, then this brute-force attack would take a long time. In addition, if necessary, the protocol could periodically re-initialize the key and counter.

The protocol is not perfect. For example, it has a replay attack. Suppose an impatient user presses the button on the remote control twice in close succession; the receiver responds to the first signal and doesn't hear the second signal. An adversary who happens to be recording the signals at the time can notice the two signals and guess that replaying the recording of the second signal may open the garage door, at least until the next time that legitimate user again uses the remote control. This weakness is probably acceptable.

The adversary can also launch a denial-of-service attack on the protocol (e.g., by jamming the radio signal remotely). The adversary, however, could also wreck the garage's door physically, which is simpler. The owner can also always get out of the car, walk to the garage, and use a physical key, so there is little motivation to deny access to the remote control.

Protocols such as the one described above are used in practice. For example, the Chamberlain garage door opener\(^1\) uses a similar protocol with an extremely simple hash function (multiplication by 3 in a finite field) and it computes the hash over the previous hash, instead of over the counter and key. The simple hash probably provides a little less security, but it has the advantage that is cheap to implement. Other vendors seem to use similar protocols, but it is difficult to confirm because this industry has a practice of keeping its proprietary protocols secret, perhaps hoping to increase security through obscurity, which violates the open design principle and historically hasn't worked.

A version that is more secure than the garage-door protocol is used for authentication of users who want to download their email from an email service. Protocols for this application can assume two-way communication and exploit the idea of a challenge and a response. One widely used challenge-response protocol is the following\(^2\):

1. Initialization. M1: Client ⇒ Server: (Opens a TCP connection)

2. Challenge. M2: Server ⇒ Client: {"This is server S at 9:35:20.00165 EDT, 22 September 2006."}

3. Response. M3: Client ⇒ Server: {"This is user U and the hash of M2 and U's password is:", HASH{M2, U's password}}

The server, which has its own copy of the secret password associated with user U, does its own calculation of HASH{M2, U's password}, and compares the result with the second field of M3. If they match, it considers the authentication successful and it proceeds to download the email messages.

The protocol isn't vulnerable to the person-in-the-middle attack of the garage protocol because the date and time in M2 functions as a nonce, which is included in the hash of M3. But addressing the person-in-the-middle attack requires two-way communication, which couldn't be used by the garage door opener.

Although this protocol is a step up over the garage door protocol, it has weaknesses too. It is vulnerable to brute-force attacks. The adversary can learn the username U from M3. Then, later the adversary can connect to the mail server, receive M2, guess a password for U , and see if the attempt is successful. Although each guess takes one round of the protocol and leaves an audit trail on the server, this might not stop a determined adversary.

A related weakness is that the protocol doesn't authenticate the server S , so the adversary can impersonate the server. The adversary tricks the client in connecting to a machine that the adversary controls (e.g., by spoofing a DNS response for the name S ). When the client connects, the adversary sends M2, and receives a correct M3. Now the adversary can do an off-line brute-force attack on the user's password, without leaving an audit trail. The adversary can also provide the client with bogus email.

These weaknesses can be addressed. For example, instead of sending messages in the clear over a TCP connection, the protocol could set up a confidential, authenticated connection to the server using SSL/TLS (see Section 5.11). Then, the client and server can run the challenge-response protocol over this connection. The server can also send the email messages over the connection so that they are protected too. SSL/TLS authenticates all messages between a client and server and sends them encrypted. In addition, the client can require that the server provides a certificate with which the client can verify that the server is authentic. This approach could be further improved by using a client certificate instead of using U's password, which is a weak secret and vulnerable to dictionary attacks. Using SSL/TLS (either with or without client certificate) is common practice today.

A challenge-response protocol is a valuable tool only if it is implemented correctly. For example, a version of the UW IMAP server (a mail server that speaks the IMAP protocol and developed by the University of Washington) contained an implementation error that incorrectly specifies the conditions of successful authentication when using the challenge-response protocol described above.\(^3\) After authenticating three times unsuccessfully using the challenge-response protocol, the server allowed the fourth attempt to succeed; the intention was to fail the fourth attempt immediately, but the implementers got the condition wrong. This error allowed an adversary to successfully authenticate as any user on the server after three attempts. Such programming errors are all too often the reason why the security of a system can be broken.

---

\(^1\) Chamberlain Group, Inc. v. Skylink Techs., Inc., 292 F. Supp. 2d 1040 (N.D. Ill. 2003); aff’d 381 F.3d 1178 (U.S. App. 2004)

\(^2\) Myers and M. Rose, Post Office Protocol Version 3, Internet Engineering Task Force Request For Comments (RFC) 1939, May 1996.

\(^3\) United States Computer Emergency Readiness Team (US-CERT), UW-imapd fails to properly authenticate users when using CRAM-MD5, Vulnerability Note VU #702777, January 2005.

 

An Incorrect Key Exchange Protocol

The challenge-response protocol over SSL/TLS assumes SSL/TLS can set up a confidential and authenticated channel, which requires that the sender and receiver exchange keys securely over an untrusted network. It is possible to do such an exchange, but it must be done with care. We consider two different protocols for key exchange. The first protocol is incorrect, the second is (as far as anyone knows) correct. Both protocols attempt to achieve the same goal, namely for two parties to use a public-key system to negotiate a shared-secret key that can be used for encrypting. Both protocols have been published in the computer science literature and systems incorporating them have been built.

In the first protocol, there are three parties: Alice, Bob, and a certificate authority (CA). The protocol is as follows:

1. Alice ⇒ CA: {"Give me certificates for Alice and Bob"}

2. CA ⇒ Alice: {"Here are the certificates:", {Alice, Apub, T}CApriv, {Bob, Bpub, T}CApriv}

In the protocol, the CA returns certificates for Alice and Bob. The certificates bind the names to public keys. Each certificate contains a timestamp T for determining if the certificate is fresh. The certificates are signed by the CA.

Equipped with the certificates from the CA, Alice constructs an encrypted message for Bob:

3. Alice ⇒ Bob: {"Here is my certificate and a proposed key:", {Alice, Apub, T}CApriv, {KAB, T}Apriv }Bpub

The message contains Alice’s certificate and her proposal for a shared-secret key (KAB). Bob can verify that Apub belongs to Alice by checking the validity of the certificate using the CA's public key. The time-stamped shared-secret key proposed by Alice is signed by Alice, which Bob can verify using Apub. The complete message is encrypted with Bob's public key. Thus, only Bob should be able to read KAB.

Now Alice sends a message to Bob encrypted with KAB:

4. Alice ⇒ Bob: {"Here is my message:", ........ T}KAB

Bob should be able to decrypt this message, once he has read message 3. So, what is the problem with this protocol? We suggest the reader pause for some time and try to discover the problem before continuing to read further. As a hint, note that Alice has signed only part of message 3 instead of the complete message. Recall that we should assume that some of the parties to the protocol may be adversaries.

The fact that there is a potential problem should be clear because the protocol fails the be explicit design principle. The essence of the protocol is part of message 3, which contains her proposal for a shared-secret key:

Alice ⇒ Bob: {KAB, T}Apriv

Alice tells Bob that KAB is a good key for Alice and Bob at time T , but the names of Alice and Bob are missing from this part of message 3. The interpretation of this segment of the message is dependent on the context of the conversation. As a result, Bob can use this part of message 3 to masquerade as Alice. Bob can, for example, send Charles a claim that he is Alice and a proposal to use KAB for encrypting messages.

Suppose Bob wants to impersonate Alice to Charles. Here is what Bob does:

1. Bob ⇒ CA: {"Give me the certificates for Bob and Charles"}

2. CA ⇒ Bob: {"Here are the certificates:", {Bob, Bpub, T'}CApriv, {Charles, Cpub, T'}CApriv}

3. Bob ⇒ Charles: {"Here is my certificate and a proposed key":, {Alice, Apub, T}CApriv, {KAB, T}Apriv }Cpub

Bob’s message 3 is carefully crafted: he has placed Alice's certificate in the message (which he has from the conversation with Alice), and rather than proposing a new key, he has inserted the proposal, signed by Alice, to use KAB, in the third component of the message.

Charles has no way of telling that Bob's message 3 didn't come from Alice. In fact, he thinks this message comes from Alice, since {KAB, T} is signed with Alice's private key. So he (erroneously) believes he has key that is shared with only Alice, but Bob has it too. Now Bob can send a message to Charles:

1. Bob ⇒ Charles: {"Please send me the secret business plan. Yours truly, Alice."}KAB

Charles believes that Alice sent this message because he thinks he received KAB from Alice, so he will respond. Designing security protocols is tricky! It is not surprising that Denning and Sacco\(^*\), the designers of this protocol, overlooked this problem when they originally proposed this protocol.

An essential assumption of this attack is that the adversary (Bob) is trusted for something because Alice first has to have a conversation with Bob before Bob can masquerade as Alice. Once Alice has this conversation, Bob can use this trust as a toehold to obtain information he isn't supposed to know.

The problem arose because of lack of explicitness. In this protocol, the recipient can determine the intended use of KAB (for communication between Alice and Bob) only by examining the context in which it appears, and Bob was able to undetectably change that context in a message to Charles.

Another problem with the protocol is its lack of integrity verification. An adversary can replace the string "Here is my certificate and a proposed key" with any other string (e.g., "Here are the President's certificates") and the recipient would have no way of determining that this message is not part of the conversation. Although Bob didn't exploit this problem in his attack on Charles, it is a weakness in the protocol.

One way of repairing the protocol is to make sure that the recipient can always detect a change in context; that is, the recipient can always determine that the context is authentic. If Alice had signed the entire message 3, and Charles had verified that message 3 was properly signed, that would ensure that the context is authentic, and Bob would not have been able to masquerade as Alice. If we follow the explicitness principle, we should also change the protocol to make the key proposal itself explicit, by including the name of Alice and Bob with the key and timestamp and signing that entire block of data (i.e., {Alice, Bob, KAB, T}Apriv).

Making Alice and Bob explicit in the proposal for the key addresses the lack of explicitness, but doesn’t address the lack of verifying the integrity of the explicit information. Only signing the entire message 3 addresses that problem.

You might wonder how it is possible that many people missed these seemingly obvious problems. The original protocol was designed in an era before the modular distinction between encrypting and signing was widely understood. It used encrypting of the entire message as an inexpensive way of authenticating the content; there are some cases where that trick works, but this is one where the trick failed. This example is another one of why the idea of obtaining authentication by encrypting is now considered to be a fundamentally bad practice.

---

\(^*\) D. Denning and G. Sacco. Timestamps in key distribution protocols. Communication of the ACM 24, 8, pages 533–535, 1981.

 

Diffie-Hellman Key Exchange Protocol

The second protocol uses public-key cryptography to negotiate a shared-secret key. Before describing that protocol, it is important to understand the Diffie-Hellman key agreement protocol first. In 1976 Diffie and Hellman published the groundbreaking paper New Directions in cryptography \(^*\), which proposed the first protocol that allows two users to exchange a shared-secret key over an untrusted network without any prior secrets. This paper opened the floodgates for new papers in cryptography. Although there was much work behind closed doors, between 1930 and 1975 few papers with significant technical contributions regarding cryptography were published in the open literature. Now there are several conferences on cryptography every year.

The Diffie-Hellman protocol has two public system parameters: \(p\), a prime number, and \(g\), the generator. The generator \(g\) is an integer less than \(p\), with the property that for every number \(n\) between \(1\) and \(p-1\) inclusive, there is a power \(k\) of \(g\) such that \(n = g^k (\text{modulo } p)\).

If Alice and Bob want to agree on a shared-secret key, they use \(p\) and \(g\) as follows. First, Alice generates a random value \(a\) and Bob generates a random value \(b\). Both \(a\) and \(b\) are drawn from the set of integers \({1, \dots, p-2}\). Alice sends to Bob: \(g^a (\text{modulo } p)\), and Bob sends to Alice: \(g^b (\text{modulo } p)\).

On receiving these messages, Alice computes \(g^{ab} = (g^b)^a (\text{modulo } p)\), and Bob computes \(g^{ba} = (g^a)^b (\text{modulo } p)\). Since \(g^{ab} = g^{ba} = k\), Alice and Bob now have a shared-secret key \(k\). An adversary hearing the messages exchanged between Alice and Bob cannot compute that value because the adversary doesn't know \(a\) and \(b\); the adversary hears only \(p\), \(g\), \(g^a\) and \(g^b\).

The protocol depends on the difficulty of calculating discrete logarithms in a finite field. It assumes that if \(p\) is sufficiently large, it is computationally infeasible to calculate the shared-secret key \(k = g^{ab}(\text{modulo } p)\) given the two public values \(g^a (\text{modulo } p)\) and \(g^b (\text{modulo } p)\). It has been shown that breaking the Diffie-Hellman protocol is equivalent to computing discrete logarithms under certain assumptions.

Because the participants are not authenticated, the Diffie-Hellman protocol is vulnerable to a person-in-the-middle attack, similar to the one in Section 5.6.4. The importance of the Diffie-Hellman protocol is that it is the first example of a much more general cryptographic approach, namely the derivation of a shared-secret key from one party's public key and another party's private key. The second protocol is a specific instance of this approach, and addresses the weaknesses of the Denning-Sacco protocol.

---

\(^*\) Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory IT–22, 6 (November 1976), pages 644–654.

Diffie and Hellman were the second inventors of public key cryptography (the first inventor, James H. Ellis, was working on classified projects for the British Government Communications Headquarters at the time, in 1970, and was not able to publish his work until 1987). This is the paper that introduced the idea to the unclassified world.

 

A Key Exchange Protocol Using a Public-Key System

The second protocol uses a Diffie-Hellman-like exchange to set up keys for encrypting and authentication. The protocol is designed to set up a secure channel from a client to a service in the SFS self-certifying file system [Suggestions for Further Reading 5.4.3]; a similar protocol is also used in the Taos distributed operating system [Suggestions for Further Reading 5.3.2 11.3.2]. Web clients and servers use the more complex SSL/TLS protocol, which is described in Section 5.11.

The goal of the SFS protocol is to create a secure (authenticated and encrypted) connection between a client and a server that has a well-known public key. The client wants to be certain that it can authenticate the server and that all communication is confidential, but at the end of this protocol, the client will still be unauthenticated; an additional protocol will be required to identify and authenticate the client.

The general plan is to create two shared-secret nonce keys for each connection between a client and a server. One nonce key (Kcs) will be used for authentication and encryption of messages from client to server, the other (Ksc) for authentication and encryption of messages from server to client. Each of these nonce keys will be constructed using a Diffie-Hellman-like exchange in which the client and the server each contribute half of the key.

To start, the client fabricates two nonce half-keys, named Kc-cs and Kc-sc, and also a nonce private and public key pair: Tpriv and Tpub. Tpub is, in effect, a temporary name for this connection with this anonymous client.

The client sends to the service a request message to open a connection, containing Tpub, Kc-cs, and Kc-sc. The client encrypts the latter two with Spub, the public key of the service:

Client ⇒ service: {"Here is a temporary public key Tpub and two key halves encrypted with your public key:", {Kc-cs, Kc-sc}Spub}

The protocol encrypts Kc-cs, and Kc-sc to protect against eavesdroppers. Since Tpub is a public key, there is no need to encrypt it.

The service can decrypt the keys proposed by the client with its private key, thus obtaining the three keys. At this point, the service has no idea who the client may be, and because the message may have been modified by an adversary, all it knows is that it has received three keys, which it calls Tpub', Kc-cs' and Kc-sc', and which may or may not be the same as the corresponding keys fabricated by the client. If they are the same, then Kc­ ' and Kc-sc' are shared secrets known only to the client and the server.

The service now fabricates two more nonce half-keys, named Ks-cs and Ks-sc. It sends a response to the client, consisting of these two half-keys encrypted with Tpub':

Service ⇒ client: {"Here are two key halves encrypted with your temporary public key:", {Ks-cs, Ks-sc}Tpub}

Unfortunately, even if Tpub' = Tpub, Tpub is public, so the client has no assurance that the response message came from the service; an adversary could have sent it or modified it. The client decrypts the message using Tpriv, to obtain Ks-cs' and Ks-sc'.

At this point in the protocol, the two parties have the following components in hand:

• Client: Spub, Tpub, Kc-cs, Kc-sc, Ks-cs', Ks-sc'
• Server: Spub, Tpub', Kc-cs', Kc-sc', Ks-cs, Ks-sc

Now the client calculates

• Kcs ← HASH ("client to server", Spub, Tpub, Ks-cs', Kc-cs)
• Ksc ← HASH ("server to client", Spub, Tpub, Ks-sc', Kc-sc)

and the server calculates

• Kcs' ← HASH ("client to server", Spub, Tpub', Ks-cs, Kc-cs')
• Ksc' ← HASH ("server to client", Spub, Tpub', Ks-sc, Kc-sc')

If all has gone well (that is, there have been no attacks), Kcs = Kcs' and Ksc = Ksc'.

At this point there are three concerns:

1. An adversary may have replaced one or more components in such a way that the two parties do not have matching sets. If so, and assuming that the hash function is cryptographically secure, about half the bits of Kcs will not match Kcs'; the same will be true for Ksc and Ksc'. Ksc and Kcs are about to be used as keys, so the parties will quickly discover any such mismatch.
2. An adversary may have replaced a component in such a way that both parties still have matching sets. But if we compare the components of Kcs and Kcs', we notice that at least one of the parties uses a personally chosen (unprimed) version of every component, and the adversary could not have changed that version, so there is no way for an adversary to make a matching change for both parties.
3. An adversary may have been able to discover all of the components and thus be able to calculate Ksc, Kcs, or both. But the values of Kc-cs and Kc-sc were created by the client and encrypted under Spub before sending them to the service, so only the client and the service know those two components. 

If Kcs = Kcs' and Ksc = Ksc', the two parties have two keys that only they know, and only the service and this client could have calculated them. In addition, because they are calculated using Ks-sc, Kc-sc, Ks-cs, and Kc-cs, which are nonces created just for this exchange, both parties are ensured that Kcs and Ksc are fresh. In summary, Kcs and Ksc are newly generated shared secrets.

The protocol proceeds with the client generating a shared-secret authentication key Kssa-cs and a shared-secret encryption key Ksse-cs from Kcs, perhaps by simply using the first half of Kcs as Kssa-cs and the second half as Ksse-cs. The client can now prepare and send an encrypted and authenticated request to the server:

{M}Ksse-cs Kssa-cs

The server generates the same shared-secret authentication key Kssa-cs and a shared-secret encryption key Ksse-cs from Kcs' and it can now try to decrypt and authenticate M . If the authentication succeeds, the server knows that Kcs = Kcs'.

The server performs a similar procedure based on Ksc for its response. If the client successfully authenticates the response the client knows Ksc = Ksc'. The fact that it received a response tells it that the server successfully verified that Kcs = Kcs'.

From now on, the client knows that it is talking to the server associated with Spub, and the connection is confidential. The server knows that the connection is confidential and that all messages are coming from the same source, but it does not know what that source is. If the server wants to know the source, it can ask and, for example, demand a password to authenticate the identity that the source claims.

To ensure forward secrecy, the client periodically repeats the whole protocol periodically. At regular intervals (e.g., every hour), the client discards the temporary keys Tpub and Tpriv, generates a new public key Tpub and private key Tpriv, and runs the protocol again.

 

Summary

This section described several security protocols to obtain different objectives. We studied a challenge-response protocol to open garage doors. We studied an incorrect protocol to set up a secure communication channel between two parties. Then, we studied a correct protocol for that same purpose that provides confidentiality but doesn't authenticate the participants. Finally, we studied a protocol for setting up a secure communication channel that provides both confidentiality and authenticity. Protocols for setting up secure channels become important whenever the participants are separated by a network. Section 5.11 describes a protocol for setting up secure channels in the World-Wide Web.

Many systems have additional security requirements, and therefore may need protocols with different features. For example, a system that provides anonymous email must provide an authenticated and confidential communication channel between two parties with the property that the receiver knows that a message came from the same source as previous messages and that nobody else has read the message, but must also hide the identity of the sender from the receiver. Such a system requires a more sophisticated design and protocols because hiding the identity of the sender is a difficult problem. The receiver may be able to learn the Internet address from which some of the messages were sent or may be able to observe traffic on certain communication links; to make anonymous email resist such analysis requires elaborate protocols that are beyond the scope of this text, but see, for example, Chaum's paper for a solution [Suggestions for Further Reading 5.5.8]. Security protocols are also an active area of research and researchers continuously develop novel systems and protocols for new scenarios or for particular challenging problems such as electronic voting, which may require keeping the identity of the voter secret, preventing a voter from voting more than once, allowing the voter to verify that the vote was correctly recorded, and permitting recounts. The interested reader is encouraged to consult the professional literature for developments.