A "no key exchange" protocol: Alice holds $K_1$, Bob holds $K_2$. Alice sends $C_1 = M \oplus K_1$, Bob returns $C_2 = C_1 \oplus K_2$, Alice sends $C_3 = C_2 \oplus K_1$, and Bob computes $C_3 \oplus K_2$. Show that Bob gets $M$, and show why the protocol is completely insecure.

Question

Accepted Answer

XOR is commutative, so $C_3 = M \oplus K_2$ and Bob recovers $M$. But an eavesdropper simply computes $C_1 \oplus C_2 \oplus C_3 = M$, without any key.
Correctness: $C_3 = ((M \oplus K_1) \oplus K_2) \oplus K_1 = M \oplus K_2$, because $K_1 \oplus K_1 = 0$ and the order of XORs does not matter. Then $C_3 \oplus K_2 = M$.
The attack: Eve records all three messages and XORs them:
$$C_1 \oplus C_2 \oplus C_3 = C_1 \oplus C_2 \oplus (C_2 \oplus K_1) = C_1 \oplus K_1 = M$$
Each key appears an even number of times across the three messages and cancels out.
Why the idea still matters: the "three-pass" pattern works if the locking operations commute but cannot be undone by combining the transcripts. Shamir's three-pass protocol uses modular exponentiation ($M^{a}$, then $(M^{a})^{b}$, …) instead of XOR, so an eavesdropper would have to solve a discrete-logarithm problem. With XOR the structure is linear, and linearity is what gives it away.
Lesson: a stream cipher is safe only if each keystream is used once on one message. Here both keys are each used twice, which is a disguised two-time pad.