Some Clarification on the RSA Power Attack

I recently posted on the some new work by researchers at the University of Michigan which showed how an RSA private key can be recovered by sifting through a collection of faulty signatures. The faults are created by lowering the power to the chip computing the signature, causing bits to be flipped in the signature multiplication chain. 

I remarked that the coverage from The Register was a bit unfair in its headline of OpenSSL being broken, which was just the cryptographic library used in the proof-of-concept experiment to test the private key recovery procedure. But as pointed out by Bradley Kuhn, the researchers seemed to stress the weakness of OpenSSL against the attack by mentioning it both the abstract and the conclusion of their paper.

But there have been some other posts bordering on the hysterical. Techie Buzz, 1024 Bit Cracked, New Milestone, leads the chorus of RSA’s demise

The RSA encryption was believed to be quite safe and this level of a crack was not achieved, until now. The methods used here are pretty low level and have given results in 100 hours. The crack which was assumed to take a lifetime with brute force, has taken a mere four days. This breaks the very backbone of RSA which believes that as long as the private key is safe, it is impossible to break in, unless guessed.

The post celebrates the fault-based factoring as an advance on the 768-bit factoring record achieved late last year. However the factoring of the RSA 768-bit modulus was unaided by any tricks, and the researchers used modern factoring methods in a distributed computation amounting to over 10^{20} operations. The results are simply not comparable since the fault-based attack is so advantageous to the attacker.

A more sober review is presented by Phil Brass, of Accuvant Insight, in his post Recent Encryption Research Demystified, where he describes the publicity of the attack as “headline hyperbole”. You should not be too worried about your online banking service since

to carry out this attack on an online banking server, the attacker would need physical access to the online banking server’s power supply, which means they would need to be inside the bank’s data centre.  Given the “wealth” of other targets available to an attacker standing inside of a bank’s data centre, theft of the online banking web server private SSL key by a difficult and time-consuming voltage regulation attack seems rather unlikely.

And as to the key recovery experiment itself

The really strange thing about this paper is that while the researchers claim to have implemented the attack on a full-size SPARC/Linux/OpenSSL workstation, the actual hardware was a Xilinx Virtex2Pro FPGA, which was emulating a SPARC CPU, and which the researchers claim is representative of an off-the-shelf commercial embedded device. It seems as if they are trying to have it both ways – i.e. it is an attack against a full-size workstation, and by the way it also is an attack against something you might see in a typical embedded system.

He provides a good summary of the attack and offers that a better headline would be “Obscure bug in OpenSSL library poses little risk to consumers.”  A similar reality check for the hoopla is given by Nate Lawson of Root Labs Rdist, who begins by recalling that the brittleness of the RSA signature operation was identified in 1997 (referenced by the Michigan researchers), with the advice to verify all signatures very carefully before returning them. Lawson provides some more details on the error checking steps taken for signature computations in OpenSSL and he concludes that a much better job could have been done. He is also a bit sceptical of the experimental environment but finally concludes “this was a nice attack but nothing earth-shattering”.

Finally, there is another de-hyped review by Luther Martin at Voltage, where he refers to the PBA Attack after the initials of the three Michigan authors. He states that

Devices that are designed to be secure, like HSMs and smart cards, filter the power so that you can't do attacks like the PBA attack, and with devices that aren't designed to be secure, there's always an easier way to recover a key from them than doing something like the PBA attack. This means that we won't be seeing hackers using the PBA attack any time soon, but you'd never think this from seeing the way it was reported by the media.

Fortunately for this incident Voltage products use DSA rather than RSA for signatures, so advanced debunking for customers will not be required.

All in all, most everyone agrees (and is happy to say) that the work is clever and worthwhile to undertake, adding to our operational knowledge of cryptography. The publicity was a bit overdone, and probably too many hours were spent by security professionals explaining the circumstances and implications of the attack.

Related articles by Zemanta

• 1024-bit RSA encryption cracked by carefully starving CPU of electricity (engadget.com)
• RSA 1024-bit Private Key Encryption Cracked (q-ontech.blogspot.com)
• 'Severe' OpenSSL vuln busts public key crypto (go.theregister.com)
• The PBA attack on RSA (superconductor.voltage.com)
• Boffins Crack OpenSSL Library Using Power Fluctuations (darknet.org.uk)

Recovering RSA Private Keys using Faulty Signatures

Researchers at University of Michigan recently devised a method for recovering the RSA private key used for signing by sifting through a collection of faulty signatures produced by the key. A faulty signature is one where the attacker has caused bits in the signature computation to be flipped from one to zero, or zero to one. Fault patterns that consist of just a single flipped bit permit an attacker to guess and verify a small piece of the private key (called a window), and to eventually recover the entire private key given a sufficient number of such faulty signatures. The researchers ran proof-of-concept experiments to demonstrate that a 1024-bit RSA private key can be recovered from a sample of just under 9,000 faulty signatures created by manipulating the voltage level to the processor computing the signatures.

There are two main ingredients to the attack: a method to recover information about the private key given some faulty signatures, and then a method to actually generate or induce the faulty signatures. We deal with the second point first.

Generating Faults Through Power Fluctuations

The researchers chose to exploit vulnerabilities in modern circuitry to changes in environmental conditions (such as temperature or power fluctuations) that inhibit signal propagation, which lead to faults in computations. The researchers experimented with varying the voltage on a SPARC-based Leon3 server running Debian, using OpenSSL for signing operations. Using runs of 10,000 multiplications the researchers discovered that 1.25V was the optimal value to induce single fault errors, and that reducing the voltage much further resulted in an exponential increase in faults (totally spurious results).

At this optimal voltage level the researchers found that from a sample of 10,000 signatures about 90% would contain at least one fault, and 12% contained exactly one fault. Note that the attacker can distinguish between faulty and non-faulty (correct) signatures by verifying with the public exponent, but cannot distinguish a priori between faulty signatures that contain one fault as opposed to those that contain multiple faults. As explained below, the most computationally intensive part of recovering the private key is performing repeated searches over the pool of faulty signatures looking for a particular single fault pattern.

Guessing and Verifying Exponentiation Windows

The signature of a message M is computed as the exponentiation M^D mod N where D is the private RSA exponent, and N the corresponding modulus. Exponentiation is computationally intensive, and is achieved through repeated (modular) multiplication. The well-known binary method computes M^d mod N by processing D bit-by-bit from left-to-right (most significant to least significant bit) in a series of squarings and multiplications. The binary method can be improved upon by processing the exponent in groups of bits, say 4 bits at a time. This approach is called the m-ary method and the groups of exponent bits are called windows (the binary method can be thought of as the 1-ary method, processing 1-bit windows).

At each step in the signature computation, m squarings are performed followed by a single multiplication if the window is non-zero. The attack devised by the researchers works by recovering the bits in the most significant window, followed by the next most significant window, until the entire private key is recovered. If the current window targeted for recover is window W, then the attacker requires a faulty signature on M such that a single fault was induced during the processing of the exponent bits represented by W.

The researchers derive an equation that involves the message to be signed M, the faulty signature S, the value of the window W, the position of the fault, and the sign of the fault (add or subtract). By equation here we mean an expression that has a left-hand side and a right-hand side which can be compared for equality. The attacker can then plug all possible values of W, the position fault and fault sign into this equation and collects solutions. There will either be no solutions, one (unique) solution, or more than one (multiple) solution. In the first and last cases, no information about D can be extracted since either the fault did not occur during the multiplication for W, or there are multiple faults in S. and another pair (M, S) must be examined. If the solution is unique then the bits of W are determined and the attacker can move on to breaking the next window using the same guess-and-verify approach.

The search for a given pair (M, S) that has a single fault in a position covered by a specified window W is computationally intensive. If S is a faulty signature then the attacker cannot easily determine the number or position of the faults in the signature. The researchers generated 10,000 signatures, of which 8,800 were faulty, and tried to recover the 1024-bit exponent. Using an 81-processor cluster this took 104 hours, with the guess-and-verify step for each window taking 2.5 seconds. The private key was recovered after 650 single fault signatures processed.

Conclusion

The Register has headlined the announcement as breaking OpenSSL, but this unfair. OpenSSL was used in the experiments but other libraries are also likely to be vulnerable to restricting voltage to induce hardware faults. As to the practicality, the attacker is required to have physical access to the device housing the private key, and be able to request or observe 10,000 or so signatures, computed under reduced voltage. These seem to be quite generous circumstances for the attacker, and given such proximity the attacker may prefer to try for a Cold Boot Attack instead. In any case, the attack shows the importance of verifying the correctness of signing operations – all the faulty signatures could be detected by merely checking that M = S^E before returning any results. Apparently this is what OpenSSL developers are doing at the moment.