ROBOT crypto attack on RSA is back as Marvin arrives

An engineer has identified longstanding undetected flaws in a 25-year-old method for encrypting data using RSA public-key cryptography.

In a paper titled, “Everlasting ROBOT: the Marvin Attack,” Hubert Kario, senior quality engineer on the QE BaseOS Security team at Red Hat, shows that many software implementations of the PKCS#1 v1.5 padding scheme for RSA key exchange that were previously deemed immune to Daniel Bleichenbacher’s widely known attack are, in fact, vulnerable.

Back in 1998, Bleichenbacher, a Swiss cryptographer who currently works for Google, showed [PDF] that a client of an SSL/TLS server could use an oracle – in this case information gleaned from server error responses – to learn enough about the padding – added data to a byte sequence ensure proper length – to decrypt the protected message.

This vulnerability has shown up repeatedly, most recently in 2017 when security researchers identified at least eight IT vendors and open source projects were vulnerable to a variation of Bleichenbacher original attack. The researchers dubbed their attack ROBOT, which stands for Return Of Bleichenbacher’s Oracle Threat.

Kario calls his technique Marvin, in reference to Marvin, “the Paranoid Android” from The Hitchhiker’s Guide to the Galaxy, by Douglas Adams, and as a nod to the ROBOT moniker.

“In this paper we show that Bleichenbacher-style attacks on RSA decryption are not only still possible, but also that vulnerable implementations are common,” the paper explains. “We have successfully attacked multiple implementations using only timing of decryption operation and shown that many others are vulnerable.”

Essentially, by sending specifically crafted RSA ciphertexts to a server that uses PKCS#1 v1.5 and measuring the amount of time required to process the messages, it’s possible eventually to read a targeted plaintext – to decrypt the message. The attacker can also use this information to forge digital signatures.

“For a TLS server that defaults to RSA encryption key exchanges, that means the attacker can record a session and decrypt it later,” the Marvin website explains. “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.”

Kario’s paper describes a practical attack on the M2Crypto library using 1024 bit RSA keys on a Lenovo T480s, Intel i7-8650U that was able to decrypt RSA ciphertext in 163,000 oracle calls that tested padding conformance. The attack took about nine hours to complete. According to the paper, the issue was reported in October 2020, assigned CVE-2020-25657 (see table below), and a partial fix was implemented. But the library is believed to be still vulnerable.

Estimating attack times on TLS servers is complicated, the paper says, adding that it depends upon the hardware and software involved as well as on how much access the attacker has. “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 a couple of hours to attack NSS,” the paper says.

Kario’s recommendation is to stop using RSA PKCS#1 v1.5 encryption, since only servers that implement RSA encryption are affected. Most modern clients, he says, rely on Elliptic Curve Diffie Hellman, so disabling cipher suites that use RSA should be possible outside of environments that have legacy systems to support.

Kario has identified at least seven affected implementations, some of which have confirmed fixes, but says most cryptographic implementations of RSA PKCS#1 v1.5 are probably vulnerable.

APIs in Go (crypto/rsa DecryptPKCS1v15SessionKey) and GNU MP (mpz_powm_sec) were also found to have errors that made them susceptible to timing attacks.

Those interested in testing their systems might like to make use of Kario’s script for testing TLS servers and the associated instructions.

Kario concludes: “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.” ®

READ MORE HERE