Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
Looks related to en.wikipedia.org/wiki/Three-pass_protocol which is insecure for xor, but works for some other commutative ciphers. –  CodesInChaos Jul 29 '12 at 22:22
    
1  
It'd be good to get the additional details about Three-pass protocol in the @D.W. answer migrated if this is going to be closed. –  archie Nov 11 '13 at 18:59
    
@archie: I agree, these questions really should be merged. We can flag a mod to do that once one of them is closed. (We could do it before that, but then the mods would have to either wait or cast a binding close vote themselves.) –  Ilmari Karonen Nov 11 '13 at 20:57

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
    
Great point, I'm embarrassed I didn't catch it. I read about it in a book a while ago so there is a good chance I remembered part of it. –  amccormack Jul 29 '12 at 22:14
1  
@amccormack, no reason you should be embarassed! It is closely related to the three-pass protocol, which you might have been remembering (in fact, if I were going to explain the three-pass protocol, starting off with the insecure xor variant is not a bad way to explain the basic concept). –  D.W. Jul 29 '12 at 22:33
    
Love this answer. I had the same doubt as the OP. –  foresightyj Dec 5 '13 at 1:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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