9
$\begingroup$

I was just wondering why this kind of algorithm can't be used instead of, say, Diffie-Hellman to exchange keys:

  1. Alice decides on a key she wishes to share with Bob.
  2. Alice generates a stream of bytes with the same length as the key (securely, say, with a CSPRNG).
  3. Alice sends to Bob:
    C1 = (key ^ alice_random_bytes)
    
  4. Bob generates a stream of random bytes in a manner similar to Alice.
  5. Bob returns to Alice:
    C2 = (C1 ^ bob_random_bytes)
    
  6. Alice XORs C2 with her random byte sequence again, leaving only key ^ bob_random_bytes like so and sends it to Bob:
    C3 = (C2 ^ alice_random_bytes)
       = (C1 ^ bob_random_bytes ^ alice_random_bytes)
       = (key ^ alice_random_bytes ^ bob_random_bytes ^ alice_random_bytes)
       = (key ^ bob_random_bytes)
    
  7. Bob XORs C3 with his random bytes and obtains the key:
    K = (C3 ^ bob_random_bytes)
      = (key ^ bob_random_bytes ^ bob_random_bytes) 
      = key
    

This seems a lot simpler than Diffie Hellman, so I was wondering: what is the issue with such an algorithm?

New contributor
guest is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
  • 3
    $\begingroup$ Your algorithm is basically one-time pads but with the fatal flaw of having two different ciphertexts encrypted with them instead of just one. $\endgroup$ – Joseph Sible-Reinstate Monica yesterday
30
$\begingroup$

I've simplified the Alice random bytes to ARB and Bob random bytes to BRB. Then the protocol follows as;

Alice knows $key$ and $ARB$ and sends $$C_1 = key \oplus ARB$$

Bob knows $C_1$ and $BRB$ and sends

$$C_2 = C_1 \oplus BRB = key \oplus ARB \oplus BRB$$

Alice calculates $C_2 \oplus key \oplus ARB = key \oplus key \oplus ARB \oplus BRB = BRB$

Alice knows $key, ARB,$ and $BRB$ and sends

$$C_3 = (C_2 \oplus ARB) = key \oplus ARB \oplus BRB \oplus ARB = key \oplus BRB$$

Now, first of all, this requires a three-pass protocol.

Now, an observer sees

\begin{align} C_1 & = key \oplus ARB \oplus {}\\ C_2 & = key \oplus ARB \oplus BRB\\ C_3 & = key \oplus \phantom{ARB}\oplus BRB \\ \end{align}

A passive observer (eavesdropper) simply x-ors all to derive the key $$key = C_1 \oplus C_2 \oplus C_3.$$ Therefore it is insecure against the weak assumption on the attacker; passive!.

So, you rely on the xor, however, did not check what an observer can get and calculate from them.

The Diffie–Hellman key exchange (DHKE), on the other hand, leaks $g^a$ and $g^b$ where Alice selects a random integer $a$ and sends $g^a$ and Bob select a random integer $b$ and sends $g^b$. Finding $a$ or $b$ from them is the discrete logarithm problem. On the other hand, The Computational Diffie–Hellman (CDH) assumption, is asked to find $g^{ab}$ given $g^a$ and $g^b$, and the DHKE is relayed on this. If the discrete logarithm is easy then CDH is easy. We don't know the reverse, in the general case.

| improve this answer | |
$\endgroup$
  • 18
    $\begingroup$ The classic XOR everything and obtain the key :) $\endgroup$ – cisnjxqu 2 days ago

Your Answer

guest is a new contributor. Be nice, and check out our Code of Conduct.

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.