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$
- Sample $r$ uniformly from $\{0, 1\}^k$
- Compute $u := G(r) \oplus m$ (bit wise XOR)
- 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
- Compute $x = c^d \bmod N$
- Compute $r' = x \bmod 2^k$
- Compute $u' = (x - r') / 2^k$
- Compute $G(r')$
- 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.
