Break an authentication protocol based on a pre-shared symmetric key

Question

Consider the following protocol, meant to authenticate $A$ (Alice) to $B$ (Bob) and vice versa.

$$ \begin{align*} A \to B: &\quad \text{“I'm Alice”}, R_A \\ B \to A: &\quad E(R_A, K) \\ A \to B: &\quad E(\langle R_A+1, P_A\rangle, K) \\ \end{align*} $$

• $R$ is a random nonce.
• $K$ is a pre-shared symmetric key.
• $P$ is some payload.
• $E(m, K)$ means $m$ encrypted with $K$.
• $\langle m_1, m_2\rangle$ means $m_1$ assembled with $m_2$ in a way that can be decoded unambiguously.
• We assume that the cryptographic algorithms are secure and implemented correctly.

An attacker (Trudy) wants to convince Bob to accept her payload $P_T$ as coming from Alice (in lieu of $P_A$). Can Trudy thus impersonate Alice? How?

_{This is slightly modified from exercise 9.6 in Information Security: Principles and Practice by Mark Stamp. In the book version, there is no $P_A$, the last message is just $E(R_A+1,K)$, and the requirement is for Trudy to “convince Bob that she is Alice”. Mark Stamp asks us to find two attacks, and the two I found allow Trudy to forge $E(R+1,K)$ but not $E(\langle R, P_T\rangle, K)$.}

Answer 1

This protocol seems to be insecure due to the fact that Bob sends $E(R_A,K)$. This can be used by Trudy to "generate" encryptions of $E(\langle R_A+1,P_T\rangle , K)$ that will later be used to complete the authentication protocol.

Specifically, consider the following attack:

Trudy picks random $R_1$ and runs the protocol with Bob in the following manner: $$ \begin{align*} T \to B: &\quad \text{“I'm Alice”}, \langle R_1+1,P_T \rangle \\ B \to T: &\quad \color{blue}{E(\langle R_1+1,P_T \rangle, K)} \\ \end{align*} $$ and then Trudy cuts the protocol in the middle (since she doesn't know how to reply). We assume both Trudy and Bob abort.

Now Trudy starts another instance of the protocol: $$ \begin{align*} T \to B: &\quad \text{“I'm Alice”}, R_1 \\ B \to T: &\quad E(R_1, K) \\ T \to B: &\quad \color{blue}{E(\langle R_1+1,P_T \rangle, K) } \end{align*} $$ How did Trudy complete the protocol this time without knowing $K$? it's easy! Bob actually performed the encryption for her in the first instance.

Lesson learned: in a cryptographic protocol, it's good for each message or separable fragment to contain a unique tag that prevents its reuse as some other message in the protocol. If Bob's reply was $E(\langle 1, R_A\rangle)$ and the third message was $E(\langle 2, R_A+1, P\rangle)$, this attack would not work.