This is not a break of RSA in general. Researchers implemented a 2007 algorithm to forge signatures after temporary, revoked access to a raw signing oracle — a much narrower problem than "crack RSA from the public key alone."
It requires an unpadded RSA signing oracle (a misconfigured HSM, or a blind-signature protocol by design). Standard PKCS#1v1.5 / RSA-PSS — the padding behind TLS, most OAuth, DNSSEC, and DKIM — is untouched.
Cost: 1,380 CPU core-years and ~4.1 billion oracle queries, versus 500,000–1,000,000 core-years to factor the same key directly. Extrapolated, even 4096-bit RSA falls short of 128-bit security in this specific model.
Why this made headlines
Media coverage ran with the framing: "new technique bypasses 1024-bit RSA without factoring it." That's technically true, but it invites a much bigger conclusion than the research supports — something closer to "RSA is broken." It isn't. The actual paper is careful and explicit about the boundaries of what was accomplished, and those boundaries matter more than the headline number.
The actual threat model
The standard RSA problem is: given only the public key (N, e) and a target value t,
compute t1/e mod N — forge a signature with zero help. Nobody broke that here.
Instead, the paper defines and attacks what it calls delayed-target RSA (DT-RSA), modeled as a "lunchtime attack":
- The attacker gets temporary, active access to a raw RSA signing/decryption oracle for a given key — they submit chosen inputs
wand receivew1/e mod Nback. - Access is then revoked.
- The attacker is handed a brand-new random target
tthey never queried, and must producet1/e mod N— entirely offline, with no further oracle access.
"RSA is as difficult to break as it is to factor large integers, at least so we thought." — reaction from the wider cryptography community on the paper's conceptual gap.
On the distinction between delayed-target RSA and standard RSA security
The algorithm: ∛NFS
The technique isn't new. It's from a 2007 paper by Joux, Naccache, and Thomé (JNT) that the community had largely filed away as a theoretical curiosity. The UCSD/Inria team built the first-ever implementation of it at meaningful scale, naming it ∛NFS ("eth-root NFS").
| Algorithm | Applies to | Complexity LN(1/3, c) |
|---|---|---|
| GNFS (general factoring) | Any RSA modulus | c ≈ 1.923 |
| SNFS (special-form factoring) | Moduli with special algebraic structure | c ≈ 1.526 |
| ∛NFS (this paper) | Delayed-target RSA, with oracle | c ≈ 1.577 |
In plain terms: with oracle access, forging a signature is computationally closer to the easier special-modulus factoring case than to general factoring — exactly why the paper's title says "nearly SNFS time."
What they physically built
This wasn't purely theoretical — they ran the attack against real commercial hardware security modules (HSMs), the tamper-resistant devices used by certificate authorities, banks, and companies like WhatsApp specifically to make private keys physically unextractable.
Attack chain, end to end
Five months, two real HSMs, one forged signature
- Get oracle access Configure two Thales Luna HSMs (K6 local, S750 remote) with FIPS mode disabled to permit raw, unpadded RSA signing. CKM_RSA_X_509
- Query the oracle Submit billions of chosen inputs and record the raw signatures returned, via a three-piece distributed query pipeline. 4,067,419,331 queries
- Precompute Feed results into a modified CADO-NFS pipeline across a ~45-machine academic cluster — polynomial selection, sieving, linear algebra. ~1,200 core-years
- Lose access Oracle access is revoked. No further queries are possible from this point forward. access severed
- Forge offline Using only precomputation output, run descent, linear algebra, and eth-root extraction to produce a valid signature on a never-before-seen random target. ~180 core-years
The numbers
Breakdown by phase
| Phase | Approx. cost | Notes |
|---|---|---|
| Polynomial selection | 40 core-years | One-time, depends only on the modulus |
| Algebraic sieving | 150 core-years | Precomputation |
| Extension sieving | ~1,055 core-years | Dominant cost — 2.5 of the 5 months |
| Descent (3 stages) | ~160 core-years | Per-target, fully offline |
| Linear algebra | ~17 core-years | Per-target |
| eth root extraction | ~3 core-years | Final assembly step |
They call their result a likely upper bound. Concurrent GPU-optimized sieving (used to set a recent RSA-260 factoring record) suggests the same attack could plausibly run in 2–9 GPU-years instead of 1,380 CPU core-years. The uncertainty points toward the attack getting cheaper, not toward it being a fluke.
Scaling to 2048 and 4096 bits
Extrapolating the observed running times to larger keys:
| Key size | Bit security (factoring) | Bit security (with oracle) | log₂(queries) |
|---|---|---|---|
| 1024-bit | 80 | 65 | 32 |
| 2048-bit | 112 | 90 | 43 |
| 3072-bit | 128 | 105 | 51 |
| 4096-bit | 144–152 | 119 | 57 |
The headline conclusion: even 4096-bit RSA doesn't reach the 128-bit security level once you're in this oracle-access threat model — a 15–30 bit shortfall across the board relative to the factoring-based numbers NIST, NSA, and EU agencies currently use to set key-size recommendations.
Where this actually applies
- Misconfigured or legacy-mode HSMs — supporting non-standard padding like ISO 9796-2 (e-passports, digital tachographs), ANSI X9.31, or RSA-FDH (used in GNU Taler).
- Blind RSA signature schemes (RFC 9474 / RSABSSA) — these inherently expose oracle-like access by design.
- Privacy Pass (Apple Private Access Tokens, Cloudflare, Fastly, Persona) — an attacker would need roughly 238 CAPTCHA solves against 2048-bit keys to make this practical, currently far out of reach but a thinner margin than assumed.
- GNU Taler e-cash — would require minting an estimated $88B in $0.01 coins against a 2048-bit key. Taler's newer clause-blind Schnorr signatures are not vulnerable at all.
- Bleichenbacher-style padding oracles could theoretically be stacked to synthesize a raw oracle at much higher cost per query.
What it does NOT do
Does not factor RSA moduli faster — factoring-hardness assumptions are untouched.
Does not break standard PKCS#1v1.5 or RSA-PSS signatures — the padding behind nearly all real TLS certificates, most OAuth/JWT tokens, DNSSEC keys, and DKIM.
Does not work from passively collected signed documents "in the wild" — real signatures are padded hashes, not the exact smooth numbers the algorithm needs.
Does not resolve the 50-year-old open question of whether breaking RSA is equivalent to factoring.
Is not a zero-day — no vendor vulnerability, no disclosure process, no patch to ship.
Verdict
| Is RSA "broken"? | No — standard padded RSA deployments are untouched. |
| Is this a fluke? | No — validated across four key sizes with a matching complexity curve, and the code is public. |
| Reproducible? | Yes — released at github.com/ucsd-hacc/NSNFSSSFSFN. |
| Panic about TLS/HTTPS? | No. |
| HSM / blind-signature operators? | Yes — reassess raw-RSA-oracle exposure and rotation policy. |
| Changes PQ migration timeline? | No new urgency mechanically, but another argument to retire RSA sooner. |
In the authors' own words: this illustrates that classical cryptanalysis of RSA still has surprises left in it, decades after most of the field assumed it was settled — not that RSA is dead. The current transition to post-quantum algorithms remains, in their view, the right moment to move past RSA altogether rather than just inflate key sizes further.
Sources
- Shea, Haller, Suhl, Heninger, Thomé — "Forging 1024-bit RSA signatures in nearly SNFS time", IACR ePrint 2026/2131.
