4
$\begingroup$

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")?

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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". $\endgroup$
    – Maarten Bodewes ♦
    Commented Sep 6, 2013 at 22:23
  • $\begingroup$ The property you ask about is called "forward secrecy." It's very important for random generators that are used to produce secret keys, but much less so for stream ciphers. $\endgroup$
    – Luis Casillas
    Commented Jul 15, 2016 at 18:57

2 Answers 2

Reset to default
6
$\begingroup$

With RC4, the answer is "yes, you can efficiently run the cipher backwards, reconstructing previous states".

For stream ciphers, whether you can reconstruct previous states in not typically considered, however for cryptographically secure random number generators (which are a similar primitive), it does come up; the term I've heard is "Backtracking Resistance".

Now, there is one thing to be careful with "Backtracking Resistance"; if the reason you have backtracking resistance is because the function that transitions between the previous state and the next state acts like a random function, then it becomes easier to fall into a short loop than if the transition function is invertable; this is because the you run into a loop if the next state happens to be any of the previous states you have visited. In contrast, if you have an invertible next-state function, the only state that you might revisit is the initial state. Because of this increased tendency to fall into short loops, it's typically considered wise if you (at least) double the size of the internal state beyond what the security strength might indicate you would need.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @HenrickHellström: "it is not sufficient that the next-state function is a permutation, but it must also be a single cycle permutation"; how do you come to that conclusion? OFB with a specific key is (likely) not a single cycle permutation; are you attempting to argue that it must be insecure? $\endgroup$
    – poncho
    Commented Sep 6, 2013 at 22:15
  • 3
    $\begingroup$ @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. $\endgroup$
    – poncho
    Commented Sep 6, 2013 at 22:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Commented Sep 7, 2013 at 1:57
0
$\begingroup$

Some stream ciphers (e.g. RC4 and Trivium) are reversible while others (e.g. A5/1) are not, but even in the non-reversible case, the expected number of preimages is always one[1], so in practice you can attempt to 'work backwards', storing all possible ancestors. The number of ancestors you need to store tends to grow linearly, but this can be sufficient to make an attack practical.

The attack on A5/1 by Biryukov et al. (html version at https://cryptome.org/a51-bsw.htm) uses this idea.

[1] Averaged over all states, for any fixed transition function.

Improve this answer
$\endgroup$
2
  • $\begingroup$ There are stream ciphers for which the number of possible previous states is not always one. For example, any non-synchronous stream cipher (e.g. CFB, Helix) likely has several possible previous states and you need the ciphertext (or at least the plaintext) to be able to tell which it was in. $\endgroup$
    – otus
    Commented Jul 15, 2016 at 10:23
  • $\begingroup$ One can certainly design a stream cipher where there is no practical way to 'work backwards'; for example, one where the state update function involves: $S_{i+1} = SHA256(S_i)$. In practice, consider a crypto rng that has "backtracking resistance" (which involves a state update with similar properties to what I listed) $\endgroup$
    – poncho
    Commented Jul 16, 2016 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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