Researchers Unveil eNFS Attack, Bypassing RSA Security Without Key Factoring
A novel attack, dubbed eNFS, can break RSA encryption by converting temporary access to signing services into offline forgery capabilities, challenging long-held security assumptions.
Security researchers have demonstrated a groundbreaking attack, named eNFS, that undermines certain RSA deployments by circumventing the need to factor the public modulus. This new method challenges the fundamental assumption that RSA's practical security is solely dependent on the computational difficulty of integer factorization. The attack effectively transforms limited, temporary access to a raw RSA signing or decryption service into a persistent capability to forge signatures or decrypt chosen ciphertexts offline.
The research, led by Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger, and Emmanuel Thomé, successfully implemented the technique against a 1,024-bit RSA key. The computation required approximately 1,380 CPU core-years spread over five months and involved 232 oracle queries. In stark contrast, factoring a 1,024-bit RSA modulus is estimated to demand between 500,000 and one million core-years, highlighting the significant efficiency gain of the eNFS attack.
The eNFS attack belongs to the number field sieve family of algorithms. Unlike the general number field sieve (GNFS) used for factoring RSA moduli, eNFS leverages a faster approach akin to the "special" number field sieve. It achieves this by substituting a portion of the traditional mathematical computation with responses obtained from a signing oracle. Crucially, the attack does not recover the prime factors of the modulus or the private RSA key itself.
The attack's execution involves distinct stages. An initial precomputation phase, requiring around 1,200 core-years, depends solely on the public modulus and exponent. Subsequently, the attacker interacts with the raw RSA oracle by submitting carefully selected values. Once the oracle's responses are collected, the attacker's direct access can be revoked. The ability to forge any chosen signature or decrypt a target ciphertext offline then requires an additional 180 core-years and can be repeated indefinitely.
While the underlying algorithm was introduced in 2007 by Antoine Joux, David Naccache, and Emmanuel Thomé, this marks its first practical implementation and large-scale demonstration against a 1,024-bit key. The researchers built upon the CADO-NFS framework, incorporating the necessary engineering for tasks such as polynomial selection, sieving, linear algebra, root extraction, and descent at scale.
It is important to note that eNFS is not a universal exploit for all RSA implementations. The attack necessitates temporary access to a raw exponentiation oracle, a feature typically absent in conventional RSA signatures employing 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 certain blind-signature protocols, such as Privacy Pass, where blinded requests can mimic the required oracle behavior.
The researchers estimate that a similar attack against 2,048-bit RSA would require approximately 2^90 work and 2^43 oracle queries, a computational cost significantly lower than the commonly assumed 112-bit factoring strength. For 4,096-bit RSA, they project roughly 2^119 work. While these figures remain beyond the reach of most attackers, they pose a tangible threat to well-resourced adversaries and protocols that utilize long-lived public keys.
Organizations are advised not to abandon RSA immediately but to take proactive measures. This includes disabling unnecessary raw RSA mechanisms, auditing HSM policies, strictly limiting oracle exposure, and implementing more frequent key rotation for vulnerable blind-signature schemes. Protocol designers should explore zero-knowledge proofs for validating requests, and long-term strategies should prioritize migration to modern signature schemes and post-quantum cryptography rather than relying solely on larger RSA key sizes for security.