The Marvin Attack

The Marvin Attack is a new side-channel attack on cryptographic implementations of RSA in which the attacker decrypts previously captured ciphertext by measuring, over a network, server response times to specially crafted messages. The attacker also may forge signatures with the same key as the one used for decryption. Red Hat published the principles and technical background of the Marvin Attack in September of 2023.

Since that time, we have identified lots of other vulnerable implementations and have shipped fixes. Note that most of the CVEs in applications that use OpenSSL have only received workarounds, not complete fixes. If such applications are used with hardware security modules (HSMs) or smart cards (PKCS #11 tokens), they may still be vulnerable.

Recommended actions

Since we have addressed only the most pressing and most common use cases (vulnerabilities in TLS servers, vulnerabilities with software implementations), the general recommendation is to stop using RSAES-PKCS1-v1_5 entirely. At the very least, stop using it in any online contexts.

If you use hardware implementations with RSA keys (HSM or smartcards), we strongly recommend auditing the complete solution for side-channel attacks, and verifying that RSAES-PKCS1-v1_5 padding is not used or accepted by applications.

As such, deployed software that uses RSA should be audited and changed to use the OAEP encryption mode, disabling the use of the PKCS #1 v1.5 padding mode.

Background and history

A few years ago Hanno Böck, Juraj Somorovsky and Craig Young published the ROBOT Attack against TLS servers that used the RSA key exchange, which internally depends on RSAES-PKCS1-v1_5 padding. None of the core cryptographic libraries in Red Hat Enterprise Linux (RHEL) (OpenSSL, NSS and GnuTLS) turned out to be vulnerable to ROBOT. As pointed out by Böck, the tool we have developed for testing TLS servers (tlsfuzzer) was one of the few tools able to test for the old Bleichenbacher vulnerability on which ROBOT was based.

They pointed out that other types of side-channel attacks may be possible though.

Side-channel attacks are a kind of attack on cryptography that do not attack the mathematical underpinnings of the algorithm, but rather the concrete implementation of it. The name refers to the fact that they use extra information about the operation attacked, like electromagnetic noise generated by the CPU, momentary power use of the computer, or, as in the case of the Marvin Attack, the amount of time the operation takes.

Side-channel attacks on RSA are almost as old as the RSA cryptosystem itself, being first described by Paul Kocher in 1996. The attack specifically on RSA decryption with PKCS #1 v1.5 padding was published by Daniel Bleichenbacher two years later. For the next 25 years, dozens of other attacks on this fundamentally broken padding have been published. The Marvin Attack is the latest variant of them.

What is new in the Marvin Attack?

Until the publication of the Marvin Attack, most of the existing research into remote (network-based) side-channel attacks had problems identifying small differences in the timing of responses in the presence of noisy measurements.

Since there are multiple sources of noise in a remote network-based attack (such as packet routing, CPU frequency scaling, and operating system thread scheduling), the consensus was that small side-channel leakage (on the order of 100 ns) was not detectable over the network. Thus, small leakage was considered to be acceptable, even if the leaky implementation was used in a network context.

Unfortunately, that assumption was based on incorrect testing. During work on the Marvin Attack we have discovered that when the testing is performed according to the statistical best practice (in a double-blind setup, with statistical tests that work with measurements that are not independent), differences in the timing of responses as small as single CPU cycles (i.e., on the order of 0.2 ns) can be detected over the network. That means that any level of leakage can be used to perform a timing-based Bleichenbacher attack.

Vulnerable implementations

The reason why RSAES-PKCS1-v1_5 is a bad padding in practice is because the errors it returns are precisely the information that the attacker needs to perform the Bleichenbacher attack.

Error leakage can happen in two places: in the cryptographic library that provides the API and in the application that uses the API. This means that even if the cryptographic library implements it correctly and returns errors in a side-channel-free way, if the application using the library does any kind of branching or memory lookups that depend on the error being returned, the information useful to the attacker will leak to the attacker through timing of the response (even if that response is “close connection”).

We have discovered that most cryptographic implementations shipped in RHEL still had some level of leakage, including OpenSSL, NSS, Go, Linux Kernel, libgcrypt and Java. Only the GnuTLS implementation turned out to be immune on the API level, but it still had leakage in the TLS layer. This was thanks to work done by Red Hat upstream in the Nettle cryptography library to address CVE-2018-16868 reported after code inspection spurred by CAT, a local cache side-channel attack.

We’ve worked closely with OpenSSL, NSS and GnuTLS projects to fix and verify the fixes for the vulnerability. Linux kernel uses its implementation of RSA only for verifying integrity of the .ko modules, thus doesn’t need support for signing or decryption, so the fix was to remove support for those operations. We also tried to fix this issue in libgcrypt, but the upstream project has not been receptive to our attempts at fixing it. As such, at the time of writing (6th of June 2024) we don’t expect that this issue will be addressed in this library.

While looking for implementations of the RSAES-PKCS1-v1_5 padding, we also found PKCS #11 drivers that perform the private key operation in hardware, but then perform the RSAES-PKCS1-v1_5 padding check in software. Those include OpenSC and openCryptoki.

We have also audited all the applications that use the OpenSSL RSA decryption API in RHEL (i.e., applications that may call the RSA_private_decrypt() or EVP_PKEY_decrypt() functions) and have verified that all the applications that use these functions with RSAES-PKCS1-v1_5 padding use those functions incorrectly. The only ones that turned out to be safe use those APIs with Optimal Asymmetric Encryption Padding (OAEP) exclusively.

The incorrect uses can be split up into two main categories: applications that use the API themselves (iperf3, cjose, xmlsec1, and so on) and language frameworks or wrappers (.NET, Node.js, perl-Crypt-OpenSSL-RSA, PHP, python-cryptography, Ruby and so on).

While applications that use the API directly, in theory, can be fixed in a backward-compatible manner, for language runtimes and OpenSSL wrappers, it generally means changing the API they expose to the applications. That is not a good solution as it means we cannot backport it to RHEL as it would require changes to third party applications. This is because the common pattern for handling errors in those high-level languages is to raise an exception.

Marvin workaround

Given the number of vulnerable implementations and the complexity of implementing fixes at the application layer, we’ve decided to implement and then backport a workaround in the form of an implicit rejection algorithm for the RSAES-PKCS1-v1_5 padding.

As the leak occurs outside the cryptographic libraries, by containing the sensitive information inside the cryptographic boundary we can make the users of the API safe against arbitrary errors in the application code. In normal operation, when an implementation tries to decrypt a random ciphertext, there is a non-insignificant chance that the ciphertext will decrypt to a random message. We can use this fact to make the API always return a random message. By making it deterministic for a given ciphertext and private key pair, the attacker won’t be able to differentiate between ciphertexts that have invalid padding and ciphertexts that genuinely contain the returned message.

Unfortunately, for this algorithm to work, the code must have access to the private key to make the returned random message unpredictable. If the implementation doesn’t have access to the private key parameters (for example, if the key is stored in an HSM or a smart card), then it’s not possible to implement it in the driver or library providing access to the HSM or smart card.

Applications are effectively protected only when they use an implementation with implicit rejection (like the pure software implementation in OpenSSL).

Future work

Given all the problems with the RSAES-PKCS1-v1_5 padding, the RHEL Crypto team is considering deprecating it. Future RHEL versions may not support it by default (similarly to the RHEL 9 default of not using SHA-1 in signatures).

For applications that absolutely cannot deprecate the use of this padding, we are working on standardizing the Marvin workaround in an IETF RFC document.