Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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
1  
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". –  owlstead Sep 6 '13 at 22:23
add comment

1 Answer

up vote 5 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
add comment

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.