Scientists Extract RSA Key From GnuPG Using Sound of CPU 264
kthreadd writes "In their research paper titled RSA Key Extraction via Low-Bandwidth Acoustic Cryptanalysis, Daniel Genkin, Adi Shamir and Eran Tromer et al. present a method for extracting decryption keys from the GnuPG security suite using an interesting side-channel attack. By analysing the acoustic sound made by the CPU they were able to extract a 4096-bit RSA key in about an hour (PDF). A modern mobile phone placed next to the computer is sufficient to carry out the attack, but up to four meters have been successfully tested using specially designed microphones."
Re:It's not the fan or mechanical components (Score:4, Informative)
Even that gets filtered out:
"Q12: Won't the attack be foiled by loud fan noise, or by multitasking, or by several computers in the same room?
Usually not. The interesting acoustic signals are mostly above 10KHz, whereas typical computer fan noise and normal room noise are concentrated at lower frequencies and can thus be filtered out. In task-switching systems, different tasks can be distinguished by their different acoustic spectral signatures. Using multiple cores turns out to help the attack (by shifting down the signal frequencies). When several computers are present, they can be told apart by spatial localization, or by their different acoustic signatures (which vary with the hardware, the component temperatures, and other environmental conditions)."
Re:Yeah right? (Score:3, Informative)
You could have spent 5 minutes to skim the page where they address your questions.
Re:Daisy, Daisy... (Score:4, Informative)
You're missing the point. He typed mHz (millihertz) instead of MHz (megahertz).
This is probably not a big deal (Score:5, Informative)
What they are exploiting is that in naive implementations of RSA the amount of computer power needed during en/decryption varies with each binary digit in the key. If the digit is zero then no computation is done and if it is one that a tight loop is executed.
There have been other side channel attacks that exploit this weakness in naive implementations. The obvious fix is to slightly change the algorithm so the same computation is done whether the digit is a zero or a one. This reduces the efficiency by a factor of two but it makes these side channel attacks much more difficult.
In fact, the authors contacted GPG before publicly releasing this exploit and the fix is in place [tau.ac.il]:
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.
Q13: What countermeasures are available?
One obvious countermeasure is to use sound dampening equipment, [...]
Alternatively, one can employ algorithmic techniques to reduce the usefulness of the emanations to attacker. These techniques ensure the rough-scale behavior of the algorithm is independent of the inputs it receives; they usually carry some performance penalty, but are often already used to thwart other side-channel attacks. This is what we helped implement in GnuPG (see Q9).
Re:Yeah right? (Score:5, Informative)
What sounds does a cpu make?
They describe that in the paper's summary.
Or better yet how does a CPU make sound?
They describe that in the first line of the paper's summary, and also in question 2 of the Q&A.
The clock speeds are in the GHZ range so it is so far outside of the sound range of any microphone it just is not funny.
They address that at the end of the first paragraph of the paper's summary, and also in question 8.
Throw in that all cpus today have more than one core you will have a more than one code stream executing at one time.
They address that in question 12.
Throw in the sound of the fans running to make picking up the sound just seem very unlikely.
Also in question 12.
Until it is duplicated I would really doubt it.
OK, thanks for the valuable feedback.
Layman interpretation (generally) (Score:5, Informative)
Ok, I'm impressed.
For those that didn't want to RTFA, this works by letting the target computer spin on a carefully chosen piece of text. That text is chosen such that the CPU will do some predictable math (such as big equations that == 0). Then, those places where the CPU hits 0 can be heard through a sensitive microphone.
The neat part is that you're not looking for a 4096-bit key. Computers don't actually handle things with that large of a size, they have to break it down into 32-bit/64-bit chunks to be able to do the math. That's the real vulnerability - despite the key length itself being massive, because the number gets broken down into small chunks, you can start to handle it. The paper goes through a very complicated way of sensing each section of a large key, and then piecing it all together. This is not a case of hearing a specific noise, and looking it up in a table. It's not even a case of looking up 32-bit chunks in a table.
So, it is a real attack, that is mostly dependent on the breakdown of the 4096bit key into bitesize chunks, that go through known math routines. If you can get the target to nicely decrypt several well-crafted messages for you, and you can get a good microphone near their CPU while they do it, and you can let this process go on long enough (so the attack program can listen to the CPU for a while to build up a profile, etc.), it really can work.
I'll say that it needs kind of an ideal scenario to get all those things lined up, but it's not impossible.
Preventing it fully is really only possible with two ways. Either switch your CPU to not use those bite-size chunks, and have the decryption take place all in one massive math operation (not realistic), or change the math that occurs on the bite-size chunks to be irregular in terms of any recognizable patterns (very realistic).
Re:Remember TEMPEST? (Score:5, Informative)
Your objection was directly addressed in the article:
"Cryptanalytic side-channel attacks typically require measurements with temporal resolution similar to the time scale of the target operation, but here the target cryptographic computation is many orders of magnitude faster....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
I dare suggest that sometimes even the experts need to RTFA.
Re:Remember TEMPEST? (Score:2, Informative)
Hi.
the Nyquist limit of the audio sampling hardware of a cell phone over instruction rate of a modern CPU is a pretty small fraction.
Also, potatoes are delicious. Both statements have very little to do with the paper in question.
Re:Yeah right? (Score:4, Informative)
The variable power load would very based on the instructions but we are not really interested in the instructions we are interested in the data. Doing an instruction on any data should cause the same power draw so how do they extract the data?
There's an 8MB PDF linked from the summary that has your name all over it. Instead of asking questions like that and waiting for the answer and ignoring all of the work that they did in producing the paper, just read the paper and get the answers.
So it can only work with some keys?
It is a chosen-ciphertext attack, not a chosen-key attack.
The summary really does not answer the questions.
Yeah, no shit. The summary is not supposed to answer all of the question. You know what is supposed to answer the questions? The paper.
The idea that the sound can extract the data violates the Nyquist–Shannon sampling theorem.
Don't tell me, tell them. Review their paper, find the flaws in it, and tell them. That's what peer review is about.
Re:Remember TEMPEST? (Score:5, Informative)
Q11: Can you realistically perform the chosen-ciphertext attack on GnuPG?
To apply the attack to GnuPG, we found a way to cause GnuPG to automatically decrypt ciphertexts chosen by the attacker. The idea is to use encrypted e-mail messages following the OpenPGP and PGP/MIME. For example, Enigmail (a popular plugin to the Thunderbird e-mail client) automatically decrypts incoming e-mail (for notification purposes) using GnuPG. An attacker can e-mail suitably-crafted messages to the victims, wait until they reach the target computer, and observe the acoustic signature of their decryption (as shown above), thereby closing the adaptive attack loop.