The forgery attack drops these levels to 265, 290, and 2119 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 request 243 tokens from Cloudflare, Apple, or another organization.
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 with an “oracle”, a property of some cryptographic protocols that gives answers to queried inputs. By performing a massive number of operations, attackers can gather enough information to decipher the ciphertext. (This technique doesn’t appear to pose a practical threat against RSA with PKCS or PSS padding, because they provide a different type of oracle..) While factoring a 1024-bit key requires an estimated 280 operations and 500,000 to 1 million CPU core-years, using the sieve to forge a signature took just (as noted earlier) 265 operations and 1,380 core-years.
The paper’s authors and other researchers stress that the new attack poses little real-world threat, at least for now. It does, however, drastically lower the estimated security of 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.
Post updated to correct the identity of the lead author. It’s Laura Shea, also with the University of California at San Diego.