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:
- Ask for encryptions and decryptions of two messages $m_0, m_1$.
- Send these to the challenger.
- 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.