How to detect if a protocol is vulnerable to a replay attack trying to impersonate?

Question

I'm having a hard to finding out how I can detect if protocols are vulnerable to impersonation of Alice/Bob by Eves' replay attack! I have an example here: $$\begin{array}{lclcl} \mathsf A & \to & \mathsf B & : & \mathtt{Hello} \\ \mathsf B & \to & \mathsf A & : & B, K_{ab}\{B\} \\ \mathsf A & \to & \mathsf B & : & A, K_{ab}\{A\} \\ \end{array}$$ I would think that this is vulnerable to Eve impersonating Bob by adding these steps: $$\begin{array}{lclcl} \mathsf A & \to & \mathsf B & : & \mathtt{Hello} \\ \mathsf B & \to & \mathsf E(\mathsf A) & : & B, K_{ab}\{B\} \\ \end{array}$$ Now that Eve has the plaintext of $B$ and the ciphertext of $B$ ($K_{ab}\{B\}$ ), depending on which cipher used she now has $K_{ab}$ with which she can impersonate as Bob to Alice. $$\begin{array}{lclcl} \mathsf E(\mathsf B) & \to & \mathsf A & : & A, K_{ab}\{A\} \\ \end{array}$$

---

But when I look at protocols such as: $$\begin{array}{lclcl} \mathsf A & \to & \mathsf B & : & A, K_{ab}\{N_a\} \\ \mathsf B & \to & \mathsf A & : & B, N_a, K_{ab}\{N_b\} \\ \mathsf A & \to & \mathsf B & : & A, B, N_a, N_b, K_{ab}\{N_a, N_b\} \\ \end{array}$$ I'm totally lost. Is there some sort of characteristic vulnerability in protocols to which Eve could take advantage which I'm not seeing? I'm sorry if this is a stupid question but I'm new to this.

---

Notes of the editor:

• $\mathsf A$ (resp. $\mathsf B$) is entity Alice (resp. Bob), $A$ and $B$ are their respective identity.
• $\mathsf E(\mathsf A)$ means entity Eve impersonating Alice.
• $K_{ab}\{A\}$ means encryption of $A$ with a symmetric cipher under key $K_{ab}$ shared by Alice and Bob but initially unknown to Eve.
• $N_a$ means a nonce chosen by Alice.
• $X, Y\dots$ denotes a reversible concatenation of two or more messages; perhaps plain concatenation if the length of messages is fixed, or concatenation with , as separator after replacing every \ by \\ then every , by \, in the messages concatenated.

Answer 1

In a pure replay attack, Eve acts as a genuine participant to the protocol with respect to the other. Therefore, having passively eavesdropped the protocol: $$\begin{array}{lclcll} \mathsf A&\to&\mathsf B&:&\mathtt{Hello}&\ \ \mathsf{[1]}\\ \mathsf B&\to&\mathsf A&:&B,K_{ab}\{B\}&\ \ \mathsf{[2]}\\ \mathsf A&\to&\mathsf B&:&A,K_{ab}\{A\}&\ \ \mathsf{[3]}\\ \end{array}$$ Eve impersonating Alice to Bob can be: $$\begin{array}{lclcll} \mathsf E(\mathsf A)&\to&\mathsf B&:&\mathtt{Hello}&\ \ \mathsf{[1a]}\\ \mathsf B&\to&\mathsf E(\mathsf A)&:&B,K_{ab}\{B\}&\ \ \mathsf{[2a]}\\ \mathsf E(\mathsf A)&\to&\mathsf B&:&A,K_{ab}\{A\}&\ \ \mathsf{[3a]}\\ \end{array}$$ where at $\mathsf{[3a]}$ Eve simply replays the value she captured from $\mathsf{[3]}$, and thus passes the implicit test by Bob at step $\mathsf{[3a]}$ that the received $K_{ab}\{A\}$ in the second part of the message deciphers to the $A$ in the first part, that Bob (wrongly) assumes is the identity of the other party.

And Eve impersonating Bob to Alice can be: $$\begin{array}{lclcll} \mathsf A&\to&\mathsf E(\mathsf B)&:&\mathtt{Hello}&\ \ \mathsf{[1b]}\\ \mathsf E(\mathsf B)&\to&\mathsf A&:&B,K_{ab}\{B\}&\ \ \mathsf{[2b]}\\ \mathsf A&\to&\mathsf E(\mathsf B)&:&A,K_{ab}\{A\}&\ \ \mathsf{[3b]}\\ \end{array}$$ where at $\mathsf{[2b]}$ Eve simply replays the value she captured from $\mathsf{[2]}$, and thus passes the implicit test by Alice at step $\mathsf{[2b]}$ that the received $K_{ab}\{B\}$ in the second part of the message deciphers to the $B$ in the first part, that Alice (wrongly) assumes is the identity of the other party.

This does not involve finding key $K_{ab}$ from plaintext $B$ and ciphertext $K_{ab}\{B\}$, which would be breaking the cipher, something assumed impossible in a replay attack.

---

One way to prevent pure replay attack is to make use of nonce, so that just replayed messages won't be accepted. That's the case in this protocol (the question's second one without $K_{ab}\{N_a,N_b\}$ in the last step) $$\begin{array}{lclcll} \mathsf A&\to&\mathsf B&:&A,K_{ab}\{N_a\}&\ \ \mathsf{[1]}\\ \mathsf B&\to&\mathsf A&:&B,N_a,K_{ab}\{N_b\}&\ \ \mathsf{[2]}\\ \mathsf A&\to&\mathsf B&:&A,B,N_a,N_b&\ \ \mathsf{[3]}\\ \end{array}$$

Alice choses a nonce $N_a$, sends it enciphered as $K_{ab}\{N_a\}$ as part of $\mathsf{[1]}$, that Bob extracts, deciphers yielding $N_a$ that he sends as part of $\mathsf{[2]}$, allowing Alice to extract and check it against the nonce she has chosen; this proves to Alice that some entity able to use $K_{ab}$ was involved in the exchange; and if Alice can rule out that this entity is herself (say, by not running more than one instance of the protocol at a given time), then that involved entity must be Bob (because there is no other entity sharing $K_{ab}$ and it is used only as the key of a cipher), thus the protocol is immune to impersonation of Bob to Alice running the protocol with Alice's role.

Also, Bob chose $N_b$ in $\mathsf{[2]}$, sends it enciphered as $K_{ab}\{N_n\}$ as part of $\mathsf{[2]}$, that Alice extracts, deciphers yielding $N_b$ that she sends as part of $\mathsf{[3]}$, allowing Bob to extract and check it against the nonce he has chosen; this proves to Bob that some entity able to use $K_{ab}$ was involved in the exchange; and if Bob can rule out that this entity is himself, then that must be Alice, thus the protocol is immune to impersonation of Alice to Bob running the protocol with Bob's role.

Notice that when Bob is a server allowing multiple concurrent connections, Eve can impersonate Alice to Bob. An attack goes as follows: $$\begin{array}{lclcll} \mathsf E(\mathsf A)&\to&\mathsf B&:&A,K_{ab}\{N_a\}&\ \ \mathsf{[1a]}\\ \mathsf B&\to&\mathsf E(\mathsf A)&:&B,N_a,K_{ab}\{N_b\}&\ \ \mathsf{[2a]}\\ \mathsf E(\mathsf A)&\to&\mathsf B&:&A,K_{ab}\{N_b\}&\ \ \mathsf{[1a']}\\ \mathsf B&\to&\mathsf E(\mathsf A)&:&B,N_b,K_{ab}\{N'_b\}&\ \ \mathsf{[2a']}\\ \mathsf E(\mathsf A)&\to&\mathsf B&:&A,B,N_a,N_b&\ \ \mathsf{[3a]}\\ \end{array}$$ where

• In $\mathsf{[1a]}$, Eve gives any plausible $K_{ab}\{N_a\}$ even though she does not actually know the matching $\{N_a\}$; that can for example be an $\{N_a\}$ captured from a previous session, or (for many ciphers) any random bit string of the same size).
• In $\mathsf{[2a]}$, Bob just does its job; Eve does not make the check Alice would have made about $N_a$.
• In $\mathsf{[1a']}$, Eve mimics starting another simultaneous connection attempt, but sneakingly supplies $K_{ab}\{N_b\}$ of $\mathsf{[2a]}$ where the convention would be to supply $K_{ab}\{N'_a\}$
• In $\mathsf{[2a']}$, Bob just does its job, and correspondingly returns $N_b$ that he has chosen and sent enciphered in $\mathsf{[2a]}$; again Eve makes no check.
• In $\mathsf{[3a]}$, Eve uses the $N_b$ conveniently supplied by Bob in step $\mathsf{[2a']}$, and the check Bob makes of that $N_b$ passes.

The above proves the protocol is vulnerable, by exhibiting an explicit attack. Whether it is a replay attack is a matter of taste. Assuming yes: the question asks how this is detected. An answer is: because $\mathsf{[1]}$ and $\mathsf{[2]}$ can be abused to make Bob a decryption oracle under key $K_{ab}$ (that is, something that allows decryption of any message), and in the protocol considered in this section of the answer, the ability to decipher a message is what authenticates Alice to Bob.

---

As an attempt to prevent the above attack (likely: made for pedagogical reasons), the question's protocol $$\begin{array}{lclcll} \mathsf A&\to&\mathsf B&:&A,K_{ab}\{N_a\}&\ \ \mathsf{[1]}\\ \mathsf B&\to&\mathsf A&:&B,N_a,K_{ab}\{N_b\}&\ \ \mathsf{[2]}\\ \mathsf A&\to&\mathsf B&:&A,B,N_a,N_b,K_{ab}\{N_a,N_b\}&\ \ \mathsf{[3]}\\ \end{array}$$ has as a step $\mathsf{[3]}$ such that Alice forms $N_a,N_b$ and encipher it into $K_{ab}\{N_a,N_b\}$, that Bob deciphers and checks against $N_a$ he deduced from $K_{ab}\{N_a\}$ received as part of step $\mathsf{[1]}$, and against $N_b$ he has chosen. That's not a good idea: since Alice makes no extra check, and makes an extra use of $K_{ab}$, it can only make her more vulnerable to impersonation of Bob. And the protocol remains vulnerable to impersonation of Alice to Bob. Proving this is left as an exercise to the reader, but the following might help detect that:

• It is not forbidden for a cipher that some public function $F$ is such that $F(X,Y,K\{X\},K\{Y\})$ always deciphers the same as $K\{X,Y\}$, and from a secure block cipher it is easy to construct a CPA-secure cipher with that property, with matching $F$ (including, that ignores its inputs $X$ and $Y$).
• Even if we restrict to CPA-secure ciphers without that property, some are malleable (e.g. a block cipher in CTR mode), and that allows Eve to make good use of a passively eavesdropped step $\mathsf{[3]}$.