Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
2  
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
    
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. – Luis Casillas Jul 15 at 18:57
up vote 6 down vote accepted

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.

share|improve this answer
1  
@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? – poncho Sep 6 '13 at 22:15
3  
@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
1  
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

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.

share|improve this answer
    
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. – otus Jul 15 at 10:23
    
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) – poncho Jul 16 at 19:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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