New Attack Against RSA

ArsTechnica has highlighted a “new” implementation of a 2007 RSA forgery attack that bypasses factoring, allowing signatures to be forged without extracting the private key. Understanding this development matters because forged signatures can undermine authentication mechanisms that many enterprises still rely on.

The Mechanics of the RSA Forgery Attack

The original research dates back to 2007, but the recent paper demonstrates a practical implementation that directly creates valid signatures. Unlike traditional attacks that aim to factor the modulus, this method sidesteps key recovery entirely.

By focusing on the mathematical structure of RSA signatures, the authors exploit a weakness that emerges when signatures are generated without any additional formatting. This approach is classified as a forgery attack, meaning the adversary can produce a signature that will verify against the public key.

Because the private exponent never leaves the attack surface, the breach does not expose the secret key itself, limiting the damage to the ability to impersonate the key holder in contexts that accept raw RSA signatures.

Scope of Vulnerability: Pure Signatures vs. Padded Schemes

The attack succeeds only against pure signatures, which are raw RSA outputs lacking any padding or encoding. Modern cryptographic libraries typically employ PKCS#1 v1.5 or PSS padding, which mitigates this specific vector.

Systems that still rely on unpadded RSA—often legacy hardware, custom protocols, or poorly configured services—remain exposed. The authors note that such usage is “not generally how we use RSA in practice,” underscoring a mismatch between theory and deployment.

Consequently, the real‑world impact hinges on the prevalence of these legacy implementations; organizations that have migrated to padded schemes are effectively insulated from this forgery technique.

Speed Advantage: Subexponential Forgery vs. Factoring

The researchers achieved signature forgeries for a 1024-bit RSA key using a subexponential-time algorithm, which is faster than classic integer factoring for the same key size. While not polynomial‑time, the method reduces the computational burden compared to full factorization.

To demonstrate feasibility, the team expended 1380 CPU core-years of work, spread over roughly five calendar months on real hardware. This resource investment, though substantial, is within reach for well‑funded adversaries or nation‑state actors.

Because the algorithm’s runtime scales subexponentially, larger key sizes (e.g., 2048‑bit) would demand dramatically more resources, yet the gap between forgery and factoring remains noteworthy for the still‑used 1024‑bit keys.

What This Actually Means For You

1. Audit any application that still generates raw RSA signatures; replace them with padded schemes such as RSA‑PSS.
2. Prioritize deprecation of 1024‑bit RSA keys, especially in environments where legacy hardware cannot be upgraded.
3. Monitor cryptographic library updates for patches that explicitly disable pure‑RSA signing modes.
4. Consider threat modeling that includes forgery attacks, not just key‑extraction scenarios.
5. Stay informed via the authors’ webpage and the linked paper for emerging refinements to the attack.

Immediate Action Steps

Begin by inventorying all systems that employ RSA signatures and verify whether they use padding. If any component relies on raw RSA, reconfigure it to use a standard padding scheme or migrate to an alternative algorithm such as ECDSA.

Simultaneously, replace any remaining 1024‑bit RSA keys with 2048‑bit or larger equivalents, and schedule regular reviews to ensure that new deployments do not revert to insecure configurations.

Frequently Asked Questions

Can the new RSA forgery attack recover private keys?

No. The attack forges signatures without recovering the private key, focusing instead on generating valid signatures directly.

Does the attack affect RSA signatures that use padding?

No. It only succeeds against pure, unpadded RSA signatures; padded schemes like PKCS#1 v1.5 or RSA‑PSS remain secure against this method.

How much computational effort is required to forge a 1024‑bit RSA signature?

The authors reported using 1380 CPU core-years over five months, indicating a subexponential but still significant resource commitment.

What Do You Think?

Given the lingering presence of pure RSA signatures in some legacy systems, will organizations invest enough to eliminate this narrow yet exploitable attack surface?