Are there flaws in this simple key exchange?

Question

I'm reviewing for a computer security exam. Here is a simple scenario:

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 stream the length of the key, XOR it with the key, and send it 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? Why or Why not?

-because of the XOR, I don't think it is possible to get the same hash from different keys (that would mean it is a bad function...)

Then there is this extension onto the scenario:

You forget about using a key and simply use a random bit stream to XOR with the message and your partner uses the same random bit stream (leveraging the fact that for a given seed, the output of a random number generator is exactly repeatable and completely deterministic.) Is there any possible flaw with this scheme?

-I would say that this breaks one of the fundamental rules of a good hash: it isn't random. Right? I know that it isn't really possible to generate true random values...is that a viable flaw here?

Answer 1

You send K xor R. Your partner sends back R. The attacker sees both values; he can thus compute (K xor R) xor R (the XOR of the two values he saw), and the R cancel out: the result is K. So, weak. Terminally.

If you want something more robust, you'll need an extra tool, e.g. a cryptographic hash function like SHA-256. For instance, you still send K xor R and your partner sends back SHA-256(R). This one works provided that R was chosen randomly and uniformly. Think about it; the point of such exercises is to get some intuitive understanding of what is going on. Here, your partner is showing his knowledge of R by sending SHA-256(R), but without revealing anything about R (mostly because SHA-256 is resistant to preimages -- yeah, I know I am taking a bit of rhetoric shortcut here). Note, however, that this scheme is vulnerable to dictionary attacks in case the key K is a password (i.e. something from a set which is small enough to be exhaustively walked through).

Other variants with a hash function are possible; they will all be weak with regards to dictionary attacks, though (you need PAKE to fix that, and this means a lot more mathematics).

---

Your other scenario is what basically a stream cipher is. It can be strong, if done properly: use a robust algorithm, a large enough "seed" (which is, really, a key), and never ever reuse the same stream for two distinct messages.

Answer 2

Completely flawed. An attacker can simply XOR the challenge (the "random bit stream") with the response (the "original random string") and thus know the secret key.

The extension is a form of stream cipher. For a stream cipher to be secure it's critical that the same stream isn't repeated twice (i.e. that a different initialization vector be used). In any case if you try using a stream cipher for authentication as proposed you will be subject to a man-in-the-middle attack.

Answer 3

It looks like what you're asking is an exchange like this:

1. Alice generates plaintext P.
2. Alice XORs P with shared key K to obtain "ciphertext" C.
3. Alice sends C (P XOR K) to Bob.
4. Bob computes C XOR K to obtain plaintext P
5. Bob sends P to Alice.

Where it breaks down is steps 3.5, 5.5, and 6:

1. Alice generates plaintext P.
2. Alice XORs P with shared key K to obtain "ciphertext" C.
3. Alice sends C to Bob. 3.5 Eve intercepts and stores C.
4. Bob computes C XOR K to obtain plaintext P
5. Bob sends P to Alice. 5.5 Eve intercepts and stores P.

6. Eve computes C XOR P and recovers key K.

Knowingly exposing plaintext for which ciphertext exists basically does an attacker's work for her, particularly in the basic "stream cipher" form you have described. See Known Plaintext Attack.

The second option, that of synchronized PRNGs, is similarly problematic. How does Alice securely communicate the seed for the PRNG to Bob? She can't, unless they already share a key.

Finally, do remember that a hash function is a specific cyrptographic primitive, not a reference to ciphertext. An enciphered message is "encrypted", not "hashed". Not being pedantic here, simply trying to avoid the red pen of the professor.