Subject: System Web Security

Topic: Authentication

Difficulty: Medium

The term Needham–Schroeder protocol can refer to one of the two key transport protocols intended for use over an insecure network, both proposed by Roger Needham and Michael Schroeder. These are:

i. The Needham–Schroeder Symmetric Key Protocol is based on a symmetric encryption algorithm. It forms the basis for the Kerberos protocol. This protocol aims to establish a session key between two parties on a network, typically to protect further communication.

ii. The Needham–Schroeder Public-Key Protocol, based on public-key cryptography. This protocol is intended to provide mutual authentication between two parties communicating on a network, but in its proposed form is insecure.

• The symmetric Protocol

  Here, Alice (A) initiates the communication to Bob (B). S is a server trusted by both parties. In the communication:

  i. A and B are identities of Alice and Bob respectively

  ii. KAS is a symmetric key known only to A and S

  iii. KBS is a symmetric key known only to B and S

  iv. NA and NB are nonces generated by A and B respectively

  v. KAB is a symmetric, generated key, which will be the session key of the session between A and B

  The protocol can be specified as follows in security protocol notation:

  A → S : A , B , NA

  Alice sends a message to the server identifying herself and Bob, telling the server she wants to communicate with Bob.

  S → A : { $N_A,K_{AB},B,{K_{AB},A } K_{BS} \} K_{AS}$

  The server generates $K_{AB}$ and sends back to Alice a copy encrypted under $K_{BS}$ for Alice to forward to Bob and also a copy for Alice. Since Alice may be requesting keys for several different people, the nonce assures Alice that the message is fresh and that the server is replying to that particular message and the inclusion of Bob's name tells Alice who she is to share this key with.

  A → B : $\{ K_{AB},A \} K_{BS}$

  Alice forwards the key to Bob who can decrypt it with the key he shares with the server, thus authenticating the data.

  $B \xrightarrow{A} \{ NB \} K_{AB}$

  Bob sends Alice a nonce encrypted under KAB to show that he has the key.

  A → B : {$N_B – 1 \} K_{AB}$

  Alice performs a simple operation on the nonce, re-encrypts it and sends it back verifying that she is still alive and that she holds the key.

• Attacks on the protocol

  The protocol is vulnerable to a replay attack (as identified by Denning and Sacco). If an attacker uses an older, compromised value for KAB, he can then replay the message

  $\{ K_{AB}, A \} K_{BS}$ to Bob, who will accept it, being unable to tell that the key is not fresh.

• Fixing the attack

  This flaw is fixed in the Kerberos protocol by the inclusion of a timestamp. It can also be fixed with the use of nonces as described below.At the beginning of the protocol:

A → B : A

Alice sends to Bob a request.

B → A : {A, $N’_B$} $K_{BS}$

Bob responds with a nonce encrypted under his key with the Server.

A → S : $A,B,N_A, \{A,N’_B \} K_{BS}$

Alice sends a message to the server identifying herself and Bob, telling the server she wants to communicate with Bob.

S → A : {$N_A,K_{AB},B,{K_{AB},A,N’_B } K_{BS} \} K_{AS}$

Note the inclusion of the nonce.

The protocol then continues as described through the final three steps as described in the original protocol above. Note that N’B is a different nonce from NB. The inclusion of this new nonce prevents the replaying of a compromised version of {KAB,A}KBS since such a message would need to be of the form $ \{ K_{AB},A,N’_B \} K_{BS}$ which the attacker can't forge since she does not have $K_{BS}$.

• The Public-Key protocol

  This assumes the use of a public-key encryption algorithm.

  Here, Alice (A) and Bob (B) use a trusted server (S) to distribute public keys on request. These keys are:

  i. $K_{PA} \ \ and \ \ K_{SA}$, respectively public and private halves of an encryption key- pair belonging to A (S stands for "secret key" here)

  ii. $K_{PB} \ \ and K_{SB}$, similar belonging to B

  iii. $K_{PS}$ and $K_{SS}$, similar belonging to S. (Note this has the property that $K_{SS}$ is used to encrypt and $K_{PS}$ to decrypt).