RSA-CCA security of $m || H(m)$ as input to modular exponentiation

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?

• It isn't even CPA secure.... – SEJPM May 4 '18 at 16:08

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.

• Also there is a general result that a public key encryption operation must be randomized in order to be CPA secure... – SEJPM May 4 '18 at 17:53
• Anything missing from my answer, pinofer? – Maarten Bodewes May 9 '18 at 15:01