# Why have 4th and 5th steps in Needham-Schroeder Protocol?

Why have 4th and 5th steps in Needham-Schroeder Protocol? It is said "These steps assure B that the original message it received (step 3) was not a replay.". But what is a replay here? And I don't actually get what those 4th and 5th steps do. Send some nonce?

Here is the protocol outline I am looking at (source)

$$\begin{array}{ccl} 1.& A \to S \colon& A,B,N_a \\ 2.& S \to A \colon& \left\{ N_a,B,K_{ab},\{K_{ab},A\}_{K_{bs}} \right\}_{K_{as}} \\ 3.& A \to B \colon& \{K_{ab},A\}_{K_{bs}} \\ 4.& B \to A \colon& \{N_{b}\}_{K_{ab}} \\ 5.& A \to B \colon& \{N_{b}-1\}_{K_{ab}} \end{array}$$ Where $N_a,N_b$ are nonces.

• Can you tell us what protocol diagram you are looking at so we can all be on the same page? – mikeazo Nov 13 '13 at 18:29
• @mikeazo Sorry, here: cs.utexas.edu/~byoung/cs361/lecture60.pdf – evening Nov 14 '13 at 12:13

Notice that $N_b$ has not been seen until step 4, so it is generated by B. In step 5, A sends $N_b-1$ back to B. This proves to B that A knows $K_{ab}$ otherwise A could not have recovered $N_b$.
This is done to prevent A from replaying the message in step 3 and therefore authenticating. For example, suppose Eve sees Alice send the message in step 3 $\{K_{ab},A\}$.
B receives this message, uses $K_{bs}$ to decrypt it and sees the identifier $A$ and therefore believes that Eve is A.
I think where most people get confused with Needham-Schroeder is that they assume that after step 3, Eve does not know $K_{ab}$ (which is correct) and therefore if B starts encrypting further session information with $K_{ab}$, Eve will not be able to decrypt those message (which is also correct). The problem is there is no guarantee that the rest of the session is encrypted. Needham-Schroeder places no such requirement on users of Needham-Schroeder (as it is simply an authentication protocol and the security of it should not be tied to how an application uses resulting keying material).
• B could do that, but that is application specific. There are tons of applications out there were all we need is authentication with no further encrypted communications (e.g., electronic system where I prove to you who I am and you open a door for me). $N_b-1$ is the number $N_b$ minus one. If the random nonce $N_b$ is chosen to be $5$, A would encrypt and send $4$. If A can't decrypt, A can't get $N_b$ so A can't send $N_b-1$. – mikeazo Nov 14 '13 at 16:28