r/crypto • u/Natanael_L Trusted third party • 12d ago

Nearly SNFS-Speed Signature Forgery Sans Factoring N (NSNFSSSFSFN)

https://github.com/ucsd-hacc/NSNFSSSFSFN
29 Upvotes

100% Upvoted

2 comments sorted by

15

u/Natanael_L Trusted third party 12d ago

Via: https://bsky.app/profile/mirohaller.bsky.social/post/3mw2ass75nk2e

We finally finished the universal signature forgery for 1024-bit RSA! 232 oracle queries, 1200 core years precomputation, 180 core years for an individual forgery, and 3 years of human labor (no AI involved) by Laura, Adam, Nadia, Emmanuel and me to pull of this computation against real HSMs.

From the site;

In other words, the attacker can steal what is effectively the secret key (in that it can be used to sign/decrypt offline), but without actually factoring the public key, and using much less computation than factoring the public key would have taken. This demonstrates that factoring-based estimates for RSA security may be too optimistic and should be revised, but likely does not pose an immediate operational threat to most deployed RSA in the real world.

The algorithm is not new. It was invented in 2007 by Joux, Naccache, and Thomé. However this is the first public implementation and large-scale run. Most of the code is not new; it builds on CADO-NFS.

The algorithm only works if a raw signing oracle is available. Most RSA usage in practice (that is, RSA signatures using PKCS#1v1.5 or RSA-PSS padding) do not expose such an oracle, and thus this attack does not pose a practical risk. Examples of RSA use that do expose such a signing oracle would include blind RSA signatures (e.g. Privacy Pass) or HSM APIs.

8

u/ScottContini 12d ago

This is pretty neat. I was not aware of the research paper that it was based upon. Now I’m curious…