Researchers devise an RSA signature-forgery attack that skips factoring

Cryptographers have long assumed that the only way to break RSA was to factor the large integers behind its keys. A team led by Nadia Heninger, a professor at the University of California, San Diego, devised a signature-forgery attack that computes valid RSA signatures without factoring the private key — a result that surprised the field. The paper is on the IACR ePrint archive and has not passed peer review. The finding poses little practical threat for now, except possibly in a few edge cases.

What the attack does

Computing valid RSA signatures was thought to require recovering the private key by factoring first. For 1024-bit RSA that was very expensive but probably within reach of large tech companies or the NSA — tens of millions of dollars of computation time per key — while 2048-bit RSA was considered out of reach, Heninger said.

The attack drops the estimated security of textbook RSA to 2^65, 2^90 and 2^119 operations for 1024-, 2048- and 4096-bit keys respectively — far below the 128-bit level (more than 2^128 operations) that the NSA, NIST and the EU's ENISA require of any cryptosystem. Factoring one 1024-bit key was estimated at 2^80 operations and 500,000 to 1 million CPU core-years; forging a signature with the sieve-based technique took 2^65 operations and 1,380 core-years. The team wrote all its code by hand, without AI or GPUs, and Heninger said those tools will "almost certainly" push the security levels lower.

Why it is not a practical threat

The attack works only against blind-signature (textbook) RSA. The overwhelming majority of deployed RSA uses PKCS or PSS padding, which adds data to the plaintext before encryption and eliminates the weakness the attack exploits. Even against deprecated 1024-bit keys, the method requires more computation than anyone short of nation-states or companies with massive resources can muster.

The best-known real-world example is Privacy Pass, an authentication protocol that lets users prove who they are without revealing their identity; it is used by Apple and Cloudflare, among many others. Attacking it would require compromising one of their servers and generating 2^43 signatures — a number that "sounds 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," Heninger said. Most Privacy Pass implementations rotate keys regularly, which greatly reduces, but does not eliminate, the attacker's chances.

Why it matters

Karsten Nohl, a cryptography expert and head of innovation at Allurity, said that if the result holds up under peer review it would be "a conceptual break-through." The technique is a variant of the number field sieve algorithm invented in 2007, aimed at an "oracle" — a weakness that gives yes-or-no answers to specific queries. Cryptographers are racing to build post-quantum alternatives before practical quantum computing arrives, which estimates place 3 to 20 or more years away, and the new attack increases the urgency of moving away from RSA.