RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis
cs.tau.ac.il
cs.tau.ac.il
My HP notebook from ~2000 had measurable (although very high impedance) 110V AC between exposed metal parts and PE in wall outlet when connected to charger. Modern thinkpads (and probably all non-Apple laptops sold in Europe) does not seem to have this problem as ground is connected through in charger, not only AC coupled to both hot and neutral.
This other type of attack, however, isn't so easily guarded against:
Beyond acoustics, we demonstrate that a similar low-bandwidth attack can be performed by measuring the electric potential of a computer chassis. A suitably-equipped attacker need merely touch the target computer with his bare hand, or get the required leakage information from the ground wires at the remote end of VGA, USB or Ethernet cables.
This serves as a reminder that it's pretty much impossible to defend against an attacker that has physical access to your box.
Probably. The answer to Q11 says "The interesting acoustic signals are mostly above 10KHz". They don't say what the high end of the range is. But I would guess that sufficiently loud music (which usually contains frequencies up to about 22kHz) would mask the sound generated by the CPU.
Noisy environment. One may expect that placing the machine in a noisy machine will foil the attack.
However, the energy of noise generated in a typical noisy environment (such as outdoors or a noisy room)
is typically concentrated at low frequencies, below 10kHz. Since the acoustic leakage is usually present
well above this rage, such noises can be easily filtered out during the data acquisition process using a
suitable high-pass filter (as we did in our experiments). Also, the signal would be observe during any
pauses in ambient noise (e.g., music). Note also that the attacker may, to some extent, spectrally shift
the acoustic signal to a convenient notch in the noise profile, by inducing other load on the machine (see
below). Thus, a carefully-designed acoustic noise generator would be required for masking the leakage.Like dubstep.
Anyway, I'm certainly not claiming to know with any certainty that loud music would work as a preventative measure against this kind of attack. I just don't think the paper sufficiently proves that it wouldn't be.
https://en.wikipedia.org/wiki/Equal-loudness_contours
EDIT: also pitch is logarithmic with respect to frequency. 8khz sounds really high pitched.
If the signal you're subtracting is known to you, you can simply lock the phases and subtract. That's pretty trivial.
But knowing the name of the song doesn't necessarily give you a known signal to subtract. Conceivably, you could be working with a version of the song that was compressed differently than the one playing on the target computer. In which case, the two signals might not have the same waveform, and they wouldn't cancel.
To the listener's ear, the signals may sound identical. A good example of this principle is musical instruments. Have a skilled violinist play the same note twice with the same articulation for the same duration under the same conditions. Record each sample the same way. Most listeners would say these two samples are identical. But if you invert one and then mix them, they won't cancel, because they didn't actually have the same waveform.
But it's definitely an interesting approach, and potentially viable, if a good filtering algorithm can be worked out. My suspicion is that such an algorithm exists or is at least possible. But I'm not an audio engineer, so I'm not certain.
Besides, in practice, upgrading to GnuPG 1.4.16 (released today) is supposed to also mitigate the key extraction attack using this side channel.
The naive approach I suggested would be easily defeated by playing two songs from two different sources; which itself would be defeated by setting up soundcloud on two devices in both places and carefully setting up/analyzing/modelling the room so that you can adjust the signal you're subtracting to account for the distance the sound waves travel and whatnot. I think after a while you just get increasing complexity and diminishing returns -- i.e. it becomes an arms race.
The brute force way is to do an exhaustive search, repeatedly correlating the signal you are looking to cancel and the received signal, whilst "sliding" the known signal across the received signal, which means adding a delay to the known signal between each correlation. Correlation peaks can be picked out and used to cancel the reflections. Similar techniques are regularly used in radio communications, to combat multipath fading, which is a fancy way of saying that the received radio signal contains reflections.
Edit: remove cruft at end of comment.
On the other hand timing attacks are something that anyone implementing anything security related has to be aware of and actively prevent as they can be conducted from mostly anywhere.
On the other hand measurement of potential on chassis seems interesting as that can possibly be measured pretty far away (eg. PC -> STP cable -> Cable modem -> CATV).
The concept of defence-in-depth suggests that you should take all[2] possible measures to avoid sensitive data leakage. If an attacker does get into your secret computer-bunker, but can't get past the cage or case-level defences, they could potentially still use such an attack as this. Also, how do you test that your shielding is working? The paper notes that their probable noise source was a faulty electrolytic capacitor, which presumably wasn't [as] faulty when QA'd at the factory. So you'd need to periodically retest, which could get pricey fast.
Likewise, the engineering tradeoffs of shielding everything make it pretty impractical for mobile/portable devices, or ones that might be used in unsecured areas.
The main issue I see is that if this (or similar improvements) is truly something that could be implemented with a mobile phone or small MEMS microphone bug in the general vicinity, it's potentially cheap enough to make it not just a "how do I protect against the NSA?" problem, but one within the means of corporate or organised crime espionage groups.
[1] https://en.wikipedia.org/wiki/Maginot_Line
[2] well, as many as economically feasible anyway.
This is addressed in the linked page.
I recommend "Wrecking Ball" by Miley Cyrus. The strength of the attacker's cryptanalysis will be moot because no one will go near you.
... or is able to hack into your phone.
> 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 resisting 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.
The frequency variation is caused by load differences. So they are in fact doing an indirect power analysis. A switching power supply will always change frequency as a reaction to variations in supply current, this is inherent to its design. I also believe that it will be very difficult to "muffle" all the inductors and capacitors as they are subjected to very high pulse loads. Magnetics will always find a way to emit sound...
It's interesting to note that the biggest difference seems to be between register and memory instructions. This seems reasonable as memory instruction may, in the worst case, require powering the external bus, which is very power hungry. This will only get worse in future CPUs, as more and more clock gating is introduced.
So, I guess some countermeasures could be:
- If the CPU supports SMT or HT, load the other cores with a thread accessing random memory positions.
- Optimize the RSA code so that it's memory access and runtime pattern does not depend on the key or clean text.
- Try to localize the RSA code as much as possible to reduce memory accesses. If memory access is required, do it all at once, for example by swapping entire cache pages.
Some of these are highly CPU dependent.
http://git.gnupg.org/cgi-bin/gitweb.cgi?p=libgcrypt.git;a=co...
I don't understand how this would be, maybe because I don't understand what they mean by "using multiple cores."
You'd think that running a decoy thread on another core would mask things pretty effectively.
The lower the clock speed, the more you can hear in the audible frequencies.
Actually I think the job of the other core would be more difficult than just doing random noises to mask the noise from the actual secret computation. Simply doing random computations (and thus, random noises) of the other core is not effective since random noise would "easily" be canceled using statistical tools (for instance, looking at the variance of the data instead of looking at it directly will already reduce some type of noises).
What would be more effective would be to balance the noise for instance, maybe running the same computation with opposite data would balance it more effectively. To picture what I'm saying better, here is a completely fanciful example (just to provide an idea). Imagine that during the RSA exponentiation (where the private key is exposed), the operation that is done when the bit of the secret key is 1 makes the sound "s_s_" and when it is 0 the sound is "_p_k". If you do the the same computation as the secret one on the other core exactly at the same time, but with the opposite secret key, then whatever the key is the attacker will always ear "spsk" at each clock cycle. And that will be harder to attack than random noises (but is also more difficult to achieve, of course).
That said, I don't know why the use of multiple cores would help the attack (but I didn't read the paper, just a few sample of the linked web page).
However, I would not bet against the fact that your machine outputs "compromising emanations" (be they acoustic or RF or otherwise) leaking _some_ information about your bitcoin keys.
There is less opportunity to execute such an attack in the bitcoin universe, though, as bitcoin-qt doesn't reuse keys that much. (When you send a payment, the "change" difference is sent to a new key.)
It's something to think about, but the attack surface is a lot smaller. Perhaps there's something specific in the ECDSA algorithm that may make it easier or harder? I don't have the requisite mathematical understanding of elliptic curves to know how they're executed in-CPU.
Interesting for sure.
I even wonder how these big guys/heroes like Julian and Snowden feel when they find out about it. I mean, maybe they just don't care about the stuff they have being accessed without their consent, it is supposed to be released anyways, but what about their conversations that are supposed to be highly confidential?
Use some common sense.
Are you only doing one thing on your computer? No.
Does your Memory vibrate when the data is stored? No.
Can data be transferred via acoustics over a 2 conductor 16 gauge wire at the speeds memory is accessed or is sent to the CPU? No.
Think of something you have heard "hum". Is the noise pattern of your Amp and another the same if the "hum is anything other than 60hz? No. Because manufacturing tolerances are not such that the flaws are the same.
This is really great FUD. Likely designed to get People to think that they are constantly at risk, and have the CIA and FBI spend billions buying acoustic shields for their computers.
If this is real. And does work, fine, just run a background task that puts multiple random RSA's through the paces in alternate threads so the extraction can't take place because of garbled data.
EDIT: Apparently I forgot that HackerNews You get downvoted if you present common sense in face of a fallacy that those with limited understanding want to hold true, as seen by the mass of links to wikipedia made by those with out the foggiest about audio, capacitance, RSA, or Electrical engineering.
-Brandon Wirtz SMPTE
Specifically this:
>just run a background task that puts multiple random RSA's through the paces in alternate threads so the extraction can't take place because of garbled data.
Adding randomness does not remove detectable, statistically-significant information. It just takes more trials to extract it. This is the basis of many side-channel attacks. Super-trivial example: if you roll a super-weighted die and it shows 6 every time it's obvious, but if it's only barely weighted it'll still be detectable with enough rolls, to the same level of confidence (since getting 6 one hundred times in a row is not impossible with a fair die).
Determine a method given only the SUM of the di to determine the value of the weighted di.
Roll the die with it "off" a few billion times. You now have a very-consistent prediction about the range and probability of each value. Throw the switch to "on", roll a few times until you're sure it has been used up, then turn it off. Repeat a few billion times. Since the computation finishes at some point, the weighted die's influence will exist most-strongly at the beginning.
You're left with a crap-ton of random-ish fluctuations that over time shows a slight bias to being larger at the start (compared to "off"), after you turned it on. Since you know it's included once every 6 times (I'm assuming random here, to make it harder), it will be the distribution for 1/6th the size of the weighted value (or something similar, I forget exactly). If it wasn't randomly included, then you should see spikes every 6th round.
--
Note that this does not require knowing that you had dice at all, nor knowing how many, nor knowing that there is always a 6, 12, and 24 sided die in the mix and 2 dozen others. If you knew that, you could be more confident about what a normal distribution looked like, so you could finish earlier.
You don't have the level of control you think. You are assuming that you will know exactly. When in truth you will only know approximately.
The human analogy falls down because we are slow. But with computers you would be controlling it from a distance, and latency would mean you wouldn't know exactly when.
Besides, if you can get the output, you can tell how many rolls occurred, so it doesn't really matter. And this is a "chosen cyphertext" example, so the attacker has some idea of how long the computation will take under certain circumstances.
Of course you can.
Telephone with two cans and a string works. But not well enough that you can convert your Vinyl to OGG.
If you had an old 286 you might be able to hear peizo's but your laptop doesn't have many of the old style caps that hum with any appreciable noise. Your power isn't clean enough that you can separated the other noises, and with Wifi enabled you have all sort of other noises.
What is described here isn't possible with acoustics. Anyone with even a rudimentary understanding of Audio can see that.
Brandon Wirtz SMPTE Committee Member for the H.264 and VC1 audio and video standards (someone with rudimentary understanding of audio)
As a side note: it's not clear to me what being an "SMPTE committee member" entails, or why it confers any special expertise about cryptographic side-channel attacks. I only point that out because you've mentioned it in two separate comments now, and I don't see why it's relevant.
Once you realize that doesn't work everything else is irrelevant.
That that sound is significant enough that you can use a microphone, to pick it up from a distance greater than a fraction of an inch is implausible.
That the sound difference is such that it can be captured with any of the setups pictured in the paper is impossible. There are systems designed for frequency isolation that do megahertz sampling rates which you could convince me are capable of reading the 1's and 0's out of a 286. The frequencies of modern electronics that is simply not possible.
They are claiming to pick up a rather large algorithm change in code that runs for dozens of milliseconds to extract a single bit. A loop taking a bit over 26 vs. a bit over 28 microseconds in the example (or something reasonably close to that description). Why would this need such high-end equipment to pick up?
On an older computer an animated gif on a web page caused my speakers to feedback differently than playing video (and this worked even when the sound card was muted). And the signals never fully masked each other. I always suspected it was a grounding fault, but it was subtle and generally unobtrusive so I never tried to fix it (it's almost a feature, like a blinking hard drive light).
Notably it is far easier to hear through the amplifier that is the sound card, but even with no speakers, a quiet room will still show the same. As others noted above, CRT monitors are notoriously loud, and you can definitely hear different image patterns.
For me, the sounds I hear are somewhat like this: Animated GIF = chuff-chuff-chuff, one chuff per frame transition Scrolling terminal window = low hissing, like someone slowly breathing out Dragging window around the screen = high-pitched whine CPU stress test = very high-pitched whistling Loading a big app = a more noisy hiss than scrolling the terminal window, interspersed with HDD sounds
I was tested at a young age to have above-average hearing range, so maybe that also has a factor in how well you can hear these things; I don't listen to loud music or subject myself to loud noises either.
Side-channel attacks (like power analysis) in the presence of other activity are well established.
Electrical signals causing audible frequency output are also well established. Look up the piezoelectric effect[1], or magneto/electrostiction[2][3]. The demand for miniaturisation of everything means even at low voltages, there are quite substantial electric fields across small distances, which are enough to flex the material audibly.
On the magnetostriction side, the flyback transformer in old CRT televisions is a perfect example. Myself and many people have been able to tell whether the TV was powered up (even if totally muted) from outside the room (and yes, double-blind tested repeatedly).
What does wire gauge have to do with anything?
On the practicality/data rate issue, a nice quote from the very intro of their paper states:
> In a nutshell, the key extraction attack relies on crafting chosen ciphertexts that cause numerical cancellations deep inside GnuPG’s modular exponentiation algorithm. This causes the special value zero to appear frequently in the innermost loop of the algorithm, where it affects control flow. A single iteration of that loop is much too fast for direct acoustic observation, but the effect is repeated and amplified over many thousands of iterations, resulting in a gross leakage effect that is discernible in the acoustic spectrum over hundreds of milliseconds.
(emphasis mine)
It seems that the main focus of their work is to fingerprint the crypto and identify that a particular key was used (but not necessarily what the key is), which is a much easier problem than the one they talk about here, which requires specially crafted input over a substantial period of time.
Your solution might work, or it might just lower the SnR of the signal and require filtering larger quantities of data to extract the desired signal again.
The road to crypto-hell is paved with people who thought that they could use their "common sense" to reason intuitively about their problem. But to paraphrase Feynman, Mother Nature is not swayed by persuasive arguments.
[1] https://en.wikipedia.org/wiki/Piezoelectricity
If you have to ask any of the rest of your arguments are invalidated.
> Can data be transferred via acoustics over a 2 conductor 16 gauge wire at the speeds memory is accessed or is sent to the CPU? No
Which is of course true, if you're talking about >GB/s signals over wide buses.
But we're not. So I don't see why it's relevant here.
These attacks are not "sniff the actual data the CPU is flinging around by coupling to signal traces", so they don't need anything like full data-rate capability.
Edit: On re-reading your claim again, I noticed the phrase "transferred via acoustics over a 2 conductor 16 gauge wire" is a bit ambiguous. Do you mean transferred electrically over those wires, but limited to the typical acoustic frequency band (say, 0-20kHz)? Or do you mean actually acoustically coupled as mechanical vibrations of the wire itself? I can't imagine it makes any difference to my argument above, but I do wonder.
It actually seemed worse when my LCD TV broke last year and I pulled out my old CRT to watch a movie in the meantime. I don't know if I had just grown unaccustomed to hearing it or what, but it was annoying me even through the sounds of the movie.
If that interest someone, look for the BellCoRe attack on CRT-RSA [1,2]. I'm also working on the countermeasure as part of my PhD [3,4], and it's quite some fun!
[1] http://cryptome.org/jya/smart.pdf
[2] http://eprint.iacr.org/2012/553
You seem to be implying that doing multiple things on a computer means that every single side channel will be masked by noise indistinguishable from random. This is obviously false. Cryptographically secure random data doesn't just appear out of nowhere.
I'm not even concerned with the credibility of this article; side channel attacks are old news and will continue to be a threat for a long time (I'm guessing we don't even understand physics well enough yet to eliminate them completely, so there will still be new breaks all the time for the near future). Luckily, everyone is still too busy trying to remove their remote code vulnerabilities to deal with real issues like side channel attacks.