Google says its AI agents make attacks on old RSA encryption keys cheaper

On November 6, Pushmeet Kohli, vice president at Google DeepMind, published a post on X with an ambitious title: “Advancing the frontier of cryptanalysis,” the discipline that looks for weaknesses in encryption systems. The content is more modest than the title, but not trivial. According to DeepMind, AI agents guided by researchers found, within a few weeks, two ways to make attacks on 1024-bit RSA cheaper. That key size is outdated but still present in old systems.

The work was led by Dj Dvijotham and Abhradeep Thakurta of DeepMind, with two renowned cryptographers: Nadia Heninger of the University of California, San Diego, and Emmanuel Thomé of Inria (the French national research institute for digital science). DeepMind states upfront that keys of 2048 bits and above, which the company says are used by nearly all modern protocols, are not affected.

First shortcut: forging a signature without knowing the key

The first result concerns digital signatures, which prove that a document or software really comes from its author. According to details relayed by Interesting Engineering and other outlets, if the attacker controls about half of the signed block, “padding” (the bytes added to protect the signature) no longer makes forgery any harder than it would be without it. Even when the attacker controls only a small part of the data, such as a 32-byte hash, a new algorithm would perform about 1,600 times better than the best known attack in that case, for 1024-bit keys.

That figure is a theoretical estimate, not a measurement. The only practical check announced involves an already solved case: an attack published in September by Laura Shea, Miro Haller, Adam Suhl, Nadia Heninger and Emmanuel Thomé. It made it possible to forge RSA-1024 signatures without breaking the key, provided the attacker had temporary access to a device that signs without padding. The researchers used a hardware security module (HSM), queried it about 2³² times (some 4 billion requests), and used 1,380 years of single-processor-core computing time over five months. In an isolated environment, the program written by the agents reproduced this result with 3.5 times less computing time.

Second shortcut: breaking old keys in bulk

The second result concerns factorization, that is, breaking down the large number at the heart of an RSA key, which is enough to break it. A new method would cut the cost of each additional key by about 30 times when attacking 1024-bit keys of the same size in bulk, after a precomputation as costly as one factorization, compared with the best method known so far under these conditions. This gain is also a theoretical estimate: according to the technical paper, such a method has never yet been implemented.

DeepMind has put two technical papers online, presented as working papers, and no independent reproduction has been published yet. The company nonetheless draws a broad conclusion: as AI progresses in mathematics, writes Pushmeet Kohli, “we cannot treat cryptographic hardness as a fixed assumption,” and cryptographic standards must be constantly stress-tested.

Where do 1024-bit keys still hide?

RSA-1024 has been deprecated for more than ten years: NIST, the US standards institute, has banned its use for creating new signatures since 2014. But old equipment, firmware or internal applications that were never reviewed can keep these keys long after their expiration date. That is where this work matters:

• inventory the RSA keys still in use and spot the 1024-bit ones: internal certificates, old VPNs, firmware signatures, SSH keys;
• replace them with keys of at least 2048 bits, and 3072 bits for uses planned beyond 2030, as recommended by the cryptographic mechanisms guide from ANSSI (France's national cybersecurity agency);
• never expose a “raw” signing function without padding: that was the condition of the September attack;
• use this inventory to prepare the post-quantum migration, which the authors of the September paper themselves recommend.

For RSA-2048, the threat is of a different nature: a future quantum computer, for which French manufacturer Alice & Bob recently put forward a figure of 23,000 qubits. Following Anthropic's work on the elliptic curves of the web, it is a new sign that AI labs are taking an interest in cryptography. It remains to be seen whether independent cryptographers will confirm the announced gains.