2
$\begingroup$

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$?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you think that the abobe could be changed somehow to work with the standard block ciphers in a secure manner? $\endgroup$ – user1563721 Jul 12 '15 at 12:58
  • $\begingroup$ 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. $\endgroup$ – Thomas Pornin Jul 12 '15 at 13:10
  • $\begingroup$ 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. $\endgroup$ – CodesInChaos Feb 20 '16 at 15:02
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.