1
$\begingroup$

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:

enter image description here

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?

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

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.

|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – devdc Jan 10 '14 at 17:22
  • $\begingroup$ Hey poncho, after doing some research I've found that state of S is 1. Is my question relevant? $\endgroup$ – devdc Jan 16 '14 at 12:37
  • $\begingroup$ I have no idea what 'state of S is 1' means. $\endgroup$ – poncho Jan 16 '14 at 14:53
  • $\begingroup$ 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? $\endgroup$ – devdc Jan 18 '14 at 9:23
  • 1
    $\begingroup$ @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. $\endgroup$ – poncho Jan 23 '14 at 22:40

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.