The Marvin Onslaught is a recent side-channel incursion on cryptographic implementations of RSA, involving the decryption of previously captured ciphertext by monitoring server response times to specifically crafted messages over a network. The attacker can also falsify signatures using the same key employed for decryption. Red Hat unveiled the principles and technical background of the Marvin Onslaught in September of 2023.

Following the revelation, numerous other susceptible implementations have been identified, and fixes have been implemented. It is important to note that many Common Vulnerabilities and Exposures (CVEs) affecting applications using OpenSSL have only received temporary solutions, not extensive fixes. If such applications are paired with hardware security modules (HSMs) or smart cards (PKCS #11 tokens), they may still remain exposed.

Recommended Steps

As the addressing has primarily focused on the most critical and frequently encountered scenarios (vulnerabilities in TLS servers, vulnerabilities in software implementations), the general advice is to cease using RSAES-PKCS1-v1_5 altogether. At a minimum, refrain from its usage in any online contexts.

For those employing hardware implementations with RSA keys (HSM or smart cards), a thorough audit of the complete solution to identify side-channel attacks is strongly advised. Ensure that RSAES-PKCS1-v1_5 padding is neither used nor accepted by applications.

Consequently, existing software using RSA should undergo an audit and transition to leveraging the OAEP encryption mode, discontinuing the utilization of the PKCS #1 v1.5 padding mode.

Context and Historical Background

A few years ago, Hanno Böck, Juraj Somorovsky, and Craig Young introduced the ROBOT Attack against TLS servers utilizing the RSA key exchange, which relies on RSAES-PKCS1-v1_5 padding internally. None of the core cryptographic libraries within Red Hat Enterprise Linux (RHEL) (such as OpenSSL, NSS, and GnuTLS) were found to be vulnerable to ROBOT. Nonetheless, there were indications that other forms of side-channel attacks could be plausible.

Side-channel attacks target the implementation rather than the mathematical foundations of a cryptographic algorithm. These attacks exploit additional information about the operation being targeted, such as electromagnetic fluctuations from the CPU, transient power usage of the system, or, in the instance of the Marvin Onslaught, the time duration of the operation.

Side-channel assaults on RSA have existed almost since the inception of the RSA cryptosystem itself, dating back to the description by Paul Kocher in 1996. The specific attack concerning RSA decryption with PKCS #1 v1.5 padding was disclosed by Daniel Bleichenbacher two years later. Over the following 25 years, numerous other exploits on this fundamentally flawed padding have been documented, with the Marvin Onslaught being the latest iteration.

Key Aspects of the Marvin Onslaught

Before the exposure of the Marvin Onslaught, most research on remote (network-based) side-channel attacks struggled to detect minor differences in response times when faced with noisy measurements.

Given the various sources of noise in a remote network-based attack (e.g., packet routing, CPU frequency fluctuations, and operating system thread scheduling), the widespread belief was that detecting small side-channel leaks (on the scale of 100 nanoseconds) over the network was unfeasible. Consequently, minor leakage was deemed acceptable, even in network contexts where a leaky implementation was utilized.

Regrettably, this presumption was founded on flawed testing methods. Through investigations on the Marvin Onslaught, it was unearthed that employing statistical best practices during testing (utilizing a double-blind setup with appropriate statistical tests designed for non-independent measurements) allowed for the detection of timing differences as minuscule as single CPU cycles (roughly 0.2 nanoseconds) over the network. This implies that any degree of leakage could potentially facilitate a timing-based Bleichenbacher attack.

Susceptible Configurations

The inherent flaw in RSAES-PKCS1-v1_5 padding stems from the fact that the errors it produces provide the attacker with the exact information essential for executing a Bleichenbacher attack.

Error leakage can manifest in two areas: within the cryptographic library offering the API and within the application employing the API. This implies that even if the cryptographic library correctly implements the padding and outputs errors devoid of side-channel leaks, any application that branches or performs memory accesses contingent on the error returned will inadvertently leak pertinent details to the attacker through response timing (even if the response denoted is “close connection”).

It was discovered that a majority of cryptographic implementations circulated in RHEL displayed some form of leakage, including OpenSSL, NSS, Go, Linux Kernel, libgcrypt, and Java. Only the GnuTLS implementation exhibited immunity at the API level, albeit still featuring leakage at the TLS layer. This immunity was attributed to efforts undertaken by Red Hat upstream in the Nettle cryptography library to tackle CVE-2018-16868, discovered post-inspection due to CAT, a local cache side-channel attack.

Collaboration with OpenSSL, NSS, and GnuTLS projects facilitated the rectification and validation of fixes for the vulnerability. The Linux kernel exclusively deploys its RSA implementation for verifying the integrity of .ko modules, thus eliminating the necessity for signing or decryption support. While endeavors were made to address the issue in libgcrypt, the upstream project exhibited reluctance in accommodating the rectifications. As of the current date (June 6, 2024), it is improbable that this issue will be redressed within the library.

Upon scrutinizing implementations utilizing the RSAES-PKCS1-v1_5 padding, hardware devices with PKCS #11 drivers that conduct the private key operation in hardware but execute the RSAES-PKCS1-v1_5 padding verification in software were identified. Such instances include OpenSC and openCryptoki.

Furthermore, all applications leveraging the OpenSSL RSA decryption API in RHEL (i.e., applications invoking RSA_private_decrypt() or EVP_PKEY_decrypt() functions) were audited. These evaluations revealed that applications employing these functions with RSAES-PKCS1-v1_5 padding were utilizing them incorrectly. Safeguarded applications exclusively employed these APIs with Optimal Asymmetric Encryption Padding (OAEP).

Incorrect implementations could be categorized into two primary classes: applications directly employing the API (e.g., iperf3, cjose, xmlsec1, and more) and language frameworks or interfaces (.NET, Node.js, perl-Crypt-OpenSSL-RSA, PHP, python-cryptography, Ruby, among others).

Although applications interfacing directly with the API could theoretically be rectified in a backward-compatible manner, language runtimes and OpenSSL wrappers would necessitate altering the APIs exposed to applications. This poses a challenge as it impedes the backporting of changes to RHEL owing to the modifications required for third-party applications. This complication arises from the prevalent approach in high-level languages of handling errors by triggering an exception.

Marvin Workaround

Given the prevalence of vulnerable implementations and the intricate nature of effecting fixes at the application tier, an implicit rejection algorithm for the RSAES-PKCS1-v1_5 padding has been devised and subsequently backported as a workaround in response to the Marvin Onslaught.

By confining sensitive data within the cryptographic boundary to shield it from external entities, users of the API can be shielded against arbitrary errors in the application code. Under normal circumstances, when an implementation endeavors to decrypt a random ciphertext, there exists a non-negligible likelihood that the ciphertext will decrypt to a random message. Leveraging this characteristic facilitates the API to consistently yield a random message. Through deterministic behavior concerning a specific ciphertext and private key pair, the attacker is unable to differentiate between ciphertexts featuring invalid padding and those genuinely containing the extracted message.

However, for this algorithm to be operational, the code must possess access to the private key to guarantee the unpredictability of the returned random message. In scenarios where the implementation lacks access to the private key parameters (e.g., if the key is housed in an HSM or smart card), deploying the algorithm in the driver or library granting access to the HSM or smart card becomes unfeasible.

Applications are effectively shielded only when interacting with an implementation featuring implicit rejection (such as the pure software implementation in OpenSSL).

Future Endeavors

In light of the challenges associated with the RSAES-PKCS1-v1_5 padding, the RHEL Crypto team ponders the prospect of deprecating it. Future iterations of RHEL may default to not supporting it (akin to RHEL 9’s default stance on avoiding SHA-1 in signatures).

For applications mandatorily reliant on this padding and incapable of abolishing its use, efforts are underway to standardize the Marvin workaround through an IETF RFC document.

Source: Red Hat Marvin Attack