11
$\begingroup$

My latest question and especially Ricky Demer's comment on the answer got me thinking: This homomorphic tranformation of RSA is most likely IND-CPA and maybe even IND-CCA1, but if it could be IND-CCA1, so could be a stream cipher in theory. This is especially interesting if you consider RSA-KEM paired with an unauthenticated stream cipher. Practically this would most likely also imply a simple standard construction for an XOR-homomorphic IND-CCA1 cryptosystem. This would also imply a post-quantum secure IND-CCA1 scheme with a partial homomorphism: McEliece as a KEM paired with a stream cipher (which is basically McBits minus the authentication).

So the question naturally follows:
Are common (unbroken) stream ciphers CCA1-secure?
Or formulated differently if CCA1-security isn't a thing: Are stream ciphers secure against non-adaptive chosen ciphertext attacks?

With "common" stream ciphers I mainly mean secure block ciphers in CTR mode and cipher such as ChaCha20 and Salsa20/20.

$\endgroup$
  • $\begingroup$ This answer may be of tangential interest though much of the discussion is about CCA2 / adaptive attacks. $\endgroup$ – puzzlepalace Mar 27 '17 at 18:29
9
$\begingroup$

Let's consider CTR mode encryption with a random IV for a block cipher (essentially the same as stream cipher, but simpler to analyze since the formalization of stream cipher security is not fully standardized). On the one hand, it seems like it should be CCA1-secure since there is nothing that an attacker can do in the CCA1 queries that can help later. Specifically, assuming that the IV is chosen at random, then the chance that a decryption query used that IV is negligible.

Of course, the above isn't enough since one needs to prove a reduction from the CCA1 security to CPA security. I think this is provable, but without writing a full proof I'm not sure, and I'll leave that to you. The way I would work is as follows:

  1. If an encryption query is received, then use the CPA oracle
  2. If a decryption query is received, then: if the query uses an IV that was previously received from an encryption query, then it's easy to compute the message (you know the plaintext/ciphertext so you know the "pad"); if the query does not use an IV that was previously received from an encryption query, then return a random value.
  3. After the CCA1 phase, then the CPA adversary just forwards everything unchanged.

If a later encryption query (or the challenge ciphertext) by chance has the same IV as a prior decryption then the simulation by the CPA adversary fails. However, this happens with only negligible probability.

So, overall, I think that this proof would work, and so yes, such schemes are CCA1 secure.

$\endgroup$
  • $\begingroup$ I read this answer as suggesting that under the model of stream ciphers used for block ciphers in CTR mode, IND-CPA security implies IND-CCA1 security. I disagree. Proof sketch: I exhibit a small variant of CTR that's secure under CPA but not CCA, by making the block cipher output the key specifically when the input block is all-zero (decryption no longer works for the block cipher, but it still works for the stream cipher). Under the CCA1 game, the key is recovered by submitting a ciphertext with zero IV and first block; while the stream cipher is still demonstrably IND-CPA. $\endgroup$ – fgrieu Mar 28 '17 at 5:58
  • 2
    $\begingroup$ @fgrieu I did not claim that all stream-cipher type modes have the property that CPA implies CCA1. I merely claimed that for CTR with random IV, I believe that it does. Your counterexample does not change this. $\endgroup$ – Yehuda Lindell Mar 28 '17 at 8:44
  • $\begingroup$ I fully agree with the claim in the second sentence of the above comment, and the fact in the third. What I still do not get is the answer's proof sketch that CTR mode with random IV is IND-CCA1. I read it as starting from the established fact that this stream cipher is IND-CPA, and trying to prove IND-CCA1 from that; I accordingly read "the CPA oracle" in the answer's 1 and 3 as any hypothetical CPA attack algorithm against the stream cipher, that is being tentatively upgraded into a CCA1 attack algorithm. Doesn't my counterexample prove this can't be done? $\endgroup$ – fgrieu Mar 28 '17 at 10:17
  • $\begingroup$ @fgrieu The place that this appears is (implicitly) due to the fact that decryption queries for IVs that didn't appear in the past are answered as random. $\endgroup$ – Yehuda Lindell Mar 28 '17 at 10:24
9
$\begingroup$

For stream ciphers, IND-CCA1 and IND-CPA security differ precisely in that an attacker can choose the IV in the CCA1 game (because that's part of the ciphertext that can be submitted to the decryption oracle); but in the CPA game is constrained to whatever choice of IV the cryptosystem makes.

We can artificially construct a stream cipher vulnerable under CCA1, but not under CPA: consider AES-128 in CTR mode with random IV, except that the AES encryption block is modified so that for all-zero input block, the output block is the key. Decryption no longer works for the block cipher, but it still works for the stream cipher (albeit differently when the counter is initialized to all-zero, or reaches that). Under the CCA1 game, an adversary recovers the key by submitting to the decryption oracle a ciphertext with all-zero IV and first block of ciphertext; while there's no way to take advantage of the modified block cipher under the CPA game, and the stream cipher remains secure (the adversary has negligible odds to get the IV to reach zero, thus the stream cipher is indistinguishable from true CTR mode, which is IND-CCA1).

For a less artificial example, we can hypothesize a block cipher vulnerable to key recovery under CPA, but not under random Known Plaintext Attack. That weakness directly makes the derived CTR or OFB stream cipher vulnerable under CCA1, but not under CPA.

Thus if there was a block cipher vulnerable to key recovery under CPA but not random KPA, with the corresponding CTR or OFB stream cipher common, that would be a common stream cipher not IND-CCA1, answering the question in the negative.

However I know no common stream cipher that's vulnerable under CCA1. Much to the contrary, modern native stream ciphers like ChaCha20 and Salsa20/20 aspire and appear to be IND-CCA1. And modern block ciphers are believed secure under CPA, and their corresponding CTR stream cipher is accordingly believed IND-CCA1 (just as claimed in that other answer, even if I fail to follow it's proof sketch).

$\endgroup$
  • 1
    $\begingroup$ My understanding from the question is whether or not common stream ciphers have this property, not whether it's possible to construct a counter example. $\endgroup$ – Yehuda Lindell Mar 28 '17 at 8:46
  • $\begingroup$ @Yehuda Lindell: I agree on your reading of the question, and that I fail to answer it in the negative. The closer I get is that if there was a block cipher vulnerable to key recovery under CPA but not KPA, and if the corresponding CTR or OFB stream cipher was common, that would allow answering the question in the negative. $\endgroup$ – fgrieu Mar 28 '17 at 10:59

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.