## [Crypto][Python] D.Bleichenbacher attack on RSA PKCS#1, part IV

The real situation is even worse. The problem is not in the PKCS#1 1.5 padding. The problem is that the attack can be used on any message that has fixed header, 'magic cookie'. Think about HTML/XML header, etc.

Here I extended by code to handle a message with 8-bit header. It must be zero. Such messages are not uncommon.

...

m_lower_bound=gmpy2.mpz(0x0001000000000000)
m_upper_bound=gmpy2.mpz(0x00FFFFFFFFFFFFFF)

...

def oracle(c):
d=gmpy2.mpz(4911287298007382225)
assert isinstance(c, gmpy2.mpz)
plaintext=pow(c, d, n)
plaintext_b=int(plaintext).to_bytes(length=BITS//8, byteorder="big", signed=False)
return plaintext_b[0]==0 # first byte is zero

...


It will offer 3 possible plaintexts:

...
Found! upper:
00000000: 00 90 CA D8 D8 DE DE DE                           ........
...
Found! upper:
00000000: 00 D9 30 45 45 4E 4E 4D                           ..0EENNM
...
Found! upper:
00000000: 00 48 65 6C 6C 6F 6F 6F                           .Hellooo
calls_to_oracle 1107


Only ~1k calls to oracle. The code.

Even if you don't know first byte value, you can just enumerate them all -- just 256 cases. This is easily doable.

Some people say this attack can be extended to just one bit in header. Not uncommon -- first character of Latin plaintext has highest zero bit.

What about mitigations? PKCS#1 1.5 must not be used at all. Think about RSA-OEAP at least. And of course, a remote server or a device must not leak information about such padding errors. About errors at all.

The 'textbook RSA' must not be used at all, only for learning.

More radical approach is to get rid of RSA completely and switch to ECC. Because RSA is so easy to misuse. However, some cryptographers say that ECC has its own problems.

Mitigation in OpenSSL -- just be silent and pretend it was decrypted incorrectly.

 * Added and enabled by default implicit rejection in RSA PKCS#1 v1.5
decryption as a protection against Bleichenbacher-like attacks.
The RSA decryption API will now return a randomly generated deterministic
message instead of an error in case it detects an error when checking
padding during PKCS#1 v1.5 decryption. This is a general protection against
issues like CVE-2020-25659 and CVE-2020-25657. This protection can be
disabled by calling
EVP_PKEY_CTX_ctrl_str(ctx, "rsa_pkcs1_implicit_rejection". "0")
on the RSA decryption context.


( CHANGES.md )

    /*
* We must not leak whether a decryption failure occurs because of
* Bleichenbacher's attack on PKCS #1 v1.5 RSA padding (see RFC 2246,
* section 7.4.7.1). We use the special padding type
* RSA_PKCS1_WITH_TLS_PADDING to do that. It will automatically decrypt the
* RSA, check the padding and check that the client version is as expected
* in the premaster secret. If any of that fails then the function appears
* to return successfully but with a random result. The call below could
* still fail if the input is publicly invalid.
* See https://tools.ietf.org/html/rfc5246#section-7.4.7.1
*/
if (EVP_PKEY_decrypt_init(ctx) <= 0