Question

Suppose that someone suggests the following way to confirm that the two of you are both in possession of the same secret key. You create a random bit string the length of the key, XOR it with the key, and send the result over the channel. Your partner XORs the incoming block with the key (which should be the same as your key) and sends it back. You check and if what you receive is your original random string, you have verified that your partner has the same secret key, yet neither of you has ever transmitted the key. Is there a flaw in this scheme?

Answer 1

yes, there is a small flaw. You can reconstruct your partner's key even if it is different from yours.

Step-by-step explanation:

Suppose you have key a and your partner has key b, you want to check if a == b, but if it is not, your partner doesn't want to reveal his key otherwise he could have just sent it.

So you create a random bit string r. and send a⊕r to him. He sends you back a⊕r⊕b. If a==b the a⊕b would cancel each other out, and you would be left with r.

However, if you calculate a⊕r⊕b⊕r⊕a, you would always get b! In other words, you XOR the received value with r and XOR it with your a. Then you get b, whatever it is.