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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.