New RSA Attack Bypasses Factoring Keys

Key Takeaways

• A novel attack, dubbed eNFS, has been demonstrated that can forge RSA signatures without factoring the private key.
• The technique targets specific RSA deployments that expose raw, unpadded signing or decryption services.
• The attack, successfully implemented against a 1,024-bit RSA key, required significantly less computational effort than traditional factorization.
• While not a universal break, it poses a threat to systems like Hardware Security Modules (HSMs) and blind-signature protocols.
• Organizations should review and disable raw RSA mechanisms and consider migrating to modern cryptographic schemes.

Researchers Uncover Faster RSA Attack Bypassing Key Factorization

Cybersecurity researchers have unveiled a groundbreaking method to compromise certain RSA implementations, achieving signature forgery and decryption capabilities without the computationally intensive process of factoring the public modulus. This discovery challenges the long-held assumption that RSA’s security strength is solely tied to the difficulty of integer factorization.

The new attack transforms temporary access to an unpadded RSA signing or decryption service into a lasting capability to forge signatures or decrypt arbitrary ciphertexts offline. This means an attacker, after an initial compromise, can maintain persistent control over signing or decryption without needing further access to the original system.

eNFS: A New Approach to Breaking RSA

A team comprising Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger, and Emmanuel Thomé successfully demonstrated this technique against a 1,024-bit RSA key. Their computational efforts spanned five months, consuming 1,380 CPU core-years and necessitating 232 oracle queries. This contrasts sharply with the estimated 500,000 to one million core-years typically required to factor a 1,024-bit RSA modulus, highlighting the efficiency of the new method.

Dubbed eNFS by its creators, the method is a variant of the number field sieve family of algorithms. Unlike the general number field sieve used for factoring RSA moduli, eNFS leverages a “special” number field sieve complexity. It achieves this by substituting a portion of the standard mathematical computations with responses obtained from the signing oracle. Crucially, the attack never exposes the prime factors or the RSA private key itself.

Attack Mechanics and Resource Requirements

The eNFS attack unfolds in distinct phases. An initial precomputation phase, which is dependent only on the public modulus and exponent, requires approximately 1,200 core-years of processing. Following this, the attacker submits carefully selected values to the raw RSA oracle. Once these responses are gathered, the need for direct access to the oracle vanishes. Subsequent operations, such as forging any chosen signature or decrypting a target, can be performed offline and require roughly an additional 180 core-years of computation.

The underlying algorithmic principles are not entirely novel; Antoine Joux, David Naccache, and Emmanuel Thomé introduced it in 2007. However, the current research marks the first practical implementation and large-scale demonstration against a 1,024-bit key. The codebase for this implementation heavily relies on CADO-NFS, with significant engineering additions for tasks such as polynomial selection, sieving, linear algebra, root extraction, and descent at this operational scale.

Targeted Deployments and Future Implications

It is important to note that this is not a universal vulnerability for all RSA implementations. The attack specifically requires temporary access to a raw exponentiation oracle. This capability is not typically exposed by conventional RSA signatures that utilize PKCS#1 v1.5 or RSA-PSS padding. More plausible targets include Hardware Security Module (HSM) interfaces that permit raw PKCS#11 RSA operations and specific blind-signature protocols, such as Privacy Pass, where blinded requests can inadvertently provide the necessary oracle behavior.

The researchers estimate that the eNFS attack would require approximately 2^{90} work and 2^{43} oracle queries to compromise 2,048-bit RSA, significantly less than the commonly assigned 112-bit factoring strength for that key size. For 4,096-bit RSA, they project roughly 2^{119} work, which falls short of a modern 128-bit security target. While these costs remain beyond the reach of most attackers, they could pose a substantial risk to well-resourced adversaries and protocols that rely on long-lived public keys.

What You Should Do

• Disable Raw RSA Mechanisms: Audit all systems and immediately disable any unnecessary raw RSA exponentiation or decryption functionalities.
• Review HSM Policies: Scrutinize Hardware Security Module (HSM) configurations to ensure they do not permit raw PKCS#11 RSA operations without proper padding and access controls.
• Limit Oracle Exposure: Implement robust security measures to prevent temporary access to raw RSA signing or decryption services, especially in blind-signature protocols.
• Increase Key Rotation: For protocols utilizing blind signatures or similar mechanisms that might be vulnerable, implement more frequent key rotation policies.
• Consider Migration: For long-term security, evaluate and plan migration to modern signature schemes and explore post-quantum cryptography solutions, rather than relying on increasingly larger RSA key sizes as a permanent defense.

Disclaimer: HackersRadar reports on cybersecurity threats and incidents for informational and awareness purposes only. We do not engage in hacking activities, data exfiltration, or the hosting or distribution of stolen or leaked information. All content is based on publicly available sources.