A very simple protocol allows two agents, A and B, to establish secure communications, using a trusted authentication server, S, and synchronized clocks all around. Agents A and B are equipped with keys Kas and Kbs, respectively, for communicating securely with S. So we have assumptions:
The goal is to have
Since S believes that key(Kas, A<->S), and S sees {t, key(Kab, A<->B)}Kas,
then S concludes that A actually said {t, key(Kab, A<->B)}. (In particular, S believes that the message was not manufactured out of whole cloth by some attacker.)
Since the clocks are synchronized, we can assume
S then forwards the key to B:
Now let's suppose that we abandon the assumption that the clocks are
synchronized. In that case, S gets message 1 from A with {t,
key(Kab, A<->B)}, but it can no longer conclude
that t is fresh. It knows that A sent this message at some time
in the past (because it is encrypted with Kas)
but not that this is a recent message, so S doesn't believe that A
necessarily wants to continue to use the key
Kab. This points directly at an attack on the
protocol: An attacker who can capture messages can guess one of the
old session keys Kab. (This might take a long
time.) The attacker then replays the old {t,
key(Kab, A<->B)} message, sending it to S. If
the clocks aren't synchronized (perhaps as part of the same attack), S might
believe this old message and request that B use the old, compromised key
over again.
The original Logic of Authentication paper (linked below) contains this example and many others, including analyses of the Kerberos handshake protocol, and two versions of the Andrew RPC handshake (one of which is defective).
The Wide-Mouthed Frog Protocol
Agent A wants to intiate a secure conversation with B. It therefore invents a key, Kab, which it will use to communicate with B. A believes that this key is secure, since it made up the key itself:
B is willing to accept this key, as long as it is sure that it came from A:
Moreover, B is willing to trust S to accurately relay keys from A:
That is, if B believes that S believes that A wants to use a particular key to communicate with B, then B will trust S and believe it also.
A reads the clock, obtaining the current time t, and sends the following message:
That is, it sends its chosen session key and the current time to S, encrypted with its private authentication server key Kas.
Since S believes fresh(t) and S believes A said {t, key(Kab, A<->B)},
S believes that A actually believes that key(Kab, A<->B). (In particular, S believes that the message was not replayed by some attacker who captured it at some time in the past.)
Because message 2 is encrypted with Kbs, and B
believes key(Kbs, B<->S), B now believes that S
said {t, A, A believes key(Kab, A<->B)}.
Because the clocks are synchronized, B believes fresh(t), and so
fresh(A believes key(Kab, A<->B)). Because B
believes that S's statement is fresh, B believes that S believes that
(A believes key(Kab, A<->B)). Because B
believes that S is authoritative about what A believes, B believes
that (A believes key(Kab, A<->B)). Because B
believes that A is authoritative about session keys between A and B, B
believes key(Kab, A<->B). B can now contact A
directly, using Kab as a secret session key.Offsite Links