Cryptography
- cryptanalysis padding oaep
- 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.