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.