Why Quantum Cryptanalysis is Bollocks

Why Quantum Cryptanalysis is Bollocks

Speakers: Peter Gutmann, Researcher, Department of Computer Science, University of Auckland

Conference: Kawaiicon

YouTube: https://www.youtube.com/watch?v=xa4Ok7WNFHY

Overview

In his compelling Kawaiicon talk, "Why Quantum Cryptanalysis is Bollocks," Peter Gutmann, a researcher from the Department of Computer Science at the University of Auckland, delivers a scathing critique of the hype surrounding quantum cryptanalysis. Gutmann argues that the perceived threat from quantum computers to modern cryptography is vastly overblown, a distraction from the pervasive and unaddressed security vulnerabilities that plague current systems. He posits that the entire field, as it currently stands, is less about genuine scientific progress and more about headline-grabbing "stunt cryptography" and academic/commercial incentives.

Gutmann likens the current fascination with quantum cryptanalysis to historical white elephants like the Gustaf gun – an immensely expensive, resource-intensive, and ultimately ineffective project that drew vital resources away from more practical and impactful endeavors. He asserts that while the security industry obsesses over hypothetical quantum threats, fundamental problems like those outlined in the OWASP Top 10 remain largely unsolved, representing the true and present danger to digital security. This talk is a vital call to refocus attention and resources on tangible, empirically validated security challenges rather than chasing what he dismisses as "magical thinking."

Background

▶ Watch: Gustaf Supergun: Misallocating resources to cool but useless attacks (0:00)

Gutmann opens his talk with a historical analogy: the Gustaf gun. Proposed in 1935 to attack the Maginot Line, this 1,300-ton behemoth, capable of firing a 5-ton shell 50 kilometers, was a marvel of engineering and a headline-grabbing attack of its era. However, it was a practical disaster, requiring immense logistical support (a 1.5 km train, 2,000-4,500 men, twin special railway tracks, two flak battalions), fired only around 50 shells across five days, and often missed its targets by hundreds of meters. Military experts had predicted its failure, yet it was built anyway, drawing critical resources from the actual war effort. Gutmann contends that today's obsession with quantum cryptanalysis mirrors this historical folly.

He contrasts this with the persistent, mundane, yet highly effective threats identified by organizations like OWASP. The OWASP Top 10 vulnerabilities have remained remarkably constant for the past 10-20 years, shifting names and classifications but representing the same core attack vectors. Similarly, API security challenges show remarkable stability. These are the threats that attackers actually use, offering a "100% chance of recovering everything," compared to "stunt cryptography" (e.g., Roham, Poodle) which offers "a 1,000th of a percent chance of measuring recovering two bits of plaintext" and is rarely, if ever, used in real-world compromises. Gutmann highlights the alarming statistic that single web browsers can accumulate more CVEs than entire operating systems, underscoring a pervasive failure to address known, fundamental security weaknesses.

The speaker then delves into the concept of key size numerology. While symmetric cryptography (e.g., AES) offers a clear doubling of work factor for each added bit, asymmetric cryptography (e.g., RSA) relies on complex, often arbitrary mappings from symmetric key strengths to vastly larger asymmetric key sizes. Gutmann argues that practical computational limits are around 2^110 operations, making AES-128, AES-192, and AES-256 effectively equivalent in their unbreakability by any imaginable human computation. Yet, NIST guidelines recommend disproportionately large asymmetric keys (e.g., 15,000-bit RSA for AES-256 equivalence), a practice he labels "numerology" that treats out-of-reach numbers as distinct.

The historical "progress" in quantum factorization further illustrates Gutmann's point. The first quantum factorization, achieved in 2001, factored the number 15 (3 5). The next record, in 2012, factored 21 (3 7). A subsequent attempt in 2019 to factor 35 failed. Since then, there have been no new factorization records using Shor's algorithm that haven't been based on "stunt factorizations" – numbers carefully chosen to facilitate the experiment, rather than cryptographically relevant unknowns.

Key Findings

▶ Watch: Quantum factorization 'records': Factoring 15 and 21 (6:10)

Gutmann's central finding is that what are often presented as "quantum computers" performing cryptanalysis are, in reality, highly specialized physics experiments designed to "demonstrate a known fact." Unlike a computer that takes arbitrary input, processes it, and produces output, these experiments are meticulously crafted to yield a pre-determined result. This distinction is critical: rather than discovering the factors of an unknown number, these experiments are configured to "demonstrate that 3 * 5 = 15," using numbers whose factors are known in advance.

These "achievements" are branded as stunt factorizations or "slight-of-hand numbers." The standard technique involves manufacturing a small, easily factorable number, then adding digits to it in a way that allows it to be factored using the same method, thus claiming a "new record." Gutmann cites a paper humorously titled "Replication of quantum factorization records with an 8bit at home computer an abacus and a dog," which illustrates how even these supposed quantum breakthroughs can be replicated with elementary classical methods. The underlying trick is often referred to as the compiled Shor's algorithm, a euphemism for knowing the factors beforehand and working backward to build an experiment that produces them. This fundamentally undermines the claim of performing cryptanalysis, as true cryptanalysis requires breaking an unknown key.

Gutmann also highlights the recurring pattern of "quantum supremacy" announcements, where a quantum device is claimed to perform a task beyond classical computers, only for a classical desktop PC to later replicate or outperform it. He extrapolates from the two legitimate data points (factoring 15 and 21) that, at current rates, a physics experiment might factor a 1000-bit number (already achievable by a supercomputer today) by 4000 AD, and this assumes an optimistic linear scaling for which there is no empirical evidence.

Finally, Gutmann introduces the "Heisenber shooting a credul effect" (or "Heisen-berry Credul Effect"), a phenomenon where the mere mention of "quantum" causes otherwise sensible people to suffer from impaired reasoning. He illustrates this with the absurd example of a Finnish firm signing a $300 million contract to purchase Helium-3 from the moon, a product of "green cheese mines," simply because "you just put quantum in it and people will just give you money for anything." This irrationality, he argues, fuels the hype and misdirection of resources.

Technical Deep Dive

▶ Watch: 'Working quantum factorization machine goes here': Missing practical details (12:10)

The core of Gutmann's technical argument lies in exposing the deceptive nature of reported quantum factorization records. He systematically dismantles the methodology behind these "stunt factorizations":

1. Factoring 15 and 21: The initial quantum breakthroughs of factoring 15 (3 5) in 2001 and 21 (3 7) in 2012 were not genuine cryptanalysis. As Gutmann explains, these numbers were chosen precisely because their factors were known. Researchers then used the compiled Shor's algorithm, which involves constructing the quantum experiment in reverse, starting from the known factors to arrive at the desired result. This is akin to a magician knowing the card in advance and then performing a trick to "reveal" it – it's a demonstration, not a discovery. The "abacus and a dog" paper further emphasizes the triviality of these numbers, implying that their "factoring" by quantum means is more a testament to experimental setup than computational power.

1. D-Wave's 2000-bit RSA claim: Gutmann points to the highly contested claims by D-Wave, a company marketing "quantum annealing" devices. D-Wave advertised factoring a "2000-bit RSA number." However, the method involved choosing a number that differed by only a small number of bits from a perfect square. Such numbers can be factored by taking the square root and then guessing a few bits – a task easily achievable with an abacus. Real RSA keys, by design, must differ by at least 100 bits from a perfect square to ensure security, making D-Wave's "achievement" entirely irrelevant to actual RSA cryptanalysis. It's an example of manufacturing a synthetic problem specifically solvable by a particular method, rather than tackling a real-world cryptographic challenge.

1. Error-Ignoring Techniques: One of the most egregious "cheats" Gutmann describes involves running the quantum experiment repeatedly, ignoring any errors, and continuing until, by random chance, the pre-known desired result is obtained. The quote from a researcher, "to my knowledge no one's cheated at factoring in this way before," is presented ironically, given the history of "shenanigans pulled by past factoring experiments." This technique further underscores that these are not robust computational processes but fragile physics experiments being coaxed to produce a specific, anticipated outcome.

1. The Discrete Logarithm Problem (DLP): Crucially, Gutmann highlights that almost all modern encryption protocols used for secure communication – TLS, SSH, IPsec, WireGuard, Signal – do not rely on RSA's factorization problem for key exchange. Instead, they depend on the Discrete Logarithm Problem (DLP) or its elliptic curve variant (ECDLP). No physics experiment has ever successfully addressed DLP, primarily because it's significantly "harder to cheat on this" than with integer factorization. This means that even if quantum computers could genuinely factor RSA numbers, they would be attacking the "completely wrong thing" for breaking the vast majority of today's encrypted traffic.

1. Scaling and Production Line Fallacy: The notion that quantum computers could quickly "pop out keys like a production line" is a dangerous misconception. Gutmann stresses that each reported quantum factorization requires a custom-designed and assembled physics experiment. He draws a parallel to the ENIAC from 1945, which required a team of programmers two weeks to set up its plugboards for a single calculation. The lack of data on how long it takes to set up these modern quantum experiments suggests a non-trivial amount of effort, making the idea of attacking "7 trillion symmetric keys a year" (the estimated web traffic alone) utterly impractical.

1. Twinkle/Twirl: Gutmann briefly mentions AD Shamir's (of RSA fame) proposed physics-based factoring device, Twinkle (later expanded to Twirl). This device, which used LEDs and thus leveraged quantum effects, was largely ignored by the community simply because Shamir "forgot to use the word quantum in it." This serves as a potent anecdote for the "Heisenber shooting a credul effect," illustrating how the absence of the buzzword can overshadow genuine, albeit classical, physics-based computational ideas.

In essence, Gutmann argues that if one excludes these "slight-of-hand" factorizations, the empirical data for quantum cryptanalysis simplifies to "literally no data" – a result identical to the evidence for faster-than-light travel or time travel.

Demo / Proof of Concept

▶ Watch: Debunking the 'Store Now Decrypt Later' (SNDL) threat (16:00)

While Peter Gutmann's talk does not feature a traditional software or hardware demonstration, it conceptually provides "proofs" for his arguments. The core "demo" lies in the debunking of supposed quantum achievements.

For instance, the reference to the paper "Replication of quantum factorization records with an 8bit at home computer an abacus and a dog" serves as a conceptual proof of concept. This paper implicitly "demonstrates" that the numbers factored by early quantum experiments (like 15 and 21) are so trivial that they can be easily handled by rudimentary classical means, thereby undermining the "quantum supremacy" claims.

Furthermore, Gutmann's playful inclusion of his own dog, Scribble, at the end of the talk, who "barks five times" to "factor" the number 15, acts as a humorous yet poignant demonstration. He asserts that Scribble, by correctly identifying one of the factors of 15, is "more powerful and more capable than the world's most powerful factorization experiment" in a practical sense, given the current state of quantum cryptanalysis. This serves to visually and humorously underscore the speaker's main point: the "achievements" of quantum factorization experiments are so limited and manipulated that they can be conceptually, if not literally, outdone by simple, everyday means.

Defensive Implications

▶ Watch: Quantum cryptanalysis: The 'string theory of security' (29:30)

Gutmann's talk carries profound defensive implications, primarily centered on the critical misallocation of resources and attention within the security industry. He argues that the hyper-focus on a largely theoretical quantum threat diverts hundreds of millions of dollars and invaluable expertise away from addressing the pervasive, empirically validated security problems that attackers exploit daily. Instead of investing in SAS tools, scanners, or fundamental fixes for the OWASP Top 10, resources are poured into physics experiments with no practical cryptographic output.

A significant portion of Gutmann's defensive argument debunks the "Store Now, Decrypt Later" (SNDL) boogeyman. This concept suggests that encrypted data stored today could be decrypted by future quantum computers. Gutmann dismantles this by highlighting several flaws:

1. Per-Key Experimentation: Each new key requires a fresh, custom-designed physics experiment. With 7 trillion symmetric keys generated annually for web traffic alone (2017 figures), the idea of setting up a unique, multi-month experiment for each key is logistically impossible.
2. Astronomical Costs: A German government study estimated that recovering a single 448-bit key would take 100 days and €4 million in electricity using a hypothetical quantum device. In that 100 days, another two trillion new keys would have been generated, creating an insurmountable backlog.
3. Attacking the Wrong Problem: The SNDL argument typically assumes quantum computers will break RSA. However, as Gutmann repeatedly states, most modern encrypted traffic, including TLS, SSH, IPsec, WireGuard, and Signal, relies on the Discrete Logarithm Problem (DLP) for key exchange, not RSA factorization. Quantum cryptanalysis has made no progress on DLP because it's "actually quite hard to cheat on this."
4. Data Irrelevance: Most encrypted data from today will be irrelevant in 30 years. Spending millions of euros to decrypt an old online chat is irrational for all but a tiny fraction of state secrets.

Furthermore, Gutmann raises serious concerns about the stability and maturity of Post-Quantum Cryptography (PQC) candidates. He provides alarming statistics from the NIST standardization process:

• Of the initial Round 1 candidates, 48% were broken.
• Of those that survived Round 1, another 25% were subsequently broken.
• Of the candidates that made it to Round 3, an additional 36% were broken.

This demonstrates extreme instability, suggesting that current PQC proposals are "really, really shaky stuff" with very little operational experience. The historical pattern of public key cryptosystems indicates that many more problems are likely to be discovered. Gutmann notes the inherent paradox: governments often advocate for "pure post-quantum" (all eggs in one basket), while others prefer "hybrid" approaches, implicitly acknowledging their distrust in the standalone security of PQC.

Finally, Gutmann emphasizes that complexity is the enemy of security. The constant churn in cryptographic standards, driven by academic incentives, standards groups, and vendors ("churn allows people to make money"), leads to an ever-increasing attack surface. He cites TLS alone having 60 RFCs and 32 drafts, totaling nearly 2,000 pages of documentation. This immense complexity inevitably hides vulnerabilities that no one has time to properly assess. In contrast, Gutmann praises highly secure embedded systems, often designed by non-security experts, which feature barebones TCP stacks, a single TLS cipher suite, and minimal attack surface, making them "really, really hard to break." The "quantum hype" perpetuates this cycle of complexity and churn, actively undermining robust security.

Key Takeaways

• Quantum cryptanalysis is scientifically dubious: Current "quantum factorization" records are based on "stunt factorizations" of numbers whose factors are known in advance, using techniques like the "compiled Shor's algorithm" to cheat the experimental setup.
• No legitimate real-world cryptographic breaks: There has never been a single legitimate factorization of a cryptographically relevant number by a quantum experiment, nor has any progress been made on the Discrete Logarithm Problem (DLP), which underpins most modern encryption.
• Resource misallocation is a critical problem: The immense funding and expertise directed towards hypothetical quantum threats divert resources from addressing pervasive, empirically proven security vulnerabilities like those in the OWASP Top 10.
• "Store Now, Decrypt Later" (SNDL) is a fallacy: The SNDL threat is built on unrealistic assumptions about quantum computer capabilities, the cost of breaking individual keys, and the relevance of data over long periods, while ignoring the sheer volume of keys generated daily and the fact that quantum experiments primarily target the wrong problem (RSA factorization, not DLP).
• Post-Quantum Cryptography (PQC) is highly unstable: NIST's PQC candidates have shown significant instability, with a large percentage being broken across various rounds, indicating a lack of maturity and operational experience, making them a risky foundation for future security.
• The "quantum hype" is an incentive-driven cycle: The focus on quantum cryptanalysis is sustained by academic, commercial, and media incentives that prioritize novelty and "churn" over addressing fundamental, persistent security challenges, thereby perpetuating complexity which is the "enemy of security."

About the Speaker(s)

Peter Gutmann is a distinguished researcher from the Department of Computer Science at the University of Auckland. He is known for his sharp critical analysis and outspoken views on various aspects of computer security and cryptography. His work often challenges conventional wisdom and highlights practical realities over theoretical or hyped advancements, as demonstrated by his incisive critique of quantum cryptanalysis in this talk.