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.&amp; A \to S \colon&amp; A,B,N_a
\\ 2.&amp; S \to A \colon&amp;
              \left\{ N_a,B,K_{ab},\{K_{ab},A\}_{K_{bs}} \right\}_{K_{as}}
\\ 3.&amp; A \to B \colon&amp;
              \{K_{ab},A\}_{K_{bs}}
\\ 4.&amp; B \to A \colon&amp;
              \{N_{b}\}_{K_{ab}}
\\ 5.&amp; A \to B \colon&amp;
              \{N_{b}-1\}_{K_{ab}}
\end{array}
$$
  Where $N_a,N_b$ are nonces.
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).