Become a fan of Slashdot on Facebook

 



Forgot your password?
typodupeerror
Encryption Security IT Linux

Researchers Find Way To Zap RSA Algorithm 173

Posted by timothy
from the vhat-here-in-ze-laboratory dept.
alphadogg writes "Three University of Michigan computer scientists say they have found a way to exploit a weakness in RSA security technology used to protect everything from media players to smartphones and e-commerce servers. RSA authentication is susceptible, they say, to changes in the voltage supply to a private key holder. While guessing the 1,000-plus digits of binary code in a private key would take unfathomable hours, the researchers say that by varying electric current to a secured computer using an inexpensive purpose-built device they were able to stress out the computer and figure out the 1,024-bit private key in about 100 hours – all without leaving a trace. The researchers in their paper outline how they made the attack (PDF) on a SPARC system running Linux."
This discussion has been archived. No new comments can be posted.

Researchers Find Way To Zap RSA Algorithm

Comments Filter:
  • by Anonymous Coward on Thursday March 04, 2010 @03:06PM (#31361876)

    ...whether interrogating a human or a computer, apparently it is a simple matter of voltage.

  • Article == Summary (Score:5, Informative)

    by fishwallop (792972) on Thursday March 04, 2010 @03:06PM (#31361882)
    The only thing the article "ads" to the summary posted here is a pretty splash screen, which in my case tried to sell me SQL Server.
    • by Sir_Lewk (967686) <sirlewk@NospAm.gmail.com> on Thursday March 04, 2010 @03:11PM (#31361940)

      A first poster that actually RTFA? What the hell is slashdot coming to?!?

      He's right though, skip TFA and just read the linked PDF if you want more details.

    • Re: (Score:3, Informative)

      by wizardforce (1005805)

      There are two articles, one is mostly worthless. The other is a PDF which is actually much more informative. The attack focuses on the implementation of RSA in OpenSSL and uses a cluster of processors to carry out the attack. All in all TFA notes that about a year of computing time is actually required to extract the key. The voltage manipulation causes faults which are used to extract the key after quite some time.

    • by poetmatt (793785)

      and the only thing it lacks is that all of this is basically impossible under FIPS 140-2 on level 4 products. [wikipedia.org] Notice how it talks about voltage sensitivity. Meanwhile FIPS 140-3 is on it's way, and from level 4 on involves this.

      I myself don't know how widespread using level 1-3 devices is, however.

      • by electrostatic (1185487) on Thursday March 04, 2010 @06:50PM (#31364912)
        A very pertinent comment.

        Level 4

        Security Level 4 provides the highest level of security.

        At this security level, the physical security mechanisms provide a complete envelope of protection around the cryptographic module with the intent of detecting and responding to all unauthorized attempts at physical access.

        Penetration of the cryptographic module enclosure from any direction has a very high probability of being detected, resulting in the immediate zeroization of all plaintext CSPs.

        Security Level 4 cryptographic modules are useful for operation in physically unprotected environments. Security Level 4 also protects a cryptographic module against a security compromise due to environmental conditions or fluctuations outside of the module's normal operating ranges for voltage and temperature. Intentional excursions beyond the normal operating ranges may be used by an attacker to thwart a cryptographic module's defenses. A cryptographic module is required to either include special environmental protection features designed to detect fluctuations and zeroize CSPs, or to undergo rigorous environmental failure testing to provide a reasonable assurance that the module will not be affected by fluctuations outside of the normal operating range in a manner that can compromise the security of the module.

    • When the summary is taken straight from the article, it's a good idea to at least link to them..

  • Just means it's time to break out the megabit keys!
  • by Animats (122034) on Thursday March 04, 2010 @03:08PM (#31361898) Homepage

    Machines where software can alter the CPU voltages and clock speeds for "overclocking" purposes may be especially vulnerable to this attack. "Advanced power management" may also offer an attack vector.

    Also worry about Intel's Nehalem architecture, where there's a small CPU dedicated to power, clock, and thermal management. Access to that allows detailed control over power.

    • by pegr (46683) on Thursday March 04, 2010 @04:11PM (#31362608) Homepage Journal

      "the researchers say that by varying electric current to a secured computer"...

      Um, if they have physical access to the computer (in order to monkey with the power), why would it be considered secure?

      • Um, if they have physical access to the computer (in order to monkey with the power), why would it be considered secure?

        This vulnerability is dangerous in the case when the same key is being used in many devices. Cracking one means you've cracked them all. This is a fairly common situation in consumer devices. See the HD-DVD player keys, or the TI graphing calculator signing keys.

        • I used to do something like this with a 6502 and an AM radio.

      • by gringer (252588)

        if they have physical access to the computer (in order to monkey with the power), why would it be considered secure?

        You've got me stumped. Perhaps you should ask the companies who make these media players, smartphones, and other devices that use RSA. While you're at it, could you please also ask the same question to the companies who distribute digital files for use on these devices?

      • by pz (113803) on Thursday March 04, 2010 @04:39PM (#31363124) Journal

        "the researchers say that by varying electric current to a secured computer"...

        Um, if they have physical access to the computer (in order to monkey with the power), why would it be considered secure?

        The faults described by the paper are so ... what's the word ... specialized that it challenges believability. Not only does the attacker have to have physical access -- and likely pretty good physical access -- they have to know precisely when the encryption algorithms are being performed so that the faults can be induced then and only then otherwise the operation of the computer will be compromised. Furthermore, the faults must be induced at a reasonable, but not too great, rate, and at randomly varying times in the computation, so as to explore the full error space and have insight into the keys. And the computations have to be repeated MANY times over in order to extract enough information. So, not only do attackers have to know exactly, to the microsecond, when the system under attack is computing the RSA algorithm, they also have to be able to vary the voltage to the CPU. Their physical proof of concept, as much as it is described in the paper, is contrived. Their assertion that the technique does not require physical access is wholly unsupported. Color me skeptical. Anyone with this level of access is going to be able to do more than trigger faults.

        The paper asserts that the probes can be done without leaving any trace. I don't know about the authors, but the voltages on my computers are monitored by software and excursions logged so that I can know if/when there are problems. Since the RSA-breaking technique requires substantial exploration of the response to voltage tweaks, it is likely to be detected by a decent monitoring program.

        Finally, the PDF does not carry any publication information suggesting strongly that it describes work that is not peer-reviewed. It is shoddy science to bypass peer review and release to the general public.

        • by lgw (121541)

          Cryptographic "breaks" are almost never useful attacks in the real world. They are merely ways to make it slightly easier to get to the plain text, in some case. These accumulate over time, and eventually you retire an algorithm because it seems like in just a few more years a practical break might happen.

          Product-of-prime-numbers asymmetric encryption (what some people call RSA encryption) has been deprecated by the NSA for new systems for about 5 years now.

        • It's "physical access" beyond most would even dream of... SPARC sounds like they're using an off-the-shelf computer system. They aren't. They downloaded the open source SPARC core (as in the source code to the CPU itself) and implemented it as a soft-processor in an FPGA chip. They're basically using their own custom computer system, with complete control and the ability to know exactly how it works, down to the deepest logic in the CPU.

          Call me when they implement this on an off-the-shelf secure embedded sy

      • Um, if they have physical access to the computer (in order to monkey with the power), why would it be considered secure?

        Because it's in a locked sheet metal box that makes every attempt to purge sensitive key material if tempering is detected?

    • When you overclock, you always have to check system stability at each level you try. Most people run some CPU stress program and see if it crashes or gives the wrong results. If you get any faults, your CPU can't handle the overclock and you have to try a lower frequency. As long as you apply this procedure properly, you won't have any faults. You most certainly won't get any predictable amount of faults. Now, the researchers could do it because they only ran OpenSSL on their hardware. If you tried that on

      • Also, Intel chips, like Nehalem, actually have voltage converters on the chip which change 12V and 5V inputs to the 1.5V or so that the CPU needs. So your Core i7 system is quite safe against this attack. (Yes, it overclocks. See above)

        Nope. The 12V to 1.xV converters are always on the motherboard (right next to the CPU). Modern CPUs might have smart power switching, but they definitely don't have on-board regulators. DC-DC voltage conversion requires large inductors, which you can't get on a chip anyway, a

    • by Weezul (52464)

      Intel's Nehalem chips are vulnerable to far easier and speedier attacks using their HTT technology, plus HTT attacks do not require rooting the machine.
      http://www.daemonology.net/papers/htt.pdf

  • by ravenspear (756059) on Thursday March 04, 2010 @03:08PM (#31361908)
    ...electronic torture?

    We can just declare this method in violation of the computer's rights and solve the problem easily!
  • by anss123 (985305) on Thursday March 04, 2010 @03:09PM (#31361910)
    In what kind of scenario would you have access to the PSU of the server you attacked? Private key servers should not be directly accessible after all.
    • Re: (Score:2, Insightful)

      by Anonymous Coward

      In what kind of scenario would you have access to the PSU of the server you attacked?

      E.g. Hosted data center

      • Re: (Score:3, Insightful)

        by interval1066 (668936)

        Kinda reminds me of the TrueCrypt attack that made a splash a couple of years ago in which the attacker can compromise an encrypted partition by obtaining possession of the host hardware right after a power-down, getting inside the chassis and spraying down the RAM DIMMS with an inverted can of air so as to cool them down to slow the entropy of the down-powered chips; the attacker then has to create and analyze the leftover ram images with his own hardware and pull the encryption key out of that mess. As th

      • Not quite. The voltage that was varied was the 1.5v CPU voltage. This is regulated on the motherboard (The PSU on the computer supplies +3.3v, +5v, -12v and +12v). So to execute this attack, you'd either need access through the bios to the CPU voltage control, or to physically tamper with the voltage regulator module present on server motherboards (Destop motherboards typically have this integrated instead of socket fit making it a lot harder to tamper with). Since both contain voltage regulators, simpl
        • by Andy Dodd (701)

          Also, this is an attack against software running on the host CPU (OpenSSL in the paper) - most likely, 95%+ of OpenSSL implementations on datacenter servers are storing the key on the hard drive, not in a TPM.

          • Well, it doesn't matter where the key is stored. The key must be read in order to be processed. So at some point in time the appropriate parts of the key must be in the CPU (since it needs to do math against the bits of the key to produce the signature), hence why the attack vector exists...
        • by lgw (121541)

          FIPS 140-2 level 3 requires zeroing of the key upon tamoer detection, but not detection of voltage or temperature abnormalities (those are level 4). This attack would be interesting against such a device.

    • by fuzzyfuzzyfungus (1223518) on Thursday March 04, 2010 @03:16PM (#31362020) Journal
      Probably much more threatening(though, frankly, that pleases me) to DRMed embedded systems and similar gear that is supposed to be "secure" vs. its immediate environment; but is also in the hands of the public in huge quantities.

      Yeah, if I can break into your datacenter and clamp some crazy widget onto the (presumably multiple) lines supplying your server's PSUs, a clever voltage attack is not the biggest of your problems.

      If, on the other hand, you can guess the private crypto keys out of a DRMed PMP just by clipping a 15 dollar device from some shady mod-chip vendor to the recharging port and waiting a few days, heads will roll. There are a lot of devices these days that are designed to keep keys secret from the owners of the hardware. Particularly for common ones, voltage attack devices might well become fairly common advanced hobbyist and/or grey market items...
    • Re: (Score:3, Interesting)

      This attack is relevant when you are trying to extract the private key of something like a TPM, in order to defeat the DRM protections it is trying to provide, or decrypt the drive whose key it is holding.

      • Re: (Score:3, Interesting)

        by owlstead (636356)

        TPM chips and certainly high end smart card chips are protected against this kind of attacks using the power source. You certainly cannot get a Common Criteria certification if you don't protect against these kind of side channel attacks. Of course, for consumer CPU's there' no CC certification or protection measures like these.

    • Re: (Score:3, Insightful)

      by benjamindees (441808)

      DRM, smart-cards, cable/tv access boxes, media players, stolen laptops, etc

      Probably not e-commerce servers exactly, but you never know depending on the physical security of your datacenter. And with DRM, of course, the purpose is to lock you out of equipment to which you have physical access.

    • Re: (Score:3, Insightful)

      by sjames (1099)

      When the 'server' is a chip on a smart card and the 'PSU' is your POS terminal.

    • by Hatta (162192)

      When you're the government.

    • Re: (Score:3, Informative)

      by pclminion (145572)

      In what kind of scenario would you have access to the PSU of the server you attacked?

      I don't know, how about a world where you've arrested a political dissident and you want to obtain his/her private key, and he/she refuses to hand it over?

    • In what kind of scenario would you have access to the PSU of the server you attacked? Private key servers should not be directly accessible after all.

      Uh, like the scenario where you're a bank's IT admin and you're trying to steal PIN encrypting keys?
      BTW, you should require direct access to load or change keys if you know what's good for you.

      Hardware crypto devices already tackle these problems, this research is further justification for them.

  • by snarfies (115214) on Thursday March 04, 2010 @03:11PM (#31361952) Homepage
    Rather than apply electrical current to a key holder, wouldn't it be easier and cheaper to apply a $5 wrench? [xkcd.com]
  • wrong headline (Score:5, Informative)

    by Lord Ender (156273) on Thursday March 04, 2010 @03:12PM (#31361964) Homepage

    Researchers Find Way To Zap RSA Algorithm

    No, reasearchers find side-channel attack on SPARC CPU (which requires elevated access, anyway).

    • Re:wrong headline (Score:5, Informative)

      by Andy Dodd (701) <atd7&cornell,edu> on Thursday March 04, 2010 @03:34PM (#31362190) Homepage

      To be more specific:

      No one attacked the algorithm itself here. They attacked one specific implementation of the RSA algorithm.

      Side channel attacks are nothing new. There are plenty of crytographic algorithms that have no known flaws which have had implementations broken via side channel attacks, due to flaws in the implementation, not the algorithm.

      • Re:wrong headline (Score:4, Insightful)

        by osu-neko (2604) on Thursday March 04, 2010 @03:43PM (#31362298)

        ...due to flaws in the implementation, not the algorithm.

        The "flaw in implementation" in most cases being the relatively common "flaw" of being implemented in real-world hardware, where it has to consume power, utilize moving electrical current, obey the laws of physics, etc, rather than existing only on paper where such "flaws" can be avoided.

        • Re: (Score:2, Interesting)

          by c++0xFF (1758032)

          "In theory there is no difference between theory and practice. But, in practice, there is."

          (p.s. Who originally said this, anyway?)

          • by lgw (121541)

            I believe it was the same sage who said "You can observe a lot just by watching." Of course, he also said "I never said most of the things I said," so it's hard to be sure.

      • by OzPeter (195038)

        There are plenty of crytographic algorithms that have no known flaws which have had implementations broken via side channel attacks, due to flaws in the implementation, not the algorithm.

        While I agree with you, I just want to go a bit philosophical and suggest that the robustness of the physical system is just as important as the algorithm when determining how flawed or not something like a security system is. Which is basically a "weakest link" consideration.

        • by Andy Dodd (701)

          Right. Which is why there are guidelines for implementing crypto algorithms so as to avoid sidechannel attacks.

          Occasionally someone finds a new sidechannel attack (such as one that relied on the Pentium 4's hyperthreading implementation), but most of the "basic" ones are well known and can be designed against. (See, for example, FIPS 140-2 level 4, which requires protection against glitching attacks such as this.)

    • by blair1q (305137)

      And unless I RFA'd wrongly, they had to map the SPARC to an FPGA in VHDL so they could be sure their assumptions about multipliers being the critical path would remain correct.

      Because if their glitching of the power supply is inducing bit-flip errors in anything other than the multiplier, they're probably going to crash the core, and they won't get the thousands of samples they need to reach 50% probability of pwning the private key in polynomial time.

      I.e., it is vanishingly unlikely that you are going to b

  • by Anonymous Coward on Thursday March 04, 2010 @03:15PM (#31361992)

    hackers these days are seriously sick, not long ago one guy dissolved chips and listened in on instructions right on die
    now this, just take a look at that paper

    sure the principle is simple, create condition that causes errors and incidentally more of the bits you have guessed the less errors you have etc etc etc

    but seriously people who figure these things out and make them work... i question their sanity, brilliant but you have to be a mad scientist to achieve these things

  • !news (Score:5, Informative)

    by betterunixthanunix (980855) on Thursday March 04, 2010 @03:20PM (#31362056)
    This is just a fault injection attack. People have been doing similar things to block ciphers for years, it is not a mathematical weakness, just a side channel attack, and an active one at that. Cool that they did it against RSA, but not really headline news...
  • Physical Access (Score:5, Insightful)

    by KevMar (471257) on Thursday March 04, 2010 @03:21PM (#31362068) Homepage Journal

    If someone has physical access to your machine, then you have already lost.

    • Re: (Score:2, Interesting)

      If someone has physical access to your machine, then you have already lost.

      So everyone who ever uses colocation has lost?

      • Re:Physical Access (Score:4, Informative)

        by Eric Smith (4379) <eric&brouhaha,com> on Thursday March 04, 2010 @03:45PM (#31362322) Homepage Journal
        So everyone who ever uses colocation has lost?

        Yes. Are you actually surprised?

      • Re:Physical Access (Score:5, Insightful)

        by OzPeter (195038) on Thursday March 04, 2010 @03:50PM (#31362362)

        So everyone who ever uses colocation has lost?

        Given that organized crime seems to be paying off minimum wage clerks to install card skimmers in gas pumps, wouldn't it be logical that minimum wage admins at co-lo facilities would also be vulnerable to the same vector - $$$$

        • Hell, even well-paid admins could be vulnerable. All kinds of things can result in a need for money. Insurance problem, spouse gets fired, simple greed....
          • by turing_m (1030530)

            Hell, even well-paid admins could be vulnerable. All kinds of things can result in a need for money. Insurance problem, spouse gets fired, simple greed....

            Gambling and drug problems are also classic cases of needs for lots of money and an addiction that overrides ethical considerations.

        • But of course, no sysadmin at say, a dinosaur zoo would ever resort to such shenanigans. And he certainly wouldn't smuggle the hardware in a can of Barbasol.

      • by lgftsa (617184)

        Yep, they've made the decision that there's nothing on the server which they can't afford to lose. Or they're idiots.

        They're placing all their trust in the security and vetting standards of their co-lo, from the admins and techs, to clerical staff, plant and maintenance, cleaners, safety inspectors, linoleum layers, electricians, the list goes on. That assumes, of course, that the co-lo has standards and follows them without exception. I don't have the time or resources to audit them.

        Our server room is only

      • in as few words as possible:

        Yes.

        If you co-anything you are giving up your security.
        now I have not just one, but mutiple targets for the tried and true XKCD wench hack. http://xkcd.com/538/ [xkcd.com]
        so, if security is the name of your game, you have already lost.
        please try again...

    • Re: (Score:3, Interesting)

      If someone has physical access to your machine, then you have already lost.

      Quoted for truth.

      If someone can gain access to your datacenter power systems remotely and change output voltages, your admins are idiots and you've got more problems than just a RSA vulnerability. And if someone already has physical access to your server thats performing the encryption in the first place, is it any surprise that they can bypass said encryption?

      It's a nifty attack, but not terribly practical.

  • by starglider29a (719559) on Thursday March 04, 2010 @03:24PM (#31362102)
    ...except for the empty bags of cheese puffs, Rockstar cans, and several bottles of "lemon gatorade", no one would suspect that they had been there.
  • Back years ago I read a book where the good/Bad guys got a suitcase sized AI to break down and confess by cycling its power to the point where it couldn't take it any more.

    Good to see reality starting to mimic fiction

    BTW Can anyone tell me the title? About the only other main thing I remember about it was helicopter pilots being blinded by laser strikes.

    • by Baby Duck (176251)

      Psychic Dictatorship in the U.S.A. talks about pilots being blinded by lasers when spying on Russian vessels. I don't remember anything about an AI in it, though.

      Despite its sensational title, the book declares mind control to be bogus. However, that hasn't stopped people from trying -- and committing atrocites in the process.

      It also discusses ambassadors and spies contracting rare blood diseases from being exposed to very low frequency radiation emitters in their offices over long periods of time. This is

      • by OzPeter (195038)
        Unfortunately thats definitely not the book I am thinking about. In the one I read there was a lot of AI stuff.
  • by ronys (166557) on Thursday March 04, 2010 @03:48PM (#31362350) Journal

    It's an implementation on specific hardware that was broken. Not the first time, nor the last. If the *algorithm* would have been broken, now *that* would have been news!

  • by BitZtream (692029) on Thursday March 04, 2010 @04:09PM (#31362582)

    Great, another 'if you have physical access to the key, you can get the key' methods.

    Look, 'stressing' the computer for a hundred hours while screwing with the voltage is going to get you noticed if its a key important enough for to use this method to do it. I can go to your PC and steal the contents of the entire drive without leaving a trace, but you're probably going to notice when I move you out of my way so I can put in a boot cd and external drive to copy the data to.

    Practical value: 0
    Research value: 1
    Geek Cred: 11
    Priceless, or rather, worthless.

    • Extracting private keys from smart cards would be one application. That's a case where you have "physical access" to the key holder, but it's protected by physical security. The card will erase the key if you open the box, but it provides a digital signature service, which you can exploit via this method to extract the key without opening the case.

  • http://www.apc.com/ [apc.com]

    Seriously. If your server is a big enough target where to have it's keys taken using this technique is beneficial (a key signing server for example) then you need a bit more protection against somebody hanging outside on a pole playing with your electricity supply.

  • The concept is called Differential Power Analysis (DPA) or for people in the industry its also known as power cryptography and has been a staple of many attack vectors since the mid-90s (at least in open research), furthermore simple techniques such as adding salt or in other words randomly chosen bogus operations into the computation flow renders such attack vectors useless.

    Nothing new here, slow news day, move along peoples.

       

    • by owlstead (636356)

      Then they mention Linux, which has little to none-to do with it. Of course, you can only reach the add by clicking away a Microsoft add. It's amazing what kind of articles are displayed on Slashdot now and then. Even the comments are starting to deteriorate (not yours of course).

      But you can be sure my home will stay void of Sparc processors after this fiasco :) The Niagra processors all have RSA in hardware so if the software uses that they are safe anyway. They probably chose a single CPU with easy RISC in

      • by xquark (649804)

        That is absolutely correct, slashdot is going downhill as of the last couple of years.

        As for your comment regarding "single CPU with easy RISC instructions" thats also absolutely correct as well, back in 98' when I was reviewing the ideas coming out of Cryptography Research (cryptography.com), we could only ever get this kind of thing to work on smart-cards for that very reason, they all have a single execution pipe-line, no prefetch or look-ahead algorithms, essentially instructions/data are pumped in and

  • NO, they did not find a glitch in the algorithm, they happened to find an implementation which was amenable to their attack method.

    All the chip makers have to do is take any one of several measures:

    (1) Regulate the CPU voltage on-chip.
    (2) or just detect that it's below spec and force a reset.
    (3) or do the calculation two times, or in two different ways, or both, and reset if the results don't match.
    (4) or add a few gates of carry-lookahead to the multiplier so it's not so speed-sensitive.
    (5) or detect

  • I find it striking how much Figure 8 in the PDF, showing the location of single-bit faults, resembles the acoustic power spectrum [unsw.edu.au] of something behaving like a closed tube. I see clear odd numbered partials and weak even numbered partials, with a missing fundamental. I would not be surprised if this distribution turns out to be connected to the exact timing of the attacks. Sweeping the timing of the attacks may cause other bits to be affected.

    Mal-2

"'Tis true, 'tis pity, and pity 'tis 'tis true." -- Poloniouius, in Willie the Shake's _Hamlet, Prince of Darkness_

Working...