The takeaway: Researchers have found a way to forge certain RSA signatures without considering the key behind them, challenging a long-held assumption about one of the oldest public-key cryptosystems on the Internet. The attack does not appear to compromise the most commonly used RSA implementations today, including those protected with PKCS or PSS padding. However, the results have attracted attention because they show that breaking RSA signatures may not always require private key recovery.
The technique is handy for 1,024-bit RSA keys that are already outdated. It also reduces the estimated security of 2,048-bit and 4,096-bit keys when used in vulnerable blind signature systems.
“If this result holds up in peer review, it would indeed be a conceptual breakthrough,” Karsten Nohl, cryptography expert and head of innovation at Allurity, told Ars Technica. “RSA is just as hard to crack as factoring large integers, or so we thought. The researcher suggests that you can practically crack RSA without cracking its key.”
RSA security is traditionally based on the difficulty of decomposing a large number into its two main components. The public key contains this large number while the private key is derived from the factors. The standard view was that an attacker had to factor the number before creating a valid signature.
The new research takes a different approach. It uses a version of the special Number Field Sieve algorithm as well as an Oracle available in some blind signature protocols. An oracle is a system function that reveals useful information in response to specific requests. By making a very large number of requests and processing the results, an attacker can gather enough information to create a valid signature.
Factoring a 1,024-bit RSA key is estimated to require approximately 2^80 operations and between 500,000 and 1 million CPU core years. The researchers said their forgery attack took about 2^65 operations and 1,380 CPU core years. They carried out the work over several months using an academic CPU cluster.
Nadia Heninger, a professor at the University of California, San Diego and co-author of the study, said the result differs from cryptographers’ expectations.
“Cryptographers thought that the only way to calculate valid RSA digital signatures was to first calculate the private key by factoring and then use the private key to calculate the signatures,” she said. “For 1,024-bit RSA, this was considered very expensive, although it is probably feasible if you have the computing resources of major tech companies or the NSA – on the order of tens of millions of dollars of computing time for a single key. For 2,048-bit RSA, it was considered completely unattainable.”
The authors estimate that the attack reduces the effective security of 1,024-bit RSA to approximately 2^65 operations. For 2,048-bit and 4,096-bit keys, they put the values at 2^90 and 2^119, respectively. The security guidelines of the National Security Agency, the National Institute of Standards and Technology and the European Union Agency for Network and Information Security require at least 128 bits of security.
The team said its estimates could improve. The implementation was written by hand and did not use GPUs or AI tools. The researchers said these tools will “almost certainly” reduce the cost of future attacks.
The attack is limited to blind signature implementations, sometimes referred to as textbook RSA. These systems allow a party to sign information without seeing its contents. Most RSA deployments don’t work this way. They use PKCS or PSS padding, which modifies the data before it is encrypted or signed, preventing the behavior on which the attack relies.
A real-world application of blind signatures is Privacy Pass, a protocol that allows users to prove they are authorized without revealing their identity. Apple, Cloudflare and other organizations use Privacy Pass. The researchers estimate that an attack on such a system would require requesting 2^43 tokens from an issuer.
Heninger said the volume is large, but not necessarily beyond the scope of a large online service. “Sounds [like] a lot, but is on the same scale of network traffic that Cloudflare says it can handle in about a day.”
Many Privacy Pass systems rotate their keys regularly, making an attack more difficult by reducing the time to collect tokens. However, this does not eliminate the risk.
