Google DeepMind’s AI Agents Find Two Weak Spots in Legacy 1024-Bit RSA

Two AI agents, with about 20 short messages from a human researcher, reran a recent attack on 1024-bit RSA signatures in under four days and used about 3.5 times less CPU time than the academic team that first pulled it off. Google DeepMind released that result Friday alongside a second paper that lowers the theoretical cost of factoring old RSA keys in bulk.

Pushmeet Kohli, Google DeepMind’s VP of research, laid out both findings in an essay posted to X. The work was led by Dj Dvijotham and Abhradeep Thakurta, with cryptographers Nadia Heninger (UC San Diego and Inria) and Emmanuel Thomé (Inria) among the co-authors. Kohli drew the boundary early: “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.”

Where the signing attack applies

The first working paper asks how much PKCS#1 v1.5 padding protects a key when an attacker can feed chosen data to a signing device, such as a hardware security module, and collect the output. The answer turns on how many of the 128 bytes in a 1024-bit block the caller controls. Through the PKCS#11 mechanism CKM_RSA_PKCS, a caller who can supply 65 of them faces a problem no harder than raw, unpadded signing, the authors found. In their measurements, a 64-byte digest such as SHA-512 behaved about the same.

A 32-byte digest like SHA-256 leaves a harder problem. Kohli wrote that a new algorithm improves on the previous best method for that case by roughly 1,600x at 1024 bits, by DeepMind’s theoretical estimates. The paper says that result is asymptotic and was not run at this size.

The authors are just as specific about the limits. Mechanisms that hash the message inside the device, such as CKM_SHA256_RSA_PKCS, never let the caller choose the block and fall outside both attack models. An attacker also needs direct calls into the signing interface, and a lot of them: about 4 billion in the reproduced computation, all made before the target was known. Current guidance, the paper notes, already no longer approves 1024-bit RSA for generating signatures.

Agents ran the engineering

The benchmark was a 1024-bit instance attacked by Laura Shea, Miro Haller, Adam Suhl, Heninger and Thomé, whose paper went up on the IACR ePrint archive in September. That team spent 1,380 CPU core-years over five calendar months and used an HSM as the signing oracle. Using the same algorithm, polynomials and bounds, DeepMind’s agents computed the first root in 391 core-years.

One model acted as supervisor, writing the design, setting checks for each stage and auditing results. A second wrote and ran the code and fixed failures. Between them they produced about 33,500 lines of new code and launched 336 distributed experiments, peaking at roughly 300,000 CPU cores and 16 GPUs. The human’s replies were mostly approvals such as “follow your recommendation” and “continue.” One problem the agents had to track down mid-run was a 32-bit index overflow that made the first computed root wrong. The paper credits the savings mainly to the code rather than the hardware, and says the much shorter calendar time “reflects mainly parallelism.”

A bulk-factoring shortcut, on paper only

The second paper, dated Thursday, is aimed at attackers who want many keys of the same size. When the shared precomputation costs about one factorization, Coppersmith’s multiple number field sieve has set the best known cost for each extra integer since 1993. DeepMind’s “fan factory” gives each target its own family of number fields fed by that shared work. At leading order, each further 1024-bit integer would cost about 1/58 of a standard number field sieve run, 30 times less than Coppersmith’s method.

One model generated the proofs and a second checked them, and the algebraic identities were machine-checked in Lean 4. The authors say no fan factory has been implemented.

The findings add to research on how AI cryptanalysis could change estimates of cryptographic security. The September ePrint paper had already pushed the point further than 1024 bits: with a signing oracle, its authors concluded, RSA’s concrete security should be 15 to 30 bits lower than factoring-based estimates for keys from 1024 to 4096 bits. The authors wrote: “Even 4096-bit RSA does not appear to meet a 128-bit security level in this attack model.”