Researchers have unveiled a novel approach to compromise certain RSA deployments that does not rely on factoring the public modulus. This breakthrough questions the traditional belief that RSA’s security is solely dependent on the difficulty of integer factorization.
The newly demonstrated technique allows temporary access to a basic RSA signing or decryption service, transforming it into a sustained ability to forge signatures or decrypt selected ciphertexts offline.
An Innovative Approach to RSA Security
Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger, and Emmanuel Thomé have successfully implemented this method against a 1,024-bit RSA key. Their effort required 1,380 CPU core-years over a period of five months and involved 232 oracle queries. In contrast, factoring a 1,024-bit RSA modulus is estimated to need between 500,000 and one million core-years.
Named eNFS by the researchers, this method is a variant of the number field sieve family, diverging from the typical number field sieve approach used for factoring RSA moduli. It reaches the faster “special” number field sieve complexity by substituting some conventional mathematical tasks with responses from the signing oracle, though it never reveals the prime factors or the RSA private key.
Step-by-Step Unveiling of the Attack
The attack progresses through several phases. Initially, it involves about 1,200 core-years of precomputation, relying only on the public modulus and exponent. Subsequently, the attacker inputs specific values into the raw RSA oracle. Once these responses are acquired, the attacker no longer needs access: generating any desired signature or decrypting a target requires approximately another 180 core-years and can be conducted offline.
The underlying algorithm was originally introduced by Antoine Joux, David Naccache, and Emmanuel Thomé in 2007. However, this work is the first to implement it on a large scale for 1,024-bit keys, leveraging CADO-NFS for polynomial selection, sieving, linear algebra, root extraction, and other complex computations.
Implications for RSA and Future Security Measures
This discovery does not universally break RSA. The attack’s success hinges on temporary access to a basic exponentiation oracle, a feature typically shielded by conventional RSA signatures using PKCS#1 v1.5 or RSA-PSS padding. More likely targets include HSM interfaces allowing raw PKCS#11 RSA operations and blind-signature protocols like Privacy Pass.
The researchers estimate that for a 2,048-bit RSA, the attack requires 290 work and 243 oracle queries, compared to the usual 112-bit factoring strength. For 4,096-bit RSA, they project about 2119 work, falling short of a modern 128-bit security benchmark. While these costs are presently prohibitive for most attackers, they are significant for well-funded adversaries and protocols with long-lived public keys.
Organizations are advised not to immediately abandon correctly padded RSA. Instead, they should disable superfluous raw RSA mechanisms, review HSM policies, limit oracle exposure, and frequently update vulnerable blind-signature keys. Protocol designers might consider zero-knowledge proofs of well-formed requests, and future strategies should prioritize modern signature schemes and post-quantum cryptography over simply increasing RSA key sizes.
