# Is this commutative encryption protocol secure?

My assumptions are:

• encryption must be commutative
• man-in-the-middle is not an issue

I would like to implement the following scheme between 2 parties ($A$ and $B$) to exchange a key:

Lets $C = P \oplus F(K, IV)$ is a commutative encryption, resp. CTR mode of some symmetric block cipher with random key $K$, random initialisation vector $IV$, and $P$ is plaintext, $C$ ciphertext.

$A$ has a $P$ which would like to share with $B$

So the following protocol would be done:

1. $A$ will choose a random $K_1$ and $IV_1$ and produce $C_1 = P \oplus F(K_1, IV_1)$
2. $A$ will send $C_1$ to $B$
3. $B$ will choose a random $K_2$ and $IV_2$ and produce $C_2 = C_1 \oplus F(K_2, IV_2) = P \oplus F(K_1, IV_1) \oplus F(K_2, IV_2)$
4. $B$ will send $C_2$ to $A$
5. $A$ will decrypt $C_2$ using $K_1$ and $IV_1$ so produce $C_3 = C_2 \oplus F(K_1, IV_1) = P \oplus F(K_1, IV_1) \oplus F(K_2, IV_2) \oplus F(K_1, IV_1) = P \oplus F(K_2, IV_2)$
6. $A$ will send $C_3$ to $B$
7. $B$ will decrypt $C_3$ using $K_2$ and $IV_2$ so produce $P = C_3 \oplus F(K_2, IV_2) = P \oplus F(K_2, IV_2) \oplus F(K_2, IV_2)$
8. $A$ and $B$ shares the same value $P$ now

Is there any security risk by combining any of the $C_1$, $C_2$, $C_3$ to get the actual value of $P$?

$C_1 \oplus C_2 = F(K_2, IV_2)$

$C_1 \oplus C_3 = F(K_1, IV_1) \oplus F(K_2, IV_2)$

$C_2 \oplus C_3 = F(K_1, IV_1)$

Could it be any possible attack how to get the value $P$?

To make notations simpler, I note $R_i = F(k_i, IV_i)$. Then: $$C_1 = P \oplus R_1$$ $$C_2 = P \oplus R_1 \oplus R_2$$ $$C_3 = P \oplus R_2$$

Therefore: $$C_1 \oplus C_2 \oplus C_3 = P \oplus R_1 \oplus P \oplus R_1 \oplus R_2 \oplus P \oplus R_2 = P$$

Your protocol looks like Shamir's three-pass protocol but it requires a bit more than mere commutativity, which is why Shamir's solution involves modular exponentiations.

• Do you think that the abobe could be changed somehow to work with the standard block ciphers in a secure manner? – user1563721 Jul 12 '15 at 12:58
• To my knowledge, nobody has found yet a way to do a secure key exchange with only symmetric cryptography algorithms. This does not prove that it is impossible, only that if it can be done then it is probably non-obvious and quite tricky. – Thomas Pornin Jul 12 '15 at 13:10
• I believe that Merkle Puzzles are Optimal - Boaz Barak, Mohammad Mahmoody-Ghidary shows that it's impossible to build secure public key encryption using only symmetric primitives. But I'm not sure if that's equivalent to proving the same for secure key-exchanges consisting of several passes. – CodesInChaos Feb 20 '16 at 15:02

Yes it is possible for a passive eavesdropper to recover the secret $P$.

Here's how:

The attacker observes $C_1,C_2,C_3$ and formes the XOR of all those values.
That's it, the result of $C_1\oplus C_2 \oplus C_3=P\oplus F(K_1,IV_1)\oplus P \oplus F(K_1,IV_1) \oplus F(K_2,IV_2) \oplus P \oplus F(K_2,IV_2)=P$ yields the desired plaintext.