How-to: crack 1024 bit RSA encryption by clusterf*ck
Granted, it’s a how-to on a theoretical level, but still. The RSA algorithm is used for for public-key cryptography and was publicly described in 1978 by messieurs Ron Rivest, Adi Shamir and Leonard Adleman (in case you read this before you’ve had your first cup of coffee of the day – the initials of their surnames spell RSA. You’re welcome). It was released to the public domain on the 6th of September, 2000. The abstract of the patent explains that what we’re talking about here, is basically
[a] communications channel coupled to at least one terminal having an encoding device and to at least one terminal having a decoding device.
That’s all well and good, but what does that mean?
A message-to-be-transferred is enciphered to ciphertext at the encoding terminal by first encoding the message as a number M in at predetermined set, and then raising that number to a first predeterminated power … and finally computing the remainder, C, when the exponentiated number is divided by the product of two predetermined prime numbers … [where] [t]he residue C is the ciphertext. The ciphertext is deciphered to the original message … by raising the ciphertext to a second predetermined power … and then computing the residue, M’, when the exponentiated ciphertext is divided by the product of the two predetermined prime numbers associated with the intended receiver. The residue M’ corresponds to the original encoded message M.
There you have it. Now, three computer scientists at the University of Michigan, Andrea Pellegrini, Valeria Bertacco and Todd Austin, claim to have found a way (PDF) to exploit a weakness and they start off by explaining that computer security boils down to having both secure hardware ans well as secure software. Compromise to the hardware layer may cause information in the software layer to be exposed, while being very hard to detect. They explain, in detail, “… an end-to-end attack on a microprocessor system and practically demonstrate how hardware vulnerabilities can be exploited to target secure systems”. The attack is an injection of “transient faults” in the target machine by, get this, “regulating the voltage supply of the system”. This means that the attack doesn’t require direct access to the target’s internal components but proximity to it.
There are three major blocks to consider in the paper; first off, they develop a “systematic fault-based attack on the modular exponentiation algorithm for RSA”. Then they exploit a flaw in OpenSSL‘s implementation of the RSA signature algorithm. Lastly, a physical demonstration of a fault-based security attack. The attack targeted the OpenSSL authentication library running on a SPARC Linux system and extracted the system’s 1024-bit RSA private key in 104 hours, using a 81 2.4 GHz Intel Pentium4-based Linux cluster with the OpenMPI libraries where one computer acted as the server and the remaining 80 a slaves. “The master distributed around 110 messages to each slave for checking. Individual slaves could check a message against a single potential window value and all fault locations and squaring iterations in about 2.5 seconds. During the analysis, the master directed all slaves to check their own messages for a particular single-bit fault in a particular window of the FWE computation. To reduce the time for synchronizing slaves, they divided their messages into 4 equal-size groups, and processed these groups serially until the value of the key window was found”.
This is pretty wild for a couple of reasons. First off, this sort of attack doesn’t damage the device, thus eliminating any evidence. OpenSSL is basically everywhere and even though the private keys contain more than 1 000 digits of binary code, which would take longer than the age of the universe to guess, voltage tampering cut that number down to roughly 100 hours. The hardware needed to do the actual tampering is quite inexpensive and simple and the varying voltage stresses the computer, causing it to produce small mistakes in its communication. These mistakes reveal ever so small pieces of the private key. When enough faults had been caused, the key could be reconstructed offline. Thankfully, the researchers hinted at a solution as simple as salting, which randomizes the order of the digits every time the key is requested. Still, not that shabby for a 30+ year old piece of technology. Or math. Whatever. The press release can be found right about here.
I’d like to leave you with some words of wisdom from an Engadget user.
If humans make it, Humans [sic] can destroy it.
Word.
No related posts.
