Researchers forged RSA signatures without ever cracking the key

The takeaway: Researchers have found a way to forge certain RSA signatures without factoring the key behind them, challenging a long-held assumption about one of the internet's oldest public-key cryptosystems. The attack does not appear to threaten the RSA implementations most commonly used today, including those protected with PKCS or PSS padding. But the findings have drawn attention because they show that breaking RSA signatures may not always require recovering the private key.

The technique is practical against 1,024-bit RSA keys, which are already deprecated. It also lowers the estimated security of 2,048-bit and 4,096-bit keys when they are used in vulnerable blind-signature systems.

"If this result holds up under peer review, it would indeed be a conceptual break-through," Karsten Nohl, a cryptography expert and head of innovation at Allurity, told Ars Technica. "RSA is as difficult to break as it is to factor large integers, at least so we thought. The researcher suggests that you can practically break RSA without cracking its key."

RSA security has traditionally rested on the difficulty of factoring a large number into its two prime components. The public key contains that 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 another route. It uses a version of the special number field sieve algorithm, along with an oracle available in some blind-signature protocols. An oracle is a system feature that reveals useful information in response to specific requests. By making a very large number of requests and processing the results, an attacker can collect enough information to generate a valid signature.

Factoring a 1,024-bit RSA key is estimated to require about 2^80 operations and between 500,000 and 1 million CPU core-years. The researchers said their forgery attack used 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 University of California at San Diego professor and co-author of the research, said the result departs from what cryptographers expected.

"Cryptographers thought that the only way to compute valid RSA digital signatures was to first compute the private key by factoring, and then use the private key to compute the signatures," she said. "For 1,024-bit RSA, this was thought to be very expensive, albeit probably doable if you have the computational resources of the large tech companies or the NSA – on the order of tens of millions of dollars of computation time for a single key. For 2,048-bit RSA, it was thought to be totally out of reach."

The authors estimate that the attack reduces the effective security of 1,024-bit RSA to about 2^65 operations. For 2,048-bit and 4,096-bit keys, they put the figures at 2^90 and 2^119, respectively. Security guidance from the National Security Agency, the National Institute of Standards and Technology and the European Union Agency for Network and Information Security calls for at least 128 bits of security.

The team said its estimates could improve. Its implementation was written by hand and did not use GPUs or AI tools. The researchers said those tools will "almost certainly" lower the cost of future attacks.

The attack is limited to blind-signature implementations, sometimes called textbook RSA. These systems allow a party to sign information without seeing its contents. Most RSA deployments do not work this way. They use PKCS or PSS padding, which modifies the data before it is encrypted or signed and prevents the behavior the attack relies on.

One real-world use of blind signatures is Privacy Pass, a protocol that allows users to prove they are authorized without exposing their identity. Apple, Cloudflare and other organizations use Privacy Pass. The researchers estimate that attacking such a system would require requesting 2^43 tokens from an issuer.

Heninger said that volume is large but not necessarily beyond the scale of a major online service. "Sounds [like] a lot, but is on the same order of magnitude of the network traffic that Cloudflare has said publicly it handles in about a day."

Many Privacy Pass systems rotate their keys regularly, which makes an attack harder by shortening the time available to collect tokens. That does not eliminate the risk, however.