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.

  • 6
    $\begingroup$ Can you tell us what protocol diagram you are looking at so we can all be on the same page? $\endgroup$ – mikeazo Nov 13 '13 at 18:29
  • $\begingroup$ @mikeazo Sorry, here: cs.utexas.edu/~byoung/cs361/lecture60.pdf $\endgroup$ – 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).

| improve this answer | |
  • $\begingroup$ Thanks, that's great. I understand everything until this sentence "The problem is there is no guarantee that the rest of the session is encrypted", what do you mean by that? I just don't see why it's bad that B sends encrypted info, Eve can't decrypt it anyways. Well, B just wastes time. Also, what is Nb-1? How it differs from Nb? Thanks again! $\endgroup$ – evening Nov 14 '13 at 16:16
  • 1
    $\begingroup$ 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$. $\endgroup$ – mikeazo Nov 14 '13 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.