A New Attack Forges RSA Signatures Without Factoring, and Even 2048-Bit Keys Look Unsafe

For decades, the rule for breaking RSA has been simple: factor the key, or give up. A team from UC San Diego and Inria Nancy, including cryptographer Nadia Heninger, has now forged RSA signatures without factoring anything, on classical hardware, faster than anyone thought possible.

The attack combines a variant of the special number field sieve with an oracle, a system that will sign messages on request. That setup matters, because it only works against textbook RSA with no padding, the kind used in blind signatures.

The numbers are what caught cryptographers off guard. Forging a 1024-bit signature took about 2 to the 65th operations, or roughly 1,380 CPU core-years spread over about five months on an academic cluster. Earlier estimates for factoring a 1024-bit key sat around 2 to the 80th operations and somewhere between 500,000 and 1 million core-years.

Scale that up and the claimed security of larger keys shrinks too: roughly 2 to the 90th for 2048-bit keys and 2 to the 119th for 4096-bit keys. Both fall below the 128-bit floor that the NSA, NIST and ENISA treat as the minimum. The team wrote its code by hand, with no AI help and no GPUs, and expects the costs to drop further.

The most exposed real system is Privacy Pass, the anonymous token scheme Apple and Cloudflare use to let people skip CAPTCHAs without being tracked. It relies on blind RSA signatures. An attack on it would need on the order of 2 to the 43rd token requests, which is roughly the volume of HTTP traffic Cloudflare handles in a day, Gizmodo reported. Rotating keys regularly shrinks that window.

Most of the RSA you touch every day is not affected. HTTPS certificates and software signing generally use PKCS#1 v1.5 or PSS padding, and the attack does not work against either. This is also not a quantum attack, and the paper still has to clear peer review.

Karsten Nohl called it a conceptual breakthrough if it holds up. It lands on an algorithm that already has an expiry date: NIST plans to deprecate RSA by 2030 and drop it entirely by the mid 2030s, as the industry moves to post-quantum schemes. While most security attention has shifted to AI, with labs handing their models to government testers, a few mathematicians with a CPU cluster just showed that old cryptography still has surprises left.