Yahalom (protocol)

Yahalom is an authentication and secure key-sharing protocol designed for use on an insecure network such as the Internet. Yahalom uses a trusted arbitrator to distribute a shared key between two people. This protocol can be considered as an improved version of Wide Mouth Frog protocol (with additional protection against man-in-the-middle attack), but less secure than the Needham–Schroeder protocol.

If Alice (A) initiates the communication to Bob (B) with S is a server trusted by both parties, the protocol can be specified as follows using security protocol notation:

• A and B are identities of Alice and Bob respectively
• ${\displaystyle K_{AS}}$ is a symmetric key known only to A and S
• ${\displaystyle K_{BS}}$ is a symmetric key known only to B and S
• ${\displaystyle N_{A}}$ and ${\displaystyle N_{B}}$ are nonces generated by A and B respectively
• ${\displaystyle K_{AB}}$ is a symmetric, generated key, which will be the session key of the session between A and B

${\displaystyle A\rightarrow B:A,N_{A}}$

Alice sends a message to Bob requesting communication.

${\displaystyle B\rightarrow S:B,\{A,N_{A},N_{B}\}_{K_{BS}}}$

Bob sends a message to the Server encrypted under ${\displaystyle K_{BS}}$.

${\displaystyle S\rightarrow A:\{B,K_{AB},N_{A},N_{B}\}_{K_{AS}},\{A,K_{AB}\}_{K_{BS}}}$

The Server sends to Alice a message containing the generated session key ${\displaystyle K_{AB}}$ and a message to be forwarded to Bob.

${\displaystyle A\rightarrow B:\{A,K_{AB}\}_{K_{BS}},\{N_{B}\}_{K_{AB}}}$

Alice forwards the message to Bob and verifies ${\displaystyle N_{A}}$ has not changed. Bob will verify ${\displaystyle N_{B}}$ has not changed when he receives the message.

Burrows􏰂, Abadi􏰂 and Needham proposed a variant of this protocol in their 1989 paper as follows:¹

${\displaystyle A\rightarrow B:A,N_{A}}$
${\displaystyle B\rightarrow S:B,N_{B},\{A,N_{A}\}_{K_{BS}}}$
${\displaystyle S\rightarrow A:N_{B},\{B,K_{AB},N_{A}\}_{K_{AS}},\{A,K_{AB},N_{B}\}_{K_{BS}}}$
${\displaystyle A\rightarrow B:\{A,K_{AB},N_{B}\}_{K_{BS}},\{N_{B}\}_{K_{AB}}}$

In 1994, Paul Syverson demonstrated two attacks on this protocol.¹