Key negotiation and Implementation issues
Finally, we are ready to tackle the key negotiation protocol.
Document Preview:
Chapter 14: Key Negotiation Chapter 15: Implementation Issues (II)
Chapter 14: Key Negotiation Chapter 15: Implementation Issues (II) H A P T E R 1 4 Key Negotiation Finally, we are ready to tackle the key negotiation protocol. The purpose of this protocol is to derive a shared key that can then be used for the secure channel we defined in Chapter 7. Complete protocols get quite complicated, and it can be confusing to present the final protocol all at once. Instead, we will present a sequence of protocols, each of which adds a bit more functionality. Keep in mind that the intermediate protocols are not fully functional, and will have various weaknesses. There are different methods for designing key negotiation protocol, some with supporting proofs of security and some without. We designed our pro tocol from the ground up-not only because it leads to a cleaner explanation, but also because it allows us to highlight nuances and challenges at each stage of the protocol's design. 1 4. 1 The Setting There are two parties in the protocol: Alice and Bob. Alice and Bob want to communicate securely. They will first conduct the key negotiation protocol to set up a secret session key k, and then use k for a secure channel to exchange the actual data. For a secure key negotiation, Alice and Bob must be able to identify each other. This basic authentication capability is the subject of the third part of this book. For now, we will just assume that Alice and Bob can authenticate messages to each other. This basic authentication can be done using RSA 227 228 Part III • Key Negotiation signatures (if Alice and Bob know each other's keys or are using a PKI), or using a shared secret key and a MAC function. But wait! Why do a key negotiation if you already have a shared secret key? There are many reasons why you might want to do this. First of all, the key negotiation can decouple the session key from the existing (long-term) shared key. If the session key is compromised (e.g., because of a flawed secure channel implementation), the shared secret still remains safe. And if the shared secret key is compromised after the key negotiation protocol has been run, the attacker who learns the shared secret key still does not learn the session key negotiated by the protocoL So yesterday'S data is still protected if you lose your key today. These are important properties: they make the entire system more robust. There are also situations in which the shared secret key is a relatively weak one, like a password. Users don't like to memorize 30-letter passwords, and tend to choose much simpler ones. A standard attack is the dictionary attack, where a computer searches through a large number of simple passwords. Although we do not consider them here, some key negotiation protocols can turn a weak password into a strong key. 1 4.2 A First Try There are standard protocols you might use to do key negotiation. A well known one based on the DH protocol is the Station-to-Station protocol [34] . Here we will walk you through the design of a different protocol for illustrative purposes. We'll start with the simplest design we can think of, shown in Figure 14.1 . This is just the DH protocol in a subgroup with some added authentication. Alice and Bob perform the DH protocol using the first two messages. (We've left out some of the necessary checks, for simplicity.) Alice then computes an authentication on the session key k and sends it to Bob, who checks the authentication. Similarly, Bob sends an authentication of k to Alice. We don't know the exact form of the authentication at the moment. Remem ber, we said we assume that Alice and Bob can authenticate messages to each other. So Bob is able to check AUTHA(k) and Alice is able to check AUTHB(k). Whether this is done using digital signatures or using a MAC function is not our concern here. This protocol merely turns an authentication capability into a session key. There are some problems with this protocol: - The protocol is based on the assumption that (p, q,g) are known to both Alice and Bob. Choosing constants for these values is a bad idea. - It uses four messages, whereas it is possible to achieve the goal using only three. Alice Known: (p, q,g) x En { 1, . . . , q - 1 ) check AUTHB(k) x := gx Y := gY AUTHB(k) Figure 1 4.1 : A first attempt at key negotiation. Chapter 1 4 • Key Negotiation 229 Bob Known: (p, q,g) Y En { 1, . . . , q - 1 ) - The session key is used as an input to the authentication function. This is not a problem if the authentication function is strong, but suppose the authentication function leaks a few bits about the session key. That would be bad. It certainly would require a new analysis of the entire protocol. A good rule of thumb is to use a secret only for a Single thing. Here k will be used as a session key, so we don't want to use it as an argument to the authentication function. - The two authentication messages are too similar. If, for example, the authentication function is a simple MAC using a secret key known to both Alice and Bob, then Bob could just send the authentication value he received from Alice, and he would not need the secret key to complete the protocol. Thus Alice would not be convinced by the last authentication message. - Implementations have to be careful not to use k until the authentication messages have been exchanged. This is not a major issue and is a rather simple requirement, but you wouldn't believe what sometimes happens when people try to optimize a program. We will fix all of these problems over the course of this chapter. 1 4.3 Protocols Live Forever We've emphasized the importance of designing systems to withstand the future. This is even more important for protocols. If you limit the size of database fields to 2000 bytes, it might be a problem for some users, but you :130 Part III Key Negotiation can remove the limit in the next version. Not so for protocols. Protocols are run between different participants, and every new version needs to be interoperable with the old version. Modifying a protocol and still keeping it compatible with older versions is rather complicated. Before you know it, you have to implement several versions of the protocol, with a system to decide which version to use. The protocol version switch becomes a point of attack, of course. If an older protocol is less secure, an attacker has an incentive to force you to use that older protocoL You'd be surprised at how many systems we've seen that suffer from what's known as a version-rollback attack. It is of course impossible to know all the future requirements, so it might be necessary to define a second version of a protocol at some point. However, the cost of having several protocol versions is high, especially in overall complexity. Successful protocols live almost forever (we don't care about unsuccessful ones). It is extremely difficult to completely remove a protocol from the world. So it is even more important to design protocols to be future-proof. This is why we can't specify a fixed set of DH parameters for our key negotiation protocoL Even if we chose them to be very large, there is always a danger that future cryptanalytical improvements might force us to change them. 1 4.4 An Authentication Convention Before we go on, we will introduce an authentication convention. Protocols often have many different data elements, and it can be hard to figure out exactly which data elements need to be authenticated. Some protocols break because they neglect to authenticate certain data fields. We use a simple convention to solve these problems. In our protocols, every time a party sends an authentication, the authentica tion data consists of all the data exchanged so far: all the previous messages, and all the data fields that precede the authentication in the authenticator's message. The authenticator will also cover (be computed over) the identities of the communicants. In the protocol shown in Figure 14.1, Alice's authenticator would not be on k, but on Alice's identifier, Bob's identifier, X, and Y. Bob's authenticator would cover Alice's identifier, Bob's identifier, X, Y, and AUTHA. This convention removes many avenues of attack. It also costs very little. Cryptographic protocols don't exchange that much data, and authentication computations almost always start by hashing the input string. Hash functions are so fast that the extra cost is insignificant. This convention also allows us to shorten the notation. Instead of writ ing something like AUTHA(X, Y) we simply write AUTHA. As the data to Chapter 1 4 • Key Negotiation ]31 be authenticated is specified by the convention, we no longer need to write it down explicitly. All further protocols in this book will use this convention. Just as a reminder: authentication functions only authenticate a string of bytes. Each string of bytes to be authenticated must start with a unique identifier that identifies the exact point in the protocol where this authenticator is used. Also, the encoding of the previous messages and the data fields into this string of bytes must be such that the messages and fields can be recovered from the string without further context information. We've already talked about this in detail, but it is an important point that is easily overlooked. 1 4.5 A Second Attempt How do we fix the problems of the previous protocol? We don't want to use a constant DH parameter set, so we'll let Alice choose it and send it to Bob. We'll also collapse the four messages into two, as shown in Figure 14.2. Alice starts by