# Recovery of RC4 key when S-box 0 stage or 1st stage known

I've been exploring around, trying to understand if such thing is even possible. I have some RC4 ciphertext which I know it's plaintext and I would like to extract the key just from cipher and plaintext. While reading through "RC4 Stream Cipher and it's variants" by Goutam Paul I came a cross (4.1.1) PRGAreverse algorithm on p.65 (Chapter 4.1) providing candidates for S by supplying to it a state of S and state number: As both KSA and PRGA are deterministic, I guess this PRGAreverse algorithm should work but I'm having difficulties understanding the probability for each candidate. I mean, let's say I get 5 candidates for S[i], i=0, then how should I know which is the right one without trying to use it against the ciphertext nor plaintext?

• Suggestion to use MathJax instead of image.
– hola
Dec 16, 2019 at 18:18

I have some RC4 ciphertext which I know it's plaintext and I would like to extract the key just from cipher and plaintext.

That turns out to be a hard problem; the only practical way known is to brute force the key, and see if you can find a key that generates a keystream that is consistent with the known plaintext/ciphertext.

That is infeasble if the key is large; however it's the only known method that has much of a chance at all of working.

While reading through "RC4 Stream Cipher and it's variants" by Goutam Paul I came a cross (4.1.1) PRGAreverse algorithm on p.65 (Chapter 4.1) providing candidates for S by supplying to it a state of S and state number

If what you have is the plaintext and the ciphertext (and nothing else), this algorithm doesn't help you. The reason it doesn't is that it assumes that you know the state of the internal permutation S at some point; the plaintext/ciphertext doesn't give you that. The best known algorithm for recovering the permutation given what you have turn out to be totally infeasible for standard RC4; you'd be better off attempting a brute force of the key.

• Hey poncho. Thanks for your answer. I understand. I coded a python bruteforcer for this mission. Obviously it takes a lot of time when trying 2^128 keys. Do you know of any known implemented bruteforcer? Jan 10, 2014 at 17:22
• Hey poncho, after doing some research I've found that state of S is 1. Is my question relevant? Jan 16, 2014 at 12:37
• I have no idea what 'state of S is 1' means. Jan 16, 2014 at 14:53
• Consider S on state 1 after initialisation. By state 1 I mean that on initialisation I give KSA the key and S is being positioned by it, now I cipher 256 zeros (as state 0) and the S is repositioned again. Now I encrypt data and by the data I chose to cipher, S is again repositioned - this is state 1. So now I know this data and this cipher and I also know the state of S (apart of knowing on which iteration S is at, I can XOR plaintext and cipher and actually get S). I hope I explained my self. Is it possible to recover the state of the previous S (the one after the 256 zeros) and so on? Jan 18, 2014 at 9:23
• @Hedgie: "I can XOR plaintext and cipher and actually get S"; errr, no, you cannot recover the state of S by exclusive or'ing the plaintext and the ciphertext. Xor'ing the plaintext and the ciphertext gives you the keystream; there is no known practical way to recover the state S of the permutation from the keystream. Jan 23, 2014 at 22:40