is the process of proving one's identity to someone else. As humans, we
authenticate each other in many ways: we recognize each other's faces when
we meet, we recognize each other's 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 (for example, 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
authentication over the network, the communicating parties cannot 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 (for example, a reliable data-transfer
protocol, a routing table exchange protocol, or an e-mail 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 (rdt) protocol, 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 (that is, 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.8. 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.
Protocol ap1.0 and a failure scenario
In the case that
Alice has a well-known network address (for example, 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! See Figure 7.9.
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 (for example, 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 (for example, 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
SYN 1996]. IP spoofing can be avoided if a router is configured to
refuse IP datagrams that do not have a given source IP address [RFC
2267]. For example, Trudy's first hop router could be configured to
forward only 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 forward only appropriately addressed
One classic 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.4 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.10.
Protocol ap3.0 and a failure scenario
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 Telnets 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, for example,
1997]). Such a threat is obviously very real, so ap3.0 clearly
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.10.
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
1981] for generating a sequence of passwords.
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.10 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
three-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 that 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
is a number that a protocol will use only 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:
is illustrated in Figure 7.11. 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).
Alice sends the
message, "I am Alice," to Bob.
Bob chooses a nonce,
R, and sends it to Alice.
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 ensure 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: 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:
The operation of
protocol ap5.0 is illustrated in Figure 7.12. 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
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
ensure that Alice is "live."
Alice uses her
private encryption algorithm with her private key, dA,
to the nonce and sends the resulting value dA(R)
to Bob. Since only Alice knows her private key, no one except Alice can
Bob applies Alice's
public encryption algorithm, eA to the received message,
that is, 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.
Protocol ap5.0 working correctly
This leads to
an interesting scenario, shown in Figure 7.13, 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)
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
(Bob might also retrieve Alice's public key from her Web site). 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!
A security hold in protocol ap5.0
From the above
scenario, it is clear that protocol ap5.0 is only as "secure" as
is the distribution of public keys. Fortunately, there are secure
ways of distributing public keys, as we will see shortly in Section 7.5.
In the scenario
in Figure 7.13, 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.14,
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).
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.