1. Basic Information
- Article Title: Modular Roots from a Restricted Oracle: Faster Affine Roots and a 1024-bit Computation
- Publisher: Google DeepMind
- Publication Date: 2026-11-05
- Collection Date: 2026-11-10T07:46:16+09:00
- Original Source: Google DeepMind
- Related Sources: Batch NFS working paper, SecurityWeek
- Severity: High
- Severity Rationale: This demonstration shows AI agents accelerating the implementation, execution, and debugging of large-scale cryptographic computations in a short time. However, the target is obsolete RSA-1024 and a specific oracle model, not a direct compromise of RSA-2048 or higher.
2. Executive Summary
AI agents and cryptographic researchers reproduced existing RSA-1024 signature forgery computations using 391 CPU core-years, achieving a 3.5x efficiency improvement over the previous 1,380 CPU core-years (comparing CPU time directly, excluding GPU processing and preliminary runs). The factorization factory is a theoretical evaluation and does not break RSA-2048 or higher.
3. Research Objectives
- Determine whether it is possible to reduce the cost of obtaining RSA roots from a fixed-format signing oracle and the amortized cost of batch-factoring multiple RSA keys.
- Assess how far AI agents can advance large-scale cryptographic computations.
4. Proposed Methodology and Inputs
Proposed Methodology
- Analyze the threshold for reducing an affine oracle to an unrestricted oracle, and improve efficiency using early aborts and factor-base extensions.
- Reimplement the existing RSA-1024 instance under the same conditions, with AI agents executing the distributed computation.
Inputs
- 1024-bit RSA modulus, e=65537, PKCS#1 v1.5 / PKCS#11 model. The demonstration calculation requires approximately 4 billion signing queries against an unrestricted oracle.
- Same modulus, polynomial, and factor-base bounds as prior research.
5. Experiment and Workflow
- A supervisor agent designs and audits the work, while an executor agent handles coding, job execution, and troubleshooting.
- Humans provide approximately 20 short messages, mainly approvals.
6. Results
- The complete computation took 391 CPU core-years (aggregating CPU time, excluding GPU linear algebra processing, trial runs, and preliminary runs), which is a 3.5x reduction compared to prior research. According to the paper, including GPU processing at CPU costs equivalent to prior research yields about a 3.4x reduction, and including preliminary runs yields about a 3.3x reduction.
- The AI agents completed the task in 3.2 days from the start of the full-scale job.
- The 32-byte hash improvement was evaluated theoretically at approximately 1,600x. For batch factoring, after performing precomputations equivalent to factoring a single integer of the same size using GNFS, it was theoretically estimated that the cost per additional key would be about 1/30th compared to MNFS (not implemented). The improvement in batch mode without precomputation is up to approximately 1.75x based on leading-order evaluation for 1024-bit against the previously best MNFS or single-polynomial batch NFS, which is a separate result.
7. Success Conditions and Scope
- The attack requires 1024-bit RSA and the necessary oracle queries. For the reduction from a fixed-format oracle to an unrestricted oracle, the caller must control roughly half of the block or more, and each original query requires two fixed-format oracle queries. This roughly half-block control requirement does not apply to the separate theoretical evaluation involving 32-byte inputs.
- The complete attack does not cover in-device hashing, RSA-2048 or higher, or configurations with sufficient restrictions on signing queries.
8. Facts, Inferences, and Hypotheses
Facts
- Using the same RSA-1024 instance and algorithm conditions, the computation took 391 CPU core-years, representing a 3.5x reduction from prior research's 1,380 CPU core-years. The 3.5x figure compares CPU times directly, excluding GPU processing and preliminary runs.
- The 3.5x improvement is due to implementation and execution enhancements rather than algorithmic improvements.
- Two AI agents wrote approximately 33,500 lines of code, ran 336 experiments, and performed debugging using about 20 human messages, completing the task in 3.2 days using up to 300,000 CPU cores and 16 GPUs.
- The signature attack does not factor the RSA modulus or recover the private key. It requires approximately 4 billion signing queries in advance, and devices that hash messages internally are outside the model. The approximately 4 billion queries apply to the unrestricted-oracle demonstration; applying the fixed-format reduction doubles the query count.
- The approximately 1,600x improvement for 32-byte hashes is a theoretical estimate. For 1024-bit targets, the approximately 30x improvement per additional key in the factorization factory is a leading-order theoretical estimate relative to MNFS, assuming precomputation equivalent to one GNFS run on an integer of the same size; the method has not been implemented. In batch mode without precomputation, the leading-order estimate for 1024-bit integers gives an improvement of up to approximately 1.75x over the best previous method, MNFS or single-polynomial batch NFS.
- The paper explicitly states that this does not threaten deployed systems using RSA-2048 or higher.
Inferences
- Risk assessments for legacy RSA-1024 and interfaces that give callers broad control over the data being signed should consider oracle access and query volume as well as key size.
Hypotheses
- There are no additional hypotheses.
9. Practical Implications
- RSA-1024 combined with broad caller-controlled signing may not provide a sufficient margin of security with padding alone.
- AI can lower the cost of known attacks through code optimization, distributed execution, and debugging.
10. Limitations
- This involves a specific RSA-1024 instance and does not constitute a break of RSA-2048.
- The approximately 1,600x and 30x figures include theoretical evaluations, and the batch method is not implemented. The approximately 30x figure is an estimate per additional key after GNFS-equivalent precomputation and is not an execution time prediction.
- Independent replication and peer review of the working paper are required.
11. Application Guidance
- Retire RSA-1024 and migrate to RSA-2048 or higher.
- Restrict raw signing and long caller-controlled data, and use in-device hashing.
- Monitor signing query rates, callers, and key usage.
12. Required Evidence
- Key size, mechanism, hash position, caller-controlled byte count, query count, source, rate limits, and rotation history.
- Code, instances, hardware, core-hours, human intervention, and failed runs.
13. MITRE ATT&CK Mapping
As this is cryptographic research in a lab environment rather than a real-world attack campaign, no MITRE ATT&CK techniques are assigned.
14. Uncertainties and Further Investigation
- Peer review status, reproducibility across different hardware and agent configurations, and the implementation cost of the theoretical algorithm remain undetermined.
15. Impact on SOCs and Organizations
This result does not indicate that currently deployed RSA-2048 or higher keys are immediately at risk. It serves as a rationale to inventory legacy RSA-1024, raw or long-data signing operations, and high-volume signing queries, and to advance key rotation and rate limiting.
16. Summary by Target Audience
- For SOCs: Monitor HSMs and signing services for high query volumes, caller-controlled data, and RSA-1024 key usage.
- For Administrators: Retire RSA-1024 and verify the use of RSA-2048 or higher, in-device hashing, query limits, and separation of key usage.
- For End Users: This research does not show that widely used modern cryptography is now broken. Review your key update policies.
Top comments (0)