Cryptographers at UC San Diego and Inria Nancy have shown that "textbook" RSA, used without padding, is substantially weaker than standard estimates when an attacker can query the key's signing or decryption function, Tom's Hardware reported Saturday. The attack lets an adversary forge signatures without factoring the key, and it applies to privacy services and hardware security modules that rely on raw RSA operations.

What Happened

The paper, titled "Forging 1024-bit RSA signatures in nearly SNFS time," is by Laura Shea, Miro Haller, Adam Suhl and Nadia Heninger of UC San Diego and Emmanuel Thomé of Inria Nancy, and was posted to the IACR's ePrint archive. It builds a practical implementation of an algorithm first described in 2007 by Antoine Joux, David Naccache and Thomé.

The attacker needs temporary access to a raw RSA oracle: a service or device that will sign or decrypt arbitrary values with the target key. After collecting enough answers, the attacker can produce valid signatures on messages of their choosing, even though the key was never extracted or factored. The researchers demonstrated this against Thales Luna hardware security modules, in both physical and online service configurations, interacting only through the devices' normal interfaces.

RelatedSuspected Chinese Spies Exploited BeyondTrust Remote Support Flaw Since August, Google Says

The full 1024-bit demonstration used about 2^32 oracle queries and roughly 1,380 CPU core-years of computation over five months, most of it one-time precomputation. After that, each additional forged signature takes around 180 core-years offline, according to the paper.

Why It Matters

The authors estimate that the concrete security of RSA with a signing oracle should be 15 to 30 bits lower than commonly assumed across standard key sizes. Tom's Hardware summarized the new figures: 1024-bit keys drop from about 2^80 operations to 2^65, 2048-bit keys from 2^112 to 2^90, 3072-bit keys from 2^128 to 2^105, and 4096-bit keys from 2^144 to 2^119. In this threat model, even 4096-bit RSA does not reach 128-bit security.

Most RSA deployments are not affected, because padding schemes such as PKCS#1 v1.5 and PSS prevent an attacker from obtaining raw signatures on chosen values. The exposure is concentrated in systems that deliberately use unpadded operations. Tom's Hardware listed Cloudflare's Privacy Pass, Apple's iCloud Private Relay and Private Cloud Compute, which use raw RSA blind signatures to issue anonymous tokens, along with PKCS #11 implementations in smart cards and USB security tokens, HSMs and trusted platform modules.

Practical Limits

The attack is not cheap or quiet. It requires billions of queries against a live service or device using the target key, which rate limiting, IP blocking and monitoring could detect or throttle. The computational cost remains out of reach for casual attackers. The researchers note, however, that their algorithms are far from optimized and could become faster, and the paper has not yet been peer reviewed.

Blind-signature token systems are a special case because their purpose is to sign values the server cannot see, which is exactly the capability the attack exploits. That makes the safety margin of those designs depend more heavily on operational controls such as issuance limits and key rotation.

What to Watch

Watch for responses from Cloudflare, Apple and Thales on whether they will change key sizes, rotation schedules or query limits for services built on raw RSA. Peer review of the paper, and any follow-up work that optimizes the algorithm, will determine how quickly the estimates move from theoretical to practical concern for high-value keys held in HSMs.