Authentication Protocols: Mutual Authentication and the Replay Problem

The rule that follows and is worth carrying: a connection-oriented protocol can use challenge and response; a connectionless or store-and-forward one must use timestamps, because there is nobody on the other end to challenge.

Needham and Schroeder, and Denning's attack

# The Needham and Schroeder authentication protocol, and Denning's replay.

import hashlib

class Party:
    def __init__(self, name, master):
        self.name = name
        self.master = master

def enc(key, data):
    """Stand-in for a real cipher: a keyed transformation that is reversible."""
    stream = hashlib.sha256(key).digest() * ((len(data) // 32) + 1)
    return bytes(a ^ b for a, b in zip(data, stream))

dec = enc                       # exclusive-or is its own inverse

KA, KB = b"Asha's master key ..............", b"Bharat's master key ..........."
print("THE PROTOCOL AS NEEDHAM AND SCHROEDER SET IT OUT")
print()

# Message 1: Asha -> KDC
n1 = 12345
print("1. Asha to the centre, in clear:")
print("     Asha, Bharat, nonce N1 = %d" % n1)

# Message 2: KDC -> Asha, encrypted under KA
session = b"session key 2026-09-30 aaaaaaaa"
ticket = enc(KB, session + b"|Asha")
reply = enc(KA, session + b"|N1=" + str(n1).encode() + b"|Bharat|TICKET")
print()
print("2. The centre to Asha, ALL encrypted under Asha's master key:")
print("     the session key Ks, the nonce N1 back, Bharat's name, and a")
print("     TICKET for Bharat which is Ks and Asha's name encrypted under")
print("     Bharat's master key, and which Asha cannot read.")
print("     Asha decrypts and finds N1 =", dec(KA, reply).split(b"|N1=")[1].split(b"|")[0].decode())
print("     so the reply is fresh and was not substituted.")

print()
print("3. Asha to Bharat: the ticket, unchanged.")
opened = dec(KB, ticket)
print("     Bharat decrypts it with his own master key and finds")
print("       the session key, and the name", opened.split(b"|")[1].decode())

n2 = 98765
print()
print("4. Bharat to Asha, encrypted under the SESSION key: nonce N2 =", n2)
print("5. Asha to Bharat, encrypted under the session key: f(N2) =", n2 - 1)
print()
print("   Messages 4 and 5 prove Asha is PRESENT and holds Ks. Without them a")
print("   replay of message 3 alone would be accepted.")
print()

print("DENNING'S ATTACK, and why messages 4 and 5 are not enough.")
print()
print("   Suppose an attacker recorded an old run and has since recovered that")
print("   run's session key, by any means: it was short, or it leaked, or the")
print("   cipher of the day was broken. The attacker now:")
print("     replays the OLD message 3, the old ticket, to Bharat;")
print("     receives message 4, a fresh nonce, encrypted under the OLD key;")
print("     they HOLD that key, so they answer message 5 correctly.")
old_session = b"session key 2020-01-01 bbbbbbbb"
old_ticket = enc(KB, old_session + b"|Asha")
attacker_n2 = 55555
challenge = enc(old_session, str(attacker_n2).encode())
answer = enc(old_session, str(attacker_n2 - 1).encode())
print()
print("   the attacker's answer to Bharat's challenge %d is %s"
      % (attacker_n2, dec(old_session, answer).decode()))
print("   which is exactly what Bharat expects:", dec(old_session, answer).decode()
      == str(attacker_n2 - 1))
print()
print("   Bharat now believes he is talking to Asha, using a key the attacker")
print("   holds. NOTHING in messages 3, 4 and 5 carries a time, so Bharat has")
print("   no way to know the ticket is years old.")
print()
print("THE FIX, from Denning: put a TIMESTAMP in the ticket and in message 2,")
print("and have each party reject anything outside a window. Then an old ticket")
print("is recognisable as old. The cost is that every clock must be synchronised,")
print("and a party whose clock is wrong is either locked out or exposed, which")
print("is the trade Kerberos makes and which its own chapters take up.")

Read five things out of that run.

Message 2 is the interesting one. It contains the session key, the nonce back, so Asha knows the reply is fresh; the original request, so she knows it was not altered in flight; and the ticket, which is the same session key and Asha's name encrypted under Bharat's master key. Asha cannot read the ticket and cannot alter it, which is exactly the property wanted.

Messages 4 and 5 exist to prove liveness. Bharat sends a fresh nonce under the session key and Asha returns a function of it, conventionally one less. An attacker replaying message 3 alone could not answer.

But an attacker who holds the old session key can. The run does it: the old ticket is replayed, Bharat's fresh challenge arrives encrypted under the old key, and the attacker, holding that key, returns the expected value. The program prints it and checks it. Bharat is now talking to an attacker and believes it is Asha.

Nothing in messages 3, 4 and 5 carries a time. Bharat has no way to know the ticket is years old. The protocol has a freshness check and is still replayable, because the freshness check proves only that somebody holding the key is present now, and the attacker is.

The fix is a timestamp, in the ticket and in message 2, with each party rejecting anything outside a window. That is Denning's proposal and it is what Kerberos adopts, at the price of synchronised clocks.

What the attacker needed, and what they did not

Worth stating because students overestimate the attack.

They needed a recording of an old run, and the old session key. The key might have been recovered because it was short, because the cipher of that era was later broken, because it was stored somewhere, or simply because the session ended and nobody thought a spent key mattered.

They did not need Asha's or Bharat's master key, any cryptanalysis of the current cipher, or any access to the key distribution centre.

That is the shape of most real protocol attacks: not breaking the cryptography, but using a piece of it after it was assumed to be worthless. A session key that is "finished" is still a live secret as long as any protocol will accept a message encrypted under it.

Distinctions that carry marks

What beginners get wrong here

Saying a nonce stops replay. It stops the replay of a message that does not contain the nonce. It does not stop an attacker who can answer the challenge, which is exactly what Denning's attack does.

Thinking the attack breaks the cipher. It breaks nothing. It uses an old session key that the protocol is still willing to accept.

Forgetting why messages 4 and 5 are there. They prove the requester is live. An answer that lists five messages without saying what the last two are for has described the protocol without explaining it.

Saying timestamps solve replay. They solve it at the cost of synchronised clocks, and the clock service then becomes security critical. That trade is Kerberos's, and it is worth naming as a trade.

Using sequence numbers for authentication. They require each party to remember state for every other party, which does not scale, which is why they are used within a session and not to establish one.

Quick revision

• Mutual authentication convinces both parties; one-way convinces the receiver only.
• The central problem is replay. Four forms: simple, logged repetition, undetectable repetition when the original was suppressed, and backward replay to the sender.
• Three countermeasures: sequence numbers (state per pair, so not used to establish a session), timestamps (need synchronised clocks), challenge and response with a nonce (needs a round trip, so no good for electronic mail).
• Needham and Schroeder, five messages: request with a nonce; the centre's reply under the requester's master key carrying the session key, the nonce, the request and a ticket; the ticket forwarded; a nonce challenge under the session key; and the response.
• Messages 4 and 5 exist to prove the requester is live.
• Denning's attack: an attacker with an old recording and the old session key replays the ticket, receives the challenge under that key, and answers it. Nothing in the protocol carries a time, so the receiver cannot tell.
• The attacker needs no master key and no cryptanalysis; only an expired session key the protocol will still accept.
• The fix is a timestamp in the ticket, which is what Kerberos does.

Test yourself

1. What is the central problem an authentication protocol must solve? Replay: an opponent copying a valid message and resending it later, so that the receiver is convinced of the presence of a party who is not actually there. Every countermeasure in the topic is a way of establishing that a message is fresh.

2. Name the four forms of replay. Simple replay, in which a copied message is resent later; repetition that can be logged, a replay within the valid time window; repetition that cannot be detected, where the original message was suppressed so only the replay arrives; and backward replay without modification, in which the message is replayed back to its own sender.

3. Give the three countermeasures and the cost of each. Sequence numbers, which require each party to keep state for every other party and so are not used to establish a session. Timestamps, which require the parties' clocks to be synchronised, making the clock service security critical. Challenge and response with a nonce, which requires a round trip and therefore cannot be used for store-and-forward applications such as electronic mail.

4. Describe the five messages of the Needham and Schroeder protocol and say what messages 4 and 5 achieve. The requester asks the centre for a key to talk to a named party, including a nonce. The centre replies, under the requester's master key, with the session key, the nonce, the original request and a ticket containing the session key and the requester's name encrypted under the other party's master key. The requester forwards the ticket. The other party sends a nonce encrypted under the session key. The requester returns a function of that nonce. Messages 4 and 5 prove that the requester is present now and holds the session key, rather than being a replay of message 3 alone.

5. Describe Denning's attack and say why messages 4 and 5 do not prevent it. An attacker who has recorded an old run and has since obtained that run's session key replays the old ticket. The receiving party, having no way to tell the ticket's age, accepts it and issues a fresh nonce encrypted under that old session key. Because the attacker holds the key, they decrypt the nonce and return the correct response. Messages 4 and 5 prove only that somebody holding the key is present, and the attacker is; they say nothing about the key being current.

6. What did the attacker need, and what did they not need? They needed a recording of an old exchange and the session key from it, which might have been recovered because it was short, because the cipher was later broken, or because it was stored and forgotten. They needed no master key, no access to the key distribution centre and no cryptanalysis of the cipher in current use.

7. What is the fix, and what does it cost? Include a timestamp in the ticket and in the centre's reply, and have each party reject anything outside an acceptable window, so that an old ticket is recognisable as old. The cost is that every party's clock must be synchronised and kept so, which makes the time service itself security critical; a party whose clock is wrong is either locked out or exposed. Kerberos makes exactly this trade.