AI agents working under human supervision have enabled Google DeepMind to identify two ways to reduce the cost of attacking 1024-bit RSA cryptosystems. This work, conducted with cryptographers from UC San Diego and Inria, indicates that attacks against legacy RSA-1024 require less computation than previously assumed.
RSA is a public-key encryption system, whose strength relies on the difficulty of factoring a large number into prime factors. Pushmeet Kohli, Vice President of Google DeepMind and Chief Scientist of Google Cloud, however, wants to put these results into perspective: “In practice, these results only concern obsolete 1024-bit RSA systems, and modern encryption protocols, which almost universally use 2048-bit keys or larger, remain secure.”
Digital Signatures and Padding
The first discovery concerns digital signatures and padding, the predetermined data that many signature standards add to a message to bring it to a fixed block size. This mechanism was known to complicate forgery, but its effectiveness against an attacker who can choose what is signed remained unclear. DeepMind established that everything depends on the portion of the signed block controlled by the attacker. As Pushmeet Kohli explains, “once they control about half the block or more, the padding no longer provides any protection.”
According to the scientific paper accompanying this work, this concerns the PKCS#1 v1.5 format, used by the PKCS#11 signature interface of cryptographic devices such as hardware security modules (HSMs).
In a test conducted in an isolated environment, the agents re-ran a forgery attack already published in an academic study, on the same 1024-bit key. The CPU computation time was reduced by a factor of 3.5. The first forgery required 391 CPU core-years, compared to 1,380 in the original study.
Two AI agents designed, executed, and debugged the forgery computation in less than four days, with about 20 messages from the human researcher, mostly approvals. The key was not factored, an operation the source estimates at 500,000 to 1 million CPU core-years. When the attacker controls a smaller portion of the block, for example a 32-byte hash, forgery is more difficult. DeepMind says it nevertheless found an algorithm that, according to its theoretical estimates, is about 1,600 times better than the previous most effective method against 1024-bit keys.
Factoring Multiple Keys
The second discovery concerns factoring many RSA keys of the same size. An attacker can then spread the cost of a single significant initial computation across all these keys. DeepMind’s agents developed an algorithm that, on average, makes factoring each additional 1024-bit key about 30 times cheaper than the best previous approach. This theoretical estimate, however, assumes an initial computation as costly as factoring a single key, and the method has not been implemented.
The researchers emphasize that the signature attack does not allow recovery of the private key. It requires upfront about 4 billion signature requests and does not work against devices that hash messages internally. “Together, these results show that, in a new era of AI-assisted mathematics and computation, we cannot consider cryptographic difficulty as a fixed assumption,” concludes Pushmeet Kohli. He adds: “Using AI to rigorously test our prior assumptions will help ensure that modern encryption remains secure.”
