The Marvin Attack is a return of a 25 year old vulnerability that allows performing RSA decryption and signing operations as an attacker with the ability to observe only the time of the decryption operation performed with the private key.
In 1998, Daniel Bleichenbacher discovered that the error messages given by SSL servers for errors in the PKCS #1 v1.5 padding allowed an adaptive-chosen ciphertext attack; this attack fully breaks the confidentiality of TLS when used with RSA encryption. In 2018, Hanno Böck, Juraj Somorovsky, and Craig Young have shown 19 years later that many internet servers were still vulnerable to slight variations of the original attack.
We show that many implementations previously thought immune, are vulnerable to the timing variant of the same attack.
While the main venue of attack are TLS servers, the core issues that caused its wide spread are applicable to most asymmetric cryptographic algorithms (Diffie-Hellman, ECDSA, etc.), not just to RSA. Lessons learned are also applicable to testing the majority of cryptographic algorithms that can be vulnerable to side-channel attacks, not just public key cryptography.
For a vulnerable implementation the attacker is able to decrypt RSA ciphertexts and forge signatures.
For a TLS server that defaults to RSA encryption key exchanges, that means the attacker can record a session and decrypt it later.
For TLS hosts that use forward secure ciphersuites, the attacker would have to perform a massively parallel attack to forge a server signature before a client would time out during the connection attempt. That makes the attack hard, but not impossible.
The attack is also applicable to other interfaces that perform RSA decryption in automated manner but don't provide the attacker ability to perform arbitrary operations with the private key. Examples include S/MIME, JSON web tokens, or hardware tokens (HSMs, smartcards, etc.).
We have identified the vulnerability in multiple implementations and confirmed fixes in few of them, but belive that most of cryptographic implementations are vulnerable in practice.
We also found few APIs that are handling errors or numbers in a way that will be vulnerable to timing attacks.
| Go | crypto/rsa DecryptPKCS1v15SessionKey | limited leakage1 |
| GNU MP | mpz_powm_sec | leaks zero high order bits in result |
Finally, so far, we have verified just two implementations that were not vulnerable when tested in at least one environment:
| BearSSL 0.6 | Intel i9-12900KS @ 5.225 GHz, x86_64, Friedman test negative (p-value=0.152, n=22.2M, k=36), 95% confidence interval for 25% trimmed mean of pairwise differences: ±466ps. |
| BoringSSL (6 Sep 2023, TLS) | Intel i9-12900KS @ 5.225 GHz, x86_64, Friedman test negative (p-value=0.074, n=17.3M, k=36), 95% confidence interval for 45% trimmed mean of pairwise differences: ±574 ps. |
| rustls 0.21.9 (TLS) | no support for TLS_RSA_* ciphersuites (inherently not vulnerable) |
Implementations not listed above have either not been tested or have been verified as vulnerable, but the issues are still embargoed. We will continue updating the lists as we learn of new vulnerabilites or once embargoes are lifted.
We have provided tools to detect the issue both on TLS server level and help with testing on API level.
If you use one of the affected implementations, you should install the relevant updates. However we are reiterating the previous recommendations:
On the TLS level, only servers that enable RSA encryption are affected. Most modern clients support the use of Elliptic Curve Diffie Hellman, thus disabling ciphersuites that use RSA encryption is the recommended way to fix this vulnerability.
Older clients will be able to use Finite Field Diffie Hellman, which will be secure as long as server uses fresh DHE key shares for every connection (protection against the Raccoon attack) and well known parameters (or safe primes in general) for the general protection against cryptologic attacks. Both of those things are trivial to check for and verify compared to testing, let alone fixing, the issues in the RSA key exchange.
While cryptographic protocols and formats allow, and have defaulted to use of the PKCS#1 v1.5 padding, they either don't need it any more for interoperability (like TLS), or have been updated to support RSA-OAEP (S/MIME, JWT, etc.). If your software or hardware doesn't allow use of RSA-OAEP, pressure the vendor to fix it.
Our recommendation is similar: deprecate and disable support for PKCS#1 v1.5 padding for encryption. While we do provide a way to handle errors in a way that should be compatible with any API and not leak the information relevant to the Bleichenbacher attack to the calling application we recommend against its use.
We have had 25 years of people trying to patch this fundamentally broken padding mode. ROBOT have shown that the far easier workaround was implemented incorrectly by a large number of implementations. Implementing the Marvin workaround correctly is much more tricky, as it must include actually testing it for side channel leakage.
While we focus on PKCS#1 v1.5, the vulnerability is not limited to just that mode, any RSA padding mode can be attacked if blinding is not implemented using side-channel free code, or conversion from numerical representation to a byte-string is not made using side-channel free code. You should verify that the deblinding operation and conversion to byte-string is side-channel free also with RSA-OAEP and RSASVE interfaces. Only when you're able to confidently verify that they are side-channel free, we would suggest looking into making PKCS#1 v1.5 side-channel free.
Finally, we don't believe that this is limited to RSA itself, any implementation that uses general purpose integer implementation (like the default mode of OpenSSL's BIGNUM, NSS's MPI, Java's BigInteger, Python's int, Rust's apint, Gnu MP's mpz_t, Go's math/big Int, etc.) will suffer from the same issues. Given that there are attacks that exploit high order bits being zero in other algorithms, like Minerva against ECDSA and Raccoon attack against FFDH (attack against ECDH works fundamentally the same way, it just requires higher precision of the timing side-channel), any cryptographic implementation that depends on general purpose integer arithmetic library will be similarly vulnerable. See the mpn interface of GNU MP for an example of an interface well suited for side-channel free programming.
We have released a script for testing TLS servers as well as instructions on how to execute it. It's very reliable (i.e. if it reports a vulnerability, there's by default a 1 in 100 thousand chance that it's a false positive) unless it's executed with --static-enc option, or executed against a server that implements a Marvin workaround.
In case the server implements the Marvin workaround (implicit rejection), you can verify that that code is implemented correctly using either the TLS based test script, or, in case you're testing the API directly, a script to generate decryption inputs.
Upon execution the script reports the p-value of sign tests and Friedman test. If they're consistently small or very small (smaller than 10-9) then it's extremely likely that the tested implementation is vulnerable.
For testing APIs, we've also prepared few scripts to make testing them easier in the marvin-toolkit repo.
Please note that to exclude the possibility of a side channel the test needs to report a 95% confidence interval for bootstrapped differences of around a nanosecond and the statistical tests need to still be negative (have p-values larger than 10-5). In practice that means collecting a data set of at least few million connections.
While we can't give general instructions, as any fixes depend on where the leak happens and how the code is implemented, we wrote a separate article about debugging the code with the use of the tlsfuzzer tooling in the Debugging Timing Side-channel Leaks article.
Everlasting ROBOT:
the Marvin Attack. local [PDF]
Hubert Kario
(pre-print)
28th European Symposium on Research in Computer Security,
The Hague, Netherlands, September 25-29, 2023
More: Cryptology ePrint Archive mirror
Out of the Box Testing
[PDF]
Hubert Kario
More: Cryptology ePrint Archive mirror
The previous comprehensive attack against RSA was called ROBOT. Given the complexity and fragility of required fixes we don't believe that this attack will generally go away. Thus we named it after an android that lasted till the end of the universe in The Hitchhiker's Guide to the Galaxy.
For the complete details, see our full technical paper.
In technical terms, the Marvin Attack is not new, both vulnerabilities to timing side-channels and vulnerability of RSA PKCS#1 v1.5 padding in general were known already in the 1990's. The main contribution we bring is related to how to test for side channel timing leakage in a way that provides high accuracy, high precision (if provided with large data set), and thus very low false positive rate. Additionally, because we measure the whole end-to-end operation, by performing a complete TLS handshake, we're able to find issues in places other than the low level numerical calls (e.g. the GnuTLS vulnerability was in code that was making a decision about what kind of error message to print if debugging mode was enabled) and able to test different implementations relatively easily and quickly.
In other words, we got results because we were thorough, not because we used novel techniques.
No. While it is a fundamental flaw in the RSA decryption, it has been widely known that padding errors need to be handled in constant time. But because of the complexity of implementing it in practice, every implementation will likely have a slightly different bug in the code.
Yes. We’ve been able to execute the attack against M2Crypto and pyca/cryptography in just a couple of hours in a normal environment on a mid-range laptop. Estimating the practically of attacks on TLS servers is more complex as it critically depends on the key sizes used, CPU model of the victim, hardware and OS configuration, the RSA implementation in question, and how closely to the server can the attacker co-locate the probe measuring the response times. For an attacker that can get access to a host connected to the same network switch as the victim, a worst case scenario (for the victim) would require a few days to perform the attack against a vulnerable version of OpenSSL and couple of hours to attack NSS.
No. While previously the general consensus was that very small side channels, on the order of a few hundred nanoseconds, were not considered to be exploitable, that was based on flawed testing.
All statistical tests make some assumptions about tested data. The most common assumption is that the compared samples are Independent and Identically Distributed (IID). That assumption is also central to the Box Test, Kolmogorov-Smirnov test and Mann-Whitney U test. In practice, we haven't found that the timing data was independent, in fact, for many tests of independence, just a few hundred observations were sufficient to absolutely exclude that possibility. For context, to get precise measurements we commonly need thousands to millions of measurements, so the lack of independence will affect large samples only more.
Since the requirements of the test were not met, it gave incorrect results and thus incorrect conclusions from it were drawn.
In our approach to testing, we use paired difference tests which require idependence of the differences within pairs of measurements, not measurements themselves. That property is much easier to achieve if we have complete control over the executed test (in which order the individual connections are executed), and is met for the collected data.
By using this kind of tests (sign test, Wilcoxon signed-rank test, bootstrapping of the median of paired differences, etc.) we were able to both show no false positives for very large samples in practice (hundreds of millions of observations) and the ability to detect very small differences in timing, in the order of a few CPU clock cycles, even when measuring across a production network, a few kilometers away, and 6 router hops between victim and attacker.
In other words, the size of the side channel affects only how many observations will the attacker need to perform, not if they will be able to measure the difference at all.
Also, because the paired difference tests require consistent environment only within each pair, parallelization of the attack is trivial.
While we have no reason to believe that the Marvin Atttack has been exploited in the wild prior to this disclosure, the original ROBOT attack did suggest that timing variants of the vulnerability may also be possible. Since the details of the vulnerability are now public, attackers may start exploiting it at any time, and we recommend taking the countermeasures explained above as soon as possible.
Indeed, while problems with RSA PKCS#1 v1.5 padding have been known for over 25 years, and just as long we had alternatives in form of RSA-OAEP, protocol and format designers valued backwards compatibility over inheritent security of better options. While protocols like S/MIME (a.k.a CMS) also date from that era, protocols like JSON Web Tokens have been concieved well after RSA PKCS#1 v1.5 was known to be hard to implement correctly, yet included it anyway. We need to go to standards as new as WebCrypto to find standards that omit this bad padding completely.
The other is complacency of implementers and protocol designers in considering that there are side channels that are "too small to be detectable". Best illustrated by subsequent versions of TLS, that included more and more complex workarounds for the attacks against ciphersuites with CBC padding and RSA key exchange, only to finally remove them completely in TLS 1.3.
No. At least, not universally. Both OpenSSL and NSS bugs were in the numerical library, not in the padding or error reporting code. That code is shared between all padding modes, be it PKCS#1 v1.5, OAEP, or RSASVE. As such, any decryption operation will leak the same kind of information, and thus can be used to attack messages encrypted with any padding method.
Only RSA-OAEP implementations that use constant-time mathematical library (specifically, constant-time code for deblinding and converstion of the large precision integer to a byte string), and ignore the value of the first byte of padding will not be vulnerable to the Marvin attack.
No. The Marvin Attacks allows an attacker to decrypt one ciphertext (connection) or sign a message at a time. The attacker does not learn the server’s private key.
Yes, but not easily. If the server supports RSA key exchange and is vulnerable to the Marvin Attack it's possible to forge a signature on an arbitrary message, including a ServerKeyExchange in TLS 1.2 or CertificateVerify in TLS 1.3. The difficulty is that both of those signatures include a random value selected by a client. Thus the signature needs to be forged before the connection times out on the client side. In practice that means that the attacker will need to attack multiple servers at once, all of which will need to provide quite clear timing signal.
Probably not. As the attacker does not learn the server’s private key, there’s no need to obtain new certificates. While continued use of the same key is necessary for the attacker to be able to decrypt previous sessions, if the server doesn't enable RSA encryption ciphersuites the attack is impossible either way.
Yes. While there is nothing practical that web browsers or other client software can do to prevent the Marvin Attack on TLS servers. The WebCrypto in Firefox does support RSA-OEAP decryption operation that is vulnerable (CVE-2023-5388), as such you should install Firefox 124 or Firefox ESR 115.9.0 to fix that.
Possibly. If you run a server and can be certain no one made a large number of connections that attempted RSA key exchange to any of your servers (for example, by examining IDS or server logs), then you weren’t attacked. Your logs may contain a small number of RSA key exchange connections from the Internet-wide scans or very old clients. In best case scenario an attack requires tens of thousands of connections per decryption.
Yes. FIPS certification for cryptographic modules doesn't require robust testing of side-channel protections. Only on Level 4 certification are protections against side-channel attacks mandatory.
Unfortunately, no. Although SSLLabs provides an invaluable suite of security tests, right now it only checks whether your HTTPS server directly allows RSA key exchange. You’re just as much at risk if your site’s certificate or key is used anywhere else on a server that does support RSA. Common examples include SMTP, IMAP, and POP mail servers, and secondary HTTPS servers used for specific web applications.
Sort of... while we have already released the tlsfuzzer scripts to check if a server is vulnerable or not (i.e. tool to run a single oracle call), and a toolkit to make testing APIs easier, we do not plan to release a complete attack script.
Testing for constant-timeness is hard. While there exists a multitude of tools to do that, their usability is not conducive to them being used by developers or researchers.
Any tool that requires code annotations to work is also subject to user error.
The other factor is the disregard of small side-channels, for example, in TLS 1.2 specification we read:
This leaves a small timing channel, since MAC performance depends to some extent on the size of the data fragment, but it is not believed to be large enough to be exploitable, due to the large block size of existing MACs and the small size of the timing signal.RFC5246
While indeed the first CVEs were assigned in 2020, the last major fixes were performed in 2023. This was caused by two problems: first is that we were struggling with false positives caused by the timing signal generated by the harness (test script), and that caused the other issue. Because of unreliable results it was hard to pinpoint the particular cause for the timing signal and without that, it was hard to convince upstream developers to work on the issue. Only when we created a constant-time test harness were we able to move forward with fixes (and that happened in the middle of 2022).
Yes. If you'd like to see if side-channel attacks are easy to perform against particularly vulnerable services, or how introduction of a network between the attacker and the victim impacts the statistical tests, or even try to implement simple password comparison using side-channel free code, we have published a blog post with relevant resources: Experiment with side-channel attacks yourself!
First practical timing attacks against DH, RSA, and DSA were presented by Paul Kocher in 1996..
Originally this type of attack was discovered by Daniel Bleichenbacher in 1998.
Klima, Pokorny and Rosa improved the attack and discovered the bad-version oracle in 2003.
In 2012 Romain Bardou and others developed a much more efficient Bleichenbacher attack algorithm that reduces the number of needed connections.
In 2014 Christopher Meyer and others discovered Bleichenbacher vulnerabilities in JSSE and other products and describe the first practical timing attacks.
Tibor Jager and colleagues discovered that it is possible to use a cross-protocol Bleichenbacher attack against TLS 1.3 and QUIC.
The DROWN attack is a protocol level Bleichenbacher vulnerability in SSL version 2. The DROWN research also contains further insights on cross-protocol scenarios.
In 2018, Hanno Böck, Juraj Somorovsky, and Craig Young did show that a lot of HTTPS hosts are still vulnerable against a slight variation of the original Bleichenbacher attack.
In 2019, Eyal Ronen and others have shown that a lot of cryptographic libraries can be attacked using cache timing attacks.
itnews: "Marvin" breathes new life into Bleichenbacher's timing oracle attack.
The Register: ROBOT crypto attack on RSA is back as Marvin arrives.
Bleeping Computer: New Marvin attack revives 25-year-old decryption flaw in RSA.
Cyber Security News: Marvin Attack: 25-year-old RSA Decryption Vulnerability Disclosed.
OpenNET: Атака Marvin для расшифровки RSA на основе измерения времени операций.
SecurityLab: Новые уязвимости: 25 лет ложной безопасности протокола RSA.
Bitdefender: ‘Marvin Attack’ Resurgence: 1998 ‘Resolved’ Vulnerability Makes a Comeback.
IT-Connect: L’attaque Marvin, le retour d’une vulnérabilité vieille de 25 ans dans le RSA.
Sophos News: Serious Security: GnuTLS follows OpenSSL, fixes timing attack bug.
Des Linux blog: Marvin Attack, časově založený RSA cracking útok.
ComputerWeekly.com: RSA and other crypto systems vulnerable to side-channel attack.
CNews: В шифровальных протоколах RSA и SSL жива и пригодна к использованию «дыра», которой 25 лет.
Bulletproof TLS newsletter: The Bleichenbacher timing side-channel attack strikes TLS again..
Snyk Blog: Understanding the RSA-based Marvin Attack.