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

Click for the previous part.

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.




def oracle(c):
    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 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-
    if (EVP_PKEY_decrypt_init(ctx) <= 0
            || EVP_PKEY_CTX_set_rsa_padding(ctx, RSA_PKCS1_WITH_TLS_PADDING) <= 0) {
        goto err;

( ssl/statem/statem_srvr.c )

All the files used.

(the post first published at 20230123, updated 20240510.)

List of my other blog posts.

Subscribe to my news feed

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.