DeepMind AI Agents Slash Cost of Breaking Legacy RSA-1024

Google DeepMind says supervised AI agents found two ways to make attacks on obsolete 1024-bit RSA far cheaper, while 2048-bit keys stay secure.

@sharedot

DeepMind AI Agents Slash Cost of Breaking Legacy RSA-1024

By @sharedot · · 6 pages

  • AI Frontier
  • Cryptography
  • AI Agents

Google DeepMind says supervised AI agents found two ways to make attacks on obsolete 1024-bit RSA far cheaper, while 2048-bit keys stay secure.

Two agents, twenty messages, four days

Google DeepMind reports that AI agents working under human supervision found two ways to lower the cost of attacking 1024-bit RSA, a key size standards bodies have already retired.

In a sandboxed rerun of a recent academic forgery attack, a supervisor agent wrote the design and audited results while an executor agent wrote roughly 33,500 lines of code and ran jobs on up to 300,000 CPU cores. The human researcher sent about twenty short messages, mostly approvals.

The first forged signature took 391 CPU core-years versus 1,380 in the original study — a 3.5-fold cut — and the run finished in 3.2 days from the first full-scale sieving job, against about five months for the earlier work.

DeepMind attributes the gain to better code and execution, not a new algorithm.

Why the padding result is a real surprise

The surprising theoretical finding concerns padding, the fixed formatting a signing device adds before signing.

DeepMind determined that padding stops protecting a 1024-bit key once the attacker controls roughly half the signed block — including a 64-byte digest such as SHA-512 — in the PKCS#1 v1.5 format used by the PKCS#11 interface of hardware security modules.

"Once they control roughly half of the block or more, padding adds no protection at all," DeepMind VP Pushmeet Kohli explained, according to SecurityWeek.

For the harder case with a 32-byte digest like SHA-256, mlq.ai reports the paper lowers the asymptotic cost exponent from 1.8171 to 1.5803, an estimated 1,600 times better than the previous best method at 1024 bits — a theoretical estimate, not a measured run.

Cheaper bulk factoring, verified in Lean 4

The second paper addresses an attacker who wants to factor many RSA keys of the same size and can share one large precomputation across them.

If that precomputation costs about as much as factoring one key, the method puts each further 1024-bit key at about 1/58 the cost of the standard number field sieve and about 30 times less than Coppersmith's multiple number field sieve, the best approach since 1993.

The estimate is at leading order with lower-order terms set to zero and the method has not been implemented, but its key algebraic identities were machine-checked in the Lean 4 proof assistant, with one AI model generating the proofs and a second verifying them.

Limits and what comes next

The forgery attack needs roughly 4 billion signing queries made in advance, direct access to a signing interface that accepts the caller's input, and does not work against devices that hash messages internally; it also never recovers the private key.

Factoring the key outright would still take an estimated 500,000 to 1 million core-years. Both papers state the results do not threaten deployed cryptosystems based on 2048-bit and larger RSA, which modern protocols almost universally use.

The work was co-written with cryptographers Nadia Heninger of UC San Diego and Inria and Emmanuel Thomé of Inria. The real stakes are legacy hardware and embedded devices that still sign with 1024-bit keys, which now have less margin than assumed.

"We cannot treat cryptographic hardness as a fixed assumption," Kohli said.

Sources

  1. mlq.ai › Google DeepMind's AI agents cut the cost of two attacks on legacy 1024-bit RSA
  2. securityweek.com › Google DeepMind's AI Agents Make 1024-Bit RSA Keys Cheaper to Attack

More on AI Frontier