Overview
Google DeepMind, working with cryptographers from UC San Diego and Inria, used AI agents under human supervision to lower the cost of two attacks on 1024-bit RSA. DeepMind stresses that only obsolete 1024-bit systems are affected.
Finding 1: Signature Forgery and PKCS#1 v1.5 Padding
Padding makes forgery harder only while the attacker controls a limited share of the signed block. DeepMind found that once an attacker controls about half the block or more, padding gives no protection. This touches the PKCS#1 v1.5 format used by the PKCS#11 signing interface on hardware such as HSMs.
- In a sandboxed test, the agents re-ran an earlier academic forgery attack on the same 1024-bit key and cut CPU time 3.5-fold: 391 core-years versus 1,380 in the original study.
- Two agents designed, ran, and debugged the computation in under four days, with about 20 human messages, mostly approvals.
- Against a 32-byte hash, the algorithm is estimated at roughly 1,600 times better than the prior best method for 1024-bit keys. This is a theoretical estimate.
Limits: the attack does not recover the private key, needs about 4 billion signing queries made in advance, and does not work against devices that hash messages internally.
Finding 2: Batch Factoring
When many RSA keys of the same size exist, an attacker can share one large upfront computation across all of them. DeepMind estimates this is about 30 times cheaper on average per additional 1024-bit key than the best previous approach. The method has not been implemented, and the estimate assumes the upfront cost equals factoring one key.
For scale, factoring a single key is estimated at 500,000 to 1 million core-years. The tested key was not factored.
Implications
Pushmeet Kohli, VP at Google DeepMind, says modern protocols mostly use 2048-bit or larger keys and remain secure. He argues cryptographic hardness should not be treated as a fixed assumption now that AI can probe long-held assumptions.
Recommendations
- Inventory any remaining 1024-bit RSA keys, especially signing keys on HSMs.
- Migrate to 2048-bit or larger keys, or to modern signature schemes.
- Prefer devices that hash messages internally rather than signing attacker-influenced raw blocks.
- Fold this into post-quantum and crypto-agility planning.