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

By Tom Whitfield

Google DeepMind's AI agents cut a 1024-bit RSA signature-forgery computation to 391 CPU core-years from 1,380, completing the rerun in 3.2 days.

DeepMind says agents working under human supervision found two ways to lower the cost of attacking 1024-bit RSA. The work appears in two working papers co-written by DeepMind researchers and cryptographers Nadia Heninger, also affiliated with UC San Diego and Inria, and Emmanuel Thomé of Inria.

Standards bodies have already retired 1024-bit RSA for new signatures, while modern protocols use 2048-bit keys or larger. DeepMind vice president Pushmeet Kohli said: "These results only affect obsolete 1024-bit RSA systems," adding that "we cannot treat cryptographic hardness as a fixed assumption."

What did the agents actually rerun?

The first paper targets signing devices, including hardware security modules, that sign data through the PKCS#11 interface. Its attack assumes an adversary can make a device sign many chosen inputs, then produce a valid signature on a new message without recovering the private key.

Earlier this year, Heninger, Thomé and their co-authors ran the attack on one 1024-bit key with about four billion signing queries and 1,380 CPU core-years. For comparison, the earlier team estimated that factoring that key outright would require 500,000 to one million core-years.

DeepMind's agents repeated the work on the same key, using the same algorithm and parameters. Their first forged root took 391 core-years, a 3.5-fold reduction that the authors attributed to better code and execution rather than a new algorithm.

The 3.5-fold saving came from better implementation and execution, not a new attack algorithm.

How did human supervision work?

• A supervisor agent wrote the design and audited the results.
• An executor agent wrote about 33,500 lines of code and ran the jobs on up to 300,000 CPU cores.
• A human researcher sent about 20 short messages, mostly approvals.

The run took 3.2 days from the first full-scale sieving job, against about five months for the original. The authors attributed most of the elapsed-time reduction to greater parallelism.

The human role centered on about 20 short messages, mostly approvals, rather than hands-on execution.

Why does padding change the attack?

Padding is the fixed formatting a signing device adds before it signs. The paper shows that padding stops protecting a 1024-bit key once the attacker controls about half the signed block, which includes a 64-byte digest such as SHA-512.

With a shorter 32-byte digest such as SHA-256, the attack stays harder. For that case, the paper lowers the asymptotic cost exponent from 1.8171 to 1.5803.

DeepMind estimates that change is about 1,600 times better than the previous best method at 1024 bits. That figure remains a theoretical estimate, not a measured run.

The 3.5-fold gain is measured, while the 1,600-fold claim remains theoretical.

How could shared precomputation cut batch factoring?

The second paper addresses an attacker who wants to factor many same-size RSA keys and can share one large precomputation across them. The mechanism is amortization: one expensive setup can serve many targets.

If the precomputation costs about as much as factoring one key, the method puts each further 1024-bit key at about 1/58 of the standard number field sieve's cost. It also estimates a 30-fold lower cost than Coppersmith's multiple number field sieve, the best approach since 1993.

The estimate keeps the leading-order term and sets lower-order terms to zero; the method has not been run. The authors machine-checked key algebraic identities in the Lean 4 proof assistant, with one AI model generating the proofs and a second verifying them.

Batch factoring could become far cheaper in theory, but no implementation yet demonstrates the saving.

What does this mean for deployed systems?

• The forgery requires billions of signing queries made in advance.
• It requires direct access to a signing interface that accepts the caller's input.
• It does not work against devices that hash messages internally.

Both papers state that their results do not threaten deployed cryptosystems based on 2048-bit and larger RSA. Systems still using 1024-bit keys for signatures, often older hardware and embedded devices, have less margin than previously assumed.

Going forward, operators of legacy 1024-bit signing devices face the clearest pressure to migrate, while 2048-bit RSA deployments remain outside the threat described in either paper.