An algorithm submitted to the NIST post-quantum encryption competition – and one that made it to the fourth round – has been defeated. The algorithm, Supersingular Isogeny Key Encapsulation (SIKE), was broken by Wouter Castryck and Thomas Decru at KU Leuven, and the process described in a paper written at the end of July 2022.
Cryptographers are not surprised by such an event; but security leaders concerned about their ability to protect secrets after the arrival of quantum computers, need to consider the implications.
For cryptographers
The defeat of SIKE follows a key recovery attack on the Supersingular Isogeny Diffie-Hellman key exchange protocol and its instantiation as SIKE in the NIST competition. The attack is based on the ‘glue and split’ theorem developed in 1997 by mathematician Ernst Kani.
In particular, say the two researchers, “Our attack exploits the existence of a small non-scalar endomorphism on the starting curve, and it also relies on the auxiliary torsion point information that Alice and Bob share during the protocol.”
The attack uses the researchers’ own Magma code to target Bob’s secret key. It could also be used to target Alice’s key, but the former yields faster results. This is a mathematical attack against the encryption algorithm rather than a brute force attack against individual keys.
The attack was run on a single classical computer – specifically an Intel Xeon CPU. “Ran on a single core, the appended Magma code breaks the Microsoft SIKE challenges… in about 4 minutes and 6 minutes, respectively. A run on the SIKE parameters, previously believed to meet NIST’s quantum security level 1, took about 62 minutes, again on a single core.”
This defeat effectively eliminates SIKE from the NIST competition, but it doesn’t necessarily prevent the algorithm from being modified and returned to the competition.
For the rest of us
SIKE is a key encapsulation algorithm, designed to deliver keys securely from source to destination across an untrusted network. It was designed to be quantum proof and thought to be one of the strongest candidates in the NIST competition.
The defeat of a NIST finalist quantum proof encryption algorithm on a single PC in little over an hour is dramatic. It suggests we need to rethink our attitude toward encryption in general and post quantum encryption in particular. SIKE is no different to any other encryption, pre- or post-quantum: it is secure only until it isn’t, and it isn’t as soon as it can be cracked.
Cryptographers, especially those funded by nation states, are continuously seeking ways to defeat encryption algorithms. In theory, what happened to SIKE yesterday could happen to RSA tomorrow. The only way that an algorithm crack is different to a zero-day vulnerability is that we are unlikely to hear about the former. Use of a state discovered algorithm crack against stolen and stored data isn’t likely to become public knowledge.
In effect, then, the use of any encryption is a leap of faith. We are told it is secure and we have no reason to disbelieve this – but we do not, and cannot, have absolute knowledge of this. Since encryption is based on mathematical problems, there is always the possibility that the algorithms can be attacked mathematically – and particularly so by massively powerful quantum computers.
The current need to change existing and apparently trustworthy algorithms for new and as yet not time-tested algorithms is promoting the development practice known as cryptographic agility (crypto agility). The idea is that if the algorithm in use is defeated, it can be swapped out for a different algorithm without significant change to the system infrastructure.
This is good practice but does not solve the underlying ‘harvest now, decrypt later’ problem posed by quantum computers. If a NIST-recommended algorithm is believed to be secure and used for ten years until it is defeated, all communications intercepted and stored by adversaries during those ten years can immediately be decrypted. The only difference between then and now is that we know this will happen to current public key encryption (thanks to Shor’s algorithm), while we don’t know that it won’t happen with new post-quantum algorithms.
The only type of cryptography that can be proven to be resistant to mathematical deconstruction is the one-time pad (OTP).
For the future
“If you want to protect your data with certainty against the harvest now and decrypt later attack, you simply cannot use an algorithm that is not mathematically proven quantum safe – and none of the post quantum candidates are mathematically proven quantum safe,” comments Chris Schnabel, VP of product at Qrypt.
He suggests a necessary question is what is the most important and sensitive data that simply must be protected against harvest now, decrypt later. This data needs additional safeguards – protected by a mathematically proven algorithm. “Any other algorithm could fail,” he added, “and SIKE is a wonderful example of this as a key exchange algorithm. If you’re really concerned about harvest now and decrypt later, you need to do something else beyond just migrating to post quantum algorithms.”
Many companies – federal agencies and regulated industries – will be required by government mandate to use NIST-sponsored post quantum algorithms. That currently cannot be avoided. A quantum-proof symmetric encryption will provide the most efficient use for bulk data transfer. For now, AES 256 is considered to be quantum proof. But this requires the key to be resident at both ends of the communication. The purpose of key encapsulation algorithms is to deliver that key safely to its destination.
Qrypt provides genuinely and provably random numbers, generated by quantum mechanics processes, to be used in building encryption. Traditionally, the random number is encryption’s weakest and most attacked element because it is impossible to generate genuinely unique and random numbers by classical means.
But Qrypt goes further by providing a mechanism to generate the number at both ends of the communication. This means that the key can be produced by both parties without requiring that it be sent across the untrusted network. If it is never transmitted, it cannot be intercepted and harvested – and any subsequent transmission of bulk data can be sent under more secure symmetric encryption.
“Everybody wants to know,” said Schnabel, “what is the most secure way to move keys around? Qrypt’s answer is very simple: don’t do it, because the algorithm could be compromised later. So, you don’t move your keys around – you independently generate identical keys at multiple endpoints.”
This is achieved through a cloud service that can be deployed on any software endpoint on the planet. It doesn’t require any dedicated hardware or dedicated fiber– just a few lines of code. “Instead of requiring key exchange that could be subject to the harvest now and decrypt later, we independently generate the keys at both ends,” he added.
The Qrypt technology offers another solution to the encryption dilemma – it can be used to generate one-time pad encryption. Right now, AES 256 is considered quantum safe – but there is no guarantee that it will remain so. Research from China has already suggested that a quantum algorithm called a variational quantum algorithm may threaten AES 256 given a large enough quantum computer. We return, then to the one-time pad as the only encryption method that cannot be cracked by computational methods, including quantum computers.
The traditional problem with OTPs is that the key must be larger than the file to be protected. This has led to the briefcase and handcuffs approach used in the past to deliver OTP keys. However, the random numbers delivered by Qrypt are effectively OTPs, and the time taken to generate them is shorter than the AES 256 encryption time. The result is the potential for Qrypt to provide quantum random numbers to produce keys that don’t need to be sent over the internet; and produce one-time pad encryption that is already and inherently safe against quantum decryption.
Zero transmitted keys built on genuinely random numbers is available today. Commercially viable one-time pad encryption is clearly coming. The combination of these solutions can provide known quantum safe encryption that doesn’t rely on the assumption and hope that a traditional post quantum algorithm will not be broken in the future – in the way that SIKE is already broken.
By Kevin Townsend on Wed, 10 Aug 2022 14:14:58 +0000
Original link