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?

Improve this question
$\endgroup$
3
  • 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
    Commented Jul 9, 2015 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
    Commented Jul 9, 2015 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
    Commented Jul 9, 2015 at 20:15

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
4
  • $\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
    Commented Jul 9, 2015 at 20:21
  • $\begingroup$ Yeah, that's about it. $\endgroup$
    – Maarten Bodewes ♦
    Commented Jul 9, 2015 at 20:23
  • $\begingroup$ Actually this isn't accurate, so I'm adding a different answer. $\endgroup$
    – Yehuda Lindell
    Commented Jul 9, 2015 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 Bodewes ♦
    Commented Sep 8, 2015 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).

Improve this answer
$\endgroup$
4
  • $\begingroup$ Sorry, but isn't that the same as saying that CBC is not secure because you might reuse the IV? $\endgroup$
    – Maarten Bodewes ♦
    Commented Jul 9, 2015 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
    Commented Jul 9, 2015 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
    Commented Jul 10, 2015 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
    Commented Jul 11, 2015 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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