1
$\begingroup$

RC4 uses two 8-bit indices. One, $j$, is key-dependent and secret, and the other, $i$, increments by one for each byte output. The $i$ index is typically considered to be public, but what if the RC4 keystream starts at an unknown position, putting $i$ anywhere in the range of $0$ to $255$ with equal probability? I can think of a few inefficient and naïve techniques, but what would be the most efficient technique to discover $i$?

$\endgroup$
3
$\begingroup$

The most efficient way I can think of (not that it's all that practical) is to take a very long section of the keystream (think a Gigabyte+), and check it against the known RC4 digraph statistics; some of these biases (actually, most of them) depend on the value of i, and so the value of i that is correct will show up as more strongly biased than incorrect values.

The practical downside is that it requires a lot of keystream; on the other hand, it is computationally efficient (and works even if the RC4 key is large)

$\endgroup$
1
  • $\begingroup$ That is the naïve technique I was thinking about. Is that really the most efficient way? $\endgroup$ – forest Sep 17 '19 at 5:34

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.