AI agents shake RSA-1024. What it means for your email keys

TL;DR. On November 6, Google DeepMind published two papers on 1024-bit RSA. In them, AI agents guided by cryptographers found two weaknesses: under certain conditions signatures can be forged far more cheaply, and anyone who wants to break many keys of this size pays, after one large upfront computation, only about 1/58 of the usual effort for each further key. RSA with 2048 bits is not affected. We looked at where 1024-bit keys are still openly online and ended up at email. 33 of the 38 DAX groups where we found keys still publish at least one email signing key with 1024 bits. The fix is small work. It belongs on this month's list, not on the day someone breaks the first key.

What DeepMind showed

RSA relies on the fact that the product of two large primes is very hard to split again. Cryptographers test how hard that really is on retired sizes such as 1024 bits. The team led by Dj Dvijotham and Abhradeep Thakurta did this with AI agents, together with Nadia Heninger (UC San Diego, Inria) and Emmanuel Thomé (Inria). Pushmeet Kohli, a vice president at Google DeepMind, sums up the results in an article. The details are in two working papers on signatures and on factoring.

• Signatures. Many schemes pad a message with fixed data before signing it. DeepMind shows that once an attacker controls about half of the signed block, this padding offers no protection at all. With a short 32-byte fingerprint it stays harder. There, a theoretical estimate puts the saving at roughly 1,600 times.
• Many keys at once. RSA keys come in fixed sizes. Anyone who wants to break many of them can spread one large upfront computation across all of them. The agents' new method: after an upfront computation the size of a single factorization, each further 1024-bit key costs about 1/58 in theory. That is 30 times less than with the best method known since 1993.

The agents did the computing, too

What stands out is how the results came about. For a real test at full size, two agents worked together. One planned, set checkpoints and audited every result. The other wrote the code, launched the compute jobs and fixed failures. According to the paper, the researcher in charge sent about 20 short messages, mostly approvals such as "continue". In a sandboxed simulation the agents forged a signature for a 1024-bit test key on which a team around Heninger and Thomé had shown the same shortly before. Along the way they wrote 33,500 lines of code, launched 336 compute runs on up to 300,000 processor cores and caught a counting error on their own that had made the first result wrong.

The authors are candid about it: the factor of 3.5 comes from better code, not from a new method. What is new is that agents did this engineering almost on their own in just under four days. It is not the first case of its kind. In September two public records for factoring RSA numbers fell, 862 bits with agents from Cognition and 896 bits with Claude, both on GPUs.

The catch

• Theory, not practice. The 1,600-fold and the 30-fold savings are estimates from formulas that drop the smaller terms. The new signature method was not run at full size, and nobody has built the method for many keys yet. We recalculated both factors and they hold: 1,646 and 30.2.
• The first key stays expensive. The paper estimates factoring one 1024-bit key at 500,000 to 1,000,000 core-years. The public record stands at 896 bits.
• The signature weakness needs a lot of access. An attacker first has to call a signing device about four billion times with data of their choice. Devices that compute the fingerprint themselves are not affected. The attack does not reveal the key itself.
• No independent verdict yet. These are working papers without peer review. Heninger and Thomé are co-authors, not reviewers.

Our test: where 1024 bits are still online

There is one place where RSA keys sit openly on the internet: email. Most mail systems sign outgoing mail with DKIM, and the recipient fetches the matching public key from DNS. Whoever factors such a key can sign mail in the company's name that passes the recipient's authenticity check. That is exactly what makes fake invoices and fake mails from the boss believable.

On November 7 we queried the public DKIM keys of the 40 DAX groups, read-only: 54 mail domains, 116 common key names each, 6,264 DNS queries. We found keys for 38 groups, 243 different keys in total.

• Only five groups use 2048 bits throughout. One key has just 768 bits, a size researchers factored publicly in 2009. Fortunately, verifiers that follow today's standard no longer accept it.
• Many short keys belong to service providers. A large share sits under names typical of newsletter and marketing services. Every service that sends mail in the company's name brings its own keys.
• Microsoft 365 is part of it too. Under the two default names of Microsoft 365 we found 55 keys at 25 groups, 12 of them with 1024 bits. According to Microsoft's guide, 1024 bits is still the default when keys are created via PowerShell.
• Forgotten keys count too. From the outside you cannot see whether a key is still in use. But the recipient checks against every key that is in DNS. A forgotten key is as good to an attacker as an active one.

We deliberately do not name any of the groups. The list would mostly help attackers.

What this means for mid-sized companies

Nobody will factor your email key tomorrow. By today's estimate, the first 1024-bit key costs hundreds of thousands of core-years. But the math is shifting. The new paper makes every further key of the same size cheaper, and at the DAX groups alone we found 94 of them. It also shows that AI agents now achieve in weeks what used to take years. The safety margin of old keys is shrinking faster than many plans assume.

The rules have been clear for a long time. The email standard RFC 8301 has recommended at least 2048 bits since 2018. The US standards body NIST no longer allows shorter RSA keys for signing. Germany's federal cyber security agency BSI recommends at least 3000 bits for RSA signatures in its guideline TR-02102-1. Beyond email, old keys can hide in firewalls and VPN gateways, in controllers with their own certificates, in SSH keys of long-running servers and in internal certificate authorities.

What you should do now

1. List every sender. Mail server or Microsoft 365, newsletter, CRM, ticketing, accounting: every service that sends mail with your domain has its own DKIM key. Your DMARC reports show who they are.
2. Switch to 2048 bits. In Microsoft 365 this is done with the command Rotate-DkimSigningConfig and the option -KeySize 2048. According to Microsoft, each rotation takes four days, and only a second rotation switches the other key too. In Google Workspace you choose 2048 when generating the key. With newsletter services the setting is usually found with the domain.
3. Delete old keys. Remove DKIM records you no longer need from DNS, including those of services you cancelled long ago. What is in DNS counts.
4. Check your other keys. Certificates in devices, VPN, SSH, internal certificate authorities, code signing: anything below 2048 bits goes on a replacement list. For devices, ask the manufacturer.
5. Lock down signing services. If you run hardware security modules or signing services, let the device compute the fingerprint and do not sign raw data from outside.
6. Plan cryptography by the calendar. Create new RSA keys with at least 3000 bits, as the BSI recommends, and plan the move to methods for the era after quantum computers at the same time.

The math behind old keys has not collapsed overnight. But it is giving way faster than before, because AI agents now help with the computing. If you want to know where old keys are still hiding in your IT, we are happy to look with you.