Key facts
- A new attack method can forge RSA signatures with significantly fewer operations than previously estimated.
- The attack requires 265 operations for a 1024-bit key, down from an estimated 280 operations for factoring.
- The technique is effective against blind-signature implementations of RSA, including the Privacy Pass protocol.
- Privacy Pass is used by major companies like Apple and Cloudflare.
- The attack poses little practical threat to RSA implementations using PKCS or PSS padding.
A new attack method has been developed that significantly lowers the estimated security of textbook RSA implementations, though researchers stress it poses little immediate real-world threat. The technique, a variant of the number field sieve algorithm invented in 2007, requires substantially fewer operations to forge RSA signatures than previously understood.
The forgery attack reduces the operational requirements to 265 for 1024-bit keys, 290 for 2048-bit keys, and 2119 for 4096-bit keys. The team that developed the method believes these levels could drop further as they performed the coding manually and did not utilize AI or GPUs.
This attack is effective only against blind-signature implementations of RSA, also known as textbook RSA. Most current RSA usage incorporates PKCS or PSS padding, which adds data to the plaintext before encryption to prevent deterministic ciphertext and enhance security against side-channel attacks. However, some real-world systems, such as the Privacy Pass protocol, continue to use textbook RSA. Privacy Pass, which allows users to authenticate without revealing their identity, is employed by companies including Apple and Cloudflare.
An attack on Privacy Pass would necessitate compromising a server from an organization like Cloudflare or Apple and generating 243 signatures. While this sounds substantial, it is comparable to the network traffic Cloudflare handles daily. Although most Privacy Pass implementations rotate keys regularly, which mitigates the risk, it does not eliminate the possibility of an attacker's success.
The new method utilizes a variant of the number field sieve algorithm. By interacting with an "oracle"—a weakness in RSA and other cryptosystems that provides yes-or-no answers to specific queries—attackers can gather enough information to decipher ciphertext through a massive number of operations. This technique does not pose a practical threat to RSA with PKCS or PSS padding, as these methods eliminate the oracle.
While factoring a 1024-bit key is estimated to require 280 operations and 500,000 to 1 million CPU core-years, the new sieve method for forging a signature requires only 265 operations and 1,380 core-years. The paper's authors and other cryptographers emphasize that this attack highlights the increasing urgency to transition away from RSA towards alternative cryptosystems that are resistant to quantum computing.