Can we ensure the security of a crypto-algorithm and -implementaton against acoustic cryptanalysis?

Question

Like people always say: “Attacks only get worse…” — which is why I'm asking early.

I have been reading the paper “RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis” published December 18, 2013 by Daniel Genkin, Adi Shamir, Eran Tromer.

Attack

In short, they discovered that it is possible to crack 4096-bit RSA encryption keys using a microphone to listen to high-pitch noises generated by internal computer components. In one of their setups, they only used a mobile phone which was placed 30 cm from a target laptop, with the phone's internal microphone pointing towards the laptop’s fan vents… successfully achieving a full key extraction in this configuration and distance.

^{image source: https://www.cs.tau.ac.il/~tromer/acoustic/}

The proof in that 57-page paper is hard enough to start thinking about related crypto-solutions. Especially since the paper mentions that rather simple hardware like parabolic microphones and laser vibrometers can be used for distant acquisition.

^{image source: https://www.cs.tau.ac.il/~tromer/acoustic/}

Now, I know this audio-based key recovery attack is a new one (published December 18, duh) but there has been quite some research on hardware-related attacks in the past already — like measuring the electrical potential of a computer's chassis during encryption etc. — and beyond that, the crypto-community tends to search for a solution to every problem encountered. So, I can imagine that there might be something out there I'm not aware of, which might be fit enough to lift one or more security impacts of acoustic cryptanalysis; especially in the described case(s) of acoustic key recovery attacks.

^{image source: https://www.cs.tau.ac.il/~tromer/acoustic/}

(Partial) Mitigation

Related to solutions, the paper's website mentions

…software countermeasures…

but also notes

How vulnerable are other algorithms and cryptographic implementations?

We don't know. Our attack requires careful cryptographic analysis of the implementation, which so far has been conducted only for the GnuPG 1.x implementation of RSA.

and

Q9: How vulnerable is GnuPG now?

We have disclosed our attack to GnuPG developers under CVE-2013-4576, suggested suitable countermeasures, and worked with the developers to test them. New versions of GnuPG 1.x and of libgcrypt (which underlies GnuPG 2.x), containing these countermeasures and resistant to our current key-extraction attack, were released concurrently with the first public posting of these results. Some of the effects we found (including RSA key distinguishability) remain present.

^{(italic emphasis mine)}

and last but not least the paper states on page 48 (as a conclusion at the end of it’s “Mitigation” section):

This too foils our key recovery attack (but not key distinguishing).

^{(italic emphasis mine)}

Question

The paper and website obviously imply that a “key distinguishing” problem still exists and that it represents a potential attack vector. They also seem to imply that no general, one-fits-all solution to the problem does not exist at the time of writing. Especially not when thinking about non-RSA ciphers. Yet, chances are that there’s something out there I haven’t heard of yet.

Can we ensure the security of a crypto-algorithm and/or -scheme against acoustic cryptanalysis? Does any generally acknowledged crypto-scheme, crypto-solution, or crypto-protocol exist which would be able to provide cryptographic security/defense against the described and maybe even other acoustic cryptanalysis of (non-RSA) ciphers?

Simpler asked: What cryptographic measures enable us to ensure the security of a crypto-algorithm and/or -scheme against acoustic cryptanalysis and/or acoustic attacks?

Answer 1

The problem is a very old one going back at least as far as the late 1940's early 1950's and has been shown to exist with Quantum Key Exchange as well.

You need to think of it in terms of entropy down to heat pollution where a coherent signal energy steps down due to inefficiency via various transducers to what is basically thermal noise where the noise threshold is significantly above any residual coherent signal.

Most people incorrectly think that TEMPEST is all about EM energy, it's not. It's about any energy (EM, acoustic/mechanical conducted or radiated even gravity) in one or more Shannon channels which have bandwidth, noise and propagation delay giving rise to phase as well as amplitude effects. It's also about transducers which can be bidirectional (a DC Motor/Generator being such a beast, as are some types of microphone/speaker by moving coil or piezo effects).

Put simply, a capacitor is two metal plates with an insulated gap. When current flows into the plates a magnetic field is generated that will cause the plates to move fractionally in sympathy with the current. Also some insulators are dielectrics which have a piezo effect as the voltage rises the dielectric deforms mechanically. Both of these effects will cause the capacitors to emit sound. Likewise inductance effects designers of RF oscillators are well aware that mechanical vibration of the inductive component will cause the resulting output of the oscillator to be modulated, it's frequently called microphonics.

These basic physical effects cannot be prevented only reduced or mitigated. In EmSec you look to reduce the bandwidth of any signal path such that it is less than the information bandwidth and also at signal containment/absorption.

Theses mitigations when done properly all add significant cost to a product. Therefor in a price sensitive market such as PC manufacture anything that is not regulated will cause a race for the bottom. And even where there are regulations (EMC) the market will still look at avoidance rather than meeting the intent of the regulations. One such avoidance is "direct sequence spreading" of the PC master clocks/oscillators such that the energy in a spur/sprog is spread so that it's energy/Hz decreases and thus meets the regulatory masks. Unfortunately the energy is still there and still caries the signal information and only needs de-spreading to recover the signal information.

One solution to "singing caps" is high melt temperature wax or some hot melt glues they absorb the audio signals and reduce the effective channel bandwidth. Another partial solutions is 'sound absorbing foam' that also lets air flow through and the right selection of materials will significantly reduce the audio channel through fan and ventilation grills.

But as I noted all steps are "mitigations" not real "solutions", but may well be sufficiently effective in their own right if (and only if) implemented correctly.

Answer 2

Start by reading the paper. They have an entire section on defences: it is Section 11, Mitigation, pp.46-48.

As far as software countermeasures for RSA specifically, they mention blinding as a good defence. Blinding is a standard defence against many kinds of side-channel attacks, and it is apparently effective against acoustic cryptanalysis as well. Blinding seems like an attractive defence; it imposes relatively little performance overhead (when the RSA public exponent is small), and helps protect against a broad range of side channel attacks (more than just acoustic side channels).

They also mention other possible countermeasures as well.

Of course, the best defense will be dependent upon the specific algorithm: for instance, you can use blinding to protect RSA, but not AES. So, don't expect to get a single definitive answer that works for all algorithms: the best defense will depend upon which algorithm you are trying to predict.

Answer 3

I haven't read the paper, but the "RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis" web page mentions that GnuPG's RSA implementation was patched to avoid the current attack. I got the impression that this was a problem along the lines of implementing AES without cache timing attacks, not "RSA is ruined forever".