Notes - Computer Security MT24, Needham-Schroeder protocol

1. $A \to B$: Alice, $E _ {k _ B}(\text{Alice} \parallel \mathbf{nonce} _ A)$
2. $B \to A$: $E _ {k _ A}(\mathbf{nonce} _ A \parallel \mathbf{nonce} _ B)$
3. $A \to B$: $E _ {k _ B}(\mathbf{nonce} _ B \parallel k _ s)$
4. $A \to B$: $E _ {k _ s}(m _ 1 \parallel \text{Alice} \parallel \mathbf{counter})$
5. …

To remember this, it’s helpful to remember step 2 as the vulnerable step, and then the rest of the protocol follows straightforwardly. Alice needs to encrypt her nonce before sending it to Bob so that she knows Bob is the one to reply.

It is vulnerable to a man-in-the-middle attack, assuming that Alice contacts the intruder at least once.

Alice contacts the intruder:

1. $A \to I$: Alice, $E _ {k _ I}(\text{Alice} \parallel \mathbf{nonce} _ A)$

The intruder, pretending to be Alice, contacts Bob:

1. $I _ A \to B$: Alice, $E _ {k _ B}(\text{Alice} \parallel \mathbf{nonce} _ A)$
2. $B \to I _ A$: $E _ {k _ A} (\mathbf{nonce} _ A \parallel \mathbf{nonce} _ B)$

The intruder uses this in their response with to Alice’s original communication:

1. $I \to A$: $E _ {k _ A}(\mathbf{nonce} _ A \parallel \mathbf{nonce} _ B)$
2. $A \to I$: $E _ {k _ I}(\mathbf{nonce} _ B \parallel k _ s)$

The intruder uses this to communicate with Bob:

1. $I _ A \to B$: $E _ {k _ B}(\mathbf{nonce} _ B \parallel k _ s)$
2. $I _ A \to B$: $E _ {k _ s}(\cdots)$

Now Bob thinks he’s talking to Alice, but is actually talking to the intruder.

To fix this, one modification is that Bob includes his name in the second step of the protocol:

1. $A \to B$: Alice, $E _ {k _ B}(\text{Alice} \parallel \mathbf{nonce} _ A)$
2. $B \to A$: $E _ {k _ A}(\mathbf{nonce} _ A \parallel \text{Bob} \parallel \mathbf{nonce} _ B)$
3. $A \to B$: $E _ {k _ B}(\mathbf{nonce} _ B \parallel k _ s)$
4. $A \to B$: $E _ {k _ s}(m _ 1 \parallel \text{Alice} \parallel \mathbf{counter})$
5. …