Researchers forge 1024-bit RSA signatures without factoring the key

Researchers at UC San Diego and Inria Nancy implemented an attack that forges arbitrary 1024-bit RSA signatures without factoring the key. Their preprint, "Forging 1024-bit RSA signatures in nearly SNFS time", was posted to the IACR ePrint archive on September 20, credited to Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger and Emmanuel Thomé.

The work implements a 2007 algorithm by Joux, Naccache and Thomé that the authors call under-appreciated. It runs in time close to the special number field sieve (SNFS), well below the general number field sieve (GNFS) used to set RSA key sizes.

What the attack requires

The threat model is a "lunchtime" attack, formally a non-adaptive chosen-ciphertext attack, or IND-CCA1: the attacker gets temporary access to a raw, unpadded RSA signing oracle for one key, then loses it. Afterwards the attacker can forge any signature of choice offline, repeatedly, for any target.

In total the computation took 1,380 CPU core-years over five calendar months and about 2^32 oracle queries. Precomputation, which depends only on the modulus, took roughly 1,200 core-years; a single forgery then takes about 180. For comparison, the paper cites 500,000 to 1,000,000 core-years to factor a 1024-bit RSA modulus.

HSMs and blind signatures

The authors used a hardware security module for their oracle queries, showing that black-box API access is enough to impersonate the HSM without extracting the key. PKCS #11, implemented by nearly all HSMs, offers raw RSA operations that match the oracle exactly. RSA-based blind signature schemes provide the same oracle, and the paper argues that the 2048-bit keys common in deployment give too low a security margin.

15 to 30 bits of concrete security lost

Extrapolating measured running times, the authors conclude RSA's concrete security with a signing oracle is 15 to 30 bits lower than factoring-based estimates for the 1024-bit to 4096-bit parameters common in practice. For 1024-bit RSA, usually rated at 80 bits, they estimate about 2^65 time. Scaling gives roughly 2^90 and 2^43 queries for 2048-bit RSA, rated at 112 bits, and about 2^119 with 2^57 queries for 4096-bit RSA. So even 4096-bit RSA does not appear to reach 128-bit security in this model.

A gap in RSA assumptions

The authors do not claim RSA is broken in everyday use. They call it practical in an academic rather than a script-kiddie sense, and note the raw unpadded oracle is a strong model. But they argue it exposes a gap: the one-more RSA assumption does not capture this kind of precomputation attack, and they propose calling the setting "delayed-target RSA". NIST plans to deprecate RSA in 2030 and disallow it by 2035, and the authors see their classical cryptanalysis as another argument for moving away from RSA during the post-quantum transition. The code is published on GitHub.