Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

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.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.