RSA OAEP Error Detection Probability

Question

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://www.rfc-editor.org/rfc/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.

P.S.

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)

Answer 1

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}$

Answer 2

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)}$