Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
This is essentially an all-or-nothing transform. –  CodesInChaos Nov 16 '12 at 23:12

2 Answers 2

up vote 6 down vote accepted

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

share|improve this answer

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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.