With reference to this question:

First, when using padding (PKCS or OAEP), if the ciphertext has errors in transmission we'll always get an error at the decryption process?

where the answer is:

Yes, with extremely high probability. This is basically a chosen-ciphertext attack and RSA-OAEP is fully immune to them, so the odds that you won't detect this attack (a.k.a. "error") are extremely low (below $2^{−128}$).

May I know how the $2^{−128}$ is computed? Is it true for RSA 1024 and 2048 bits?

Some Finding

With reference to https://tools.ietf.org/html/rfc3447, Chapter "3. EME-OAEP decoding", point g(as below):

g. Separate DB into an octet string lHash' of length hLen, a (possibly empty) padding string PS consisting of octets with hexadecimal value 0x00, and a message M as

DB = lHash' || PS || 0x01 || M.

If there is no octet with hexadecimal value 0x01 to separate PS from M, if lHash does not equal lHash', or if Y is nonzero, output "decryption error" and stop. (See the note below.)

For the implementation of openssl, SHA1 is used and SHA1 is 20 bytes and implies the length of lHash(and lHash') is 20 bytes. Therefore, I will suggest that the probability of error rate is below $2^{−160}$. Can anyone have some contribution on this? thanks.


From the source code for openssl(https://docs.huihoo.com/doxygen/openssl/1.0.1c/rsa__oaep_8c_source.html), the RSA_padding_check_PKCS1_OAEP(), line 152, it codes as below. I believe it is checking for if lHash does not equal lHash', or if Y is nonzero. Can anyone have a view on this? thanks.

if (memcmp(db, phash, SHA_DIGEST_LENGTH) != 0 || bad)

  • 1
    $\begingroup$ See the paper en.wikipedia.org/wiki/Optimal_asymmetric_encryption_padding $\endgroup$ – kelalaka Dec 27 '20 at 14:06
  • 1
    $\begingroup$ That probability stands for RSA-OAEP with an at-least 128-bit hash, and random ciphertext. It follows from counting how many ciphertexts pass the verification step. It does not apply for malicious replacement of the ciphertext, which is a real possibility in any unauthenticated public-key encryption. $\endgroup$ – fgrieu Dec 27 '20 at 16:05
  • $\begingroup$ @kelalaka Is Wikipedia a paper? $\endgroup$ – Maarten Bodewes Dec 27 '20 at 22:40
  • $\begingroup$ @MaartenBodewes nope, It is on the first line :) $\endgroup$ – kelalaka Dec 27 '20 at 22:41
  • 1
    $\begingroup$ Note that I've asked CHL to ask it here. I don't see any particular calculation that is immediately apparent from the PKCS#1 standard, at least as far as I can see. $\endgroup$ – Maarten Bodewes Dec 27 '20 at 22:43

In OAEP we pad the message with $k_1$ zero bits and $k_2$ random bits. It's the zero bits which give you verification. The all or nothing gurantee means if you change anything you will flip all bits with probability 0.5 and the chances of getting $k_1$ zero bits by chance is 1 over $2^{k_1}$

  • $\begingroup$ Thanks Meir Maor. But what is the length of k1? $\endgroup$ – CHL Dec 28 '20 at 9:27
  • $\begingroup$ Neither OAEP nor PKCS specify specific sizes they are designed to work with different size messages, different size hashes and different size RSA keys. $\endgroup$ – Meir Maor Dec 28 '20 at 14:07
  • $\begingroup$ For the standard PKCS#1 OAEP padding(v2.0), do you know how many size of the k1? $\endgroup$ – CHL Dec 29 '20 at 1:44

Though I've given answer in your previous question. Here it is more simplified.

  • r is a random k0-bit string and length of RSA modulus is n bits.
  • Now length of zero padding bits k1 = n- k0
  • An expansion function E(r) expands r to n-k0 bits. then take xor with msg padded with 0s.
  • ${X=m00..0 \oplus E(r)}$,
  • Now a compression function ${C(X)}$ reduces ${X}$ to k0 bits.
  • ${Y=r \oplus C(X)}$
  • ${Output = X || Y }$

Can be decoded as:

  • ${r = Y \oplus C(X)}$
  • The message as: ${m00..0 = X \oplus E(r)}$
  • $\begingroup$ Thanks SSA for the explanation $\endgroup$ – CHL Jan 6 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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