3.1 The Needham-Schroeder Protocol

Roger Needham and Michael Schroeder of the Xerox Palo Alto Research Center published a paper in December of 1978 describing their framework for designing a secure network authentication system. The paper, entitled "Using Encryption for Authentication in Large Networks of Computers," described two different protocols that could be implemented to provide a reliable, secure authentication service for a distributed network of computers. The first protocol described in the paper uses private key encryption, and it is this protocol that forms the basis of the Kerberos network authentication protocol.

Needham and Schroeder outlined several assumptions around which they designed their protocol. One assumption, the ability for a malicious attacker to capture packets in-transit on the network, modify them, and send packets of his own design, was described by the authors as an "extreme view," yet now is regarded as a routine requirement for any secure network protocol. Designing a protocol that is resistant to these types of attacks is difficult, and I'll point out the specific design decisions that were made to thwart them as I discuss the protocol.

Other assumptions made by the authors, however, did not hold up as well in practice as they did on paper. The assumption that users' secret keys are not readily available through an exhaustive search has not held up in the hostile environments in which Kerberos operates. No matter how much education you provide users, users will continue to choose poor passwords. The Needham and Schroeder protocol, and consequently the basic Kerberos protocol, provides no protection against an offline brute force or dictionary attack against a user's secret key, as we'll see in Chapter 6.

The Needham-Schroeder protocol defines three participants in the protocol exchange: a client machine, a server that the client wishes to access, and an authentication server. The client is any machine that requests authentication; usually, it's a user's personal desktop. The server is any application server, say a mail server, which provides a service the client wishes to contact. Finally, the authentication server is a dedicated server that holds a copy of the encryption keys for all users and servers on the network (the "trusted third-party"). This should sound familiar; these are the same three players involved with the Kerberos protocol.

The concept behind the Needham-Schroeder protocol is not to authenticate the user directly by sending a password or password equivalent (such as a hash of the password) to the authentication server. Instead, the Needham-Schroeder protocol provides a mechanism to securely distribute a short-lived encryption key to two parties (a client and a server) so their communication can be secured with the encryption key. The verification of each endpoint's identity happens to be a side effect of this key exchange process. We'll see what this means as we discuss how the protocol works.

The protocol begins with the client contacting the authentication server. The client sends the authentication server a message containing the its own identity and the identity of the application server that it wishes to contact. In addition, the client includes a nonce, or a random value, with its request. We'll see why this random value is important in a moment. Figure 3-1 illustrates the information sent by the client to the authentication server.

Figure 3-1. Needham-Schroeder authentication request

The authentication server receives this information and locates the secret encryption keys it has stored for both the client and application server. It also creates a third key, the session key, which can be used to enable secure communication between the client and application server. This new key is a random key generated by the authentication server, is completely unrelated to the long-term keys of both the client and server, and is never reused.

Next comes the tricky part. In the Needham-Schroeder protocol, the authentication server never communicates directly with the application server, only the client. Therefore, the authentication server sends a reply back to the client that includes the session key and the verified identities of both parties. But how can this message be kept secure from an observer who is watching network traffic to snag these session keys as they pass through the wire? And furthermore, when the client transmits the session key and its identity to the application server, how does the application server know that the client is not lying, and that the message is authentic?

The answer involves several layers of encryption. First, a message is constructed that is intended to be viewed only by the application server. This message includes the name of the requesting client and the session key. To keep this message secure from eavesdropping and tampering by a malicious client, it is encrypted with the long-term key of the application server. Since only the application server and the authentication server know this key, an attacker cannot decrypt this message to alter the contents or steal the session key. In Kerberos terminology, this encrypted message is also known as a ticket.

The message is wrapped inside of another message, this one intended for the client. The client message also includes the name of the application server, a copy of the session key, and a copy of the nonce originally sent in the first message. The whole message is then encrypted with the client's long-term key. Once all the information has been assembled and encrypted, the authentication server sends it to the client (Figure 3-2).

Figure 3-2. Needham-Schroeder authentication reply

Needham-Schroeder, Kerberos, and Locked Boxes It's easy to get confused by all of the encryption that's happening in the Needham-Schroeder protocol (and, consequently, the Kerberos protocol). Since there are often multiple layers of encryption at work, it's useful to have a real-world analogy to relate to when discussing these protocol exchanges. A good analogy in this case is a set of locked boxes, nested inside each other. The encryption keys can be thought of as real-life keys that can open these boxes. So, in this analogy, the user's password can be translated into a physical key. Two copies of that key exist: the user has one copy, and the authentication server has another copy. The same situation exists for service keys: each application server has two identiacal keys, one held by the server itself, and the other held by the authentication servers. Boxes locked with the user's key can be unlocked with a copy of the user's key, and the same with the service key. Figure 3-3 shows the authentication server's reply to a client's authentication request. The first box (the ticket box) contains a copy of the session key and a piece of paper containing the name of the client; it is locked with the service's key. The second box (the reply box) contains the other copy of the session key and is locked with the user's key. In addition, the first box, locked with the service's key, is placed inside the second box. By placing the ticket box inside of the reply box, the authentication server ensures that only the legitimate user can unlock the reply in order to get the ticket, since only the user has a key that can open the reply.

Figure 3-3. Needham-Schroeder authentication reply represented as locked boxes

Note that the authentication server does not know whether the requesting client is actually who she claims to be. The authentication server will return this encrypted message to anyone who requests it, granted of course that the client's name exists in the authentication server's database of encryption keys. This seems to indicate that any user could masquerade as any other user when requesting authentication to an arbitrary service. However, since the message is encrypted with the client's key, it cannot be decrypted by anyone but the legitimate client.

Therefore, when the client receives this reply from the authentication server, it first decrypts the "outer" layer with its key (the client's password). The user is prompted for her password. If the password fails to decrypt the message, then the authentication request has failed.

Now all that's left is for the client to send the session key back to the application server (Figure 3-4). This is where the inner contents of the last message come into play. Now that the client has removed the first "layer" of encryption, the client can send the application server the inner portion of the message (the ticket), which consists of a copy of the session key and the client's name. Since this message is still encrypted with the application server's key, only the application server can read it, and attackers are unable to modify it.

Figure 3-4. Client sends session key to application server

At this point, it would seem that we're done; any communication that occurs henceforth that is encrypted with the session key should only be understood by the client and application server. The client knows that the application server is legitimate since only the legitimate application server can decrypt the message containing the session key (as it is encrypted with the long-term key of the application server). The application server knows that the client is legitimate because only the legitimate client could decrypt the message that contains the session key and identity of the client that was forwarded to the application server.

There is, however, one more attack that can be undertaken against this scheme, and this is where the nonce that we mentioned earlier comes into play.

Let's take a look at the situation that is presented to an attacker who wishes to impersonate a client, so that the attacker can communicate with an application server under the guise of the victim's identity. We'll assume that the attacker has the ability to read all network messages and send messages of his own crafting, but does not have knowledge of the long-term key of the client or the service (which would, obviously, allow him to impersonate the victim without any trickery).

Since all of the protocol exchanges above are simply electronic messages sent over an insecure network, the attacker manages to acquire the authentication message sent from a victim to the application server (the message that contains the session key and the identity of the client, both encrypted with the application server's key). The attacker can simply resend that message at a later time to the application server. Since the message can be decrypted by the application server, generating a valid session key and identity (of the victim), then it is accepted as legitimate and the session is authenticated. While the attacker does not know the session key, if the application server only uses the protocol to ensure authentication and does not use the session key to encipher its communications to clients, then the attacker can completely impersonate the victim.

These attacks are known as replay attacks, and the Needham-Schroeder protocol supplies a rather obvious solution to thwart these attacks: force the client to prove to the application server that it really does know the session key. To do this, the application server generates another random number, encrypts it with the session key, and sends it to the client. Then the client decrypts the number, performs an operation on it (for example, adding one to it), encrypts the new number with the session key, and sends the message back to the application server. Through this process, only authentic clients that have knowledge of the session key can send back the correct number, and observers who replay previous messages cannot (Figure 3-5).

Figure 3-5. Needham-Schroeder reply attack prevention

Here we see one of the many practical problems presented when attackers are assumed to have the ability to both read all network traffic as well as send arbitrary messages on the network. The Needham-Schroeder protocol uses an interactive challenge-response system that requires the client to prove that it knows the session key. The Kerberos protocol uses a slightly different approach—based on synchronized clocks—to thwart replay, as we'll see in the next section. We'll also discuss replay attacks in Chapter 6, with more replay attack scenarios that present themselves in some Kerberos software.