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.

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

Most descriptions that explain how streamciphers work (like the one on Wikipedia), tend to describe a model that boils down to a simple “$ciphertext = plaintext \oplus stream$”, where the stream is determined by a nonce and a key, while the plaintext and ciphertext do not affect the stream at all.

On the other hand, streamcipher designs like Helix* seem to ignore the usual approach as their stream depends on the plaintext… reasoning that this approach adds authentication.

My personal feel is, that the dependence on plaintext has a good chance to introduce additional attack vectors (chosen plaintext attacks etc.). Looking at the potential downsides, it’s a bit unclear to me if I’m missing something. Maybe there are other reasons or arguments – besides the authentication aspect – which might support the idea of ignoring the regular streamcipher model, and I’m not seeing them.

Is there anything else to be gained by making the stream depend on the plaintext? If, what are the other potential advantages (besides gaining authentication) of making the stream depend on the plaintext, compared to the more frequently used “$ciphertext = plaintext \oplus stream$” approach?

*Helix: Fast Encryption and Authentication in a Single Cryptographic Primitive” by Ferguson, Whiting, Schneier, Kelsey, Lucks, Kohno


Nota Bene: In his “Salsa20 Design” paper on page 4, Bernstein asks an alike question – ”Should the stream be independent of the plaintext?” – and argues against it. But he merely argues about the authentication part of things and nothing else… which doesn’t really help when trying to learn about the potential benefits such a construction might have besides the debated authentication aspect.

share|improve this question
up vote 5 down vote accepted

Most advantages have to do with the fact that it includes authentication. For example:

  • An authenticated encryption primitive is easier to use correctly.
  • Only a single primitive that has to be secure.
  • One pass over the data to both encrypt and authenticate may be faster. (Bernstein's rebuttal is that a separate MAC allows faster detection of forgeries, mitigating denial of service attacks.)

There is one potential benefit I can think of that isn't related to authentication, but it should never come into play if you are using the cipher securely:

  • A plaintext dependent keystream may recover from IV collisions.

This is similar to how a block cipher in CFB mode can be secure after the first block, even with duplicate IVs, if the plaintext differs.

share|improve this answer

It is incorrect that Wikipedia does not mention other stream ciphers than the synchronous ones. It also mentions asynchronous ones (that is, where the keystream depends on the previous ciphertexts -- and thus, the previous plaintext) together with associated advantages: this allows re-synchronisation of the sending and receiving end. Additionally, an asynchronous stream cipher might help concealing the underlying plaintext redundancies or format (e.g., network packets, ASCII, etc).

The asychronous stream ciphers described in Wikipedia however only capture the so-called stream ciphers with finite memory. There are also ones with infinite memory which comprises those providing authentication mechanisms -- such as Helix (stream ciphers with finite memory do not).

Note that the synchronous stream ciphers are susceptible to a number of attacks directly due to the lack of authentication, e.g. plaintext can be manipulated by an attacker in a predictable way such as flipping bits, inserting bits, deleting bits (even without knowing the underlying plaintext), so that the authentication feature cannot be regarded as a simple gadget only.

Finally, the mixing of plaintext into the internal state surely offers opportunities for attacks: such an attack was mounted against Helix by Frédéric Muller and is the rational behind the proposal of Phelix. But these issues can be mitigated (such as in Phelix) by slowly mixing the plaintext chunks into a state of much bigger size and ensuring rapid diffusion and confusion with the key, together with careful extraction from the internal state.

share|improve this answer
1  
Why would it conceal plaintext better? A perfect (normal) stream cipher should already conceal it completely. – otus Jul 18 '14 at 21:13
    
Nope: if you have ASCII text encrypted with, say, RC4, it is straightforward for an attacker, to e.g. uppercase all lowercase letters. This would not happen with Helix for instance. Also note I never wrote "conceal plaintext" but rather conceal the structure of the underlying plaintext (redundancies or format)... This is heavily relied upon in practice by attackers and is among the reasons why the keystream is assumed to be available to attackers in the attack models for stream ciphers. – bob Jul 18 '14 at 21:32
3  
@bob, oh you mean prevent changing instead of finding out? In that case, sure, but any authentication would also guarantee that. – otus Jul 18 '14 at 21:38
    
@otus For the auhtentication, exactly what I said in the third paragraph of my answer: "due to the lack of authentication". Also note that asynchronous stream ciphers help concealing the underlying structure even if they do not provide authentication (as I said, not all asynchronous stream ciphers provide authentication, e.g. the self-synchronizing ones are asynchronous but do not provide full authentication such as the one provided by Helix/Phelix). – bob Jul 18 '14 at 21:41

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.