19 Needham-Schroeder Public Key Protocol

Question

If Alice and Bob know each other’s public keys, can they set up a symmetric key ?

$$\begin{array}{rl}1.& A\to B:E_B(N_a,A)\\ 2.& B\to A:E_A(N_a,N_b)\\ 3.& A\to B:E_B(N_b)\end{array}$$

• Public Key Encryption Notation $E_X(\_)$ means public key encryption.
• $N_a$ and $N_b$ can then be used to generate a symmetric key.

Message Guarantees

$\to$ Goal : Alice and Bob are sure they are talking to each other.

• Whoever could know $N_a$ is the person who decrypted the first message
• Whoever could know $N_b$ is the person who decrypted the second message.

Man-in-the-Middle Attack on Needham-Schroeder

How the Attack Works

• Alice sends $E_E(N_a,A)$ to Elvis, BUT Elvis then forwards this to B pretending to be A : $E_B(N_a,A)$.
• Bob responds with $E_A(N_a,N_b)$, thinking he’s talking to Alice, BUT Elvis forwards this to Alice.
• Alice now sends $E_E(N_b)$ to Elvis, so Elvis now has Bob’s nonce AND forwards it to B to complete the protocol.
• Now Elvis can impersonate Alice and Bob.