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

As far as I know, all stream ciphers work by generating a stream of pseudo random bytes, and XOR it with the plain text to get the cipher text. It has the property that one bit change in the cipher text results only the corresponding bit change in the decrypted message.

Is there any stream cipher that has the avalanche effect, where one bit change in the cipher text will result about half of the bits changed in the decrypted message after the corresponding bit?

share|improve this question
    
Your description of avalanche effect is a bit off. Usually it is a single bit change in the clear text which causes cascading changes in the cipher text, not the other way around. There are modes which have this cascading effect in both encryption and decryption, but usually it is not a desirable property, so many modes don't have it in both directions. – kasperd Jan 31 at 11:13
    
Perhaps you want format-preserving-encryption. – CodesInChaos Jan 31 at 14:55
    
@kasperd, PCBC mode has the effect on both directions, but there's problem on block swapping. For modes that turns a block cipher into a stream cipher, I'm not aware of any that has this avalanche effect. – Wu Yongzheng Feb 1 at 3:44
    
@WuYongzheng, every bit would have to depend on the previous bit, so the stream cipher would be incredibly slow. Real stream ciphers act on bytes (RC) or larger blocks at a time (e.g. ChaCha). In that case you cannot make the next bit change, only the following blocks. – otus Feb 1 at 7:50
    
@otus, In both RC4 and ChaCha, changing one input byte doesn't affect later output bytes. – Wu Yongzheng Feb 1 at 8:31

A stream cipher, by definition, acts on individual bits at a time. This effectively means that bits later in the plaintext cannot affect bits around the beginning of the ciphertext. It can, however, feed the ciphertext back into the state of the PRNG to affect all future bits. This can be seen in the CFB (Cipher Feedback) block cipher mode. It acts similarly to a stream cipher, in that each ciphertext bit can be drawn one at a time, but they feed back into the system to affect all future bits.

share|improve this answer
    
I think acting on a bit at a time doesn't mean a bit cannot affect later bits. It can have state. Are you suggesting applying block cipher mode to stream cipher? How does it work exactly? By the way, in CFB, a bit change in ciphertext results only two blocks of plaintext changed, not all future bits. – Wu Yongzheng Jan 31 at 7:47
    
"I think acting on a bit at a time doesn't mean a bit cannot affect later bits. It can have state." That's what the second half of my answer is about. "Are you suggesting applying block cipher mode to stream cipher?" No, I'm saying there are block cipher modes which act like stream ciphers. "By the way, in CFB, a bit change in ciphertext results only two blocks of plaintext changed" Yes, but a bit change in the plaintext affects all future ciphertext blocks, just not the other way around. – Daffy Jan 31 at 7:58
2  
To clarify the significance of stream ciphers acting on bits at a time, my point here is that it's impossible for stream ciphers to go back in time to change bits they've already outputted. – Daffy Jan 31 at 8:04
    
CBC and CFB only have this cascade effect at encryption time. There is no cascading effect when decrypting. Also one need to be careful when streaming data with an encryption mode not designed to be used as a stream cipher. SSL has had security problems due to using CBC in ways it wasn't designed for. Due to the similarity of CBC and CFB I could imagine a similar attack being possible, though I must admit that on my first attempt I wasn't able to make the attack work against CFB. – kasperd Jan 31 at 11:42

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.