© PxHere
This is the second time in six months that a “post quantum” algorithm has been destroyed by a calculation carried out on a simple PC. A fiasco that demonstrates the difficulty of finding replacements for our current encryption techniques.
Imagined by a group of 17 cryptographers, the SIKE encryption algorithm (Supersingular Isogeny Key Encapsulation) was to protect us from attacks carried out from the powerful quantum computers of the future, thanks to ultra-complex mathematical techniques. But the process was finally broken in the space of an hour… on a traditional single-core PC.
To know the details of this resounding failure, you have to read the scientific report of the researchers of the KU Leuven University, who carried out this incredible cryptanalysis. Entitled “An efficient key recovery attack on SIDH”, it nevertheless requires in-depth knowledge in the field of elliptic curves. Which is a bit off-putting.
The failures multiply
SIKE was one of a set of four algorithms that remain in contention in the “Post Quantum Cryptography” competition of NIST, an American standards organization. This competition, which started in 2017 with 69 proposals, is of paramount importance for the world of the Internet. Indeed, the day when quantum computers worthy of the name exist, all the asymmetric encryption algorithms currently used in our communications and transactions may be thrown away, due to the power of quantum computing. To avoid this apocalypse, mathematicians and cryptographers are desperately looking for replacements.
But this story shows that this quest is not so simple, especially since this is the second time such a fiasco has happened in the space of six months. Last March, the “Rainbow” algorithm succumbed to attacks by Ward Beullen, a researcher at IBM. Using a simple laptop computer, he managed to calculate a secret key to Rainbow within 53 hours.
How is it that algorithms supposed to protect us from the most powerful computers ever created by man are finally destroyed by calculations carried out on commercial PCs? Interviewed by Ars Technica, David Jao, one of the authors of SIKE, makes his self-criticism. He believes that the cryptographers working on these algorithms may not have a sufficiently deep knowledge of the mathematical objects they manipulate. In the last two failures listed, the attacks were carried out with known mathematical processes, dating from the end of the last century.
Lack of advanced skills
“In general, there is a lot of advanced mathematics that has been published without being well understood by cryptographers. I fall into the category of those many researchers who work in cryptography, but who don’t understand mathematics as much as we really should. So sometimes all it takes is someone to recognize the applicability of existing theoretical mathematics to these new cryptosystems. That’s what happened here,” says David Jao.
To date, four algorithms have already been officially selected by NIST as the standard. Four others, including SIKE, were still in contention. They are therefore only three. Let’s hope we won’t find any other holes in the racket, otherwise we’re in trouble.
Ars-Technica