DeepMind AI agents cut the cost of attacking 1024-bit RSA

Google DeepMind researchers, working with cryptographers from UC San Diego and Inria, say AI agents under human supervision found two ways to reduce the computational cost of attacks on legacy 1024-bit RSA systems. Google DeepMind vice-president Pushmeet Kohli said modern protocols, which almost universally use keys of 2048 bits or more, remain secure.

One result concerns forging digital signatures using PKCS#1 v1.5, including through the PKCS#11 signing interface used by devices such as hardware security modules. DeepMind found that padding provides no protection if an attacker can control roughly half or more of the signed block. In a sandboxed test, agents cut the CPU time for an earlier forgery attack on the same 1024-bit key from 1,380 to 391 core-years.

They designed, ran and debugged the computation in under four days, with about 20 messages from a human researcher. The attack does not recover the private key: it requires roughly 4 billion signing queries in advance and does not work against devices that hash messages internally. Factoring the key would still take an estimated 500,000 to 1 million core-years. For attacks controlling less data, such as a 32-byte hash, DeepMind estimated a method around 1,600 times better than the previous best.

The second result is a theoretical method for factoring multiple RSA keys of the same size, sharing the cost of an initial computation. It could make each additional 1024-bit key roughly 30 times cheaper to factor on average than with the previous best approach. That estimate assumes an initial computation as costly as factoring one key, and the method has not been implemented.