Why does OAEP have 2 rounds with 2 random oracles?

Question

I strive into understanding why OAEP has two rounds of computations and not just one. I.e: Wouldn't it be safe to hash the random number r and XOR it with the original message?What security risks if any that padding scheme violates?

Answer 1

This variant of OAEP would be malleable if the underlying trapdoor permutation is malleable, and hence would not be chosen-ciphertext secure. This is a major theoretical weakness, as I explain below, and one that may lead to attacks in practice.

In more detail, suppose $G$ is the (lone) hash function and $f$ is trapdoor permutation used, so the formula for the encryption algorithm of this variant of OAEP is $$f(m\oplus G(r)\|r).$$ Suppose you have are given the output of the encryption algorithm (call it $y$) for some unknown message $m$. If $f$ is malleable, it may be feasible to come up with $y'$ that is an encryption of $m$ with a bit flipped, meaning $$y' = f(m'\oplus G(r)\|r)$$ for $m'$ equal to $m$ with a bit flipped. If one obtains a decryption of $y'$ (as is allowed in a chosen-ciphertext attack) then one learns $m'$ and hence $m$.

The extra round of OAEP is to ensure that such ciphertexts decrypt to unrelated messages that do not help an attacker. You may want to look at SAEP and SAEP+ [1] for some more results on one-round variants of OAEP that are secure.

[1] D. Boneh. Simplified OAEP for the RSA and Rabin functions. In proceedings of Crypto '2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp. 275-291, 2001

Answer 2

Adding to David Cash's answer, besides SAEP and SAEP+ by Boneh, there is another paper that improves OAEP using only a one-round Feistel structure and has an additional feature: redundancy-free encryption (which none of OAEP, SAEP and SAEP+ have). Read Verified Security of Redundancy-Free Encryption from Rabin and RSA by Barthe, Poitcheval and Beguelin (2012).