New RSA signature forgery method sharply lowers security estimates
Researchers developed a classical-computing attack that forges signatures in certain RSA blind-signature systems without factoring the private key.
RSA has long been expected to become vulnerable once practical quantum computers arrive. New research, however, describes a substantially faster way to undermine some uses of RSA with classical computers available today.
The technique does not recover an RSA private key by factoring a large integer, as traditional attacks attempt to do. Instead, it forges valid digital signatures in certain blind-signature implementations. Researchers demonstrated that the method is practical against deprecated 1024-bit RSA keys and lowers the estimated security of larger keys.
The immediate risk remains limited because the attack does not apply to the PKCS- or PSS-padded RSA implementations used in most systems. Still, the findings challenge a basic assumption about RSA and could add urgency to efforts to replace it.
Breaking RSA without factoring the key
Cryptographers have generally treated RSA signature security as closely connected to the difficulty of factoring large integers. Under that model, an attacker would first need to factor the public key’s modulus, recover the private key, and then use that key to generate valid signatures.
The new attack takes a different route. The researchers found a way to create a valid signature without first computing the private key. Karsten Nohl, head of innovation at Allurity, described the work as a potential conceptual breakthrough if it survives peer review because it suggests RSA can be practically broken in a specific setting without cracking the underlying key.
Nadia Heninger, a University of California at San Diego professor and co-author of the research, said factoring a single 1024-bit RSA key was previously expected to require computation costing tens of millions of dollars. Such an effort might be possible for a large technology company or intelligence agency, while factoring 2048-bit RSA was considered out of reach.
The research paper’s lead author is Laura Shea, also of the University of California at San Diego.
Security estimates fall below accepted thresholds
The team’s signature-forgery method is practical for 1024-bit RSA. The researchers completed the work on an academic CPU cluster over a handful of months. They estimate that the attack required 2^65 operations and 1,380 CPU core-years.
By comparison, conventional factoring of a 1024-bit RSA key is estimated to require:
- About 2^80 operations
- Between 500,000 and 1 million CPU core-years
The method also reduces the estimated security of larger RSA keys. According to the researchers, the resulting security levels are:
- 1024-bit RSA: 2^65 operations
- 2048-bit RSA: 2^90 operations
- 4096-bit RSA: 2^119 operations
These figures are below the minimum 128-bit security level required by guidance from the National Security Agency, the National Institute of Standards and Technology, and the European Union Agency for Network and Information Security. A 128-bit security target means an attack should require more than 2^128 operations.
The researchers wrote their code manually and did not use graphics processors or artificial intelligence tools. Heninger said those resources would almost certainly reduce the security estimates further.
The attack only affects specific RSA implementations
The technique is not a general attack against every system using RSA. It applies to blind-signature implementations, also described as textbook RSA in the source material.
Most deployed RSA systems use PKCS or PSS padding. These formats add data to plaintext before encryption, preventing deterministic ciphertext and helping protect against side-channel and related attacks. The newly described technique does not appear to present a practical threat to RSA using either of those padding systems because they expose a different type of oracle.
The attack combines an oracle—a protocol property that provides answers to selected inputs—with a variant of the special number field sieve. That algorithm was introduced in 2007. By making a very large number of queries and computations, an attacker can collect enough information to forge a signature.
Although its scope is narrow, some real-world systems still use the affected form of RSA. Heninger identified Privacy Pass as the best-known example.
Privacy Pass illustrates the practical limits
Privacy Pass is a protocol designed to let users authenticate without revealing their identities. Apple and Cloudflare are among the organizations that use it.
Attacking a Privacy Pass deployment would require an adversary to request tokens from an organization approximately 2^43 times. Heninger noted that this is comparable to the amount of network traffic Cloudflare has publicly said it handles in roughly one day.
That comparison does not mean such an attack would automatically succeed. Most Privacy Pass implementations rotate their keys regularly, which greatly reduces the available window for collecting the required information. Key rotation lowers the likelihood of a successful attack, although the researchers said it does not necessarily eliminate the possibility.
The paper’s authors and other cryptographers therefore describe the current real-world threat as small. Organizations using standard PKCS or PSS padding are not affected by the demonstrated technique, while systems using blind signatures may have operational defenses that make exploitation difficult.
A new reason to move beyond RSA
The main significance of the research is conceptual rather than an immediate widespread security crisis. It shows that RSA signatures can be attacked more efficiently than previously understood under particular protocol conditions, without factoring the key.
Cryptographers are already developing and deploying alternative systems designed to resist attacks from future quantum computers. This classical-computing result adds another reason to examine remaining RSA deployments, especially those using blind signatures or deprecated 1024-bit keys.
For most RSA users, the findings do not require panic. They do, however, weaken long-standing assumptions about RSA’s security and reinforce the importance of modern padding, regular key management, and migration planning.
Original reporting: Ars
Originally reported by Ars.