2
$\begingroup$

The heart of OAEP algorithm used for RSA encryption are the cryptographic hash functions $H$ and $G$.

Does everybody (so also an adversary) know these functions?

  • If YES: How does it help the security, if he just can decode the padding and read the message?

  • If NO: What knowledge is needed for these functions? Are keys or something priorly exchanged? Are they related to the receivers private key?

$\endgroup$

1 Answer 1

6
$\begingroup$

Well, yes, everyone (or, at least, everyone who can use the public key) knows the hash function H and G; so we can assume that an adversary knows them as well.

You ask:

If YES: How does it help the security, if he just can decode the padding and read the message?

Well, he can't decode the padding; the ciphertext has been encrypted using RSA, and he doesn't have the private key; so he can't get at the padded version.

Here's how OAEP works; you take the plaintext message $m$ to send, you pick a random value $r$, and compute the function:

$Padded = OAEP(m, r)$

(with H and G as parts of OAEP). Then, once we have that, we encrypt it using the base RSA public operation (using the public key):

$Ciphertext = RSA(PublicKey, Padded)$

The $Ciphertext$ is what's actually sent; because it is encrypted using RSA, the attacker cannot recover $Padded$.

So, if the OAEP operation doesn't prevent an attacker from decrypted the ciphertext in this straightforward manner, why is it there at all?

Well, raw RSA has some nastly properties (called an homeomorphic property), namely:

$RSA(k, A) \times RSA(k, B) = RSA(k, A\times B)$

(where $\times$ is implicitly modulo the public key modulus).

Because of this property, using raw RSA to directly encrypt plaintexts is almost always the wrong thing to do; there are clever ways to use this homeomorphic property to recover plaintext.

What the OAEP function does is try to mimic a random function between plaintexts and padded versions; because we present the raw RSA operation with effectively random texts, these homeomorphic properties are no concern.

$\endgroup$
3
  • $\begingroup$ For some reason I thought, the padding is done AFTER the message was encrypted! Now it makes sense. Thanks a lot for the detailed explanation! $\endgroup$
    – schrobe
    Commented May 16, 2013 at 22:36
  • $\begingroup$ How the legal receiver gets rid of the pad if he doesn't know the $r$? It just spits the $#pad$ bytes? That implied a public knowledge of the pad length. $\endgroup$
    – curious
    Commented Dec 17, 2013 at 9:58
  • $\begingroup$ @curious: the $OAEP$ function is designed to be invertable; however it does assume that the length of $r$ is publicly known. $\endgroup$
    – poncho
    Commented Dec 17, 2013 at 15:01

Your Answer

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

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