If we encrypt a message $m$ as $m || H(m)$ using textbook RSA encryption algorithm, $H$ is random oracle modeled. In this case the message can be recovered.
Is this encryption CCA secure? If so how can we prove it or not?
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.Sign up to join this community
CCA security assumes CPA security, and $m || H(m)$ is not CPA secure. This is simple to show: say that $C = E(m || H(m))$ is known, then an adversary can simply guess $m'$ and encrypt that. Then $C' = C$ will show the adversary that $m'=m$.
To show a CCA attack you can use this attack. You can of course replace the value $2$ in that question with $y$ where $y = x || H(x)$ for any $x$. In that case you end up with $z \cdot m || H(m)$ after decryption. Calculating $m || H(m)$ will then just consist of division with $z$.
To avoid this it is of vital important that the signature is over data protected by randomized padding, and that this randomization is well distributed over the input to the RSA exponentiation. This is what OAEP does with the MGF(1) padding.
Alternatively a hybrid scheme such as RSA-KEM combined with a block cipher could be used.
Deterministic encryption cannot be fully CPA or CCA secure; some kind of randomness or at least uniqueness is required to be CPA / CCA secure to not leak information for repeated messages.