The cryptographic library Libgcrypt is vulnerable to a local side-channel attack; something researchers warn could allow full key recovery for RSA-1024.
The vulnerability (CVE-2017-7526) is tied to the fact that Libgcrypt, which is based on code from GnuPG, uses left to right sliding windows exponentiation. The method is commonly used by cryptographic implementations and computes power by looking at a number of exponent bits at a time. The method leaks a fraction of those exponent bits in the process however.
An academic paper describing the flaw, “Sliding right into disaster: Left-to-right sliding windows leak” (.PDF) was actually released a week ago, but patches to prevent the attack didn’t surface in Linux distributions until earlier this week.
GnuPG issued an update for the library last week that should mitigate any future attacks.
The paper’s authors, 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, plan to present it later this year, in September, at the Conference on Cryptographic Hardware and Embedded Systems in Taiwan.
The research is based on the concept that exponentiation via the sliding window algorithm leaks information. It’s been long assumed the number of bits leaked via sliding windows wouldn’t be enough to carry out a full key-recovery attack against RSA but the researchers say the way that Libgcrypt uses left-to-right sliding windows “leaks significantly more information about exponent bits than for right-to-left.”
The researchers took aim at Libgcrypt’s exponentiation routine with a Flush+Reload cache-timing attack, something that allowed them to completely break RSA-1024 as its implemented by the library.
One of the paper’s authors, Yarom and Katrina Falkner, a colleague at the University of Adelaide, first described how Flush+Reload attacks worked in a paper back in 2014. The cache side-channel attack targets a weakness in Intel X86 processors. The attacks have previously been used to extract private encryption keys from programs running GnuPG 1.4.13
The “sliding right” attack monitors shared memory locations for access, something that helps form a trace of accesses to the monitored location over time. After tossing out errors and combining captured traces, the researchers arrived at a complete series of square-and-multiply sequences, which in turn can help recover the key for RSA-1024.
The academics hint their attack could potentially be tweaked to obtain key recovery for RSA-2048; it would just take time and more computational power. As it is, their attack only proved efficient for 13 percent of RSA-2048 keys.
Yarom and company wrote the paper while looking at Libgcrypt 1.7.6 and said the maintainers of the library “refused” to issue a patch to switch from sliding windows to fixed windows, insisting it was “unnecessary to stop the attacks.” While version 1.7.7 was released without a fix for the issue the maintainers eventually came around to fixing the vulnerability in 1.7.8 it seems.
Werner Koch, the author and primary developer behind GnuPG, announced last Thursday the GnuPG Project would address CVE-2017-7526 with 1.7.8.
Koch points out there are some limitations to the attack and that theoretically there are easier ways than the ‘sliding right’ attack to access private keys. The patch in particular however sounds like it benefits users running virtual machines, as the vulnerability could have made it easier for one VM to steal a private key from another VM.
“Note that this side-channel attack requires that the attacker can run arbitrary software on the hardware where the private RSA key is used,” Koch wrote, “Allowing execute access to a box with private keys should be considered as a game over condition, anyway. Thus in practice there are easier ways to access the private keys than to mount this side-channel attack. However, on boxes with virtual machines this attack may be used by one VM to steal private keys from another VM.”
SUSE Linux was quick to fix the issue in versions 1.6.1, 1.5.0, and 1.2.2, last Friday. Developers with Debian meanwhile encouraged users to upgrade their libgcrypt20 packages, pushing patches to mitigate the attack, on Sunday. Marc Deslauriers, a security engineer for Ubuntu, warned users of the open source operating system of the issue – and an update, 1.7.6-1ubuntu0.1 – on Monday.
