# Can stream ciphers (usually) be “run backwards”?

Is it possible to reconstruct the previous output bits of a stream cipher, e.g. RC4, when only the current state is known, or is that computationally hard, or even impossible (due to ambiguous preceding states)?

For Salsa, it's obviously possible, since that even allows for random access.

Is there a formal name for the presence or absence of that property ("backward secrecy")?

-
For block ciphers using CTR streaming mode (which different from a stream cipher) then the key and counter are part of the state, and it is therefore certain possible to "backtrace". – Maarten Bodewes Sep 6 '13 at 22:23

@HenrickHellström: it is precisely correct as I wrote it; if you have an iterated invertible next state function, so your states are $X_0, F(X_0), F(F(X_0)), ..., F^n(X_0)$, and all the states you've visited so far are distinct, then the only way you have fall into a loop on the next state is if $X_0 = F^{n+1}(X_0)$; that is, you revisit the initial state. If we drop the assumption on invertibility, the $F^{n+1}(X_0)$ can be any of the previous states. – poncho Sep 6 '13 at 22:28
Poncho is right. Poncho never claimed that an arbitrary permutation is safe. What is true is that a random permutation is safer than a random function: this is because the expected cycle length for a random permutation on $n$ bits is $(2^n+1)/2$, whereas the expected cycle length for a random function on $n$ bits is $\sqrt{2^n}$, a huge difference. To the extent that the next-state function is intended to be indistinguishable from a random permutation, it is safer against short-cycle problems than a next-state function that is intended to look like a random function. – D.W. Sep 7 '13 at 1:57