The forgery attack drops security levels to 2⁶⁵, 2⁹⁰, and 2¹¹⁹ for 1024-, 2048-, and 4096-bit keys respectively. These levels may drop further, as Heninger’s team performed all coding by hand without AI or GPUs. The researcher said those tools will “almost certainly” reduce the security levels even more.
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. This 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 noted, 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 request tokens from Cloudflare, Apple, or another organization 2⁴³ times. 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.
How the Attack Works
The technique implements a variant of the number field sieve algorithm invented in 2007. This “special” number field sieve is used in combination with an “oracle” — a property of some cryptographic protocols that returns answers to queried inputs. By performing a massive number of operations, attackers can gather enough information to decipher the ciphertext. This technique does not appear to pose a practical threat against RSA with PKCS or PSS padding, as those schemes provide a different type of 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 required just 2⁶⁵ operations and 1,380 core-years — a significant reduction that underscores the practical relevance of the new approach for systems still relying on blind-signature RSA.
