There's a new way to break RSA that's faster than anything we've seen before
A new sieve-based forgery attack lowers textbook RSA security to 2^65 for 1024-bit keys.
Researchers including Nadia Heninger describe a special number-field-sieve forgery attack against blind-signature, or textbook, RSA. Estimated work drops to 2^65, 2^90, and 2^119 operations for 1024-, 2048-, and 4096-bit keys; a 1024-bit forgery took about 1,380 core-years versus an estimated 2^80 operations to factor such a key. PKCS and PSS padding remove the oracle, so most deployed RSA is unaffected. Privacy Pass, used by Apple and Cloudflare, still uses blind signatures, but an attack would need a compromised issuer and about 2^43 signatures, and keys are often rotated. The authors say the result poses little immediate real-world threat.
- Forgery work falls to 2^65, 2^90, and 2^119 for 1024-, 2048-, and 4096-bit keys.
- Attack applies only to blind-signature RSA, not PKCS or PSS padding.
- A 1024-bit signature forgery took about 1,380 core-years.
- Privacy Pass, used by Apple and Cloudflare, still needs a compromised issuer.
- Hand-coded work used no GPUs or AI, which could cut costs further.
Full article426 words · extracted from arstechnica.com · click to collapse
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 compromise a server belonging to Cloudflare, Apple, or another organization and generate 243 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 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. 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.