# Break an authentication protocol based on a pre-shared symmetric key, with message numbers

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(\langle 1, R_A\rangle, K) \\ A \to B: &\quad E(\langle 2, 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, \ldots, m_n\rangle$ means an assemblage of the $m_i$'s that can be decoded unambiguously ($n$ is encoded unambiguously as well).
• 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 a follow-up to Break an authentication protocol based on a pre-shared symmetric key.

• Since $\langle m_1, ..., m_n\rangle$ encodes the $n$ as well, then Alice is the only one that generates encryption of messages with n=3, and at any of these, the last argument is $P_A$. Mar 18, 2012 at 0:25

The only party that generates encryptions of messages $m$ such that $m$:
is Alice. Each time she generates such a chipertext, the last component is $P_A$. If $E$ is a strong enough encryption (non malleable), then Trudy will not be able to generate by herself a an encryption $E(m)$ of a massage in the formt $m=\langle 2,R,P_T \rangle$ that Bob would accept (except with negligible probability).
• Hence only Alice can make these messages, though Trudy can replay them. And since Bob doesn't contribute his own nonce, it's up to him to check that he's only ever accepting one message 3 per value of $R_A$, which is one message 3 per message 1. This protocol isn't nearly as interesting as I thought it would be when I asked the question. Mar 20, 2012 at 17:27