Mythos attack on 3rd-round PQC algorithm candidate puts it out of commission

AI-GENERATED CRYPTANALYSIS HAWK withstood years of testing that had yet to uncover a fatal weakness found through Mythos. A quantum-resistant cryptography algorithm that was under consideration as an official US standard has been taken out of the running after an Anthropic security model helped find a flaw that rendered it broken. The algorithm is known as HAWK. It’s a digital signature scheme designed to withstand future attacks from quantum computers. HAWK had survived two rounds of testing by NIST (the National Institute of Standards and Technology) for evaluating the security of PQC (post-quantum cryptographic) algorithms through widespread testing. HAWK was in a third round of testing designed to catch precisely the kinds of flaws Mythos helped uncover. Following Anthropic’s Monday announcement of the results, the developer of HAWK said Tuesday he was withdrawing it. Even before the development, Anthropic was hailing the results of the two cryptographic problems it threw at its Mythos AI security model. The model found weaknesses in the mathematical problems underpinning HAWK and, separately, the widely used AES cipher. Despite the withdrawing of HAWK, it’s hard to know how much of the company’s reporting is marketing hype, but the findings are still worth paying attention to because they could signal important advances in breaking cryptography that’s crucial to privacy and security. Before digging into the results, a few caveats. First, the outcomes are incremental. They don’t break any of the cryptosystems anyone relies on today. Instead, they reveal methods for moderately reducing the work that would be required to defeat the systems. Second, the cryptosystems tested were weakened versions of the ones defined in their formal specifications. Such “challenge instances” are provided by the specification authors for use in adversarial peer review. It’s standard to use the weakened versions in testing, but the real ones are considerably more robust in production settings. Third, even with the improvement, the underlying “primitives”—meaning the underlying mathematical problems that form the basic building blocks of cryptosystems—remain safe, at least for now. Lastly, both of the attacks use methods that would likely be infeasible outside of testing environments. HAWK is dead Anthropic said its Mythos model—which currently remains available only to a select group of trusted users—was able to advance attacks against two cryptosystems. The first system is HAWK, a digital signature scheme designed to withstand future attacks from quantum computers. With about 60 hours of work and about $100,000 of compute cost, an Anthropic researcher with no expertise in cryptography prompted Mythos to improve the best-known existing attack on the algorithm that effectively cut its key strength in half. The math HAWK’s security relies on is the hardness of the Lattice Isomorphism Problem, which, unlike today’s most used digital signature schemes, is believed to be safe from quantum computing attacks. The best-known classical computing attack to solve this problem works by finding what are known as automorphism symmetries. Mythos outputted a previously unknown method for finding such symmetries by definition broke the algorithm. The weakness can be mitigated by doubling the key size, but the added computation makes HAWK less desirable than available PQC signing algorithms. In academics cryptographic algorithms are considered broken when weaknesses allow an adversary to derive a key faster than is possible using a brute-force attack. Matthew Green, a Johns Hopkins professor and expert in cryptography, said the impressive thing about the discovery was its reliance on several existing methods that no one previously thought to put together. “What’s particularly concerning (and so especially ripe for AI) is that the attack does not invent fundamentally new mathematics,” Green wrote. “It simply extends a bunch of tools that were lying around and well-known, and gets a good result.” Anthropic elaborated: To find the attack, Claude Mythos Preview worked semi-autonomously in an agentic harness, with occasional human guidance and nontechnical direction. Mythos found the attack after an extensive literature review to understand the state of the art, and substantial mathematical reasoning and computational experiments. After finding the attack, Mythos implemented an end-to-end verification pipeline to convince itself—and the human operator—of the attack’s correctness. To find the improved method, Mythos deployed two separate agents that worked largely independently. One initially rejected the method as unworkable. The second found a way to make it work. The agents eventually worked in unison until they produced an agreement that the improved attack was effective. (As with the description of the attack against AES later in this article, the HAWK attack methodology has been simplified. For the full details, see the Anthropic post or two longer papers on the HAWK and AES attacks, respectively.) Sophie Schmieg, an expert in PQC at Google, said HAWK was already suspected to have weaknesses that would eventually be found. Still, the method for halving the key strength found through Mythos made the candidate algorithm less competitive than existing PQC digital signature schemes such as ML-DSA and FN-DSA. “Basically with this paper, HAWK is dead,” she wrote. Less drama, but still kind of neat The attack against AES produced less dramatic results. It’s based on an improvement found through Mythos for performing a “meet-in-the-middle” attack, which is used to derive a key under a chosen plaintext threat model, the best-known existing attack against AES. The technique inputs large numbers of known plaintext into the crypto system and analyzes the encrypted output for clues that, with enough inputs, eventually reveal an unknown key. Previously, the best-known meet-in-the-middle attack against AES required roughly 2105 plaintext inputs, a number large enough to make the method infeasible. Mythos helped to find a new meet-in-the-middle technique that relies on a Möbius Bridge, a more sophisticated fingerprinting algorithm used in meet-in-the-middle attacks. Using it, Green said, the code Mythos produced was able to reduce the number of required inputs to 289. Anthropic said that savings can reduce the time required for such attacks by 200- to 800-fold. The ability to produce that many inputs makes the attack beyond reach outside of the laboratory. Further, the actual speed-up is unknown, since the weakened AES algorithm tested used only 7 rounds. Specification-compliant AES, Green said, uses 10, 12, or 14 rounds, depending on key size. Anthropic is careful to explicitly spell out most of these caveats. The Monday blog post goes on to argue, however, that the results are nonetheless meaningful and could ultimately fundamentally disrupt the process of cryptanalysis, or the adversarial testing of cryptosystems. “The cybersecurity community is now grappling with the fact that language models are able to discover so many bugs that the standard human processes (like vulnerability triage, verification, and remediation) struggle to keep up,” Anthropic wrote. “We predict that the same will soon be true in academic cryptography research. As language models increasingly produce novel research outputs autonomously, human researchers may become bottlenecked on studying and validating these results for technical validity, novelty, and utility.” Not mentioned in Anthropic’s report is whether its researchers used Mythos to attack more tested cryptosystems, such as elliptic curve cryptography and RSA. Attack improvements against these systems would be more impressive. By achieving the most impressive result against an algorithm still in its infancy, it’s not clear how much of an advantage Mythos truly provided. There’s no way of knowing if researchers using conventional cryptanalysis techniques were already close to discovering the same attack. Ultimately, the lesson from the research is simple. AI-assisted cryptanalysis remains untested, and providers of these platforms have a vested interest in exaggerating their benefits. At the same time, there’s growing evidence that LLMs may provide significant advantages in finding cryptographic weaknesses. It would be a mistake to conclude that LLMs won’t one day play an important role in the race between securing and compromising our most vital assets. The headline and body of this story have been updated to reflect the withdrawing of HAWK. Dan Goodin is Senior Security Editor at Ars Technica, where he oversees coverage of malware, computer espionage, botnets, hardware hacking, encryption, and passwords. In his spare time, he enjoys gardening, cooking, and following the independent music scene. Dan is based in San Francisco. Follow him at here on Mastodon and here on Bluesky. Contact him on Signal at DanArs.82. 15 Comments