There's a new way to break RSA that's faster than anything we've seen before

The forgery attack drops these levels to 2⁶⁵, 2⁹⁰, and 2¹¹⁹ for 1024-, 2048-, and 4096-bit keys respectively. These levels may further drop because Heninger’s team did all the coding by hand and used no AI or GPUs in performing the forgeries. The researcher said these tools will “almost certainly” drop the security levels further.

The attack works only against blind-signature implementations of RSA. The overwhelming majority of RSA in use today provides PKCS or PSS padding, a format that adds data to the plaintext before it’s encrypted. It prevents ciphertext from being deterministic and makes it less vulnerable to side channel and similar attacks. Still, some real-world systems continue to use blind-signature, also known as textbook, RSA. The best-known example, Heninger said, is Privacy Pass, a protocol that allows users to authenticate themselves without revealing their identity. Privacy Pass is used by both Apple and Cloudflare, among many others.

An attack on Privacy Pass would require an attacker to compromise a server belonging to Cloudflare, Apple, or another organization and generate 2⁴³ signatures. Heninger said the requirement “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 rotate keys regularly, a measure that greatly reduces, but doesn’t automatically eliminate, the chances of attacker success.

The technique implements a variant of the number field sieve algorithm that was invented in 2007. This “‘special’ number field sieve” is used against an “oracle,” a weakness in RSA and some other cryptosystems that gives yes-or-no answers to specific queries. By performing a massive number of operations, attackers can gather enough information to decipher the ciphertext. (Again, this technique poses no practical threat against RSA that uses PKCS or PSS padding, because they eliminate the oracle.) While factoring a 1024-bit key requires an estimated 2⁸⁰ operations and 500,000 to 1 million CPU core-years, using the sieve to forge a signature took just (as noted earlier) 2⁶⁵ operations and 1,380 core-years.

The paper’s authors and other researchers stress that the new attack poses little real-world threat. It does, however, drastically lower the estimated security of textbook RSA, and it does so in a way no one knew of previously.

Cryptographers have worked furiously in recent years to devise alternative cryptosystems that aren’t vulnerable to quantum computing attacks. The new attack will further increase the urgency of completely moving away from the cryptosystem. The paper authors provide an easier-to-digest explainer here.