Breaking Libgcrypt RSA via a side channel

A recent paper [PDF] by a group of eight cryptography researchers shows, once again, how cryptographic breakthroughs are made. They often start small, with just a reduction in the strength of a cipher or key search space, say, but then grow over time to reach the point of a full-on breaking of a cipher or the implementation of one. In this case, the RSA implementation in Libgcrypt for 1024-bit keys has been fully broken using a side-channel attack against the operation of the library—2048-bit keys are also susceptible, but not with the same reliability, at least using this exact technique.

The RSA cryptosystem involves lots of exponentiation and modular math on large numbers with sizable exponents. For efficiency reasons, these operations are usually implemented by a square-and-multiply algorithm. Libgcrypt is part of the GNU Privacy Guard (GnuPG or GPG) project and underlies the cryptography in GPG 2.x; it uses a sliding window mechanism as part of its square-and-multiply implementation. It is this sliding window technique that was susceptible to analysis of the side channel and, thus, allowed for the break.

The cryptographers who wrote the paper (Daniel J. Bernstein, Joachim Breitner, Daniel Genkin, Leon Groot Bruinderink, Nadia Heninger, Tanja Lange, Christine van Vredendaal, and Yuval Yarom from multiple universities across the globe) note that the Libgcrypt maintainers at one point rejected a fix that would have thwarted the extraction of key information: "However, the maintainers refused a patch to switch from sliding windows to fixed windows; they said that this was unnecessary to stop the attacks." The reason was that even though sliding windows can reveal some parts of the key to local attackers, Libgcrypt's window was such that only 40% of a 1024-bit key (and 33% of a 2048-bit key) was exposed, which was insufficient to recover the full key efficiently, or so it was thought. The researchers found that reasoning did not hold up.

If an attacker can observe the pattern of squarings and multiplications by way of the cache, which is an established technique for an attacker running on the same hardware, they can extract some parts of the key. It turns out that there are two ways to implement the sliding window algorithm: right to left (i.e. starting with the least-significant bit) or left to right. It is slightly more efficient to use the left-to-right direction and that is what is recommended in several reference texts, so it is not surprising that Libgcrypt chose that direction. But the researchers found that the left-to-right calculation leaks many more bits of the key.

To verify the results, the researchers monitored particular memory locations in the RSA signature code path to extract the needed sequence of squarings and multiplications. That resulted in exposing 48% of the key bits, but 50% or more is needed for the technique used to reconstruct the full key. By analyzing the algorithm used by Libgcrypt, the researchers were able to find patterns and rules that could be used to add more known bits to the key.

In the paper, they say that most 1024-bit keys can be recovered by searching through 10,000 candidates, though some require searching up to 1,000,000 candidates. For 2048-bit keys, 13% could be found by searching only 2,000,000 possible keys. Since the public key is known, it should be straightforward to use any signatures produced to verify which of the possibilities is the proper key.

As might be guessed, the paper goes into great detail about the algorithms and how the information provided by the FLUSH+RELOAD side channel was used to extract enough to bits to break the keys.

On June 29, the Libgcrypt project released version 1.7.8 to address the problem (which is also known as CVE-2017-7526). The change made was not to switch to right-to-left operation or to a fixed window as mentioned in the paper, but to instead use blinding on the exponent to obscure the actual bits of the key. Blinding uses a reversible algorithm to alter the input to a calculation such that the result returned can be transformed into the result as if the initial input had been used. Attackers observing the sequence of calculations will be unable to extract the actual value of interest.

A note in the commit message makes it clear that blinding is simply a quick fix, though it is not clear if something more substantial is in the works. "Exponent blinding is a kind of workaround to add noise. Signal (leak) is still there for non-constant-time implementation." But the release announcement does downplay the significance of the bug somewhat:

The research is definitely an important result, but the practical implications, at least for those not running on virtual machines alongside those of attackers, would seem to be fairly small. On the other hand, it only takes one security hole that lets an attacker's code onto a system that regularly uses a private key of interest for that key to be at fairly serious risk. This kind of incident helps remind us that attacks against cryptography only get better over time—that's something worth keeping in mind.

While it is not necessarily directly related, it should be pointed out that the GnuPG project is currently looking for financial support. Both GPG itself and Libgcrypt are used by a wide variety of other tools; it is worrisome that the project is not better supported financially. While there is no reason to believe there is Heartbleed-level bitrot going on within GnuPG, there should be concern that the project may not be able to keep up with the threats it faces in today's internet.