Forging 1024-bit RSA signatures in nearly SNFS time

This article discusses a significant development in the field of cryptography, specifically concerning the security of RSA encryption. While RSA is widely believed to be secure due to the complexity of factoring large numbers, a 2007 algorithm by Joux, Naccache, and Thomé challenges this assumption. This algorithm enables an attacker to forge RSA signatures after temporarily accessing a raw RSA signing/decryption oracle, a process that takes time comparable to that of the special number field sieve (SNFS) without actually factoring the key.

The researchers implemented and executed this algorithm on a 1024-bit RSA system. The entire attack required 1380 CPU core-years over five calendar months, with the majority of time spent on precomputation. After this initial phase, the attacker could produce any desired signature offline in just 180 core-years. To demonstrate their findings, the researchers used a hardware security module (HSM) as the signing oracle, effectively showing how an attacker could impersonate such a system through black-box API interactions without ever needing to extract the encryption key.

The implications of this work extend to larger RSA key sizes as well. Extrapolating the empirical running times to keys ranging from 1024-bit to 4096-bit, the authors conclude that the practical security of RSA with a signing oracle is between 15 to 30 bits lower than traditional factoring-based security estimates. Even with 4096-bit RSA, the system fails to meet the commonly accepted 128-bit security level under this attack model.

This revelation points to a gap in current RSA security assumptions, suggesting that the cryptographic community should reconsider reliance on RSA during the ongoing post-quantum transition. The article highlights the need for a reevaluation of RSA-type security assumptions in light of this new cryptanalytic evidence.