The Challenge
Cryptographic hardness has often been seen as a constant in risk assessments. You choose a key length, document it, and move on. However, recent research by Google DeepMind with cryptographers from UC San Diego and Inria challenges this view. AI agents, under human supervision, have found two ways to reduce the cost of attacking 1024-bit RSA.
This isn't about broken modern encryption. Pushmeet Kohli, VP at Google DeepMind, clarifies that these results affect obsolete 1024-bit RSA systems. Protocols using 2048-bit or larger keys remain secure. The real challenge is identifying any 1024-bit keys still in use within your systems.
Environment and Constraints
Two technical conditions define the risk.
First, signature padding. Padding adds preset data to a message to reach a fixed block size, traditionally making forgery harder. DeepMind found its effectiveness depends on how much of the block an attacker controls. If they control half or more, padding offers no protection. This is linked to the PKCS#1 v1.5 format used by the PKCS#11 signing interface in devices like hardware security modules (HSMs).
Second, scale. If an attacker targets many RSA keys of the same size, one large computation can be shared across them all.
These constraints are crucial. The signature attack doesn't recover the private key. It requires about 4 billion signing queries and doesn't work against devices that hash messages internally. The factoring improvement is theoretical and hasn't been implemented.
The Approach Taken
DeepMind's team used two AI agents to design and execute the forgery computation. The agents completed their task in under four days with minimal human input. The test was conducted in a sandbox environment, replicating an earlier academic forgery attack on a 1024-bit key.
For the factoring result, the agents developed an algorithm making each additional 1024-bit key roughly 30 times cheaper to factor than previous methods. This assumes an initial computation as costly as factoring one key.
For harder forgery cases, where less of the block is controlled by the attacker, DeepMind's algorithm is theoretically 1,600 times more efficient than previous methods against 1024-bit keys.
Results and Metrics
- The first forgery required 391 CPU core-years, compared to 1,380 in the original study, a 3.5-fold reduction.
- Factoring a single 1024-bit key is still estimated at 500,000 to 1 million core-years. The test key wasn't factored.
- Each additional 1024-bit key becomes roughly 30 times cheaper to factor under the new algorithm, though this remains theoretical.
These shifts in attacker economics should be noted in your risk register.
Applying the Findings
The research team didn't specify regrets, but you can apply these findings to your program. Many organizations don't revisit key lengths after initial documentation. If your cryptographic inventory hasn't been updated since system authorization, you're relying on outdated assumptions.
Examine your assessment evidence. A control narrative stating "RSA is used for signing" without specifying key length, padding scheme, and hashing location can't address the questions raised by this research.
Takeaways for Your Team
1. Inventory by Key Length and Padding Scheme. Identify every RSA-1024 key, certificate, and signing function. Under NIST SP 800-53 Rev 5, SC-12 and SC-13 cover this. Review CM-8 to ensure your inventory includes cryptographic assets.
2. Examine HSM Signing Interfaces. The padding finding implicates PKCS#1 v1.5 via PKCS#11 on devices like HSMs. Determine which devices hash messages internally, as the attack doesn't work against them. Assess who can influence signed content, as risk scales with block control.
3. Validate Adequacy, Not Just Validation. A FIPS 140-2 validated module indicates testing, not that a legacy key length meets your risk tolerance. Check current NIST key-length guidance for your use case and document the results.
4. Respond Based on Risk. For genuine 1024-bit exposure, plan to migrate to 2048-bit or larger keys. If immediate migration isn't possible, document compensating controls and a dated Risk Response decision. For systems handling Controlled Unclassified Information under NIST SP 800-171, weak legacy keys are a potential assessment finding.
5. Build a Review Trigger. Don't treat cryptographic hardness as fixed. Add a recurring review of cryptographic assumptions to your monitoring plan, tied to published cryptanalysis, not just calendar dates.
6. Communicate Precisely to Leadership. Modern 2048-bit and larger deployments aren't affected, and the factoring improvement is unimplemented. Clearly state this in briefings, and identify where your inventory shows exposure. Precision maintains your credibility when real findings emerge.
