Present an attack for the combination of OTP and textbook RSA

Question

• Let $N=p \times q$ where $p$ and $q$ are two primes.
• Compute $\Phi (N) = (p-1)(q-1)$.
• Choose $e$ s.t. $1 < e < \Phi(N)$ and $gcd(e,\Phi(N))=1$.
• Compute $d = e^{-1}(mod \ \Phi(N))$.
• Set $pk = (N, e)$ and $sk = (N, d)$.
• Let $m \in Z_N$ be a plaintext message. A random $r \in Z_N$ is selected, such that $|r|=|m|$, and the plaintext $m$ is encrypted: $E_{pk=(N,e)}(m; r) = ((m \oplus r), (r^e\ mod\ N))$.

Present an attack against this scheme assuming the weakest possible attacker capabilities.

I couldn't think of any easy attack here. The random key for the OTP is encrypted using textbook RSA, and aside for the "usual" textbook RSA attacks, I don't see anything special in this scheme that can be attacked. This is a question from a past exam, so I don't think the meaning is to simply state the known textbook RSA attacks. Any help would be appreciated.

Answer 1

This scheme follows the KEM/DEM approach of contructing secure asymmetric encryption schemes. However for a KEM/DEM PKCS (public key cryptosystem) to be secure it is required that both the key encapsulation mechanism (KEM) and the data encapsulation mechanism (DEM) are CPA or CCA secure for CPA or CCA of the whole scheme.

Indeed the DEM looks CPA secure as it is an OTP. The KEM scheme may be CPA secure, but I can't prove it now. Somebody else may be able to do this though. However the whole scheme isn't CPA secure as pointed out by Yehuda Lindell in the other answer.

But neither of the part is CCA secure. I'll present two attacks breaking this scheme by attacking the KEM and the DEM in isolation.

Attack 1: Breaking the DEM

The DEM is basically a simple OTP. Now let's assume you're given the ciphertext $c=(u,v)$ to be broken. First choose a random $s$ and construct $c'=(u\oplus s,v)$. Note that $c'\neq c$ so asking the decryption oracle for decryption of $c'$ is valid. Obtain the decryption $m'$ of $c'$ using you decryption oracle. Note that $m'=(m \oplus r \oplus s) \oplus r=m \oplus s$, now finally obtain the message $m=m'\oplus s$. You have successfully broken the DEM in a chosen ciphertext attack.

Attack 2: Breaking the KEM

The KEM is simple textbook RSA. However interaction is a bit more tricky here but still quite simple. Let's again assume you're given a ciphertext $c=(u,v)$ to decrypt. Now choose a random $s$ again and construct the ciphertext $c'=(t,v\cdot s^e\bmod N)$ with $t$ being a random message, note again that $c\neq c'$ so asking for the decryption of $c'$ is totally valid. Ask your decryption oracle for the decryption of $c'$ and learn the corresponding message $t'$. Note that $t\oplus t'=r'=r\cdot s$. Finally reconstruct the original $r=(t\oplus t')\cdot s^{-1} \bmod N$ and reconstruct the message as $m=u\oplus r$. You have now successfully broken the KEM.

So you see that this scheme is totally flawed in a chosen ciphertext setting and message recovery is quite easy.

Answer 2

Sorry, I would only give partial points for a CCA attack on this scheme. The answer by @SEJPM is of course correct (and very informational so it's good it was posted). However, it is not the "best" answer, since this scheme can be easily broken under a chosen-plaintext attack. I will not write the full answer out (so that I can leave some work to be done for the exercise). I will just note that given a ciphertext of the form $(c_1,c_2)$ and a guess $m$ for the plaintext, it is easy to verify whether or not $(c_1,c_2)$ encrypts $m$. This can be achieved by computing $(c_1 \oplus m)^e \bmod N$ and comparing it to $c_2$. Note that if this ciphertext indeed encrypts $m$, then $c_1 \oplus m=r$ where $c_2=r^e \bmod N$. Thus, this works. I'll leave it as an exercise to translate this into a "formal" CPA attack. However, note that this is completely broken in practice (and is not just a theoretical attack).

An interesting note: if you encrypt by $(H(r) \oplus m,r^e \bmod N)$ then it's CPA-secure in the random-oracle model. So, another warning that slight changes to schemes can completely break them.