Several open source cryptographic libraries are vulnerable to a dangerous but hard-to-exploit side-channel attack that a hacker could use to steal Secure Shell (SSH) server keys or Transport Layer Security (TLS) private keys.
Patches are being released to address the flaw, CVE-2018-0495, found in the signature generating component of multiple cryptographic libraries, including CryptLib, LibreSSL, Mozilla NSS, Botan, OpenSSL, WolfCrypt, Libgcrypt, LibTomCrypt, LibSunEC, MatrixSSL, and BoringSSL, Google’s fork of OpenSSL that is used in Chromium and Android for creating secure connections.
The libraries are vulnerable to a memory cache side-channel attack discovered by NCC Group researcher Keegan Ryan that exploits “vulnerable code patterns” in their implementation of the widely-used Elliptic Curve Digital Signature Algorithm (ECDSA) and the related Digital Signature Algorithm (DSA).
As their names suggest, ECDSA and DSA are schemes for generating cryptographic signatures which are used to prove the authenticity of a message.
ECDSA is used to protect HTTPS websites and is crucial to Bitcoin’s method for ensuring only rightful owners can spend funds by requiring possession of the right private key that corresponds to the public key on Bitcoin's public ledger system.
Ryan found that the affected libraries leak information through memory caches when they use a private key to create a signature for things like TLS or SSH connections.
An unprivileged attacker would need to run code on the same machine as the target, which would be likely in the case of a shared server or VMs on the same hardware in a cloud environment.
In a soon-to-be-released proof of concept exploit for OpenSSL, he demonstrates that an attacker could collect the information leaked by the memory caches from just a few thousands signatures, and in one minute recover the value of the private 256-bit ECDSA key.
Each of the cryptographic libraries’ implementation of the two algorithms contain similar "vulnerable code patterns” in the equation that computes the signature.
The side-channel attack is similar to the Meltdown and Spectre attacks that exploit speculative execution in modern CPUs, but instead relies on pauses that occur when a computer attempts to calculate certain values inputted into the algorithm’s “modular arithmetic” equation.
Ryan compares the pauses to the small but noticeable difference in time it takes a human to calculate what time it is at five hours after 1pm (1 + 5 = 6) and five hours past 11pm (11 + 5 = 4). The attack exploits the fact that mentally navigating a 12-hour loop can make the same addition more complex in the context of the equation. These timing differences can be used over multiple instances to collect enough information to recover the private key.
"You may have noticed that it took just a tiny bit longer to come up with 11 + 5 = 4 than it did to find the others. The other values were easy because they can be added the normal way, but the last one looped around and required an extra step to subtract 12 from the sum. Computers often do modular addition in the same way, and it is exactly this difference from adding two numbers that loop around that we will exploit in our attack."
Developers of the GnuPG Project have fixed the issue in their latest release, describing it as a “novel” attack. Other projects are expected to release patches soon, according to Ryan.
Fortunately, the attack is very difficult to exploit, according to Ryan.
“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 specialized knowledge, and even on their own, none of the the attack steps are easy.”
On the other hand, he was alarmed by the fact that the vulnerable code patterns were so widespread and that key information can leak through “simple side channels”.
A detailed explanation of the attack is available in a technical paper published by NCC Group.