RSA, the encryption scheme that has guarded the internet for decades, has a new and unexpected weakness — one that does not involve factoring.
Researchers led by Nadia Heninger of the University of California, San Diego, have devised a method that forges valid RSA signatures without first computing the private key. Cryptographers had long assumed that the only route to breaking RSA was factoring the large integers behind the keys. The team instead applied a variant of the “special” number field sieve — invented in 2007 — against a weakness called an oracle, performing a vast number of operations to gather enough information to produce signatures.
The practical picture is nuanced. The attack works only against blind-signature, or “textbook,” RSA; the PKCS and PSS padding used by the overwhelming majority of real-world RSA eliminates the oracle and remains safe. Encryption and key exchange are not directly affected.
But the estimates are striking. Forging a signature against 1024-bit RSA needs about 2^65 operations — roughly 1,380 core-years — versus an estimated 2^80 operations and 500,000 to 1,000,000 core-years to factor such a key. Security levels for 1024-, 2048- and 4096-bit keys fall to roughly 2^65, 2^90 and 2^119 respectively, far below the 128-bit minimum demanded by the NSA, NIST and ENISA.
One real-world system still uses blind signatures: Privacy Pass, an anonymous-authentication protocol used by Apple and Cloudflare, among others. Attacking it would require compromising a server and generating 2^43 signatures — a large number, Heninger noted, but of the same order as the network traffic Cloudflare says it handles in about a day. Most implementations rotate keys regularly.
The researchers coded the attack by hand, without GPUs or AI, and say those tools will “almost certainly” lower the estimates further. The work has not yet been peer-reviewed, and experts stress it poses little immediate threat — but it gives new urgency to retiring RSA.
