Hardware attack on RSA implementation

Researchers at the University of Michigan have succeeded in accessing the private RSA key used by an embedded processor by manipulating the power supply to the processor. The attack targets the calculation of RSA signatures using the FWE (fixed window exponentiation) algorithm, which is used, for example, in the OpenSSL cryptographic library. The attack was carried out on a SPARC-based Leon3 Soc embedded processor, which runs on an FPGA from Xilinx and is, according to the researchers, a representative embedded system.

The attack described in a paper by Andrea Pellegrini, Valeria Bertacco and Todd Austin is based on reducing the voltage of the power supply to the processor unit just far enough to induce occasional bit errors in the multiplication operations required for calculating signatures. The mathematical characteristics of the FWE algorithm mean that in certain cases erroneous signatures can be used to calculate four bits of the private key. Because it is impossible to predict which signatures will contain a suitable error and which four bits of the key can be calculated from a given erroneous signature, the technique requires the collection of large numbers of signatures.

Reconstructing the secret key from a set of 8,800 erroneous signatures took a cluster of 80 PCs about 100 hours. A report on The Register cites cryptography expert Karsten Nohl as stating that it is relatively easy to equip the FWE algorithm with error detection to stymie this attack. The OpenSSL development team plans to release a patch to this effect shortly.

The attack is likely to prove difficult to use in practice. According to the researchers, you need around 1,000 faulty signatures that had exactly one bit flipped during the FWE calculation. Even in the researchers' special test system, which was aimed solely at generating signatures, only 10 per cent of signatures met this criterion.

In practice few actual systems would be able to be induced to continually generate signatures which an attacker could read without further ado. If a processor is primarily concerned with other stuff, the voltage manipulation will primarily generate errors, and quite possibly crashes, in code for non-RSA related functions.

In addition, RSA-based cryptography is rare on embedded systems – examples include HDMI/HDCP or TPM modules, which are generally implemented on special chips. The extent to which the FWE attack can be used on other processors and cryptographic systems remains to be seen. In most situations there are likely to be much easier ways – e.g. cold boot attacks – of getting hold of the private key.

See also:

• Fault-Based Attack of RSA Authentication, a University of Michigan white paper.

(djwm)