0
$\begingroup$

Consider Shamir's No-Key protocol. What if you substitute the asymmetric operations with XOR, each party using an ephemeral OTP.

  1. It's symmetric, so you could apply the protocol scheme as if it were homomorphic
  2. It's much faster than Shamir's solution using public key crypto

Would this still be a valid and comparably secure protocol as Shamir's No-Key protocol?

$\endgroup$
4
$\begingroup$

Would this still be a valid and comparably secure protocol as Shamir's No-Key protocol?

No, it would not be secure at all.

In this revised protocol, Alice sends a message $M$ to Bob, to do that, she picks a random string $A$, and sends:

$$A \oplus M$$

Bob receives this, picks a random string $B$, and sends:

$$B \oplus (A \oplus M) = A \oplus B \oplus M$$

Alice then xors in her original string $A$, and sends

$$A \oplus (A \oplus B \oplus M) = B \oplus M$$

Now, someone in the middle hearing these three exchanges, if they exclusive or all three, they get:

$$(A \oplus M) \oplus (A \oplus B \oplus M) \oplus (B \oplus M) = M$$

$\endgroup$
2
$\begingroup$

Shamir's three-pass or no-key protocol is based on a public-key encryption scheme with keys $(k, K)$, encryption $E_K(m)$, and decryption $D_k(c)$, with the conjugation property that for any $K'$, $D_k(E_{K'}(E_K(m))) = E_{K'}(m)$. In other words, $D_k \circ E_{K'} \circ E_K = E_{K'}$. (Thus the group of encryption and decryption operators is abelian.) The protocol to send a message $m$ is:

  1. Sender picks key pair $(s, S)$ and transmits $c_0 = E_S(m)$.
  2. Receiver picks key pair $(r, R)$, receives $c_0'$, and transmits $c_1 = E_R(c_0')$.
  3. Sender receives $c_1'$ and transmits $c_2 = D_s(c_1')$.
  4. Receiver receives $c_2'$ and computes $m' = D_r(c_2')$.

Correctness. If $c_0' = c_0$, then $$c_1 = E_R(c_0) = E_R(E_S(m)).$$ If $c_1' = c_1$, then $$c_2 = D_s(c_1) = D_s(E_R(E_S(m))) = E_R(m).$$ If $c_2' = c_2$, then $$m' = D_r(c_2) = D_r(E_R(m)) = m.$$

The question is: What happens if we let $s = S$ and $r = R$ be message-length pads, $E_k(m) = k \oplus m$, and $D_k(c) = k \oplus c$?

Then we have \begin{align*} c_0 &= E_s(m) = s \oplus m, \\ c_1 &= E_r(E_s(m)) = r \oplus s \oplus m, \\ c_2 &= D_s(E_r(E_s(m))) = s \oplus r \oplus s \oplus m \\ &= r \oplus m. \end{align*} From this an eavesdropper can compute \begin{align*} c_0 \oplus c_1 \oplus c_2 &= s \oplus m \oplus r \oplus s \oplus m \oplus r \oplus m \\ &= (s \oplus s) \oplus (r \oplus r) \oplus (m \oplus m) \oplus m \\ &= m. \end{align*}

Oops.

$\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.