RSA, the workhorse public-key cryptosystem, has spent years being politely ushered towards retirement. A new attack gives it a firmer shove. In a paper posted on September 20th to the IACR ePrint archive, a team including Nadia Heninger of the University of California, San Diego, shows how to forge certain RSA signatures without the cripplingly expensive task of factoring the key—faster than any comparable attack seen before.
The numbers are stark. The forgery drops the effective security of blind-signature RSA to 2^65, 2^90 and 2^119 operations for 1024-, 2048- and 4096-bit keys respectively, according to Ars Technica’s account of the work. Those levels may fall further: Ms Heninger’s team wrote all the code by hand and used neither artificial intelligence nor graphics processors, tools she says will “almost certainly” improve the results.
There is an important caveat. The attack works only against blind-signature RSA, also known as textbook RSA. The overwhelming majority of RSA in use today applies PKCS or PSS padding, which adds data to plaintext before encryption and thereby eliminates the weakness the attack exploits. Yet textbook RSA survives in real systems. The best-known example, Ms Heninger told Ars Technica, is Privacy Pass, a protocol that lets users authenticate without revealing their identity, and which is used by Apple and Cloudflare among others.
Attacking Privacy Pass would still be a slog. An assailant would need to compromise a server run by Cloudflare, Apple or another operator and obtain 2^43 signatures. That, Ms Heninger said, “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.” Most Privacy Pass implementations also rotate their keys regularly, which greatly reduces, without automatically eliminating, an attacker’s chances.
The technique itself revives a variant of the number field sieve invented in 2007. This “special” number field sieve is turned against an “oracle”, the yes-or-no answers that blind RSA gives to particular queries; with enough such answers an attacker assembles the information to forge a signature. Factoring a 1024-bit key would require an estimated 2^80 operations and 500,000 to 1m CPU core-years. The forgery took 2^65 operations and just 1,380 core-years over five calendar months, with 2^32 oracle queries.
The paper’s authors and other researchers stress that the practical danger is slight. Nobody’s bank account will be emptied this week. But the work slashes the estimated security of textbook RSA in a way nobody previously knew about, and adds urgency to the long migration away from RSA altogether, alongside the push for cryptosystems that can withstand quantum computers. RSA has been buried prematurely many times. This time the gravediggers have at least shown their workings.