Researchers Claim RSA Authentication Crack

By Brian Prince  |  Posted 2010-03-03 Print this article Print

Researchers at the University of Michigan say they have uncovered a way to circumvent encryption used on many devices.

The research is the work of Valeria Bertacco, Todd Austin and Andrea Pellegrini. According to their paper, entitled 'Fault-Based Attack of RSA Authentication' (PDF), the trio demonstrated a way to beat the popular encryption method, which is used in media players, laptop computers, smartphones and other devices. It is also used by retailers to secure customer information online.

The researchers found that by varying the voltage on a device it was possible to get their hands on the 'private key' needed to beat the security feature. Using what they described as an inexpensive device specially-built for the experiment, the trio manipulated the voltage and caused the computer to make small mistakes in its communications with other clients. This ultimately revealed small pieces of the private key, which they eventually used to reconstruct the key offline.

From the paper:

"The paper makes three important contributions: first, we develop a systematic fault-based attack on the modular exponentiation algorithm for RSA. Second, we expose and exploit a severe flaw on the implementation of the RSA signature algorithm on OpenSSL, a widely used package for SSL encryption and authentication. Third, we report on the first physical demonstration of a fault-based security attack of a complete microprocessor system running unmodified production software: we attack the original OpenSSL authentication library running on a SPARC Linux system implemented on FPGA, and extract the system's 1024-bit RSA private key in approximately 100 hours."

These private keys contain more than 1,000 digits of binary code. Due to their size, trying to guess a private key would be an exercise in futility - in fact, it would take as long as the age of the universe, Pellegrini, a doctoral student in the Department of Electrical Engineering and Computer Science, said in a statement announcing the research.

"The RSA algorithm gives security under the assumption that as long as the private key is private, you can't break in unless you guess it. We've shown that that's not true," said Bertacco, an associate professor in the Department of Electrical Engineering and Computer Science, in the statement.

Pellegrini is slated to present the findings next week at the Design, Automation and Test in Europe conference in Dresden on March 10. While the paper only discusses the problem, the researchers say a technique called "salting" - where the order of the digits is changed in a random way every time the private key is requested - can help address the issue.

While the three said a hacker would probably not use the attack on a large institution, they also believe mobile device manufacturers, media companies and consumers should be concerned.

"We've demonstrated that a fault-based attack on the RSA algorithm is possible," Austin said in the statement. "Hopefully, this will cause manufacturers to make a few small changes to their implementation of the algorithm. RSA is a good algorithm and I think, ultimately, it will survive this type of attack." |

Submit a Comment

Loading Comments...
Manage your Newsletters: Login   Register My Newsletters

Rocket Fuel