The RSA encryption algorithm may be even more endangered now, courtesy of University of California, San Diego and Inria Nancy researchers.
Cyber Security News reported that a new signature forgery attack detailed in the researchers’ paper deployed a novel method to crack 1,024-bit RSA encryption without factoring (finding the two primes used to create a key). The researchers were able to break encryption with an academic CPU cluster that dedicated 1,380 CPU core-years to the problem over five months. Factoring a 1,024-bit RSA key, Cyber Security News noted, has previously been estimated to require 500,000 to 1 million CPU core-years.
RSA is not quantum-resistant, potentially meaning anything encrypted using it today could be broken by future attackers with access to a quantum computer. (The most obvious candidate is a nation-state.)
Ars Technica reported that the results bring even 2,048-bit and 4,096-bit keys to unacceptably low levels of security per standards published by the National Security Agency, the National Institute of Standards and Technology (NIST), and the European Union’s main cybersecurity agency. The NIST already plans to deprecate RSA by 2030 and eliminate it by the middle of the next decade.
“If this result holds up under peer review, it would indeed be a conceptual break-through,” Allurity head of innovation and cryptographer Karsten Nohl told Ars Technica. “RSA is as difficult to break as it is to factor large integers, at least so we thought.”
The technique relies on a variant of the number field sieve algorithm which Cyber Security News noted was first proposed in 2007, but which researchers hadn’t run at this scale until now.
This isn’t a short-term threat. Beyond the immense computing capacity required, the technique doesn’t appear to be effective against RSA using PKCS#1 v1.5 or PSS padding. Those techniques package extra data into encrypted communications to make them harder to crack, and are in widespread (but not universal) deployment today.
UC San Diego professor and co-author Nadia Heninger told Ars Technica an attack on Apple’s or Cloudflare’s 2,048-bit implementation of Privacy Pass, which does not use either form of padding, would take about as many token requests as Cloudflare handles HTTP requests daily.
Quantum computers capable of breaking RSA at scale are under development, but remain largely theoretical. Two studies earlier this year, however, suggested that breaking a separate public-key method called elliptic-curve cryptography may take fewer resources than previous estimates.
