3

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.

skaffman
  • 398,947
  • 96
  • 818
  • 769
josephus
  • 8,284
  • 1
  • 37
  • 57

1 Answers1

5

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.

Henrick Hellström
  • 2,556
  • 16
  • 18
  • Thought so too. But if "it's hard to reproduce", that could mean it's not impossible. +1, and if no one has something better in 2 days, it's yours. :) – josephus Mar 06 '12 at 10:30
  • The algorithm has been around for 25 years and received extensive cryptoanalysis. The reason I wrote the way I did was not that I think there is a feasible way to make it seekable in constant time, but only because I couldn't rule out that some of the known weaknesses might make it possible to find a sub linear algorithm that is slightly better than actually iterating the key stream generator. If there was an easy way to make RC4 support random access, there would be research paper written about it. – Henrick Hellström Mar 06 '12 at 10:50
  • 1
    OTOH, you could cash the internal state at regular intervals. – Henrick Hellström Mar 06 '12 at 11:00
  • caching the byte array state was actually something i considered - and i think would actually work. but for the purpose of the question, i'm more interested on the "research paper" that someone, somewhere, wrote. – josephus Mar 06 '12 at 11:36
  • 1
    another idea also is to use different keys for each 10meg chunk of data - also should work. – josephus Mar 06 '12 at 11:41
  • 1
    i ended up using a different key per chunk. the key will be provided by a derivation function, so i actually know the keys beforehand. this i think is a better solution than the state memoization as that solution will still fail terribly when the user just started playing the video and wanted to seek immediately to, say, the last 5 minutes of content. – josephus Mar 12 '12 at 02:06
  • 1
    The important thing when using RC4 that way, is that you use a KDF, and not just pass the concatenation of the key and the salt/chunk id directly to the RC4 key schedule. There are known cipher text only attacks against the latter use of RC4. – Henrick Hellström Mar 12 '12 at 08:25