3
$\begingroup$

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?

|improve this question
$\endgroup$
4
$\begingroup$

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.

|improve this answer
$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Paŭlo Ebermann Mar 28 '13 at 21:57
  • $\begingroup$ What if you had the messages encrypted with the same keystream (and nonce) ? how can you XOR both messages? $\endgroup$ – Devela Oct 26 '17 at 17:54
3
$\begingroup$

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)

|improve this answer
$\endgroup$
  • $\begingroup$ What if you had the messages encrypted with the same keystream (and nonce) ? how can you XOR both messages? $\endgroup$ – Devela Oct 26 '17 at 17:54
  • $\begingroup$ @Devela: if you xor the two ciphertexts, the result will be exactly the same as the xor of the two plaintexts. Whether the attacker can use that depends quite a lot about the languages the plaintexts are in (and how much foreknowledge the attacker has about the plaintexts); in a surprising number of cases, the attacker can rederive both plaintexts; the canonical example is if both texts were in ASCII-English (and the attacker initially has no knowledge beyond that) $\endgroup$ – poncho Oct 26 '17 at 18:21
  • $\begingroup$ That's why I was asking how I am suppose to XOR the messages/ciphertexts, I did for example: M1 = 4141414141414141 M2 = 424242414141 C1 = 838aa77c81e28ce0 C2 = f8e92b1da5b1 C1 XOR C2 = 7b638c612453 M1 XOR M2 = 030303000000. Notice I am able to decrypt both ciphertexts with the same key. $\endgroup$ – Devela Oct 26 '17 at 22:27

Your Answer

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.