Sniffing Keys - A New Type of Side Channels for Cryptographic Operations

2014-04-01

Introduction
In a recently published paper, Adi Shamir and others described a new way to extract RSA keys using the noise made by the processor when performing cryptographic operations [1]. The importance of this paper is that it has demonstrated the ability to use side effects that have not yet been considered for extracting critical information from a computer system.

On the other hand, side channels that use the power consumption of a computer system to extract keys have been known for many years [2]. Simple and differential power analysis are now common assessments performed for smart card chips to ensure that they do not leak cryptographic keys due to those types of side channels. Electromagnetic radiation has also been successfully used as a source to extract cryptographic keys [3]. Timing differences as well, have been used very successfully as a side channel [4].

The New Side Channel
These results have encouraged atsec's researchers to look for other potential sources of side channels that have not been considered so far. The one we have focused our attention on is a side effect of the power analysis side channel that, until now, has been completely ignored: the differences in power consumption also resulting in differences in the heat produced by the computer system. While measuring the heat directly with the required precision turned out to be very complicated, we have used another side effect: the differences in heat resulting in differences in the dissemination of material, which can be measured more easily than the heat differences itself. In some respect, one can say we have "sniffed the keys!"

Extracting Keys Using the Side Channel
The disseminations are of course too small and changes too fast for a human nose to detect those differences. As with Adi Shamir's noise related side channel, our side channel is also one that requires dedicated equipment to extract the changes in the dissemination. In our case we have used a mass-spectrometer ("the sniffer") to detect those changes. We have used a similar test setup as Shamir (using also GnuPG RSA as the example) but used the sensors of the mass-spectrometer where Shamir used a microphone. The complicated part was to analyze what type of dissemination to look for. To 'calibrate' the whole system, we sprinkled the CPU with some (good smelling) fragrance, which ensured us that a significant number of molecules of a known type would be disseminated. We measured the distribution of those molecules over time using a known key and then performed the correlation between the hamming weights of the key when in operation and the dissemination captured. It turned out that this calibration was not as easy as we originally had thought. The fan of the computer system introduced a significant amount of turbulences that added a large amount of 'noise' to the data measured. We therefore had to take those turbulences into account and solve the initial value problem for the Navier-Stokes differential equations, which allowed us to eliminate (to a large extent) the effect of the fan in our mathematical model.

After having successfully performed this calibration, we the tried to extract an RSA key without prior knowledge. After several attempts where we refined our analysis software we were able to extract a 1024 bit RSA key within one hour using about 200ml of fragrance.

Further Work
So far we have used only a single CPU (an Intel i7 processor) and a dedicated fragrance [4711]. We are currently experimenting with other CPUs and other fragrances to obtain more general results. As a first step, we were able to reduce the time for extracting the key significantly by using bullshit [5] instead of the fragrance, but our team had to leave the room while conducting the experiment. Also the time to clean the computer and the spectrometer after the experiment was considered to be not acceptable. In another experiment we used alcohol instead of the fragrance, but the negative effect on the productivity of our team has forced us to stop using this material. The ladies in our team are now experimenting with different fragrances that smell much better than feces, while also keeping the time for extracting the key low.

References
[1] Daniel Genkin, Adi Shamir, Eran Tromer: RSA Key Extraction via Low-Bandwidth Acoustic Cryptoanalysis; December 18, 2013
[2] Paul Kocher, Joshua Jaffe, Benjamin Jun: Differential Power Analysis; Cryptographic Research
[3] Karine Gandolfi, Christophe Mourtel, Francis Olivier: Electromagnetic Analysis: Concrete Results
[4] Jean-Jacques Quisquater, Francois Koeune, Werner Schindler: Unleashing the Full Power of Timing Attacks
[5] Harry G. Frankfurt: On Bullshit; Princeton University Press; 1st edition January 2005
[4711] 4711