Skipping / seeking to position with RC4 encryption

Question

I have this problem when I want to "skip" to a position while streaming an encrypted video

So what I have is:

An http streaming server (local, running on the Android device) the native android Media Player RC4 encryption utility

Basically, I'm storing an Encrypted video in the sdcard, and i want to stream it to the media player using my http streaming server. The server already does the encryption on-the-fly, which actually works, by transforming the bytes using the RC4 encryption utility before writing it out to the OutputStream.

Encrypting the file is no problem - just run the whole file against the generated bits of the encryption utility - which I just do over when trying to playback the video. The problem is when I want to "seek to" a position in the video, for example i want to view the middle part of a 2-hr movie. What I'm currently doing, which works, albeit very slowly, is to reset the RC4 encryption utility, feed it an amount equal to the duration of which i jumped to in the video.

Pardon me if I don't sound very clear in my explanation here, but if you actually worked with RC4 encryption with streaming, you should have encountered the same problem.

So the question is, is it possible, and if it is, how can I, "seek to" a position in my RC4 bit generator without passing through all the unnecessary bytes that I just skipped?

Each video is about 500mb or so in size, so if I seek to the near the end of the video, that's around 500,000,000 useless bit iterations to do before being able to stream the correct data.

Answer 1

No, the RC4 algorithm is not seekable. Each iteration of the key stream generation involves permuting the key dependent S permutation using a stateful swap of two elements, in a way that is hard to reproduce without actually performing all of the intermediate swaps.

It would have been trivial to accomplish what you want if you had used e.g. AES in CTR mode, since CTR mode was designed to be fully seekable.

Edit: However, one thing you could do if memory is not scarce, would be to use your own RC4 implementation (see link, it is easy to do), and cache the internal state (258 bytes in total at each position) at regular intervals. This would help if the user is jumping back and forth a lot, but the first time the user skips ahead the full RC4 key stream would have to be generated to that position.