Are common (secure) stream ciphers CCA1-secure?

Question

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.

Answer 1

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.

Answer 2

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).