A side-channel attack on GnuPG

Using equipment that is reminiscent of the Van Eck phreaking scene in Cryptonomicon, some security researchers have shown that keys can be extracted from a laptop in the next room. It is a passive attack that exploits a side channel in the GNU Privacy Guard (GnuPG) implementation of the Elliptic Curve Diffie-Hellman (ECDH) key-exchange protocol. The problem has been fixed in Libgcrypt, but the possibility of similar weaknesses in other algorithms or implementations makes this kind of attack worthy of some study by those working in cryptography.

The paper [PDF] that describes the technique was authored by Daniel Genkin, Lev Pachmanov, Itamar Pipman, and Eran Tromer, who are researchers at Tel Aviv University. There are pictures of the equipment used in the paper, as well as on a web page with some FAQs on the technique. The current setup costs around $3000 for the equipment needed to intercept the electromagnetic (EM) signals from a computer on the other side of a wall, but it is believed that much less expensive (and more portable) equipment could be developed.

The basic idea is to measure the EM output of the laptop as it decrypts chosen ciphertext. GnuPG is used by tools like the Enigmail plugin for Mozilla Thunderbird, so email can be used as a way to cause the laptop to do the decryption. Enigmail will automatically pass encrypted email to GnuPG for decryption, which means that email sent will result in decryption that can be captured in the next room. Multiple emails were sent to improve the reliability of the key extraction. So, by sending emails encrypted with a victim's public key, an attacker (or government agency) in the next room can recover most of the victim's private key—thus decrypt any other encrypted email that has been intercepted.

In Libgcrypt 1.6.3 and earlier, the decryption algorithm does an optimization that allows the key to be recovered. Large integers (such as keys) are represented in non-adjacent form (NAF) in order to reduce the number of non-zero digits (each of which requires additional arithmetic operations) from roughly one-half to one-third. Numbers in that form are strings of 1, 0, and -1 values.

By observing the operations performed on the ciphertext, the researchers were easily able to distinguish the 0 "bits" in the key, but there was still a problem determining whether the non-zero values were 1 or -1. That's where choosing the ciphertext comes into play. By using specific points on the elliptic curve in the ciphertext, the researchers could reliably distinguish between the sequence of operations done for a 1 value versus those done for a -1 value.

The net result is described in the paper:

While the entire key is not necessarily extracted, the search space has been reduced enormously. Presumably, brute-force techniques can determine the missing digits and any errors in short order.

In order to avoid this side-channel leak, Libgcrypt 1.6.5 was released. It always does the same set of operations for each digit, regardless of its value. The researchers worked with the GnuPG developers to ensure that the change resisted the attack. The new algorithm is slower, but won't be subverted with this technique. Other tools use Libgcrypt, too, of course, so the update is important. The big unknown is whether other implementations of ECDH are vulnerable—and what other side channels (in other cryptographic algorithms) are out there waiting to be found.

Cryptographic algorithms are hard to get right even before considering problems like side channels. While these kinds of attacks are not particularly new, they do represent a threat to users, particularly from targeted, nation-state-level attackers. Though, as noted in the FAQ, this kind of attack is unlikely to be used except against the most security conscious:

For those who are taking more precautions than most, however, these techniques have to be a little worrisome. It is not terribly hard to imagine some agency setting up shop in the next hotel room over and monitoring the activity of the laptop next door, then sending these targeted emails and collecting the data needed. The best defense may well be to ensure that decryption only takes place under the direction of the user—and in a secure location.