RSA OAEP Error Detection Probability

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?

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)

• Dec 27 '20 at 14:06
• 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.
– fgrieu
Dec 27 '20 at 16:05
• @kelalaka Is Wikipedia a paper? Dec 27 '20 at 22:40
• @MaartenBodewes nope, It is on the first line :) Dec 27 '20 at 22:41
• 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. 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}$$

• Thanks Meir Maor. But what is the length of k1?
– CHL
Dec 28 '20 at 9:27
• Neither OAEP nor PKCS specify specific sizes they are designed to work with different size messages, different size hashes and different size RSA keys. Dec 28 '20 at 14:07
• For the standard PKCS#1 OAEP padding(v2.0), do you know how many size of the k1?
– 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)}$$
• Thanks SSA for the explanation
– CHL
Jan 6 '21 at 2:55