Informally, we can define the problem as creating a secure connection between Alice and Bob. We'll have to formalize this a bit before it becomes clear what we are talking about.

7.1.1 Roles

First, most connections are bi-directional. Alice sends messages to Bob, and Bob sends messages to Alice. You don't want to confuse the two streams of messages, so there must be some kind of asymmetry in the protocol. In real systems, maybe one party is the client and the other the server, or maybe it is easier to speak of the initiator (the party that initiated the secure connection) and the responder. It doesn't matter how you do it, but you have to assign the Alice and Bob roles to the two parties in question in such a way that each of them knows who is playing which role.

Of course, there is always Eve, who tries to attack the secure channel in any way possible. Eve can read all of the communications between Alice and Bob and arbitrarily manipulate these communications. In particular, Eve can delete, insert, or modify data that is being transmitted.

We always talk about transmitting messages from Alice to Bob, and most of the time our mental image is of two separate computers sending messages to each other over a network of some sort. Another very interesting application is storing data securely. If you think of storing data as transmitting it to the future, then all the discussions here apply. Alice and Bob might be the same person, and the transmission medium could be a backup tape or a USB stick. You still want to protect the medium from outside eavesdroppers and manipulations. Of course, when you send data to the future, you cannot have an interactive protocol, since the future cannot send a message back to the past.

7.1.2 Key

To implement a secure channel, we need a shared secret. In this case we will assume that Alice and Bob share a secret key K, but that nobody else knows this key. This is an essential property. The cryptographic primitives can never identify Alice as a person. They can at most identify the key. Thus Bob's verification algorithm will tell him something like: “This message was sent by somebody who knows the key K and who played the role of Alice.” This statement is only useful if Bob knows that knowledge of K is restricted, preferably to himself and Alice.

How the key is established is not our business here. We just assume the key is there. We will talk about key management in great detail in Chapter 14. The requirements for the key are as follows:

• The key K is known only to Alice and Bob.
• Every time the secure channel is initialized, a new value is generated for the key K.

The second item is also important. If the same key is used over and over again, then messages from older sessions can be replayed to Alice or Bob, and lead to much confusion. Therefore, even in situations where you have a fixed password as key, you need a key negotiation protocol between Alice and Bob to set up a suitable unique key K, and you must re-run this protocol every time a secure channel is established. A key such as K that is used for a single communication session is called a session key. Again, how K is generated will be discussed in Chapter 14.

The secure channel is designed to achieve a security level of 128 bits. Following our discussion in Section 3.5.7, we will use a 256-bit key. Thus, K is a 256-bit value.

7.1.3 Messages or Stream

The next question is whether we look at the communications between Alice and Bob as a sequence of discrete messages (such as e-mails) or as a continuous stream of bytes (such as streaming media). We will only consider systems that handle discrete messages. These can trivially be converted to handle a stream of bytes by cutting the data stream into separate messages and reassembling the stream at the receiver's end. In practice, almost all systems use a discrete message system at the cryptographic layer.

We also assume that the underlying transport system that conveys the messages between Alice and Bob is not reliable. Even a reliable communication protocol like TCP/IP does not form a reliable communication channel from a cryptographic point of view. After all, the attacker can easily change, remove, or insert data in a TCP stream without interrupting the flow of data. TCP is only reliable with respect to random events such as loss of packet. It does not protect against an active adversary. From our adversarial point of view, there is no such thing as a reliable communication protocol. (This is a good example of how cryptographers view the world.)

7.1.4 Security Properties

We can now formulate the security properties of the channel. Alice sends a sequence of messages m1, m2, … that are processed by the secure channel algorithms and then sent to Bob. Bob processes the received messages through the secure channel algorithms, and ends up with a sequence of messages m′1, m′2, ….

The following properties must hold:

• Eve does not learn anything about the messages mi except for their timing and size.
• Even when Eve attacks the channel by manipulating the data that is being communicated, the sequence m′1, m′2, … of messages that Bob receives is a subsequence of m1, m2, …, and Bob learns exactly which subsequence he received. (A subsequence is best defined by saying that it can be constructed from the original sequence by the removal of zero or more elements.)

The first property is secrecy. Ideally, Eve should not learn anything about the messages. In real life, this is very hard to achieve. It is extremely hard to hide information such as the size or the timing of the messages. The known solutions require Alice to send a continuous stream of messages at the maximum bandwidth that she will ever use. If she doesn't have any messages to send, she should invent some trivial ones and send those. This might be acceptable for military applications, but it is not acceptable for most civilian applications. Given that Eve can see the size and timing of messages on a communication channel, she can find out who is communicating with whom, how much, and when. This is called traffic analysis. It yields a host of information, and is extremely hard to prevent. This is a well-known problem with other secure channels, like SSL/TLS, IPsec, and SSH. We will not solve it in this book, so Eve will be able to perform traffic analysis on our secure channel.

The second property ensures that Bob only gets proper messages, and that he gets them in their correct order. Ideally, we would want Bob to receive the exact sequence of messages that Alice sent. But none of the real-world communications protocols are reliable in a cryptographic sense. Eve can always delete a message in transit. As we cannot prevent the loss of messages, Bob will necessarily have to make do with getting only a subsequence of the messages. Note that the remaining messages that he does receive are in order. There are no duplicates, no modified messages, and no bogus messages sent by someone other than Alice. As a further requirement, Bob learns exactly which messages he has missed. This can be important in some applications where the interpretation of the message depends on the order in which they are received.

In most situations, Alice wants to ensure that Bob gets all the information she sent him. Most systems implement a scheme whereby Bob sends acknowledgments (either explicit or implicit) to Alice, and Alice resends any information for which she didn't receive an acknowledgment from Bob. Note that our secure channel never takes the initiative in resending a message. Alice will have to do that herself, or at least the protocol layer that makes use of the secure channel will have to do that.

So why not make the secure channel reliable by implementing the resend functionality inside the secure channel? Because that would complicate the secure channel description. We like to keep the security-critical modules simple. Message acknowledgments and resends are standard communication protocol techniques, and they can be implemented on top of our secure channel. Also, this is a book about cryptography, not about basic communication protocol techniques.

Obviously we will apply both encryption and authentication to the message. There are three approaches [7, 82]: we can encrypt first and then authenticate the ciphertext (encrypt-then-authenticate); authenticate first and then encrypt both the message and the MAC value (authenticate-then-encrypt); or both encrypt the message and authenticate the message and then combine (such as concatenate) the two results (encrypt-and-authenticate). There is no simple answer for which method is best.

There are two main arguments in favor of encrypting first. There are theoretical results that show that, given certain specific definitions of secure encryption and authentication, the encrypt-first solution is secure, whereas the other approaches are insecure. If you look at the details, it turns out that authenticate-first is only insecure if the encryption scheme has a specific type of weakness. In practical systems, we never use encryption schemes with such weaknesses. However, these weak encryption schemes satisfy a particular formal security definition. Applying the MAC to the ciphertext of such a weak encryption scheme fixes it and makes it secure. Having these theoretical results is valuable. But these theoretical results don't always apply to real-life encryption schemes. In fact, there are similar proofs that these problems do not occur at all for stream ciphers (such as CTR mode) and CBC-mode encryption when the nonce or IV is authenticated.

The second argument in favor of encrypting first is that it is more efficient in discarding bogus messages. For normal messages, Bob has to both decrypt the message and check the authentication, irrespective of the order they were applied in. If the message is bogus (i.e., has a wrong MAC field) then Bob will discard it. With encrypt-first, the decryption is done last on the receiver side, and Bob never has to decrypt bogus messages, since he can identify and discard them before decryption. With authenticate-first, Bob has to decrypt the message before he can check the authentication. This is more work for bogus messages. The situation in which this is relevant is when Eve sends Bob a very large number of bogus messages. With encrypt-first, Bob saves the work of decrypting them, which reduces the CPU load. Under some very special circumstances, this makes a denial-of-service (DOS) attack a little bit harder, though only by a factor of at most approximately two. Further, in many real-life situations, a more effective DOS attack works by saturating the communication channel rather than by bogging down Bob's CPU.

The main argument for encrypt-and-authenticate is that the encryption and authentication processes can happen in parallel. This can increase performance in some situations. Under the encrypt-and-authenticate composition approach, an attacker can view the MAC tag of the initial message itself. This is because the MAC is not encrypted (unlike the authenticate-then-encrypt approach) and because the MAC is not of an encrypted value (unlike the encrypt-then-authenticate approach). MACs are designed to protect authenticity, not privacy. This means the MAC in an encrypt-and-authenticate approach could leak private information about the underlying message, thereby compromising the privacy of the secure channel. As with authenticate-first, there are also some underlying encryption schemes that are insecure when used in an encrypt-and-authenticate approach. With judicious choice of the underlying MAC and the underlying encryption scheme, and by including additional data like the nonce in the input to the MAC, the encrypt-and-authenticate approach can be secure.

There are two main arguments in favor of authenticating first. In the encrypt-first configuration, the MAC input and MAC value are both visible to Eve. In the authenticate-first configuration, Eve only gets to see the ciphertext and the encrypted MAC value; the MAC input (i.e., the plaintext) and actual MAC value are hidden. This makes it much harder to attack the MAC than in the encrypt-first situation. The real choice is which of the two functions is applied last. If encryption is applied last, then Eve gets to attack the encryption function without further hindrance. If the authentication function is applied last, she gets to attack the authentication function without further hindrance. In many cases, one can argue that authentication is more important than encryption. We therefore prefer to expose the encryption function to Eve's direct attacks, and protect the MAC as much as possible. Of course, these issues are moot if both the underlying encryption scheme and MAC are secure, but we take an approach of professional paranoia and would like a secure channel with some robustness even if we do not assume that.

When might authentication be more important than encryption? Imagine a situation in which a secure channel is being used. Consider how much damage Eve could do if she could read all the traffic. Then think about how much damage Eve could do if she could modify the data being communicated. In most situations, modifying data is a devastating attack, and does more damage than merely reading it.

The second argument in favor of authenticating first is the Horton Principle. You should authenticate what you mean, not what you say. Authenticating the ciphertext breaks this rule, and creates a vulnerability. The danger is that Bob might check that the ciphertext is correctly authenticated, but then decrypt the ciphertext with a different key than what Alice used to encrypt the message. Bob will get a different plaintext than Alice sent, even though the authentication checked out. This shouldn't happen, but it can. There is a particular (unusual) configuration of IPsec that has this problem [51]. This vulnerability has to be fixed. You could include the encryption key in the additional data being authenticated, but we don't like using keys for anything but their normal use. It introduces extra risks; you don't want a faulty MAC function leaking information about the encryption key. The standard solution is to derive both the encryption key and the authentication key for the secure channel from a single secure channel key, as we do in Section 7.4.1. This removes the vulnerability, but it also introduces a cross-dependency. The authentication suddenly depends on the key derivation system.

You can argue for hours which order of operations is better. All orders can result in good systems, all can result in bad systems. Each has its own advantages and disadvantages. We choose to authenticate first for the rest of this chapter. We like the simplicity of authenticate-first, and its security under our practical paranoia model.

The solution consists of three components: message numbering, authentication, and encryption. We will walk through the design of one possible secure channel and, in the process, illustrate how to think about the underlying issues.

7.3.1 Message Numbers

Message numbers are vital for various reasons. They provide a source for IVs for the encryption algorithm; they allow Bob to reject replayed messages without the necessity of keeping a large database; they tell Bob which messages were lost in transit; and they ensure that Bob receives the messages in their correct order. For these reasons, the message numbers must increase monotonically (i.e., later messages have larger message numbers) and must be unique (no two messages may have the same message number).

Assigning message numbers is easy. Alice numbers the first message as 1, the second message as 2, etc. Bob keeps track of the message number of the last message he received. Any new message must have a message number that is larger than the message number of the previous message. By accepting only increasing message numbers, Bob ensures that Eve cannot replay him an old message.

For our secure channel design, we will use a 32-bit number for the message number. The first message is numbered 1. The number of messages is limited to 232 − 1. If the message number overflows, then Alice will have to stop using this key and rerun the key negotiation protocol to generate a new key. The message number must be unique, so we cannot allow it to wrap back to 0.

We can now discuss the details of the secure channel. Again, we stress that this is not the only way to implement a secure channel, but instead an opportunity to dive into the challenges and nuances with building a secure channel. For convenience, we've defined the channel to be bi-directional, so the same key can be used for both directions. If we define the channel to be one-directional, then you can bet that somebody will use the same key for both directions and utterly destroy the security. Making the channel bi-directional reduces this risk. On the flip side, if you're using a secure channel defined by someone else, be extra careful not to use the same key in both directions.

We describe all our algorithms using a pseudocode notation that should be easy to read for anyone familiar with the conventions of programming. Program blocks are denoted both by the indent level and by paired key words such as if/fi and do/od.

7.4.1 Initialization

The first algorithm we show is the initialization of the channel data. This has two main functions: setting up the keys and setting up the message numbers. We derive four subsidiary keys from the channel key: an encryption key and an authentication key to send messages from Alice to Bob, and an encryption key and an authentication key to send messages from Bob to Alice.

There is also a function to wipe the state information . We will not specify this in any detail. All it does is wipe the memory that used to store information. It is vital that this information be wiped because the keys were stored in that area. On many systems, just deallocating the memory doesn't necessarily wipe it, so you must erase when you are done with it.

7.4.2 Sending a Message

We now turn to the processing required to send a message. This algorithm takes the session state, a message to send, and additional data to be authenticated, and produces the encrypted and authenticated message ready for transmission. The recipient must have the same additional data at hand to check the authentication.

Given our earlier discussions, this is relatively straightforward. We check for exhaustion of the message counter. We cannot stress enough how important this check is. If the counter ever wraps, the entire security falls apart—and this is a mistake we've seen often. The authentication and encryption are as described in our previous discussion. Finally, we send i with the encrypted and authenticated message so that the receiver will know the message number.

Note that the session state is updated because the MSGCNTSEND value is modified. Again, this is vital, as the message number must be unique. In fact, almost everything in these algorithms is vital for the security.

Our secure channel uses CTR mode for encryption. If the encryption scheme requires padding, be sure to verify the contents of the padding when you decrypt.

7.4.3 Receiving a Message

The receiving algorithm requires the encrypted and authenticated message that SENDMESSAGE produced and the same additional data x to be authenticated. We assume the receiver knows x through some out-of-band means. For example, if x contains the protocol version number, then surely Bob must know this if he's participating in the protocol.

We have used the canonical order for the operations here. You could put the check on the message number before the decryption, but then this function would report the wrong error if i were mangled during transmission. Instead of notifying the caller that the message was mangled, it would notify the caller that the message is in the wrong order. As the caller might wish to handle the two situations differently, this routine should not give the wrong information. The reason some people like to put the check earlier is that it allows false messages to be discarded more quickly. We don't consider this to be of great importance; if you receive so many false packets that the speed of discarding them becomes significant, you already have much bigger problems.

There is one very important issue for the receiver. The RECEIVEMESSAGE function may not release any information about the key stream or the plaintext message until the authentication has been verified. If the authentication fails, a failure indication is returned, but neither the key stream nor the plaintext may be revealed. An actual implementation should wipe the memory areas used to store these elements. So why is this so important? The plaintext message reveals the key stream, because it is assumed that every attacker knows the ciphertext. The danger is that the attacker will send a fake message (with an incorrect MAC value) but still learn the key stream from the data released by the receiver. This is the paranoia model at work again. Any data released or leaked by this routine is automatically assumed to end up in possession of the attacker. By destroying the data held in k and m before returning with an error, this routine ensures that this data can never be leaked.

7.4.4 Message Order

Like the transmitter, the receiver updates the state by modifying the MSGCNTREC variable. The receiver ensures that the message numbers of the messages it accepts are strictly increasing. This certainly ensures that no message is accepted twice, but if the stream of messages is reordered during transmission, otherwise perfectly valid messages will be lost.

It is relatively easy to fix this, but at a cost. If you let the receiver accept messages out of order, then the application that uses the secure channel must be able to handle these out-of-order messages. Many applications cannot deal with this. Some applications are designed to handle it, but have subtle bugs (often security-relevant) when messages are reordered. In most situations, we prefer to fix the underlying transport layer and prevent accidental reordering of messages, so that the secure channel does not have to deal with this problem.

There is one situation that we know of in which the receiver allows messages to arrive out of order, and for a very good reason. This is IPsec, the IP security protocol [73] that encrypts and authenticates IP packets. As IP packets can be reordered during transport, and as all applications that use IP are very well aware of this property, IPsec maintains a replay protection window rather than just remembering the counter value of the last received message. If c is the message number of the last received message, then IPsec maintains a bitmap for the message numbers c − 31, c − 30, c − 29, …, c − 1, c. Each bit indicates whether a message with the corresponding message number has been received. Messages with numbers smaller than c − 31 are always refused. Messages in the range c − 31 to c − 1 are only accepted if the corresponding bit is 0 (and this bit is then set, of course). If the new message has a message number larger than c, then c is updated and the bitmap is shifted to maintain the invariant. Such a bitmap construction allows some limited reordering of the messages without adding too much state to the receiver.

Another option is to terminate the communications if a message is dropped. This is particularly suited when the secure channel runs on top of a reliable transport like TCP. Unless there is malicious activity, messages should arrive in order and without any loss. So if a message is dropped or arrives out of order, terminate the communications.

The secure channel definition we have given is not always practical; especially when implementing a secure channel in embedded hardware, it becomes relatively costly to implement SHA-256. As an alternative, there has recently been interest in creating dedicated block cipher modes for providing both privacy and authenticity at the same time.

These dedicated privacy-and-authenticity block cipher modes take a single key as input, just like CBC mode and CBC-MAC. These modes generally also take a message as input, additional data to be authenticated, and a nonce. These modes are not as simple as just using CBC mode and CBC-MAC with the same key, however. Using the same key for both a regular encryption mode and a regular MAC can lead to security problems.

The most well-known initial combined mode is OCB [109]. This mode is very efficient. Each plaintext block can be processed in parallel, which is attractive for high-speed hardware. The existence of patents has limited OCB's adoption.

Because of the patent issues surrounding OCB, and because of the need for a dedicated, single-key block cipher mode for encryption and authentication, Doug Whiting, Russ Housley, and Niels developed a mode called CCM [126]. It is a combination of CTR mode encryption and CBC-MAC authentication, but with care taken to allow for the use of the same key with both CTR mode and CBC-MAC. Compared to OCB, it requires twice as many computations to encrypt and authenticate a message, but as far as we know there are no patent issues at all with CCM. The designers know of no patents that cover CCM, and they have not applied, nor will they apply, for a patent. Jakob Jonsson provided a proof of security for CCM [65]. NIST has since standardized CCM as a block cipher mode [41].

To improve on the efficiency of CCM, Doug Whiting, John Viega, and Yoshi developed another mode called CWC [80]. CWC builds on CTR mode to provide encryption. Under the hood, CWC uses universal hashing to achieve authenticity [125]. We mentioned but did not discuss universal hashing in Chapter 6 when we introduced GMAC [43]. CWC's use of universal hashing makes CWC fully parallelizable, like OCB, but avoids the patents surrounding OCB. David McGrew and John Viega improved on CWC with a more efficient universal hashing function for hardware implementations. Their improved mode is called GCM [43]. NIST has now standardized GCM as a block cipher mode.

Just like our secure channel from earlier in this chapter, OCB, CCM, CWC, and GCM can all take two strings as input—a message to be sent and additional data to be authenticated. The GMAC message authentication scheme is actually just GCM mode where the main message is the empty string.

These modes are all reasonable choices. Because they are standardized and unencumbered by patents, we prefer CCM and GCM. Unfortunately, GCM's authentication capability shares the limitations of GMAC that we discussed in Section 6.3. Therefore, although it is possible to reduce the size of the authenticator for GCM from 128 bits to something less, we recommend not doing so. Our recommendation is to only use GCM with the full 128-bit authentication tag.

Another important point: OCB, CCM, CWC, GCM, and similar modes do not by themselves provide the full secure channel. They provide the encryption/authentication functionality, and require a key and a unique nonce for each packet. We discussed the risks of relying on external systems to correctly generate nonces in Section 4.7. It is easy, however, to adapt our secure channel algorithms to use one of these block cipher modes rather than the separate MAC and encryption functions. Instead of the four subsidiary keys generated in INITIALIZESECURECHANNEL, you will need two keys, one for each direction of traffic. The nonce can be constructed by padding the message number to the correct size.

Stepping back, we observe that the secure channel is one of the most useful applications of cryptography, and it is used in almost all cryptographic systems. You can construct a secure channel from good encryption and authentication primitives, and there are also dedicated privacy-and-authenticity block cipher modes that you can build upon. There are many details to pay attention to, and all the details must of course be done correctly. A separate challenge, which we will consider later, is establishing a symmetric key.

Exercise 7.1 In our design of a secure channel, we said that the message numbers must not repeat. What bad things can happen if the message numbers do repeat?

Exercise 7.2 Modify the algorithms for the secure channel in this chapter to use the encrypt-then-authenticate order for encryption and authentication.

Exercise 7.3 Modify the algorithms for the secure channel in this chapter to use the a dedicated, single-key mode for providing both encryption and authentication. You can use OCB, CCM, CWC, or GCM as a black box.

Exercise 7.4 Compare and contrast the advantages and disadvantages among the different orders of applying encryption and authentication when creating a secure channel.

Exercise 7.5 Find a new product or system that uses (or should use) a secure channel. This might be the same product or system you analyzed for Exercise 1.8. Conduct a security review of that product or system as described in Section 1.12, this time focusing on the security and privacy issues surrounding the secure channel.

Exercise 7.6 Suppose Alice and Bob are communicating using the secure channel described in this chapter. Eve is eavesdropping on the communications. What types of traffic analysis information could Eve learn by eavesdropping on the encrypted channel? Describe a situation in which information exposure via traffic analysis is a serious privacy problem.