Recent Encryption Research Demystified
March 08, 2010
Last week, NetworkWorld published an article under the headline “RSA 1024-bit private key encryption cracked.” RSA encryption was one of the first widely-used asymmetric key algorithms, meaning it used two keys, one public and one private. A message encrypted with the public key couldn’t be decrypted without the private key, the idea being that your public key would be published so that anybody could encrypt messages with your key and send them to you, and the private key is kept secret so that only you could decrypt and read those messages.
This asymmetric encryption idea was such a huge improvement over previous shared-secret cryptosystems that it is used in everything from web browsers, where it protects sensitive transactions like online banking and shopping cart checkouts, to cryptoprocessors used in banking mainframes, embedded devices like iPhones and mp3 players, and credit-card sized smart cards like those that protect premium satellite and cable TV content. The most common use of RSA is probably in web browsers and web servers, with an installed base of more than one billion personal computers.
Given such pervasive use of asymmetric crypto, and RSA’s algorithm in particular, news that 1024-bit private key encryption has been cracked would be alarming indeed. Fortunately for all the online shoppers out there, this is another example of headline hyperbole. The article outlines the findings of a paper titled “Fault-based attack of RSA authentication” that describes an attack the authors carried out on an encryption library that implements the RSA algorithm, called the OpenSSL library. In order to perform the attack, the authors had to tamper with the power supply of the computer they were attacking, lowering the voltage just to the point where the computer would still operate, but occasionally operate incorrectly.
So, the first thing to note is that the thing that was cracked was the OpenSSL library’s version of the RSA algorithm. The paper did not find any weaknesses in the actual RSA algorithm itself. And the second point of interest is that the attack required physical access to the power supply of the target system. For example, 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 center. Given the “wealth” of other targets available to an attacker standing inside of a bank’s data center, theft of the online banking web server private SSL key by a difficult and time-consuming voltage regulation attack seems rather unlikely.
These restrictions make the attack sound like something that is purely theoretical, and not useful in real life. While it is true that online shopping and banking probably aren’t under much threat from this kind of attack, RSA and related algorithms are used in many other applications. This kind of attack is most likely to be carried out against systems that are designed to operate in a public environment: smart grid electric meters for example, or consumer electronics devices like iPhones and game consoles - any device with a private key embedded in the hardware that could, if extracted, be used to impersonate the device or card.
While this kind of attack is most useful against embedded devices, the paper’s author’s claim that one of their contributions with this research is demonstrating that voltage-manipulation fault injection attacks can be applied to larger devices like the microprocessors found in desktop PCs and servers. 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. (What kind of embedded system would be running Linux on an emulated SPARC on an FPGA? Maybe an embedded cryptoprocessor or something).
The attack seems to be based on causing short-lived faults in the CPU during one of the RSA signature algorithms used by OpenSSL. Since this kind of attack has been around for a while, the OpenSSL library actually contains some code to counter it. According to the paper, the signature is first generated with the private key rather quickly using Chinese Remainder Theorem style multiplication. Then the signature is checked, using the public key. If the signature is invalid, the system assumes it was attacked and goes to a slower, but supposedly more attack-resistant signature mechanism, i.e. left-to-right squaring.
According to the paper, the results of the fallback left-to-right squaring RSA signature are not checked before the signature is sent to the other party. That is probably the bug in OpenSSL. Because the result isn’t checked, an invalid signature is sent. The recipient can use these invalid signatures to infer information about the private key and with enough invalid signatures and processing time, the entire private key can be broken.
While the NetworkWorld headline is an exaggeration, the paper itself could probably be summarized in the following three sentences:
- It is possible to perform fault-based crypto attacks against microprocessor systems, at least when they are implemented in an FPGA.
- The OpenSSL RSA signature algorithm’s fallback algorithm, left-to-right squaring, is also vulnerable to fault-injection style attacks, even though it was supposedly chosen as the fallback algorithm because of its increased resistance to such attacks.
- The OpenSSL RSA signature algorithm apparently doesn’t check the result of the fallback algorithm prior to sending signed messages.
The paper does present an attack that might be used to jailbreak the next iPhone or Xbox, or clone satellite TV or cable cards, at least if any of those systems use a vulnerable version of OpenSSL. However, a more accurate headline might have been “Obscure bug in OpenSSL library poses little risk to consumers.”