4
$\begingroup$

A stream cipher usually generates a stream of pseudo-random bits which get XORed with the plaintext to form the ciphertext. The stream is generated using a given IV / nonce and a secret key. CTR-mode for block ciphers is usually described as turning a block cipher into a stream cipher.

It is now widely known that the CTR-mode of operation provides IND-CPA security. Katz proves this in his book.

Does this result imply that all stream ciphers are IND-CPA?

$\endgroup$
  • 3
    $\begingroup$ I think I am missing something here. Vigenere cipher is a stream cipher, but obviously not IND-CPA as it fails even more basic security definitions. What am I missing about your question? $\endgroup$ – mikeazo Jul 9 '15 at 19:58
  • $\begingroup$ @mikeazo, I think the (implicit) assumption you're questioning is: "The pad generator is assumed to be strong" Or maybe it's even enough to say that the vigenere cipher didn't use an IV / nonce? $\endgroup$ – SEJPM Jul 9 '15 at 20:01
  • $\begingroup$ okay, I can buy the "vigenere cipher didn't use an IV/nonce" explanation. I still think there would have to be some basic security assumptions you would have to place on the stream cipher to make the implication. The theorem in the book assumes $F$ is a pseudorandom function, but that is for the block cipher. $\endgroup$ – mikeazo Jul 9 '15 at 20:15
7
$\begingroup$

No.

There is a difference between the type of a cipher and the construction of a cipher. If a cipher is of a specific type for which there are known IND-CPA secure constructions then that doesn't mean that an entirely different construction is secure. There are known attacks on stream ciphers, including "modern" stream ciphers such as RC4.

A stream cipher must be used correctly for the encryption scheme to be IND-CPA secure.

If the generated key stream is secure then the XOR of the plaintext with the key stream will of course also be secure (up to the specified limits of the stream cipher anyway).

$\endgroup$
  • $\begingroup$ So if the underlying construction is sufficiently secure (like AES or SHA-256 running in some trusted mode like CTR/HKDF), a stream-cipher can be IND-CPA although not all stream-ciphers are "by definition" IND-CPA as their construction can be flawed (-> RC4)? $\endgroup$ – SEJPM Jul 9 '15 at 20:21
  • $\begingroup$ Yeah, that's about it. $\endgroup$ – Maarten - reinstate Monica Jul 9 '15 at 20:23
  • $\begingroup$ Actually this isn't accurate, so I'm adding a different answer. $\endgroup$ – Yehuda Lindell Jul 9 '15 at 22:37
  • $\begingroup$ Amended answer indicating that the stream cipher must be used correctly after reading through the answer & remarks of Yehuda Lindell. $\endgroup$ – Maarten - reinstate Monica Sep 8 '15 at 13:49
3
$\begingroup$

No. Indeed, as in the answer by Maarten, it depends on the security and strength of the stream cipher. However, even if the stream cipher is a secure pseudorandom generator (which is its proper modeling), encryption is not necessarily CPA-secure when XORing the pad with the plaintext. This is also explained in great detail in Katz-Lindell.

In fact, it is only guaranteed to be eavesdropping-secure due to the problem of pad reuse (for a real attack that used this, see this paper - The Misuse of RC4 in Microsoft Word and Excel).

$\endgroup$
  • $\begingroup$ Sorry, but isn't that the same as saying that CBC is not secure because you might reuse the IV? $\endgroup$ – Maarten - reinstate Monica Jul 9 '15 at 22:53
  • 1
    $\begingroup$ No, because a basic stream cipher does not necessarily even have an IV (at least, historically this was the case). For example, when encrypting a session, no IV is needed since "synchronized mode" is used. I admit that we are possibly arguing about semantics more than anything else... $\endgroup$ – Yehuda Lindell Jul 9 '15 at 22:58
  • $\begingroup$ So for security I'd require: "If the scheme has an IV, no known (good) cryptanalytic attacks against the pad generator and the advesary is IV / nonce respecting, then and only then is the scheme IND-CPA"? $\endgroup$ – SEJPM Jul 10 '15 at 18:38
  • $\begingroup$ First I would like a proper modeling of the stream cipher. Are you assuming that it generates a new pseudorandom stream for every unique IV, or for random IVs only? This is just one example... $\endgroup$ – Yehuda Lindell Jul 11 '15 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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