NIST Post-Quantum Cryptography Candidate Cracked

Much more detail linked to.   Post quantum still an issue.  

ACM NEWS

NIST Post-Quantum Cryptography Candidate Cracked  By David Geer

Commissioned by CACM Staff, January 24, 2023

The U.S. National Institute of Standards and Technology intended its PQC standard algorithms to resist post-quantum hacking capabilities, but the researchers broke SIKE using a legacy computer chip.

Belgian researchers have cracked the SIKE cryptographic algorithm, a fourth and final-round candidate that the U.S. National Institute of Standards and Technology (NIST) was evaluating for its Post-Quantum Cryptography (PQC) standard.

Wouter Castryck and Thomas Decru, research experts at the KU Leuven research university in Leuven, Belgium, broke the SIKE algorithm in about 62 minutes. They did it using a single core on a six-core Intel Xeon CPU E5-2630v2 at 2.60GHz, according to their article, An Efficient Key Recovery Attack On SIDH. 

NIST intends its PQC standard algorithms to resist post-quantum hacking capabilities. Yet, the researchers broke SIKE using a legacy computer chip.

According to an article on the news site The Debrief, experts, authorities, and news outlets have confirmed the researchers' findings. NIST has since determined that it will not standardize the SIKE algorithm.

As part of its PQC Standardization Process, NIST chose 69 of 82 cryptographic algorithm candidates for the first round of its evaluations, according to The Register. NIST had narrowed its list to eight algorithms, including SIKE, by July 2022, according to NIST.

The same month, Castryck and Decru cracked SIKE, including SIKE parameters that people thought could meet NIST quantum security levels one through five, according to the article by Castryck and Decru. "On July 22, we informed the SIKE team about our attack, and on July 30, we posted our corresponding paper online," says Castryck.

PQC algorithms matter because criminal hoard encrypted data for future attacks using quantum computers. "There's a threat called' harvest now, decrypt later'. Your enemy could get access to your data and copy it. Though it's encrypted, they can hold on to it until the quantum computer comes out, then they can get into it," says Dustin Moody, a mathematician at NIST.

According to a Whitehouse.gov fact sheet, President Biden has mandated that NIST will publish quantum-resistant cryptographic standards to mitigate the risk that quantum computers could break the cryptography safeguarding digital communications on the Internet.

According to an Office of Management and Budget memorandum, the U.S. must transition its cryptographic systems to quantum-resistant cryptography, mitigating as much of the quantum risk as possible by 2035. However, according to McKinsey, quantum computers may crack classical encryption methods as soon as 2030. Obviously, affected organizations must implement the PQC standards as quickly as they can once these become available.

The SIKE crack is both concerning and encouraging, according to Tomas Gustavsson, chief Public Key Infrastructure (PKI) officer of Keyfactor, a PKI-as-a-Service company. "It's normal to break new suggested algorithms, which is a sign that good cryptographers are working on evaluating those," says Gustavsson.

"The concern is that we probably can't trust SIKE's underlying mathematical problem of supersingular isogenies any longer," says Gustavsson. "So, the SIKE hack may also have implications for other algorithms that people have based on the same problem," he says. 

NIST has already selected four cryptographic algorithms for PQC standardization: CRYSTALS-Kyber, CRYSTALS-Dilithium, FALCON, and SPHINCS+. Three additional algorithms are under consideration in the fourth round of the NIST evaluation process: Classic McEliece, BIKE, and HQC. "We think we might choose one or two more of those fourth-round algorithms, but we wanted more time to evaluate them," says Moody.

There are challenges to creating cryptographic algorithms that can resist quantum-level hacking. "Solving challenging scientific problems, and having a high level of confidence in these, always takes a lot of time and effort by scientists, engineers, and whole teams of people," says Gustavson.

The algorithms NIST chose for PQC standardization use older, harder math problems that many people have studied, according to Castryck. The hope is that quantum computers will not break these four algorithms, he says, although there is always that possibility.

According to Moody, no one can guarantee that no one will ever develop a smart new attack that could break a post-quantum cryptographic algorithm. "The best we can do in cryptography (post-quantum or not) is say that a lot of smart people have looked at it for many years and believe it is secure, i.e., no known attacks or lines of attack seem viable," says Moody.

It is essential for organizations not to lock into a single algorithm, according to Ted Shorter, CTO of Keyfactor. "I suspect that's part of why NIST is looking to standardize several algorithms this time," says Shorter.  ... ' 

Post-Quantum Cryptography Scheme Is Cracked?

 Generally true? Is this easily fixable, say by adding more digits? This kind of work, which challenges new methods is key. 

‘Post-Quantum’ Cryptography Scheme Is Cracked on a Laptop

Two researchers have broken an encryption protocol that many saw as a promising defense against the power of quantum computing.

By Jordana Cepelewicz, Senior Writer,    QuantaMagazine

If today’s cryptography protocols were to fail, it would be impossible to secure online connections — to send confidential messages, make secure financial transactions, or authenticate data. Anyone could access anything; anyone could pretend to be anyone. The digital economy would collapse.

When (or if) a fully functional quantum computer becomes available, that’s precisely what could happen. As a result, in 2017 the U.S. government’s National Institute of Standards and Technology (NIST) launched an international competition to find the best ways to achieve “post-quantum” cryptography.

Last month, the agency selected its first group of winners: four protocols that, with some revision, will be deployed as a quantum shield. It also announced four additional candidates still under consideration.

Abstractions navigates promising ideas in science and mathematics. Journey with us and join the conversation.

Then on July 30, a pair of researchers revealed that they had broken one of those candidates in an hour on a laptop. (Since then, others have made the attack even faster, breaking the protocol in a matter of minutes.) “An attack that’s so dramatic and powerful … was quite a shock,” said Steven Galbraith, a mathematician and computer scientist at the University of Auckland in New Zealand. Not only was the mathematics underlying the attack surprising, but it reduced the (much-needed) diversity of post-quantum cryptography — eliminating an encryption protocol that worked very differently from the vast majority of schemes in the NIST competition.

“It’s a bit of a bummer,” said Christopher Peikert, a cryptographer at the University of Michigan.

The results have left the post-quantum cryptography community both shaken and encouraged. Shaken, because this attack (and another from a previous round of the competition) suddenly turned what looked like a digital steel door into wet newspaper. “It came out of the blue,” said Dustin Moody, one of the mathematicians leading the NIST standardization effort. But if a cryptographic scheme is going to get broken, it’s best if it happens well before it’s being used in the wild. “There’s many emotions that go through you,” said David Jao, a mathematician at the University of Waterloo in Canada who, along with IBM researcher Luca De Feo, proposed the protocol in 2011. Certainly surprise and disappointment are among them. “But also,” Jao added, “at least it got broken now.”  .... ' 

NIST Chooses Future Tools

First step,  good start.   Openly presented on Github.

NIST Announces First Four Quantum-Resistant Cryptographic Algorithms

Federal agency reveals the first group of winners from its six-year competition.

July 05, 2022

The first four algorithms NIST has announced for post-quantum cryptography are based on structured lattices and hash functions, two families of math problems that could resist a quantum computer's assault.

GAITHERSBURG, Md. — The U.S. Department of Commerce’s National Institute of Standards and Technology (NIST) has chosen the first group of encryption tools that are designed to withstand the assault of a future quantum computer, which could potentially crack the security used to protect privacy in the digital systems we rely on every day — such as online banking and email software. The four selected encryption algorithms will become part of NIST’s post-quantum cryptographic standard, expected to be finalized in about two years.

“Today’s announcement is an important milestone in securing our sensitive data against the possibility of future cyberattacks from quantum computers,” said Secretary of Commerce Gina M. Raimondo. “Thanks to NIST’s expertise and commitment to cutting-edge technology, we are able to take the necessary steps to secure electronic information so U.S. businesses can continue innovating while maintaining the trust and confidence of their customers.”

The announcement follows a six-year effort managed by NIST, which in 2016 called upon the world’s cryptographers to devise and then vet encryption methods that could resist an attack from a future quantum computer that is more powerful than the comparatively limited machines available today. The selection constitutes the beginning of the finale of the agency’s post-quantum cryptography standardization project.

“NIST constantly looks to the future to anticipate the needs of U.S. industry and society as a whole, and when they are built, quantum computers powerful enough to break present-day encryption will pose a serious threat to our information systems,” said Under Secretary of Commerce for Standards and Technology and NIST Director Laurie E. Locascio. “Our post-quantum cryptography program has leveraged the top minds in cryptography — worldwide — to produce this first group of quantum-resistant algorithms that will lead to a standard and significantly increase the security of our digital information.” .... ' 

Is Q-Day Coming?

Brought to my attention.   Note mention of D-Wave Annealing, recall we connected to  them.  Could this mean the ability to break most encryption?  Breaking many parts of security infrastructures.   Scary?  Encrypting better with annealing?   See also the most recent Security Now for more comments.     Is the claim about D-Wave accurate?  Following up. 

Q-Day Is Coming Sooner Than We Think  By Arthur Herman Contributor  in Forbes, introduction: 

I comment on quantum computing and AI, and American national security.

Jun 7, 2021,01:37pm EDT

“Q-Day” is the term some experts use to describe when large-scale quantum computers are able to factorize the large prime numbers that underlie our public encryption systems, such as the ones that are supposed to protect our bank accounts, financial markets, and most vital infrastructure. That’s a feat that’s all but impossible for even the fastest supercomputers but which the unique features of quantum computers, using the physics of superpositioning and entanglement, will be able to deliver.

There’s a growing consensus that this quantum threat is real; there’s no agreement how long it will take before a quantum computer has the 4000 or so stable qubits it will need to meet the requirements of Shor’s algorithm for cracking those encryption systems. 

For example, it would take a classical computer 300 trillion years to crack an RSA-2048 bit encryption key. A quantum computer can do the same job in just ten seconds with 4099 stable qubits—but getting to that number is the main problem quantum computer engineers face since the stability or coherence of qubits lasts only for microseconds. Today’s most entangled computer, Google’s GOOG -1.1% Bristlecone, has just 72 stable qubits. 

Nonetheless, I have been arguing for the past four years, including in this column, that Q-Day is likely to come sooner than even quantum scientists can predict, and that the time to get ready to protect our vulnerable data and networks is now.  Others prefer to procrastinate, citing other experts who say such a threat is at least a decade or more away. The fact that the National Institute of Standards and Technology won’t have its quantum-resistant algorithm standards ready until 2024, and expects the rollout to space out for another five to fifteen years, has helped to encourage complacency disguised as confidence.  ... ' 

No Known Flaws in NIST Quantum Resistant Algorithms

Been re-involved in a quantum encryption effort, the below is from Schneier, has further comments, more at the link with some useful concerns about related flaws. 

The NSA Says that There are No Known Flaws in NIST’s Quantum-Resistant Algorithms

Rob Joyce, the director of cybersecurity at the NSA, said so in an interview:

The NSA already has classified quantum-resistant algorithms of its own that it developed over many years, said Joyce. But it didn’t enter any of its own in the contest. The agency’s mathematicians, however, worked with NIST to support the process, trying to crack the algorithms in order to test their merit.

“Those candidate algorithms that NIST is running the competitions on all appear strong, secure, and what we need for quantum resistance,” Joyce said. “We’ve worked against all of them to make sure they are solid.”

The purpose of the open, public international scrutiny of the separate NIST algorithms is “to build trust and confidence,” he said.

I believe him. This is what the NSA did with NIST’s candidate algorithms for AES and then for SHA-3. NIST’s Post-Quantum Cryptography Standardization Process looks good. ... ' 

Post Quantum Encryption Cracking

 If so, a  problem for one kind of approach. 

Encryption Meant to Protect Against Quantum Hackers Is Easily Cracked

By New Scientist, March 11, 2022, Comments

Ward Beullens at IBM Research Zurich in Switzerland easily cracked a cryptography algorithm touted as one of three contenders for a global standard against quantum hacking.

Rainbow is a signature algorithm submitted to the U.S. National Institute of Standards and Technology (NIST)'s Post-Quantum Cryptography competition, and Beullens extracted Rainbow's secret key from a public key in just 53 hours on a standard laptop.He said this flaw would enable attackers to wrongfully "prove" they are someone else, rendering Rainbow "useless" for message verification.

NIST's Dustin Moody said the Rainbow hack had been confirmed, and the algorithm will not likely be selected as the final signature algorithm.

From New Scientist

On the State of Quantum

 This also talks about D-Wave, which we touched with in our early examinations.  We are getting to closer to having the ability to solve complex problems very fast, and to have to worry about Quantum making some of our security less successful.

The State of Quantum Computing   By Logan Kugler, Commissioned by CACM Staff, April 8, 2021

In December 2020, a Chinese research team claimed to have successfully achieved "quantum advantage" by using quantum computing methods to perform computations that classical supercomputers can't.

Using photons, the team carried out a calculation called a boson-sampling problem. The calculation has so many variables that existing supercomputers "would take half the age of Earth" to calculate the problem, according to Nature. The Chinese team used quantum computing to achieve the calculation in a few minutes.

"[This] is certainly an impressive academic achievement, showing that quantum machinery can in some cases strain the abilities of conventional computers," said Chris Monroe, co-founder and chief scientist of IonQ, a quantum computer maker developing what it describes as a general-purpose trapped ion quantum computer and software to generate, optimize, and execute quantum circuits. "But it's important to consider that the problem they solved is a narrow application space with no known practical use, and it will be difficult to tune their experiment for any other type of problem."

Several leading companies are working to avoid that problem by developing practical quantum machines and deploying them for real commercial applications.

D-Wave Systems is one such company at the forefront of recent quantum computing developments. British Columbia, Canada-based D-Wave makes quantum machines specifically for businesses. Last year, the company announced the general availability of Advantage, its 5,000-qubit quantum system, accompanied by its quantum cloud service, Leap. The company's machines take a unique approach to quantum computing called "quantum annealing," which uses the physics of quantum phase transitions to perform computations. The company bet big on annealing early on, a bet that it says has paid off.

Murray Thom, D-Wave's vice president of software and cloud services, said, "We believed—and still believe—that annealing is the fastest path to our number-one objective: fueling customer value through practical quantum applications." The company says over 250 quantum-powered applications built with its system are now in production from Fortune 500 companies like Volkswagen, DENSO, and Accenture.  .. ...

........ "Quantum computing technology is accelerating rapidly, with new advancements and new companies getting involved nearly daily," says IonQ CEO and President Peter Chapman. "When I joined IonQ in 2019, people said that quantum would never work. We don't hear much from those people anymore."

Logan Kugler is a freelance technology writer based in Tampa, FL, USA. He has written for over 60 major publications.

Post-Quantum Crypto

 Will Quantum be able to cut through Crypto?   Effects on other solution expectations?

The Scramble for Post-Quantum Cryptography

By Samuel Greengard,  Commissioned by CACM Staff,  February 4, 2021

Researchers are working to counter the threat to current communications posed by the nascent quantum computing arena, which could undermine almost all of the encryption protocols used today.

History has demonstrated that where there are people, there are secrets. From elaborately coded messages on paper to today's sophisticated cryptographic algorithms, a desire to maintain privacy has persisted. Of course, as technology has advanced, the ability to cipher messages but also crack the codes has grown.

"Today's encryption methods are excellent, but we are reaching an inflection point," says Chris Peikert, an associate professor in the Department of Science and Engineering at the University of Michigan Ann Arbor. "The introduction of quantum computing changes the equation completely. In principle, these devices could break any reasonably-sized public key."

Such an event would wreak havoc. "It would affect nearly everything we do with computers," says Dustin Moody, a mathematician whose focus at the U.S. National Institute of Standards and Technology (NIST) includes computer security. Within this scenario, he says, computing subsystems, virtual private networks (VPNs), and digital signatures would no longer be secure. As a result, personal data, corporate records, intellectual property, and online transactions would all be at risk.

Consequently, cryptographers are developing new encryption standards that would be resistant to the brute force power of quantum computing. At the center of this effort is an initiative at NIST to identify both lattice-based and code-based algorithms that could protect classical computing systems but also introduce new and more advanced capabilities.  ... '

Cisco on Post Quantum Security

Full considerable article at the link, a good overview of the direction of quantum Crypto, with predictive time line.

It’s Not Too Early to Start Thinking About Post-Quantum Security
By Eve Griliches

In networking and communication, information security is absolutely necessary when transmitting over any untrusted medium, especially the Internet. Interestingly, people have been trying to securely encrypt information for 1000s of years, mostly using intuitive methods of encrypting, which is a good reason why we need cryptography. Cryptography protects data from being stolen or altered and is also used for individual authentication.

Physics proposed a solution known as quantum key distribution (QKD) which uses the quantum property of the particle to create and transmit a secure key. This is an interesting solution because a quantum particle state cannot be copied, so it is inherently possible to validate that a transmitted key is secure.

Actual quantum computers are still in early development but the threat to communication security has triggered investigations into alternative methods to distribute encryption keys. As mentioned before one of the methods proposed to address post-quantum security challenges is the Quantum Key Distribution (QKD) because of its theoretical promise to be intrinsic unbreakable and offering an easy method to detect the eavesdropper presence. Unfortunately, implementation flaws and side-channel attacks could open up a vulnerability, and while current commercial QKD systems are designed to have no exploitable implementation flaws and be resistant against known side-channel attacks, it leaves open the question about side-channel attacks which have yet to be discovered.

It is believed that quantum computing will have a huge impact on areas such as logistics, military activities, pharmaceuticals (drug design and discovery), aerospace design, nuclear fusion, financial modeling, polymer design, Artificial Intelligence (AI), cybersecurity, fault detection, Big Data, and capital goods, especially digital manufacturing. According to an analysis by Nature, private investors have funded at least 52 quantum-technology companies. The market for quantum computing is projected to reach $64.98 billion by 2030 from just $507.1 million in 2019, growing at a CAGR of 56.0% during the forecast period (2020–2030). According to a CIR estimate, revenue from quantum computing is pegged at $8 billion by 2027.

How quantum computing will scale, while quantum error correction itself is an implementation challenge, and still needs to be solved. Real quantum cryptoanalysis is most likely ~10 years away. Quantum key exchange has proven fantastic and unbreakable when implemented correctly, but it is limited by the physical infrastructure. There may be a niche application for relatively short distances, but it will not be a general solution. Cisco is tracking all of the solutions in this area and will bring to market a flexible solution that will enable our customers to use whatever PQ secure solution they feel more appropriate for them.

Read the full Cisco Post-Quantum Security Brief here: