Google DeepMind, in collaboration with cryptographers from UC San Diego and Inria, has introduced two innovative methods to decrease the cost associated with attacking 1024-bit RSA encryption systems. These findings, though significant, primarily affect older RSA-1024 systems, as modern encryption protocols typically employ 2048-bit or larger keys, ensuring their continued security, according to Pushmeet Kohli, VP at Google DeepMind and chief scientist at Google Cloud.
Advancements in Digital Signature Security
The research highlights a notable discovery concerning digital signatures and the padding used to standardize message sizes. Padding has traditionally been seen as a deterrent to forgery, but its effectiveness against attackers who can dictate signature content was uncertain. DeepMind revealed that padding’s protective value diminishes when an attacker gains control over half or more of the signed block, as explained by Kohli.
This vulnerability is particularly relevant to the PKCS#1 v1.5 format, prevalent in cryptographic devices like hardware security modules (HSMs). In controlled experiments, AI agents replicated a prior academic forgery attack on a 1024-bit key, significantly reducing CPU time required to forge a signature from 1,380 core-years to just 391. The operation was completed in under four days with minimal human intervention.
Efficiency in RSA Key Factoring
DeepMind’s second major finding pertains to the factoring of numerous RSA keys of identical size. The AI developed an algorithm that makes the factoring of each additional 1024-bit key approximately 30 times more cost-effective than previous methods. However, this approach relies on a significant initial computation cost, akin to factoring a single key, and remains theoretical as it hasn’t been practically applied yet.
Despite these advancements, it’s important to note that the signature attack does not compromise the private key. It necessitates around 4 billion pre-computed signing queries and is ineffective against devices that internally hash messages.
Implications for Future Cryptographic Security
These breakthroughs underscore the evolving landscape of AI-assisted mathematics and computation in cryptography. As Kohli emphasized, the assumption of cryptographic hardness cannot remain static. Employing AI to rigorously test and challenge these assumptions is crucial to maintaining the integrity and security of modern encryption systems.
The research serves as a reminder of the need for continuous evaluation and adaptation in the field of digital security, ensuring that encryption methods remain robust against emerging threats.
