A cipher meant to withstand quantum computing was broken on a single-core PC in an hour
This is the second time in six months that a “post-quantum” algorithm has been destroyed by a calculation performed on a simple PC. A fiasco that shows how difficult it is to find a replacement for our current encryption techniques.
The SIKE (Supersingular Isogeny Key Encapsulation) encryption algorithm, developed by a group of 17 cryptographers, should protect us from attacks by the powerful quantum computers of the future thanks to ultra-complex mathematical techniques. But the process eventually stalled within an hour…on a traditional single-core PC.
To know the details of this resounding failure, you need to read the scientific report of the KU Leuven University researchers who performed this incredible cryptanalysis. Justified “An Efficient Key Recovery Attack on SIDH”, but requires extensive knowledge of elliptic curves. Which is a bit daunting.
The failures are increasing
SIKE was one of four algorithms competing in NIST’s “Post Quantum Cryptography” competition. This competition, which started in 2017 with 69 proposals, is of outstanding importance for the world of the internet. Indeed, the day quantum computers worthy of the name exist, all of the asymmetric encryption algorithms currently used in our communications and transactions could be thrown away due to the power of quantum computing. To avoid this apocalypse, mathematicians and cryptographers are desperate for a replacement.
But this story shows that quest is not that easy, especially since this is the second time such a fiasco has happened in six months. Last March, the “Rainbow” algorithm succumbed to attacks by Ward Beullen, a researcher at IBM. Using a simple laptop, he managed to calculate a secret key to Rainbow within 53 hours.
How is it that algorithms that were supposed to protect us from the most powerful computers ever created by man are finally destroyed by calculations on commercial PCs? In an interview with Ars Technica, David Jao, one of the authors of SIKE, expresses himself critically. He believes that the cryptographers working on these algorithms may not have deep enough knowledge of the mathematical objects they are manipulating. In the case of the last two errors listed, the attacks were carried out using well-known mathematical methods that date back to 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’m one of many researchers who work in cryptography but don’t understand the math as much as we should. So sometimes it just takes someone to recognize the applicability of existing theoretical mathematics to these new cryptosystems. That’s what happened here.” explains David Jao.
To date, four algorithms have already been officially selected as the standard by NIST. Four others, including SIKE, were still in the running. So you are only three. Hopefully we don’t find any more holes in the racket or we’ll get in trouble.
Source :
Ars-Technica
