Technical advisory: “ROHNP”- key extraction side channel in multiple crypto libraries

Vendors affected: Multiple Versions affected: Multiple Author: Keegan Ryan <keegan.ryan[at]nccgroup[dot]trust> <@inf_0_> Advisory URL / CVE Identifier: CVE-2018-0495 Risk: Medium (Key disclosure is possible, but only through certain side channels) 

Summary

We have discovered an implementation flaw in multiple cryptographic libraries that allows a side-channel based attacker to recover ECDSA or DSA private keys. When these cryptographic libraries use the private key to create a signature, such as for a TLS or SSH connection, they inadvertently leak information through memory caches. An unprivileged attacker running on the same machine can collect the information from a few thousand signatures and recover the value of the private key.

We have demonstrated this attack against the latest version of OpenSSL and can recover a 256 bit ECDSA key in around a minute by using a simple memory cache side-channel attack.

Location

The flaw is located in the code that computes signature component s:

s = k-1(m + r * x) (mod q)

In many libraries, the code that performs modular addition does not run in constant time, and so a side channel can recover information that can be used to calculate the private key.

We analysed the source code of several open source cryptographic libraries to see if they contain the vulnerable code pattern in the code for ECDSA, DSA, or both. This list is accurate to the best of our knowledge, but it is not exhaustive. Only the first group was affected by this finding; the other three groups are not thought to be vulnerable.

Contains vulnerable pattern: CryptLib (Both), LibreSSL (Both), Mozilla NSS (Both), Botan (ECDSA), OpenSSL (ECDSA), WolfCrypt (ECDSA), Libgcrypt (ECDSA), LibTomCrypt (ECDSA), LibSunEC (ECDSA), MatrixSSL (ECDSA), BoringSSL (DSA)

Non-constant math, but different pattern: BouncyCastle, Crypto++, Golang crypto/tls, C#/Mono, mbedTLS, Trezor Crypto, Nettle (DSA)

Constant time-math: Nettle (ECDSA), BearSSL, Libsecp256k1

Does not implement either: NaCl

Impact

Impact varies depending on how the application is used. The attacker and victim need to be running code on the same machine in order to achieve the side channel (network timing data on it’s own is not enough for a practical attack).

The most common scenario is when the attacker and victim are both running in a cloud computing environment and their virtual machines are assigned to share the same physical host. In this hypothetical, an attacker could use a cross-VM side-channel attack to, for example, steal SSH server keys or TLS private keys.

These attacks are still going to be very difficult for an attacker. To see why, consider what an attacker would have to do to compromise a site using a vulnerable library and an ECDSA public key. The attacker must first identify the cloud provider where the site is hosted, then the attacker must create virtual machines with that provider until one of the virtual machines shares the same physical processor as the victim site. Next, the attacker initiates TLS connections to trigger the ECDSA signing process and uses the cross-VM side channel to monitor for leaked information and then uses this information to recover the site’s private key. Now, the attacker must be in a position to intercept the traffic between the site and a user, modifying the content of the TLS packets and using the stolen private key to forge a signature. This chain of events requires highly specialised knowledge, and even on their own, none of the the attack steps are easy.

We have considered common cases, but ECDSA and DSA are used in countless very different ways. The most dangerous aspect of the bug, in my opinion, is that the flawed implementation pattern is widespread and the key information can leak through simple side channels. The issue likely exists in implementations we did not consider where side-channel attacks are more practical, so the impact to those systems might be greater.

Details

An easy to understand introduction to how the attack works can be found here. The paper with the more technical details is located here.

Proof of concept

We currently have a generic PoC that demonstrates the cryptanalysis step of the attack and a full PoC that performs the attack against the latest OpenSSL. Although we do not anticipate mass exploitation, we are waiting two weeks before publishing these PoCs to make immediate exploitation more difficult.

Recommendation

A large number of affected vendors are publishing patches today. For use cases where side channel attacks are not a primary concern, just apply the patches as they are released.

For maintainers of ECDSA and DSA signing code, check to see if your code follows the vulnerable pattern and implement the mitigations. More detailed information can be found in the paper.

In some situations, patching may be difficult and side channel attacks are a concern. This may apply, for example, to embedded devices that store private signing keys in a trusted execution environment. It is difficult to give a specific recommendation here, as it varies from situation to situation. In general, we recommend building any cryptographic system with consideration of side-channel attacks, implementing defense-in-depth mitigations to make these attacks more difficult, and understanding how to handle a compromised key.

Disclosure details

NCC Group began disclosing this issue on May 23, 2018 and finished reaching out to the affected parties on June 2, 2018. No contact information could be found on LibTomCrypt’s website or in the repository, but we successfully made contact with all other parties. Patching went very quickly for many libraries, as the blinding mitigation only requires a small change to existing code.

This is an atypical disclosure scenario due to the wide variety of affected products. Public release has to be synchronised, since one library patching significantly earlier than the others could give away the details of the cryptanalytic attack, leaving the unpatched libraries at risk.

With these considerations in mind, we decided on a release date of today, June 13, 2018. This would get patches out to the most people as soon as possible.

Of the affected libraries, LibreSSL, NSS, OpenSSL, WolfCrypt, Botan, Libgcrypt, MatrixSSL, and BoringSSL have indicated to me that they either have a patch ready or have a plan to patch. Side-channel attacks are explicitly excluded from Cryptlib’s threat model.

• MatrixSSL: A patch is available from the vendor by contacting support@matrixssl.org
• Libgcrypt: Announcement is here