Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
If I have the following:
E1 = RC4(M1, K);
E2 = RC4(M2, K);
If two different messages M1 and M2 are encrypted with the same key, K, can the key be recovered by doing:
K = E1 XOR E2
I tried XORing the two streams and could not get the key. Does RC4 not work this way?
No. The key is not used to encrypt the message. RC4 is a stream cipher. The key is utilized to generate a one-time pad to encrypt the message. This is what you have actually done:
E1 = RC4(M1,K) = M1 XOR PAD(k)
E2 = RC4(M2,K) = M2 XOR PAD(k)
E1 XOR E2 => M1 XOR M2
Ergo, RC4 keys are safe for single time use. You need to concatenate a nonce to the key for multiple use.
Well, it depends on what your 'RC4' function does, and what you mean by the key. Let's step through the possibilities:
Possibility 1: if the RC4 function takes the key, runs the RC4 Key Setup Algorithm on it, and then generates some keystream with that state, and exclusive-or's that keystream with the message to generate the ciphertext. In addition, this possibility assumes that, by key, you're actually referring to the RC4 keystream. In that case, then yes, it is easy to recover the exclusive-or of the two messages. And, f you have partial information on what the messages are (e.g. they are ASCII English), you would likely be able to recover the keysream (or, at least, reduce it to a handful of possibilities); and so in this scenario, an attack is plausible.
Possibility 2: the RC4 function is as above, but by key, you mean the original RC4 key. In that case, then no, it is infeasible to reconstruct the key from the keystream. Now, the messages are still vulnerable, and so this scenario isn't ideal, even though the specific leakage you're asking about doesn't occur (we generally care about protecting the messages more than the keys; after all, the only reason we care about the key is that revealing the key also reveals the messages).
Possibility 3: if your program has already run the RC4 Key Setup algorithm, and all your RC4 function does is to generate the next N keystream output, and exclusive-or's those into the plaintext (which is how, for example, TLS uses RC4). In this case, exclusive-or'ing the two ciphertexts tells you nothing (neither the keystream, nor the original RC4 key)
