Forgot your password?
typodupeerror
Encryption Technology

Scientists Extract RSA Key From GnuPG Using Sound of CPU 264

Posted by Soulskill
from the noisy-fans-are-now-a-feature dept.
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."
This discussion has been archived. No new comments can be posted.

Scientists Extract RSA Key From GnuPG Using Sound of CPU

Comments Filter:
  • Remember TEMPEST? (Score:5, Interesting)

    by Bruce Perens (3872) <bruce@perens.com> on Wednesday December 18, 2013 @06:10PM (#45730735) Homepage Journal

    TEMPEST was a details-secret government requirement meant to defeat means of eavesdropping on classified computer data from its electromagnetic emissions. I guess they need to include audio too.

    My impression is that the noise comes from the power supply, not the CPU. I can certainly hear it with some computers, and it is related to work on the video card in my experience. I'm astonished that you can actually pull data from that, and in fact I'd like to see independent confirmation before I believe it.

    • by Hatta (162192) on Wednesday December 18, 2013 @06:12PM (#45730767) Journal

      Seems like GPG could defeat this pretty easily by putting in some random HLTs.

      • by Gothmolly (148874) on Wednesday December 18, 2013 @06:21PM (#45730873)

        Or HCF, if you wanted to be really sure.

    • I don't think you need that. It shouldn't be all that surprising. It's all a matter of the signal/noise ratio of how a "slice" of a program's execution trace maps onto something you can measure from the outside. I'm more wary of the "one hour" requirement. If it's one hour of continuous execution of RSA routines, it's not exactly practical. But it shows how dangerous making assumptions can be ("hardware protection (386 protected mode, HW virtualization etc.) is sufficient for preventing information leaks!")
    • Re:Remember TEMPEST? (Score:5, Interesting)

      by DaveAtWorkAnnoyingly (655625) on Wednesday December 18, 2013 @06:31PM (#45730983)
      I'm not a computer scientist by trade, I'm an engineer (nukes), and this sounds dubious. Perhaps I'm way behind the curve on acoustic engineering, but being able to pull a 4096 bit key from noise that not only is pretty polluted, but also, surely depending on what the PC is doing, could be dependent of lots of other things?

      Also, it's Bruce Perens. Hi!
      • I was wondering how far I'd have to scroll down to see someone call BS on this. Wish I had mod points now.

        • by Algae_94 (2017070)

          I was wondering how far I'd have to scroll down to see someone agree with me. Wish I had mod points now.

          FTFY

      • by Opportunist (166417) on Wednesday December 18, 2013 @06:53PM (#45731239)

        Well, think of it like trying to hear an opera singer in between a lot of traffic noise. Even your ear can do that to some degree, but for software it is fairly trivial to separate the song from the other noises, especially if you know what opera is being sung. The singer might not be singing in the key you know or he might have a bit of variety in the way he interprets the song, but you know in general what it should sound like so you know what to look for, and then you work from there.

        • by bug1 (96678)

          you know in general what it should sound like so you know what to look for, and then you work from there

          If it was just one opera singer it might be reasonable to "work from there", but keys need to be 100% correct unless they are combinign it with a brute force attack, but then they would still need to know whci hbits they heard correctly.

          But i still call bullshit, what if there are more than one opera singers singing, or its some new age music that has elements of opera, but isnt really opera at all.

          What if a bug flys into your fan ?

        • I'm not current on the relevant literature, but I thought that this is something that computers tend to be generally inferior to humans at. Think about voice recognition and how awful almost all of it is.
        • Your analogy may work if you add that the sound of the singer is at frequencies near 1GHz (a high-frequency coloratura soprano?), and the sound is filtered as usual through a 44kHz lowpass filter before being recorded.

      • by zlives (2009072)

        I am sure it is my shortcoming:
        i wonder if a single core processor with a single repeating process in isolation could eventually reveal the process if additional processes are added later, but then again i am flabbergasted as to how it actually reveals the code... to me it has the sense of dousing for encryption keys...

      • 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.

        • Re: (Score:2, Informative)

          by chuckugly (2030942)

          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.

      • Particularly relevant high-level from the PDF:

        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.

      • by loufoque (1400831)

        In the situation in question, they fully control the load of the computer.

      • by sonamchauhan (587356) <sonamc&gmail,com> on Thursday December 19, 2013 @06:19AM (#45734447) Journal

        Also, it's Bruce Perens. Hi!

        Also, while we are still in 'appeal to authority' mode, the coauthor of the paper is Adi Shamir, the 'S' in RSA.

    • Thus far, it seems theoretical more than practical. Not only is it a chosen-plaintext attack, it also requires the user repeatedly decipher the text many times before the key can be extracted. I can't think of any practical way of getting people to do that (unless you can somehow get to the key in a Visual Basic Outlook script or something). That's my understanding of the paper, with this relevant quote:

      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

      Since microphones can't grab frequencies in the Ghz range (where CPUs operate), they can't directly obse

    • by Burz (138833)

      Yet the processing for that key nevertheless stretches out quite a while in computing terms; Choose the right time scales at which to analyze the acoustic signal, and perhaps something like an RSA key can be recovered where most other types of info are beyond reach because they are processed only fleetingly.

  • by sideslash (1865434) on Wednesday December 18, 2013 @06:13PM (#45730773)
    This makes me re-think the push toward quiet, fanless computers. Now I am thinking that I want a white[/some other color] noise generator to add privacy to my personal computing.
    • by LNO (180595) on Wednesday December 18, 2013 @06:21PM (#45730871)

      It's more awesome than that. The white noise generated by the fan doesn't matter at all.

      "The acoustic signal of interest is generated by vibration of electronic components (capacitors and coils) in the voltage regulation circuit, as it struggles to maintain a constant voltage to the CPU despite the large fluctuations in power consumption caused by different patterns of CPU operations. The relevant signal is not caused by mechanical components such as the fan or hard disk, nor by the laptop's internal speaker."

      The attack scenarios are even more fantastical. I have no idea how plausible they are, but wow, regardless:

      "We discuss some prospective attacks in our paper. In a nutshell:
      Install an attack app on your phone. Set up a meeting with your victim, and during the meeting, place your phone on the desk next to the the victim's laptop (see Q2).
      Break into your victim's phone, install your attack app, and wait until the victim inadvertently places his phone next to the target laptop.
      Have a web page use the microphone of the the computer running the browser (using Flash or HTML Media Capture). Use that to steal the user's GnuPG key.
      Put your stash of eavesdropping bugs and laser microphones to a new use.
      Send your server to a colocation facility, with a good microphone inside the box. Then acoustically extract keys from all nearby servers.
      Get near a TEMPEST/1-92 protected machine, such as the one pictured to the right. Put your microphone next to its ventilation holes and extract its supposedly-protected secrets."

      • It's more awesome than that. The white noise generated by the fan doesn't matter at all.

        Right, I mentioned the fan as one source of noise to act as a countermeasure (not a good one, of course, since you want something random).

        • by LNO (180595) on Wednesday December 18, 2013 @06:27PM (#45730937)

          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)."

    • Moving back to fan computers won't help so you can keep your ultra quiet fans. Read The Fine Article:

      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 si

      • Moving back to fan computers won't help so you can keep your ultra quiet fans. Read The Fine Article:

        *sigh* ... yes, I was aware of that. That was why in the next sentence I suggested adding a random/colored noise generator.

  • Daisy, Daisy... (Score:5, Interesting)

    by jtara (133429) on Wednesday December 18, 2013 @06:16PM (#45730813)

    In High School, we had a program we would run on the IBM 1620 (this was in ancient history...) that would play a song on a transistor radio placed on the console. Somebody figured out what instructions to run to create different frequencies.

    We used to just leave the radio there even when not running that program.

    "That's a loop!"

    "Whoa! A "FORMAT" statement!"

    One can easily see how A leads to B.

    • Re:Daisy, Daisy... (Score:5, Interesting)

      by Spiridios (2406474) on Wednesday December 18, 2013 @06:26PM (#45730923) Journal

      In High School, we had a program we would run on the IBM 1620 (this was in ancient history...) that would play a song on a transistor radio placed on the console. Somebody figured out what instructions to run to create different frequencies.

      We used to just leave the radio there even when not running that program.

      "That's a loop!"

      "Whoa! A "FORMAT" statement!"

      One can easily see how A leads to B.

      Back when the 486dx4 was out, I'd tune my FM radio to ~100mHz and listen to the weird whirs and buzzes that occurred during disk access or mouse movement. Many years later, during a security class of all things, when I suggested using this as a method to leak information out of a secure room, the speaker said using radio transmission to leak information was much too sophisticated to be a viable attack for anything but the government and military.

    • On every motherboard I've owned the onboard audio always picked up noise from unrelated CPU, or maybe GPU, activity. Moving the mouse, opening a menu, and just typing would create random clicks and buzzes from the speakers. And, naturally, there was the white noise, no doubt from the poor quality hardware. The only way I could get sound to work well is with a discrete sound card.

  • I'm turning off the web server right now!

  • by sandytaru (1158959) on Wednesday December 18, 2013 @06:26PM (#45730925) Journal
    I'm totally going to use this if I'm ever asked to turn my music down in the office. "But sir, this is increasing my encryption security!"

    Since 90% of the people in my office are not tech people, that just might work.
  • by nurb432 (527695) on Wednesday December 18, 2013 @06:34PM (#45731021) Homepage Journal

    I run a quantum computer. Good luck getting noise from that.

  • New? (Score:5, Interesting)

    by Anonymous Coward on Wednesday December 18, 2013 @06:36PM (#45731045)

    Wait, this is a new paper? Neat, they updated it since 2004. Um, this is a pretty old technique, I've seen it demonstrated, on GnuPG, no less, before. RSA squares and multiply have different loops. This one, I know, GCHQ did first.

    It's one of the reasons we like Ed25519 and the other safecurves - constant time loops, no key-dependent branches, massively reduces side-channel attack potential.

  • I'm sure the NSA has been doing this for some time. Not to mention listening in on keyboard sounds and emissions from computer displays to get the same information.
  • by wonkey_monkey (2592601) on Wednesday December 18, 2013 @06:40PM (#45731091) Homepage

    but up to four meters have been successfully tested

    Were they all the same size?

  • by cold fjord (826450) on Wednesday December 18, 2013 @06:59PM (#45731295)

    There have been other attacks previous discussed here as I recall, such as using power fluctuations or timing attacks, and so on, as cribs to retrieve a key. It appears this sort of attack that exploits the characteristics of the system performing the encryption will continue to be an attack vector of growing importance.

    Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems [cryptography.com]

    Abstract. By carefully measuring the amount of time required to perform private key operations, attackers may be able to find fixed Diffie-Hellman exponents, factor RSA keys, and break other cryptosystems. Against a vulnerable system, the attack is computationally inexpensive and often requires only known ciphertext. Actual systems are potentially at risk, including cryptographic tokens, network-based cryptosystems, and other applications where attackers can make reasonably accurate timing measurements. Techniques for preventing the attack for RSA and Diffie-Hellman are presented. Some cryptosystems will need to be revised to protect against the attack, and new protocols and algorithms may need to incorporate measures to prevent timing attacks.

    Breaking DES with side-channel attacks [isy.liu.se]

    This lab will demonstrate how power analysis of cryptographic hardware can reveal the key. We will be using basic electronic measurement tools such as oscilloscopes to demonstrate this side-channel attack.

    You will be using a small hardware board (fig. 1) with a generic microprocessor programmed to perform DES encryption and decryption. The scenario is that you are the attacker and want to find out the secret key stored inside the board. There is no way of getting to the key directly, so you will need to perform a side-channel attack by measuring the power consumption of the board while the algorithm is running. The hardware board also allows the user to load a custom key in order to compare the power consumption.

    And to think that there were people poopooing NSA for pulling cables and servers that Snowden had access to. More attack vectors for everybody!

    The technology inside Apple’s $50 Thunderbolt cable [arstechnica.com]

    A source within the telecom industry explained to Ars that active cables are commonly used at data rates above 5Gbps. These cables contain tiny chips at either end that are calibrated to the attenuation and dispersion properties of the wire between them. Compensating for these properties "greatly improves the signal-to-noise ratio" for high-bandwidth data transmission.

  • by DrJimbo (594231) on Wednesday December 18, 2013 @07:06PM (#45731351)

    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).

  • Back when I had my TRS-80 Model 1 you could 'listen' to the 1.77 MHz Z80 processor do its thing on any AM radio nearby. Now get off my lawn.
    • Back when I had my TRS-80 Model 1 you could 'listen' to the 1.77 MHz Z80 processor do its thing on any AM radio nearby. Now get off my lawn.

      In those days I carried a transistor radio and used it for debugging - (on stuff substantially larger than a TRS-80). It gave subtle insights into how much time the machine was spending in different parts of algorithms. (The ear and its post-processing in the brain is really good at picking this stuff out.)

      The rise of multitasking, with fine-grained time slices, ruine

  • by avoisin (105703) <swh8@cornell.edu> on Wednesday December 18, 2013 @07:25PM (#45731479)

    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).

  • rsa works by doing the same little set of manipulations over and over, masked downstream by a counter and/or how compressed your data is. this set of manipulations manifests as a (probably not very) musical note which repeats itself over and over in the cacophony every machine radiates, and unfortunately it is the constant repetition which gives the game away.

    unfortunately it is the blindly repetitive nature of the operation which makes rsa even vagely feasible given the vast amounts of data we expect it t

  • Put toddlers around the office to drown out the CPU sound.

  • I run grid computing using the BOINC and World Community Grid, so my four cores are running flat out all the time.

    Would this be enough to blind any software that was trying to listen to the noise your CPU makes? Sort of a CPU white noise generator?

  • Back in the 80s when personal computers began to appear on every desk, the NSA was spending a ton of money to shield every PC they had. So when they built their new main offices at Fort Meade, they decided it was cheaper to shield the entire building.

  • TFA did not mention the particular fix to the problem, so I'll speculate. They mentioned that zeros would cause a recognizable branch, so choices are: make the code non-branching, or make the timing of the branch for zero the same as not branching. Other possibilities include inserting pseudo-random delays in the code, processing sections of the message out of order (randomly), and interspersing decoding of bogus messages with the decoding of the real message.
  • by Cley Faye (1123605) on Thursday December 19, 2013 @05:45AM (#45734319) Homepage
    From what I muster, it's far from exploitable in real-life scenario. Still impressive though, and this might broaden the way peoples see side-channel attacks on general computers, and not only on specific hardware.
    Still, http://www.debian.org/security/2013/dsa-2821 [debian.org]

Whenever a system becomes completely defined, some damn fool discovers something which either abolishes the system or expands it beyond recognition.

Working...