A team of security researchers, including Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger, and Emmanuel Thomé, has implemented a new attack against RSA encryption that bypasses the traditional requirement of factoring the RSA public modulus. This method, termed eNFS, allows attackers with temporary access to a raw, unpadded RSA signing or decryption service to subsequently forge signatures or decrypt chosen ciphertexts offline. Their work challenges the assumption that RSA's practical strength is solely tied to the computational difficulty of integer factorization.
The researchers successfully demonstrated eNFS against a 1,024-bit RSA key. The computation involved approximately 1,380 CPU core-years over five months and required 232 oracle queries. This contrasts sharply with estimates for factoring a 1,024-bit RSA modulus, which typically range from 500,000 to one million core-years.
The eNFS method is a variation of the number field sieve family of algorithms. Instead of employing the general number field sieve used for factoring RSA moduli, eNFS achieves the faster complexity of a "special" number field sieve. It does so by substituting a portion of the usual mathematical work with responses obtained from a signing oracle. Crucially, this technique does not recover the prime factors of the RSA modulus or the RSA private key.
The attack proceeds in two main stages. The first involves an approximately 1,200-core-year precomputation that depends only on the public modulus and exponent. Following this, the attacker submits specific values to the raw RSA oracle. Once these responses are collected, the need for oracle access ceases, allowing the attacker to forge any chosen signature or decrypt a target ciphertext offline, a process that takes roughly an additional 180 core-years.
The underlying algorithm for this attack is not new; Antoine Joux, David Naccache, and Emmanuel Thomé first introduced it in 2007. However, the current research marks its first large-scale implementation and demonstration against a 1,024-bit RSA key. The code for eNFS builds upon the CADO-NFS software, incorporating additional engineering for polynomial selection, sieving, linear algebra, root extraction, and descent at this scale.
The researchers emphasize that this is not a universal break for all RSA implementations. The attack requires temporary access to a raw exponentiation oracle. This capability is generally not exposed by conventional RSA signatures that use PKCS#1 v1.5 or RSA-PSS padding. More plausible targets for this attack include Hardware Security Module (HSM) interfaces that permit raw PKCS#11 RSA operations, and blind-signature protocols such as Privacy Pass, where blinded requests can provide the necessary oracle behavior.
For 2,048-bit RSA, the researchers estimate the eNFS method would require approximately 2^90 work and 2^43 oracle queries, compared to the commonly accepted 112-bit factoring strength. They project roughly 2^119 work for 4,096-bit RSA, which falls short of a modern 128-bit security target.