Security researchers have unveiled a novel attack method that compromises some RSA implementations without the need for factoring the public modulus. This discovery challenges the belief that RSA's security is solely tied to the difficulty of integer factorization. The attack utilizes temporary access to a raw RSA signing or decryption service to enable the forging of signatures or decryption of chosen ciphertexts offline.
The team, consisting of Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger, and Emmanuel Thomé, successfully executed the attack on a 1,024-bit RSA key. They employed 1,380 CPU core-years over five months and conducted 232 oracle queries. In contrast, factoring a 1,024-bit RSA modulus is believed to require between 500,000 to one million core-years. Their method, named eNFS, is part of the number field sieve family and uses a special number field sieve complexity by leveraging responses from the signing oracle instead of traditional mathematical processes.
The attack progresses in stages, beginning with a precomputation phase that takes about 1,200 core-years and relies on the public modulus and exponent. This is followed by interactions with a raw RSA oracle. After collecting the necessary responses, the attacker no longer needs access and can forge signatures or decrypt messages offline in approximately 180 core-years.
While this method is not a universal break of RSA, it poses a threat to systems that expose raw exponentiation oracles, such as certain HSM interfaces and blind-signature protocols like Privacy Pass. For a 2,048-bit RSA, the researchers estimate the work required to be 2^90 and 2^43 oracle queries, which is significantly less than the conventional 112-bit security level. Although these costs are prohibitive for most attackers, they could be within reach for well-resourced adversaries.
Organizations are advised not to rush to abandon correctly padded RSA. Instead, they should focus on disabling unnecessary raw RSA mechanisms, auditing HSM policies, limiting oracle exposure, and frequently rotating vulnerable keys. Protocol designers are encouraged to explore zero-knowledge proofs and consider transitioning to modern signature schemes and post-quantum cryptography for long-term security.
