5
$\begingroup$

Is it possible to find the key if we know the plaintext and ciphertext with RC4. How should I write the algorithm?

$\endgroup$
  • 1
    $\begingroup$ Only if you use many related keys. $\endgroup$ – CodesInChaos Mar 20 '15 at 18:22
9
$\begingroup$

No, to the best of our knowledge, it is not possible, apart from a brute force search over all possible keys. RC4 has known cryptographical weaknesses; however, none of them are of much help in recovering the key, given a plaintext/ciphertext pair.

There are backtracking approaches that might take circa $2^{700}$ effort independent of the key size; however that is impractically huge (and unless the key is huge, a brute force search is still simpler)

On the other hand, if you have two ciphertexts encrypted with the same RC4 key, and you know the plaintext for one of the ciphertexts, it's easy to recover the other plaintext. All you need to do is compute the exclusive-or of the two ciphertexts, and the known plaintext -- the result will be the unknown plaintext.

This works because RC4 takes the key, and using that, generates a long string of bytes (the keystream). RC4 then takes the keystream, and exclusive-or's that with the plaintext, generating the ciphertext. That is, if $P_i$ is byte $i$ of the plaintext, and $C_i$ is byte $i$ of the ciphertext, and $RC4_i(key)$ is byte $i$ of the keystream generated by the key, then:

$$C_i = P_i \oplus RC4_i(key)$$

If we have a second plaintext $P'$ and ciphertext $C'$ that is encrypted with the same key, we then have:

$$C'_i = P'_i \oplus RC4_i(key)$$

Combining them, we have:

$$P_i = P'_i \oplus C_i \oplus C'_i$$

Now, we can recover the values of $RC4_i(key)$, however there's no known way to recover $key$ from that. However, if all you want to know is the plaintext $P$, you don't need the key.

Of course, if $P$ (the unknown plaintext) is longer than $P'$ (the known plaintext), this trick will reveal only the first part of $P$.

In addition, even if you don't know the value of $P'$, a similar trick will allow you to compute be value of $P \oplus P'$ - depending on what the plaintext is, that is often sufficient to allow an attacker to deduce the original values of $P, P'$. Hence, it is always a mistake to RC4 encrypt two different things with the exact same key.

$\endgroup$
  • $\begingroup$ To be more clear , I have two chipertexts that are encrpyted with same key, and one of the ciphertexts belongs to a plaintext which I know. I want to find another plaintext. $\endgroup$ – ccca Mar 20 '15 at 18:22
  • $\begingroup$ I have algorithm to encrpyt and decrpyt in C# , Encrypt(string key, string data) , Decrypt(string key, string data) . they get the paremeters as string , and convert to byte. Can I use same functions or I need a different function ? $\endgroup$ – ccca Mar 21 '15 at 22:53
  • $\begingroup$ Can anyone provide a citation/publication for this known plaintext attack on RC4? I searched a lot but could not find it. $\endgroup$ – learnerX Feb 1 '18 at 8:24
0
$\begingroup$

Trying to solve this exact question i've stumbled across several threads with almost the same question and absolutely the same answer... which didn't work for me. BUT! The answers were absolutely correct and @poncho gives very accurate description of what needs to be done!

Here is my C code which worked for me:

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[])
{
    if(argc != 4)
    {
        printf("usage: ./rc4_pa cipher1 cipher2 message1\n");
        return 1;
    }
    char *c1 = argv[1]; 
    char *c2 = argv[2];
    char *m1 = argv[3];

    int len_c1 = strlen(c1);
    int len_m1 = strlen(m1);
    char m2[len_m1 + 1];
    m2[len_m1] = '\0';

    for(int i = 0; i < len_m1; i++)
    {
        m2[i] = c1[i] ^ m1[i] ^ c2[i];
    } 
    printf("decrypted: %s\n", m2);
}

Why my code didn't work out of the box? I've got my cipher text from a web server and usually some chars of a ciphertext are not really printable. The only way to pass them further is to encode once more. In my case that was base64.

save the code to rc4_pa.c and make rc4_pa than use it like this

$ ./rc4_pa $(echo L1Gd8F5g | base64 -d) $(echo MFuD8FVg | base64 -d) hello

hope someone else might find it helpful.

$\endgroup$
  • $\begingroup$ Welcome to crypto.stackexchange - There's a few things to mention about this attempt at posting an answer. If poncho's answer was not around, this answer would become more or less not useful anymore. It's also a copy+paste of the same answer found on Stackoverflow with the credit swapped to a different user. Lastly, code in general is also not really appropriate for crypto.se, since we are more of a mathematics based site. $\endgroup$ – Ella Rose Jul 9 at 19:30
  • $\begingroup$ Well, that’s actually my answer, wondering how did you came with this statement of user swapping. Since I cannot comment, I decided to leave this answer ‘cause someone asked for a working solution $\endgroup$ – Igor Voltaic Jul 9 at 19:39

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.