4
$\begingroup$

There is a communication protocol that I believe creates the equivalent of a one time pad, with the downside that the secret message must be transferred multiple times. The protocol is so simple that I imagine that it has a name but I can't find a protocol which matches its description.

Assumptions:

  1. A client C wants to send a password P of L bytes to a Server S.
  2. A function Z(P,M) exists whereby both P and M are L bytes and

    Z(P,M)= P[i] xor M[i]; for all i < L

Thus the protocol would work as follows:

  1. C generates a random string of L bytes called CM. C sends to S: Q0 where Q0=Z(P,CM)
  2. S generates a random string of L bytes called SM. S sends to C: Q1 where Q1=Z(Q0,SM)
  3. C reapplies the CM mask to Q1. C sends to S Q2 where Q2=Z(Q1,CM).
  4. S reapplies the SM mask to Q2. Q gets P from P=Z(Q2,SM)

The protocol is taking advantage of the fact that the xor operation is both associative and commutative.

$\endgroup$
9
$\begingroup$

The name I would use for this protocol is "broken".

It is insecure. An eavesdropper gets to observe $Q_0 = P \oplus CM$, $Q_1 = Q_0 \oplus SM = P \oplus CM \oplus SM$, and $Q_2 = Q_1 \oplus CM = P \oplus SM$. Notice that we have the relation $$Q_0 \oplus Q_1 \oplus Q_2 = (P \oplus CM) \oplus (P \oplus CM \oplus SM) \oplus (P \oplus SM) = P.$$ Therefore, an eavesdropper who xor's the three messages he observes can recover the message $P$. In other words, this protocol is completely insecure.

If I recall correctly, I believe that an early version of the Bluetooth specification used this algorithm for key exchange. Fortunately, the error was caught and fixed.

You may be thinking of the three-pass protocol for key exchange. It is basically the same concept as what you have, but using something other than xor. With xor, this is insecure, but if you replace xor with an appropriate other operation, you can get something secure. The most well-known instantiation is to replace xor with Pohlig-Hellman exponentiation-based encryption. In that scheme, we set $Q_0 = P^c \pmod{p}$, $Q_1 = Q_0^s \pmod{p}$, $Q_2 = Q_1^{c^{-1}} \pmod{p}$, and then S can compute $P = Q_2^{s^{-1}} \pmod{p}$, where everything is done modulo a large prime $p$. However, the three-pass protocol has no advantages over standard public-key key-exchange systems, so it is rarely (if ever) used. For instance, its security is roughly equivalent to the security of Diffie-Hellman key-exchange, so it has no clear advantages over Diffie-Hellman or RSA.

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