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
|| EVP_PKEY_CTX_set_rsa_padding(ctx, RSA_PKCS1_WITH_TLS_PADDING) <= 0) {
SSLfatal(s, SSL_AD_DECRYPT_ERROR, SSL_R_DECRYPTION_FAILED);
goto err;
}
( ssl/statem/statem_srvr.c )
Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.