Cryptography
Updated Sat, 04 Jun 2022 21:27:58 GMT

# OAEP Cryptanalysis

If $M_1$ and $M_2$ are $\operatorname{OAEP}$ padded, encrypted and sent and an adversary somehow manages to get around the encryption and retrieve $\operatorname{OAEP}(M_1) \oplus \operatorname{OAEP}(M_2)$, would it be possible to retrieve either $M_1$ or $M_2$ without any prior knowledge of $M_1$ and $M_2$?

## Solution

No, knowledge of $$\operatorname{OAEP}(M_1)\oplus\operatorname{OAEP}(M_2)$$ does not disclose information about plaintexts $$M_1$$ or $$M_2$$. In particular it does not allow to recover either, even with full knowledge of the other. More generally, it does not help predict any efficiently computable function of $$M_1$$ and $$M_2$$.

The reasons lie in the definition $$\operatorname{OAEP}(M_j)=(\operatorname{MGF}(R_j)\oplus\operatorname{Pad}(M_j))\mathbin\|(H(\operatorname{MGF}(R_j)\oplus\operatorname{Pad}(M_j))\oplus R_j)$$ where $$R_j$$ is a fresh random. It follows that knowledge of $$\operatorname{OAEP}(M_1)\oplus\operatorname{OAEP}(M_2)$$ only gives \begin{align} &\operatorname{MGF}(R_1)\oplus\operatorname{MGF}(R_2)\oplus\operatorname{Pad}(M_1)\oplus\operatorname{Pad}(M_2)\quad\text{ and}\\ &H(\operatorname{MGF}(R_1)\oplus\operatorname{Pad}(M_1))\oplus H(\operatorname{MGF}(R_2)\oplus\operatorname{Pad}(M_2))\oplus R_1\oplus R_2 \end{align} which does not allow to reconstruct either $$R_1$$ or $$R_2$$, even with full knowledge of $$M_1$$ and $$M_2$$. And then with $$R_1$$ and $$R_2$$ unknown, we have nothing to connect knowledge about $$M_1$$ and $$M_2$$. This handwaving argument could be made rigorous under the hypothesis that $$\operatorname{MGF}$$ and $$H$$ behave as random functions.