Researchers Forged Signatures Under an RSA Key Without Ever Recovering It
Five researchers say they forged digital signatures under a live 1,024-bit RSA key without ever recovering the key or the two prime numbers it is built from. Laura Shea and colleagues at UC San Diego, with Emmanuel Thomé of INRIA Nancy, posted the work to the Cryptology ePrint Archive on Sept. 20. The paper is a preprint and has not been peer reviewed.
RSA key lengths are chosen on the assumption that breaking a key means factoring it, splitting the public number back into its two primes. The authors write in the preprint that this may not describe RSA's security in practice.
The method is not new: the paper describes it as an under-appreciated 2007 algorithm by Joux, Naccache and Thomé, and what the team did was implement it and run it. The attack needs temporary access to a service that signs or decrypts raw RSA data on request.
The run took 1,380 CPU core-years over five calendar months and made about 4.3 billion requests to that service. The authors report that most of that was one-time precomputation, and that once it is done, any signature of the attacker's choosing can be forged offline in 180 core-years.
The signing service was a hardware security module, the sealed appliance that holds a key and signs without releasing it. The team reports that it could impersonate that module through ordinary interactions with its interface, and that the key was never extracted. The paper notes that blind RSA schemes expose the same kind of signing service.
Extrapolating from their timings, the authors conclude that RSA's actual security against an attacker who can reach such a service sits 15 to 30 bits below the factoring-based estimates used for the key sizes common in practice, and that even 4,096-bit RSA does not appear to reach a 128-bit security level in this attack model. That is an extrapolation from the single key they attacked.
The authors argue the result is classical evidence for moving away from RSA during the current shift to post-quantum cryptography.
