RC4, finding key if we know plain text and ciphertext [duplicate]

Question

Having plain text A , and cipher text B. Can we somehow retrieve key , when we want to decrypt text C which was also crypted with the same key?

Answer 1

The correct answer depends on whether you want to recover the key or the keystream. Let's first review how RC4 works:

RC4 Recap

RC4 takes a key as input and generates a cryptographically secure stream of pseudo random numbers:

$KS= RC4(k)$

To encrypt a plaintext message M, we simply XOR it with the keystream KS:

$KS= RC4(k)$

$C= M \oplus KS$

To decrypt the ciphertext, we have to reproduce the keystream by providing the same shared key as input to RC4:

$M= C \oplus KS$

Now, it is cruical that the same keystream is never used twice for encryptoin, since an attacker could learn the XOR of the two messages:

$C1= M1 \oplus KS$

$C2= M2 \oplus KS$

$C1 \oplus C2= M1 \oplus KS \oplus M2 \oplus KS= M1 \oplus M2$

Known-plaintext attacks against RC4

RC4 keystream recovery: This is a trivial thing to do once you are in possession of the plaintext:

$KS= C \oplus M$

This is normally not a problem since no one that has basic understanding of cryptography uses the same keystream to encrypt multiple messages. However, if I understand the description correctly, you have the following scenario:

$B= A \oplus RC4(K)$

$D= C \oplus RC4(K)$

If an attacker is in possession of A,B and D, it is trivial to extract the keystream generated by RC4(K) and decrypt the message C (at least up to the same length as A):

$C= D \oplus B \oplus A$

Example:

Let's say RC4 produces the following keystream:

KS= 11010110 00011010 01101011 10001110 11001101 11011111 01001010

With message A="hello" and C="secret!", you get the following ciphertexts:

A = 01101000 01100101 01101100 01101100 01101111 
C = 01110011 01100101 01100011 01110010 01100101 01110100 00100001 

B = 10111110 01111111 00000111 11100010 10100010
D = 10100101 01111111 00001000 11111100 10101000 10101011 01101011

By computing $A \oplus B$, you get the first 5 bytes of the keystream, which allows you to decrypt the first 5 bytes of C. Without the knowledge of the secret key or a longer plaintext-ciphertext pair you will not be able to decrypt the rest of C!

Note: You can already see in this example why it is a bad idea to re-use a keystream: the second byte of the ciphertexts of B and D are identical since they both encrypt the same character ("e").

RC4 key recovery: Recovering the secret key K is a much more difficult. There exist large classes of keys for which a small part of the secret key determines a large number of bits of the keystream. This is why it was recommended to throw away the first 256 bytes of the keystream (nowadays the recommendation is to not use RC4 at all). Observing enough plaintext/ciphertext pairs generated under a key can eventually be leveraged by attacks like the one by Fluhrer et al., leading to the recovery of the key by an attacker.