Security researchers Crack 1024-bit RSA Encryption in GnuPG Crypto Library
4.7.2017 securityaffairs Krypto

Experts have devised a side-channel attack on RSA secret keys that allowed to crack 1024-bit RSA Encryption in GnuPG Crypto Library.
Security researchers have found a critical vulnerability, tracked as CVE-2017-7526, in a Gnu Privacy Guard (aka (GnuPG or GPG) cryptographic library that allowed them cracking RSA-1024 and extract the RSA key to decrypt data.

The research team was composed of experts from several universities, including Technical University of Eindhoven, the University of Illinois, the University of Pennsylvania, the University of Maryland, and the University of Adelaide.
GnuPG is popular open source encryption software currently used by many operating systems, including Linux, Windows, and macOS X.

The vulnerability resides in the Libgcrypt cryptographic library used by GnuPG, that opens to local FLUSH+RELOAD side-channel attack on RSA secret keys dubbed “Sliding right into disaster”

The expert discovered that the “left-to-right sliding window” method used by the libgcrypt library leaks significantly more information about exponent bits than for right-to-left, allowing RSA key recovery.

“It is widely believed that, even if the complete pattern of squarings and multiplications is observed through a side-channel attack, the number of exponent bits leaked is not sufficient to carry out a full key-recovery attack against RSA. Specifically, 4-bit sliding windows leak only 40% of the bits, and 5-bit sliding windows leak only 33% of the bits.” states the research paper.
“In this paper, we demonstrate a complete break of RSA-1024 as implemented in Libgcrypt. Our attack makes essential use of the fact that Libgcrypt uses the left-to-right method for computing the sliding-window expansion,”
“The pattern of squarings and multiplications in left-to-right sliding windows leaks significantly more information about the exponent than right-to-left. We show how to extend the Heninger-Shacham algorithm for partial key reconstruction to make use of this information and obtain a very efficient full key recovery for RSA-1024.”

In the L3 Cache Side-Channel Attack scenario, hackers run arbitrary software on the hardware handling the private RSA key.
The analysis of the pattern of memory utilization or the electromagnetic outputs emitted during the decryption process could allow the attacker to extract the encryption key from a system.

“Note that this side-channel attack requires that the attacker can run arbitrary software on the hardware where the private RSA key is used. Allowing execute access to a box with private keys should be considered as a game over condition, anyway.” reads the Libgcrypt advisory .

“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.”
According to the experts, the side channel attack also works against RSA-2048, the attack
is efficient for 13% of keys.

“Scaling up to RSA-2048 does not stop our attack: we show that 13% of all RSA-2048 keys with CRT and w = 5 are vulnerable to our method after a search through 2000000 candidates” continues the paper.

The GnuPG Project released the Libgcrypt version 1.7.8. to fix the local side-channel attack.to fix the local side-channel attack.

Libgcrypt has released a fix for the issue in Libgcrypt version 1.7.8. Debian and Ubuntu already updated their library with the latest version of Libgcrypt.