Authentication is the process of proving one's identity to someone else. As humans, we authenticate each other in many ways: we recognize each others' faces when we meet; we recognize each others' voices on the telephone; we are authenticated by the customs official who checks us against the picture on our passport.
In this section we consider how one party can authenticate another party when the two are communicating over a network. We focus here on authenticating a "live" party, at the point in time when communication is actually occurring. We will see that this is a subtly different problem from proving that a message received at some point in the past (e.g., that may have been archived) did indeed come from that claimed sender. This latter problem is referred to as the digital signature problem, which we explore in section 7.4.
When performing authentication over the network, the communicating parties can not rely on biometric information, such as a visual appearance or a voiceprint. Indeed, we will see in our later case studies that it is often network elements such as routers and client/server processes that must authenticate each other. Here, authentication must be done solely on the basis of messages and data exchanged as part of an authentication protocol. Typically, an authentication protocol would run before the two communicating parties run some other protocol (e.g., a reliable data transfer protocol, a routing table exchange protocol, or an email protocol). The authentication protocol first establishes the identities of the parties to each others' satisfaction; only after authentication do the parties get down to the work at hand.
As in the case of our development of a reliable data transfer protocol, rdt, in Chapter 3, we will find it instructive here to develop various versions of an authentication protocol, which we will call ap ("authentication protocol"), and poke holes (i.e., find security flaws) in each version as we proceed. Let's begin by assuming that Alice needs to authenticate herself to Bob.
Perhaps the simplest authentication protocol we can imagine is one where Alice simply sends a message to Bob saying she is Alice. This protocol is shown in Figure 7.3-1. The flaw here is obvious – there is no way for Bob to actually know that the person sending the message, "I am Alice" is indeed Alice. For example, Trudy (the intruder) could just as well send such a message.
Figure 7.3-1: Protocol ap1.0 and a failure scenario.
In the case that Alice has a well-known network address (e.g., IP address) from which she always communicates, Bob could attempt to authenticate Alice by verifying that the source address on the IP datagram carrying the authentication message matches Alice's well-known address. If so, then Alice would be authenticated. This might stop a very network-naive intruder from impersonating Alice. But it wouldn't stop the determined student studying this book, or many others!
Figure 7.3-2: Protocol ap2.0 and a failure scenario.
Given that we have now studied both the network and data link layers, we know that it is not that hard (e.g., if one had access to the operating system code and could build one's own operating system kernel, as is the case with Linux and several other freely available operating systems) to create an IP datagram, put whatever IP source address we want (e.g., including Alice's well-known IP address) into the IP datagram and send the datagram over the link layer protocol to the first hop router. From then on, the incorrectly-source-addressed datagram would be dutifully forwarded to Bob. This approach is a form of IP spoofing, a well-known security attack technique [Cert 96]. IP spoofing can be avoided if a router is configured to refuse IP datagrams that do not have a given source address. For example, Trudy's first hop router could be configured to only forward datagrams containing Trudy's IP source address. However, this capability is not universally deployed or enforced. Bob would thus be foolish to assume that Trudy's network manager (who might be Trudy herself!) had configured Trudy's first hop router to only forward appropriately-addressed datagrams.
One classical approach to authentication is to use a secret password. We have PIN numbers to identify ourselves to automatic teller machines and login passwords for operating systems. The password is a shared secret between the authenticator and the person being authenticated. We saw in section 2.2.5 that HTTP uses a password-based authentication scheme. Telnet and FTP use password authentication as well. In protocol ap3.0, Alice thus sends her secret password to Bob, as shown in Figure 7.3-3.
Figure 7.3-3: Protocol ap3.0 and a failure scenario.
The security flaw here is clear. If Trudy eavesdrops on Alice's communication, then she can learn Alice's password. Lest you think this is unlikely, consider the fact that when one Telnet's to another machine and logs in, the login password is sent unencrypted to the Telnet server . Someone connected to the Telnet client or server's LAN can possibly "sniff" (read and store) all packets transmitted on the LAN and thus steal the login password. In fact, this is a well-known approach for stealing passwords (see, e.g., [Jimenez 1997]. Such a threat is obviously very real, so ap3.0 clearly won't do.
Having just studied the previous section on cryptography, our next idea for fixing ap3.0 is naturally to use encryption. By encrypting the password, Trudy will not be able to learn Alice's password! If we assume that Alice and Bob share a symmetric secret key, KA-B, then Alice can encrypt the password, send her identification message, "I am Alice," and her encrypted password to Bob. Bob then decrypts the password and, assuming the password is correct, authenticates Alice. Bob feels comfortable in authenticating Alice since not only does Alice know the password, but she also knows the shared secret key value needed to encrypt the password. Let's call this protocol ap3.1.
While it is true that ap3.1 prevents Trudy from learning Alice's password, the use of cryptography here does not solve the authentication problem! Bob is again subject to a so-called playback attack: Trudy needs only eavesdrop on Alice's communication, record the encrypted version of the password, and then later play back the encrypted version of the password to Bob to pretend that she is Alice. The use of an encrypted password doesn't make the situation manifestly different from that in Figure 7.3-3.
The problem with ap3.1 is that the same password is used over and over again. One way to solve this problem would be to use a different password each time. Alice and Bob could agree on a sequence of passwords (or on an algorithm for generating passwords) and use each password only once, in sequence. This idea is used in the S/KEY system [RFC 1760], adopting an approach due to Lamport [Lamport 81] for generating a sequence of passwords.
Rather than just stop here with this solution, however, let us consider a more general approach for combating the playback attack. The failure scenario in Figure 7.3-3 resulted from the fact that Bob could not distinguish between the original authentication of Alice and the later playback of Alice's original authentication. That is, Bob could not tell if Alice was "live" (i.e., was currently really on the other end of the connection) or whether the messages he was receiving were a recorded playback of a previous authentication of Alice. The very (very!) observant reader will recall that the 3-way TCP handshake protocol needed to address the same problem - the server side of a TCP connection did not want to accept a connection if the received SYN segment was an old copy (retransmission) of a SYN segment from an earlier connection. How did the TCP server side solve the problem of determining if the client was really "live"? It chose an initial sequence number (which had not been used in a very long time), sent that number to the client, and then waited for the client to respond back with an ACK segment containing that number. We can adopt the same idea here for authentication purposes.
A nonce is a number that a protocol will only ever use once-in-a-lifetime. That is, once a protocol uses a nonce, it will never use that number again. Our ap4.0 protocol uses a nonce as follows:
Alice sends the message, "I am Alice," to Bob
Bob chooses a nonce, R, and sends it to Alice
Alice encrypts the nonce using Alice and Bob's symmetric secret key, KA-B. , and sends the encrypted nonce, KA-B (R) back to Bob. As in protocol ap3.1, it is the fact that Alice knows KA-B and uses it to encrypt a value that lets Bob know that the message he receives was generated by Alice. The nonce is used to insure that Alice is "live."
Bob decrypts the received message. If the decrypted nonce equals the nonce he sent Alice, then Alice is authenticated.
Protocol ap4.0 is illustrated in Figure 7.3-4. By using the once-in-a-lifetime value, R, and then checking the returned value, KA-B (R), Bob can be sure that both Alice is who she says she is (since she knows the secret key value needed to encrypt R) and is "live" (since she has encrypted the nonce, R, that Bob just created).
Figure 7.3-4: Protocol ap 4.0: no failure scenario.
The use of a nonce and symmetric key cryptography formed the basis of our successful authentication protocol, ap4.0. A natural question is whether we can use a nonce and public key cryptography (rather than symmetric key cryptography) to solve the authentication problem. The use of a public key approach would obviate a difficulty in any shared key system - worrying about how the two parties learn the secret shared key value in the first place. A protocol that uses public key cryptography in a manner analogous to the use of symmetric key cryptography in protocol ap4.0 is protocol ap5.0:
Alice sends the message,
I am Alice, to Bob
Bob chooses a nonce, R, and sends it to Alice. Once again, the nonce will be used to insure that Alice is "live."
Alice uses her decryption algorithm with her private key, dA, to the nonce and sends the resulting value dA(R) to Bob. Since only Alice knows her decryption key, no one except Alice can generate dA(R).
Bob applies Alice's public encryption algorithm, eA to the received message, i.e., Bob computes eA(dA(R)). Recall from our discussion of RSA public key cryptography in section 7.2 that eA(dA(R)) = R = dA(eA(R)). Thus Bob computes R and authenticates Alice.
Figure 7.3-5: Protocol ap 5.0 working correctly.
The operation of protocol ap5.0 is illustrated in Figure 7.3-5.
Is protocol ap5.0 as secure as protocol ap4.0? Both use nonces. Since ap5.0 uses public key techniques, it requires that Bob retrieve Alice's public key. This leads to an interesting scenario, shown in Figure 7.3-6, in which Trudy may be able to impersonate Alice to Bob:
Trudy sends the message, "I am Alice" to Bob
Bob chooses a nonce, R, and sends it to Alice, but the message is intercepted by Trudy.
Trudy applies her decryption algorithm with her private key, dT, to the nonce and sends the resulting value, dT(R), to Bob. To Bob, dT(R) is just a bunch of bits and he doesn't know whether the bits represent dT(R) or dA(R).
Bob must now get Alice's public key in order to apply eA to the value he just received. He sends a message to Alice asking her for eA. Trudy intercepts this message as well, and replies back to Bob with eT, that is Trudy's public key. Bob computes eT(dT(R)) = R, and thus authenticates Trudy as Alice!
From the above scenario, it is clear that protocol ap5.0 is only as "secure" as is the distribution of public keys. There are secure ways of distributing public keys, a topic we will examine soon in section 7.5.
Figure 7.3-6: A security hole in protocol ap5.0
In the scenario in Figure 7.3-6, Bob and Alice might together eventually discover that something is amiss, as Bob will claim to have interacted with Alice, but Alice knows that she has never interacted with Bob. There is an even more insidious attack that would avoid this detection. In the scenario in Figure 7.3-7, both Alice and Bob are talking to each other, but by exploiting the same hole in the authentication protocol, Trudy is able to transparently interpose herself between Alice and Bob. In particular, if Bob begins sending encrypted data to Alice using the encryption key he receives from Trudy, Trudy can recover the plaintext of the communication from Bob to Alice. At the same time, Trudy can forward Bob's data to Alice (after re-encrypting data using Alice's real public key).
Figure 7.3-7: A "man-in-the-middle" attack
Bob is happy to be sending encrypted data, and Alice is happy to be receiving data encrypted using her own public key; both are unaware of Trudy's presence. Should Bob and Alice meet later and discuss their interaction, Alice will have received exactly what Bob sent, so nothing will be detected as being amiss. This is one example of the so-called man-in-the-middle attack (more appropriately here, a "woman-in-the-middle" attack). It is also sometimes known as a bucket-brigade attack, since Trudy's passing of data between Alice and Bob resembles the passing of buckets of water along a chain of people (a so-called "bucket brigade") who are putting out a fire using a remote source of water.
Return to Table Of Contents
Copyright Keith W. Ross and James F. Kurose 1996–1999. All rights reserved.