A full key recovery for RSA-1024 and conceivably RSA-2048 might be possible according to an academic paper released last week. The said paper, titled: “Sliding right into disaster: Left-to-right sliding windows leak”, described a flaw (CVE-2017-7526) in the cryptographic library Libgcrypt that made it prone to local side-channel attack.
According to AO Kaspersky Lab, Libgcrypt, which is a general purpose cryptographic library originally based on code from GnuPG to provide functions for all cryptographic building blocks, uses left to right sliding windows exponentiation. This method, although common in cryptographic implementations and computes power, leaks a fractions of the exponent bits during process. Although it’s been assumed that the number of leaked bits will not be enough to carry out full key-recovery attack against RSA, the researchers explained that Libgcrypt’s employment of left-to-right sliding windows “leaks significantly more information about exponent bits than for right-to-left.”
The researchers utilized a Flush+Reload cache-timing attack on Libgcrypt’s exponentiation routine in order to successfully break the library’s implementation of RSA-1024. The Flush+Reload attacks, first described in 2014 by one of the paper’s authors along with a colleague at the University of Adelaide, target a vulnerability in Intel X86 processors and were successfully used before to harvest private encryption keys from programs running GnuPG 1.4.13.
In the paper, researchers first monitored shared memory locations for access and over time were able to form a trace of accesses to the monitored location. When the traces were analysed, researchers were able to detect a complete series of square-and-multiply sequences. These sequences were in turn used to recover the key.
This attack proved efficient for 13 percent RSA-2048 keys. Researchers implied that a tweak along with enough time and computational power will allow recovery of RSA-2048 just as easily.
Author and primary developer behind GnuPG, Werner Koch, wrote that there are easier ways than the method explained in the paper to access private keys especially as the proposed scenario involved execute access on the hardware where the private RSA key is used which is already considered a jeopardy. However, he also admitted that it can be used on hardware running multiple VMs; as a software running on one VM could use the attack to compromise private keys stored on another.
The authors contacted developers of the library while writing the paper and reported that the developers refused to push patches that uses fixed windows instead of sliding windows and deemed it as unnecessary. However, Koch announced on Thursday that the GnuPG Project would address CVE-2017-7526 in version 1.7.8.
Necessary patches to stop the attack soon followed on Friday as SUSE Linux was the first to resolve the issue in versions 1.6.1, 1.5.0, and 1.2.2. Developers with Debian promoted users to upgrade the vulnerable packages, pushing patches to prevent possible compromise. A security engineer for Ubuntu informed users of the issue and the update containing the fix was released on Monday.
The paper, authored by eight academics from Technische Universiteit Eindhoven in Netherlands, the University of Illinois, the University of Pennsylvania, the University of Maryland, and the University of Adelaide — Daniel J. Bernstein, Joachim Breitner, Daniel Genkin, Leon Groot Bruinderink, Nadia Heninger, Tanja Lange, Christine van Vredendaal, and Yuval Yarom, is scheduled to be presented in Septemeber at the Conference on Cryptographic Hardware and Embedded Systems in Taiwan.
