Why have Nonce and why encrypt everything in step 2 for Needham-Schroeder?

Question

Here is the protocol outline I am looking at (source: Foundations of Computer Security, Lecture 60: The Needham-Schroeder Protocol)

$$ \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.

My questions are:

• Why do we need nonce $N_a$ in step 1?
• Why do we encrypt everything in step 2? Surely $S$ could instead send message to $A$ like $K_{as}\{K_{ab}\} || K_{bs}\{K_{ab}\}$?
• Why $S$ can't send $K_{ab}$ to $B$?

Answer 1

As Marcin already said, nonces are for replay protection. Imagine an attacker records message 2 and later on manages to comprimise the old key. He could then impersonate $ S $ and make $ A$ and $ B $ reuse the old key by sending the recorded message to $ A $. To prevent this, the nonce is included. $ A $ remembers previously received nonces and does not accept messages if an already known nonce is included. If the attacker now tries to resend the old message again, he would fail.

Regarding the second point, I guess you want to ask if double encryption is necessary? If so, you forgot to include the IDs and the nonce :) Kerberos v4 used the same aporoach and was often critized for double encrypting the ticket to $ B $. In v5 they changed that and did your approach, so yes it is possible. Without the IDs it is not possible though, $ A $ wouldn' t know to whom the ticket has to be delivered.

Regarding the last point, of course the key has to be encrypted. If we assume $ S$ has a shared key with $ B $ too, this wouldn't be a problem however. The main reason why $ S $ forwards the ticket to Alice and not to Bob is scalability I guess. $ S $ is a central component and thus reducing the number of message exchanges it has to initiate is probably a good thing.

Answer 2

Nonces are just there to protect from replay attacks.
In Step 2, Na proves that S got Na from A. Encryption proves that you got private key. Sending Kbs{Kab} to A makes no sense because A doesn't know Kbs. S does not want to send Kab because sending keys in clear is just not a good idea (sets you up for snooping/MitM)

I am just a computer security geek, not a cryptographer. I'm just trying to see if I understand it correctly myself.