Abstract:
A new study shows that an attacker may still be able to forge a valid RSA digital signature without decomposing the RSA public key modulus or extracting the private key. The research team has completed a practical demonstration on a 1024-bit RSA key. This result shakes the long-term perception that "breaking RSA must first decompose large integers".
The study was conducted by researchers at the University of California, San Diego and the French National Institute for Information and Automation, including Laura Shia, Miro Haller, Adam Suhr, Nadia Henninger and Emmanuel Thom. The research results are currently public in the form of a preprint, and the paper is titled "Forging 1024-bit RSA signatures at a speed close to the special number field sieve method."
RSA security is usually built on the hard problem of large integer factorization. According to traditional estimates, decomposing a 1024-bit RSA modulus requires about 500,000 to 1 million CPU core years, and usually only national-level institutions or enterprises with large-scale computing resources are capable of trying it. The research team took another path this time: they did not directly obtain the RSA private key, but used a "signature oracle" that can perform the original RSA signature operation, combined with an improved algorithm of the number field sieve method, and finally obtained the ability to forge signatures offline.
The mathematical basis of this method was proposed as early as 2007, but it has remained at the theoretical level before. This study extends it to large-scale practical operations for the first time. During the experiment, the researchers used the hardware security module as a signature oracle, which consumed about 1,380 CPU core years in about five months and initiated about 2^32 queries, equivalent to more than 4 billion original RSA signature requests. After the main precomputation is completed, the attacker no longer needs to continue to access the target device. Forging any given signature requires approximately 180 core years, and this process can be performed offline repeatedly.
This means that even if the private key always remains inside the hardware security module, an attacker may eventually obtain the signature capability equivalent to mastering the private key by continuously calling the device's interface. Attackers can use this to forge authentication information, generate fake authorization files, or communicate pretending to be a legitimate service.
However, this research does not mean that all RSA systems have been lost. The premise for the attack to be established is that the target system exposes the original, unpadded RSA signature or decryption interface. Today's Internet certificates, TLS connections, and most software signing mechanisms typically use PKCS#1 v1.5 or RSA-PSS padding, and researchers say these common deployments are not directly affected by this method.
What really needs attention are some hardware security modules, the original PKCS#11 interface and the blind signature protocol. Blind signature allows the service party to complete the signature without knowing the specific message content. Privacy authentication systems such as Privacy Pass use similar mechanisms. The researchers noted that certain blind signature systems could become potential targets if an attacker could consistently obtain enough signature responses. However, the query size required for an actual attack is extremely large, and regular key rotation can significantly reduce the risk.
Based on the experimental results, the research team calculated that under the attack model with a signature oracle, the actual security strength of RSA may be 15 to 30 bits lower than the traditional estimate based on decomposition difficulty. For 1024-bit, 2048-bit, and 4096-bit RSA keys, the attack costs are approximately equivalent to 2 to the 65th power, 2 to the 90th power, and 2 to the 119th power, respectively, which are all lower than the 128-bit security level typically required by modern cryptosystems. The researchers also stated that their experiments did not use GPUs or artificial intelligence tools. If more efficient hardware and software are introduced in the future, the cost of attacks may be further reduced.
Cryptography experts believe that the importance of this achievement mainly lies in the fact that it reveals a blind spot in the RSA security model: signature forgery does not necessarily require obtaining the private key first, nor does it necessarily have to complete large integer decomposition in the traditional sense. However, current attacks still require a large amount of computing resources and special interfaces, and will not pose a direct threat to the widely used standardized RSA certificates and regular HTTPS connections in the short term.
Security agencies and system operators should still check whether the hardware security module opens unnecessary original RSA operations, limit the calling permissions of the signature interface, shorten the rotation period of the blind signature key, and gradually migrate to more modern signature algorithms and post-quantum cryptography systems. The researchers pointed out that as traditional cryptographic algorithms get closer to the theoretical and practical security boundaries, enterprises should not continue to consider increasing the length of RSA keys as a permanent solution.
Learn more:
https://github.com/ucsd-hacc/NSNFSSSFSFN
Comments