The Needham-Schroeder public key protocol

 The aim of the Needham-Schroeder protocol [NS78] is to establish mutual authentication between two users A and B . It uses public key cryptography.

We will denote with $PK_U$ and $SK_U$ the public and secret keys for a generic user U , respectively. The protocol uses nonces which are random numbers generated with the purpose of being used in a single run of the protocol. In general, $N_A$ will represent a nonce generated by A .

The protocol starts with A consulting the authentication server in order to obtain B 's public key:

$$\begin{array} {llllll} & A & \rightarrow & AS &: & A,B\end{array}$$

where the notation $\begin{array} {llllll} & Usr_1 & \rightarrow & Usr_2 &: &Msg\end{array}$

means that $Usr_1$ is sending the message Msg to $Usr_2$.

AS replies with:

$$\begin{array} {llllll} & AS & \rightarrow & A &: & SK_{AS}(PK_B,B)\end{array}$$

where $SK_{AS}$ is the authentication server secret key. So the AS is signing the public key of B and we assume that A knows the AS 's public key $PK_{AS}$, which can be used to decrypt the message.

The next step is to initiate the communication with B :

$$\begin{array} {llllll} & A & \rightarrow & B &: & PK_B(N_A,A)\end{array}$$

Since the message is encrypted with B 's public key, then only B can decrypt it. The message means that someone who claims to be A wishes to establish communication; $N_A$ is the nonce generated by A .

B decrypts the message and, similarly to A , asks for A 's public key to AS :

$$\begin{array} {llllll} & B & \rightarrow & AS &: & B,A \\ & AS & \rightarrow & B &: & SK_{AS}(PK_A,A)\end{array}$$

At this point a double handshake is needed to authenticate A and B one another:

$$\begin{array} {llllll} & B & \rightarrow & A &: & PK_A(N_A,N_B)\\ & A & \rightarrow & B &: & PK_B(N_B) \end{array}$$

In the first message B replies to A , sending the new nonce $N_B$ and the one received from A ($N_A$), both encrypted with A 's public key. When A receives the nonce $N_A$back, (s)he can conclude that is really talking with B since only B could have decrypted the message sent by A containing $N_A$.In the second message A replies to B , sending back the $N_B$ nonce. Following the same reasoning as above, B will conclude that is indeed talking with A .

The protocol is composed by seven steps, but four of them can be avoided if A and B have local caches of commonly used public key.