# What are the possible CCA attacks on RSA with r||m+G(r) as the padding?

I was trying to come up with simple padding functions for the RSA, then trying to break them just to have a better understanding of why we need all the pieces used in the RSA OAEP... So, I am considering the following.

Let $$N = p\cdot q$$, $$pk = e$$ and $$sk = d$$ be the RSA parameters and keys, as usual.

Now, let $$n = \lceil \log_2 N \rceil$$ be the number of bits of $$N$$ and $$k < n$$ be some extra parameter controlling the padding. Let $$G:\{0,1\}^k \rightarrow \{0,1\}^{n-k}$$ be some mask generating function. Then, define the padding as sampling a random value $$r$$, computing $$G(r)$$ and xoring it with the message, then concatenating $$r$$ with the result of the xor. That is,

Padding $$P: \{0, 1\}^{n-k} \rightarrow \{0, 1\}^n$$ of a message $$m$$

1. Sample $$r$$ uniformly from $$\{0, 1\}^k$$
2. Compute $$u := G(r) \oplus m$$ (bit wise XOR)
3. Output $$r + 2^k \cdot u$$ (this is the same as $$r || (G(r) \oplus m)$$, i.e., concatenation)

Then, to encrypt a message $$m \in \{0, 1\}^{n-k}$$, we would output $$c = P(m)^e \bmod N$$, that is, padding then usual RSA encryption.

Now, let's say that the decryption just takes $$c$$ and tries to output $$m$$. That is, $$Dec: \mathbb{Z}_N \rightarrow \{0, 1\}^{n-k}$$ is

1. Compute $$x = c^d \bmod N$$
2. Compute $$r' = x \bmod 2^k$$
3. Compute $$u' = (x - r') / 2^k$$
4. Compute $$G(r')$$
5. Output $$u' \oplus G(r')$$

It is clear that if $$c$$ is a valid ciphertext, then the decryption is correct. But for a ciphertext encrypting something that does not correspond to a valid padding, the output will be a somewhat random message, but the decryption is always well-defined.

Now, I was wondering how one can use a decryption oracle to mount an attack that shows that this padding plus RSA is not CCA2-secure.