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

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?

• The keystream is just the xor of plain and ciphertext, so another text with the same key can also be decrypted "xor with that keystream again. $P_2 = C_2 \oplus (C_1 \oplus P_1)$. – Henno Brandsma Mar 25 '17 at 12:14
• so basicly doing B xor A i should retrieve the key to decrypt message C? – trolkura Mar 25 '17 at 17:34
• @trolkura RC4 keys are single use, since RC4 has no support for separate nonces. Using the same key means using the same key stream, which amounts to a many-time-pad. We have several, questions about many-time-pads, e.g. Taking advantage of one-time pad key reuse? – CodesInChaos Mar 26 '17 at 16:54

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.

• What if Cipher text1 and cipher text2 differ in length? – trolkura Mar 27 '17 at 11:14
• @trolkura I added an example to illustrate different ciphertext lenghts :) You can basically only recover as much of the keystream as your plaintext-ciphertext pair is long! If the ciphertext you want to decrypt is shorter or equally long, you are good to go, a longer one can only be decrypted up to the length of the recovered keystream ;) – derbenoo Mar 27 '17 at 14:38