Google DeepMind says AI agents working under human supervision have found two ways to reduce the cost of attacking 1024-bit RSA cryptosystems.
The research, conducted with cryptographers from UC San Diego and Inria, indicates that attacks on legacy RSA-1024 require less computation than previously assumed.
“In practice, these results only affect obsolete 1024-bit RSA systems, and modern encryption protocols, which almost universally use 2048-bit or larger keys, remain secure,” said Pushmeet Kohli, VP at Google DeepMind and chief scientist at Google Cloud.
The first finding involves digital signatures and padding, the preset data that many signature standards add to a message to bring it to a fixed block size. Padding was known to make forgery harder, but its value against an attacker who can choose what gets signed was unclear.
DeepMind determined that it depends on the share of the signed block the attacker controls. “Once they control roughly half of the block or more, padding adds no protection at all,” Kohli explained.
According to the accompanying paper, this applies to the PKCS#1 v1.5 format used by the PKCS#11 signing interface of cryptographic devices such as hardware security modules (HSMs).
In a sandboxed test, the agents re-ran an earlier academic forgery attack on the same 1024-bit key, cutting CPU time 3.5-fold. The first forgery took 391 CPU core-years, versus 1,380 in the original study.
Two AI agents designed, ran and debugged the forgery computation in under four days, with approximately 20 messages from the human researcher, mostly approvals. The key was not factored; that would take an estimated 500,000 to 1 million core-years.
Forgery is harder when the attacker controls less of the block, such as a 32-byte hash. Even then, DeepMind found an algorithm that by its theoretical estimates is roughly 1,600 times better than the previous best method against 1024-bit keys.
The second finding concerns factoring many RSA keys of the same size, where an attacker can share the cost of one large upfront computation across all of them.
DeepMind’s agents came up with an algorithm that makes factoring each additional 1024-bit key roughly 30 times cheaper on average than the best previous approach. However, this theoretical estimate assumes an initial computation as costly as factoring one key, and the method has not been implemented.
The researchers noted that the signature attack does not recover the private key. It requires roughly 4 billion signing queries made in advance, and does not work against devices that hash messages internally.
“Together, these results show that in a new era of AI-enabled mathematics and computation, we cannot treat cryptographic hardness as a fixed assumption. Using AI to rigorously test our previously held assumptions will ensure that modern encryption stays secure,” Kohli said.
Related: Encryption Backdoors: The Security Practitioners’ View
Related: Quantum Decryption of RSA Is Much Closer Than Expected
Related: Half of the 6 Million Internet-Facing FTP Servers Lack Encryption
Related: Password Managers Vulnerable to Vault Compromise Under Malicious Server
