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.

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?

share|improve this question
add comment

2 Answers 2

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.

share|improve this answer
3  
Please note that RC4 is vulnerable to related key attacks, so simple concatenation is not safe (this is what led to the WPA break). Apply at least a hash function on both, or better use a pseudorandom function with the key as key and the nonce as input. –  Paŭlo Ebermann Mar 28 '13 at 21:57
add comment

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)

share|improve this answer
add comment

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.