Forging 1024-bit RSA signatures in nearly SNFS time
6 points by dzwdz
6 points by dzwdz
Alternate title: Nearly SNFS-Speed Signature Forgery Sans Factoring N (NSNFSSSFSFN)
Abstract. The security of RSA is generally understood to be based on the complexity of factoring, and key size parameters are extrapolated from the general number field sieve (GNFS). However, this may not accurately represent RSA security in practical scenarios.
An under-appreciated 2007 algorithm of Joux, Naccache, and Thomé allows an attacker to forge RSA signatures after temporary access to a raw RSA signing/decryption oracle in time close to the special number field sieve (SNFS) without factoring the key. We implement and run this algorithm for 1024-bit RSA. In total, the attack took 1380 CPU core-years over five calendar months, and made 232 oracle queries. Most of this time is precomputation; after the precomputation the attacker can forge any signature of choice, offline, in 180 core-years.
We carried out our attack using a hardware security module (HSM) as the signing oracle, thus demonstrating the ability to impersonate the HSM through black-box API interactions, without exfiltrating the key. Blind RSA schemes also provide such a signing oracle.
Extrapolating our empirical running times to larger key sizes, we conclude that the concrete security of RSA with a signing oracle should be 15 to 30 bits lower than the factoring-based security estimates for the 1024-bit to 4096-bit RSA parameters that are common in practice. Even 4096-bit RSA does not appear to meet a 128-bit security level in this attack model. This highlights a gap in current RSA-type security assumptions, and gives classical cryptanalytic evidence in favor of moving away from RSA entirely during the current post-quantum transition.
Even applying the attack against the deprecated use of 1024-bit keys, the method requires more computation than just about anybody—short of nation-states or companies with massive resources—can achieve.
That doesn't really seem to match what the paper says:
Both our findings and the pre-2026 factoring records were completed using academic computational resources and engineering skills, a far cry from industry- or state-level adversaries. That leaves substantial leeway before one can get a sense of the feasibility limit that would apply to adversaries with larger computing power. Extrapolations that RSA-1024 could be factored in weeks using industry-grade GPU facilities are no fantasy.
[...] A back-of-the-envelope scaling suggests that our 1024-bit RSA signature forgery computation would take between 2 and 9 GPU-years if we had used their [Weis's] implementations; for 2048 bits a very rough estimate would be 2^27 GPU-years.
Continuing the very rough calculations - Weis's post says that Anthropic can pull in 3 GPU-years per day for a "low-priority job". That's enough to execute this attack against 1024-bit RSA in a few days (compared to 5 months on academic hardware).
Yes, even the abstract seems to push moving away from RSA, no matter the key size:
[…] and gives classical cryptanalytic evidence in favor of moving away from RSA entirely during the current post-quantum transition.