# Why is padded RSA not CCA-secure?

Why is the padded RSA construction given in the picture not CCA secure？

• Possible duplicate of Is the standard scheme of RSA CCA and CPA secure? – user2313067 Mar 28 '16 at 11:58
• short answer: it lacks a failure condition (i.e. a condition under which decryption fails). long answer to follow. – SEJPM Mar 28 '16 at 13:04
• One obvious additional issue is that with $l(n)=2n-2$ (where $n$ is the number of bits in each of the prime factors of $N$), there remains almost no room for randomness in $r$. – fgrieu Mar 29 '16 at 11:09

The (CCA-related) problem of this padding scheme is that it lacks a failure condition, i.e. a ciphertext which a decryption oracle will refuse to decrypt.

Now first for the chosen ciphertext attack which exploits RSA's homomorphic property. Assume you want to decrypt a ciphertext $c$ that is the encryption of $m$ which is encrypted properly according to the above procedure. Assume further you have a decryption oracle which won't decrypt $c$ itself.

First you chose a random integer $1<k<N$ yourself. Next you compute $c'=k^e\cdot c \bmod N$. You send $c'$ (which clearly isn't $c$) to the decryption oracle and get $m'$ in return. You compute $(r||m)=m'\cdot k^{-1} \bmod N$ and unpad the result as in the original decryption procedure.

As was noted by poncho in the comments of this answer, my above attack assumes, that the decryption oracle will give you the full message back and not just the lower $l(n)$ bits.

To fix this we'll apply an attack I like to call "hard-core predicate attack". It bases on the fact (as can be found in Katz' and Lindell's Introduction to modern Cryptography) that the least significant bit of a RSA encrypted message is a hard-core predicate. In the book the authors outline an attack to recover a full RSA message, given only an oracle that tells them whether the message corresponding to the queried ciphertext is even. Using this method we can recover the full blinded message $m'$ using polynomially many decryption queries and afterwards proceed with the above attack. For simplicity of the description I'll assume the decryption oracle only yields the least significant bit.

First, we determine whether the current least significant bit of $m$ is $0$.
If yes, then we know the least significant bit and multiply the ciphertext with $2^{-e}\bmod N$ (which shifts the message to the right by one bit) and continue from the start.
If no, then we know the least significant bit and multiply the ciphertext with $2^{-e}\bmod N$, the second least significant bit is then the negated XOR of the least significant bit of the new ciphertext and the second least significant bit of the modulus.

• Of course you don't need this property if the "message" is a secret key which is then used for e.g. authenticated encryption. In that case the authenticated decryption will act as the oracle, e.g. see RSA-KEM (which disposes of the padding as well). – Maarten Bodewes Mar 28 '16 at 13:51
• Actually, the decryption oracle doesn't give you $m'$, but instead only the lower $\ell(n)$ lower bits. How do you compute $m' \cdot k^{-1}$? – poncho Mar 28 '16 at 14:24