# The 9 lives of Bleichenbacher's CAT, it puts another scratch again

Bleichenbacher demonstrated a padding oracle attack against RSA implementations that follow the PKCS #1 v1.5. Through the years, there are various mitigation techniques developed as OAEP and limiting the number of query execution over a period of time. OAEP has been proven secure in the random oracle model.

In November 2018, Ronen et. al demonstrated in The 9 Lives of Bleichenbacher’s CAT: New Cache ATtacks on TLS Implementations that Bleichenbacher is still applicable.

• How does the new attack work at top level?
• Which TLS implementations are affected?
• How one can mitigate from the attack?

• How does the new attack work at top level?

In short

They used BEAST-like Man in the Browser attack by using Cache-like attacks to perform a downgrade attack against any TLS connection to a vulnerable server. With this, they showed the feasibility of using Cache-like attacks.

More detailed

Even over the years, numerous mitigation techniques are deployed against the padding oracle attacks, they showed that some implementations are still vulnerable to various microarchitectural side channels. They target PKCS #1 v1.5 implementations that leak information via microarchitectural side channels.

Their attacker requires 3 capabilities:

1. Side channel capability: attacker must be able to execute code on the victim machine to mount microarchitectural side channel attack. They used Flush+Reload attack.

2. Privileged Network Position Capability: The attacker must be in the man-in-the middle position so that padding oracle attack with the private key can be exploited. The attacker downgrades the communication to TLS 1.2 RSA key exchange with Jager et. al.'s attack and used BEAST method.

3. Decryption Capability: The attacker needs an ability to start decryption of ciphertext chosen by him on the target system. They utilized Bleichenbacher and Manger’s Attack attack.

A concrete scenario of the attack:

• A physical device shared between a TLS server and the attacker's virtual machine. This requires a determined adversary.

• Second and third can be achieved by the controlling a node between the server and client

Note: Manger’s Attack that requires $$\log_2(N)$$ perfect Oracle queries. Bleichenbacher's attack requires millions of Oracle calls but can tolerate false negatives. They mounted an improved Manger’s Attack's attack with only 6144 queries due to an error.

Although the timeout of the browser limits the attack, they were able to parallelize the attack by using TLS servers that share the same public key certificate.

• Which TLS implementations are affected?

They tested the following implementations:

• OpenSSL
• Amazon s2n
• MbedTLS
• Apple CoreTLS
• Mozilla NSS
• WolfSSL
• GnuTLS
• BoringSSL

All, except the BearSSL and BoringSSL are affected by their attack.

• How one can mitigate from the attack?
• Keep the system up-to-date: don't support different versions.
• The backward compatibility is the main issue of this attack. TLS 1.3 security doesn't help you if your server can be downgraded to an earlier version.
• Deprecate the RSA key-exchange.
• Certificate Separation: Don't use the same key for signing and RSA-key exchange.
• Constant-Time Code and Safe API as in BearSLL and BoringSSL API.
• Using Large RSA Keys. The attack requires $$\approx \log N$$ oracle calls. Use larger keys $$>2048$$-bits to make the attack less practical.
• Reduce the TLS Handshake Timeouts in order to make MitM attack harder.
• Use BearSSL or BoringSSL

Note: The 30-second timeout in Firefox can be extended see Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice. by Adrian et. al.

Note 2: There is a related question in SecuirtySO about effected cipher suites.

• I know this is the crypto site and not the security site, but still, surely the first mitigation should be keeping your system up-to-date? Dec 12, 2018 at 23:19
• @Gilles definitely. But they say that by Jager's work they downgraded the communication to the TLS 1.2. If you insist that you will only use TLS 1.3 you may lose some connection with some server/clients until all updates? Dec 12, 2018 at 23:27
• No, keeping the system up-to-date is not about using a different version of the protocol. It's about upgrading to a library version with the latest security fixes. Dec 12, 2018 at 23:30
• Hm, why does it require PITM, can’t attacker’s just directly connect and query till they have the secret key? (They still can intercept and downgrade after that) Feb 10, 2019 at 4:46
• @eckes This is an oracle attack. It allows the attacker to trick the legitimate system into decrypting a ciphertext. It doesn't allow the attacker to recover the key. Feb 12, 2019 at 21:14