RSA signatures forged in nearly SNFS time without factoring the key
Forging 1024-bit RSA signatures in nearly SNFS time [pdf]
Researchers at UC San Diego and Inria implemented a 2007 algorithm to forge 1024-bit RSA signatures after temporary black-box access to a signing oracle, without factoring the modulus. The attack took 1380 CPU core-years, including 1200 core-years of precomputation and 2^32 oracle queries, then forged any signature offline in 180 core-years. Extrapolating to 2048- and 4096-bit keys, they estimate RSA security is 15–30 bits lower than factoring-based estimates, meaning even 4096-bit RSA falls short of 128-bit security in this model.
Even 4096-bit RSA does not appear to meet a 128-bit security level in this attack model.
- tptacek
The most important thing to know about this work, which is awesome, is that it relies on access to a raw RSA oracle, where you have a public key and an API that allows you to directly do RSA operations with the corresponding key. The idea is that you then lose access to the oracle, and thus to the private key, but you've gained enough information from your session with the oracle to make forgeries in the future.
So it's not a straightforward general-purpose RSA-1024 signature break; it's pretty situational. The paper goes into detail (in section 5) about how those situations can emerge in practical scenarios.
- nk_kolja
I was unaware of snfs algorithms for generic moduli and/or signatures. Very nice.
The theoretical result is purely due to the 2007 Joux et al. paper.
What’s new is the implementation and the 1024-bit rsa signature forgery.
Also no ai, so we can expect some speedups soon.
I really didn’t expect rsa to be targeted so much this year. Hope that these results will motivate people to pursue algorithmic improvements!
- benmmurphy
nice poem at the end of the paper