quantum computing

Hack Post-Quantum Cryptography Now So That Bad Actors Don’t Do It Later

By Edward Parker, Michael Vermeer
Thursday, July 28, 2022, 11:33 AM

In February, a researcher sent a shock wave through the cryptography community by claiming that an algorithm that might become a cornerstone of the next generation of internet encryption can be cracked mathematically using a single laptop. This finding may have averted a massive cybersecurity vulnerability. But it also raises concerns that new encryption methods for securing internet traffic contain other flaws that have not yet been detected. One way to build trust in these new encryption methods—and to help catch any other weaknesses before they are deployed—would be to run a public contest to incentivize more people to look for weaknesses in these new algorithms.

 The new encryption algorithm that was just cracked was designed to be secure against quantum computers. A large-scale quantum computer may eventually be able to quickly break the encryption used to secure today’s internet traffic. If internet users don’t take any countermeasures, then anyone in possession of such a computer might be able to read all secure online communications—such as email, financial transactions, medical records, and trade secrets—with potentially catastrophic impacts for cybersecurity that the U.S. National Security Agency has described as “devastating to … our nation.”

 One defense against this future threat is post-quantum cryptography or PQC—a set of new cryptography algorithms that are expected to resist attacks from quantum computers. Since 2015, the U.S. National Institute for Standards and Technology (NIST) has been evaluating algorithms to design a new standard for this type of cryptography, which will likely be adopted eventually by communication systems worldwide. Although quantum computers powerful enough to threaten encryption are unlikely to arrive before 2030, upgrading to PQC will take years and cost billions of dollars. The U.S. government considers the swift and comprehensive adoption of PQC across its own communication systems to be an important national security imperative: Over the past two months, the White House has issued a National Security Memorandum directing all federal agencies to begin preparing for the transition. And related bills have passed the House of Representatives and been introduced in the Senate with bipartisan support.

If a deployed PQC algorithm contained a security flaw, an enormous amount of sensitive information could be left vulnerable. And there could be a chaotic and costly scramble to fix the flaw throughout the communication infrastructure. The recent claim to have found just such a flaw in one of the PQC algorithms that NIST was considering shows that this risk is not far-fetched.

 NIST and others in the cryptography community are carefully analyzing several PQC algorithms to try to catch any potential vulnerabilities. But it’s almost impossible to mathematically prove the security of most cryptography algorithms. In practice, the strongest evidence for an algorithm’s security is simply that many experts have tried and failed to break it. The more people try to attack the new PQC algorithms and fail, the more likely it is that they are secure.

 One possible option for further crowdsourcing the analysis of NIST’s final candidate PQC algorithms would be a contest in which the general public is invited to try to break them. As hundreds of companies that offer public bug bounties have discovered, crowdsourced penetration testing can be a very useful tool for improving cybersecurity. The U.S. Departments of Homeland Security and Defense have also recently experimented with offering bug bounties to anyone who discovers cyber vulnerabilities in the departments’ systems. A public contest certainly can’t replace a mathematical security analysis, but it could be a useful complement that provides additional evidence of the algorithms’ security.

 Here’s one possible option for what such a contest might look like: NIST could use its recently selected candidate PQC algorithms to encrypt a nonsensitive document and then publicly release the encrypted ciphertext (and the algorithms used to encrypt it) along with a large bounty for its decryption. The first person—anywhere in the world—to successfully decrypt the document and explain how they did so would receive the bounty. If anyone succeeds, NIST would know that it needs to refine its algorithms before releasing the final standard.

One of the main advantages of a high-profile contest is that it would enable the examination of the candidate algorithms from fresh perspectives. NIST’s standardization process has been quite transparent. But PQC is still an esoteric and highly technical topic, and relatively few people have carefully studied NIST’s chosen algorithms. A public contest might attract more cryptographers and others with a wider variety of backgrounds, including enthusiasts, white-hat hackers, and anyone who would appreciate the opportunity to publicly “pwn the government” by defeating its proposed cryptography systems (in addition to winning a substantial financial prize).

 There are several potential objections to this proposal. The first is that previous cryptography cracking contests have often failed to be very effective. But cryptography cash bounties have also been successfully offered. As long as this contest is carefully designed, it can avoid the common pitfalls of previous contests. For example, the contest would need to offer a large enough prize to incentivize significant effort, the PQC algorithm(s) used would need to be clearly specified, and there would need to be few constraints on which tools the participants are allowed to use.

A second objection is that such a contest could backfire. If it incentivizes participants to discover a vulnerability, they could potentially decide to exploit or sell the vulnerability rather than disclosing it to the contest sponsor and claiming the bounty. This outcome is conceivable, but unlikely. Most people who would be incentivized on the margin by this contest would likely be hobbyists or academics rather than professional black-hat hackers, and they are unlikely to be either willing or able to exploit or sell a serious vulnerability. If a financially motivated person does discover a vulnerability, then a cash bounty would create an incentive for them to disclose it to the U.S. government instead of exploiting or selling it. Also, if multiple people discover the same vulnerability, only a single person would need to disclose it in order for the contest to succeed—and it’s unlikely that every single person who discovers the vulnerability would choose to misuse it. More generally, the broad cryptography principle known as Shannon’s maxim—“the enemy knows the system”—favors rapidly uncovering and fixing any fundamental weaknesses in cryptography systems, rather than counting on those vulnerabilities to remain undiscovered by adversaries.

A third objection is that organizing such a contest would be a waste of effort, because participants would be unlikely to uncover any vulnerabilities that the professional mathematicians at NIST have missed after years of work. It’s true that the bounty would (fortunately) probably never need to be paid out. But the contest could be valuable whether or not it ever awards a prize. Its mere existence might reassure the business community—which is more familiar with the notion of bug bounties than with the kind of formal cryptographic analysis that NIST is carrying out—that these new PQC algorithms are secure. The authors previously recommended that the government look for innovative ways to spur the rapid adoption of PQC. Assuring organizations of the security of the PQC standard is one way to do so. Moreover, a contest would raise public awareness of PQC and would encourage participants to dig into the mathematical details. An increase in public familiarity with PQC (at all levels of technical detail) could generate broad cybersecurity benefits for years to come.

It may seem counterintuitive to directly incentivize people to break cryptography that will eventually be used by government and commercial organizations. But given the incredibly high stakes of the transition to PQC, it’s absolutely critical that NIST receive every possible assurance that these algorithms are secure. If the new PQC algorithms do turn out to contain vulnerabilities like the recently discovered one, then it would be much better to find those vulnerabilities before the algorithms are rolled out widely. These PQC algorithms will eventually become the bedrock of cybersecurity for the entire internet. If a bounty helps to catch a vulnerability before it’s deployed, then the modest cost of the bounty could prevent much higher costs further down the line.