Needham–Schroeder fix by adding opponent's identity to the first message

Question

Recap: Needham–Schroeder is as follows:

1. $A \rightarrow B : \{A, N_a\}_{pk_B}$
2. $B \rightarrow A : \{N_a, N_b\}_{pk_A}$
3. $A \rightarrow B : \{N_b\}_{pk_B}$

Then, there is a MITM attack by Lowe as follows:

1. $A \rightarrow C(A) : \{A, N_a\}_{pk_C}$
2. $C(A)\rightarrow B : \{A, N_a\}_{pk_B}$
3. $B \rightarrow C(A) : \{N_a,N_b\}_{pk_A}$
4. $C(A)\rightarrow A : \{N_a,N_b\}_{pk_A}$
5. $A \rightarrow C(A) : \{N_b\}_{pk_C}$
6. $C(A)\rightarrow B : \{N_b\}_{pk_B}$

Now $C(A)$ knows both $N_a$ and $N_b$, and he can compute the session key. The solution that Lowe suggests is to put $B$'s identity to the second message:

1. $A \rightarrow B : \{A, N_a\}_{pk_B}$
2. $B \rightarrow A : \{N_a, N_b, B\}_{pk_A}$
3. $A \rightarrow B : \{N_b\}_{pk_B}$

But what happens if we put B's identity into the first message?

1. $A \rightarrow B : \{A, B, N_a\}_{pk_B}$
2. $B \rightarrow A : \{N_a, N_b\}_{pk_A}$
3. $A \rightarrow B : \{N_b\}_{pk_B}$

Is it still vulnerable to MITM attack or is it secure too?

Answer 1

It's easy to see that the man-in-the-middle attack you describe still applies to the modified protocol.

1. $A \rightarrow C(A) : \{A, C, N_a\}_{pk_C}$
2. $C(A)\rightarrow B : \{A, B, N_a\}_{pk_B}$
3. $B \rightarrow C(A) : \{N_a,N_b\}_{pk_A}$
4. $C(A)\rightarrow A : \{N_a,N_b\}_{pk_A}$
5. $A \rightarrow C(A) : \{N_b\}_{pk_C}$
6. $C(A)\rightarrow B : \{N_b\}_{pk_B}$

The idea why adding $B$'s identity to the second message might be helpful is that $B$ is telling the receiver who they are. So if $A$ sees that message they will realize that something is afoot, since they wanted to talk to $C$ but received a reply from $B$.¹

Whereas in your solution Alice tells the receiver who $A$ thinks they are. But since the man in the middle does not forward this message blindly, but in fact decrypts it and uses it to construct an entirely new message, this doesn't help in any way.

---

¹This only really helps if the public key encryption scheme used does not have malleable ciphertexts. Using encryption for authentication is just not a good idea and does not lead to robust solutions.