In three different, highly reputable sources (e.g. "Introduction to Modern Cryptography" by Katz and Lindell, 2007), the definition of CCA attack doesn't allow the adversary to decrypt the challenge, but also doesn't require the adversary to send never-before seen messages.

I'm assuming that this is a mistake, and that the CCA security definition is supposed to disallow the replay of previously seen messages as well (seeing as that would be equivalent to asking for their decryptions)? Or is there a subtlety I'm missing?

If it is indeed allowed to send previously seen messages, then I don't see why the following is not a simpler CCA attack for Rabin than the one described in this post:

  1. Ask for encryptions and decryptions of two messages $m_0, m_1$.
  2. Send these to the challenger.
  3. Compare $Enc(m_b)$ to saved decryptions of $m_0$,$m_1$.

Even if random padding is added, we can look at the deterministic part of the decryptions.

  • $\begingroup$ Here our Canonical Q/A for this. Easy explanation of "IND-" security notions? and Don't forgot that there was a name change in the history on CCAs. And, your good! highly reputable sources need a link here. $\endgroup$
    – kelalaka
    Aug 16, 2022 at 10:00
  • $\begingroup$ @kelalaka Thanks. So if I understand correctly, CCA (as it appears in "Introduction to Modern Cryptography" by Katz and Lindell, 2007) is actually IND-CCA1 in your link, and that it DOES allow replaying messages and therefore my Rabin attack is valid? $\endgroup$
    – Anon
    Aug 16, 2022 at 10:11
  • $\begingroup$ Correction: I can actually see the book's description matches IND-CCA2, but I'm still doubting whether I got this right, i.e. under IND-CCA2, is the adversary indeed allowed to replay m_i rendering the above attack valid? $\endgroup$
    – Anon
    Aug 16, 2022 at 10:27
  • 1
    $\begingroup$ It is not clear how one can look at the deterministic part of the decryptions? $\endgroup$
    – kelalaka
    Aug 16, 2022 at 12:37
  • 1
    $\begingroup$ Padding (or a nonce for symmetric systems) is applied before encryption, not after. Since each bit of the plaintext influences every bit of the ciphertext (any IND-CPA secure cryptosystem will exhibit this "avalanche" property) changing the padding will randomize the entire ciphertext. There are no "padding bits" in the ciphertext. ALL the bits are random. $\endgroup$ Aug 17, 2022 at 17:37


Your Answer

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