News and updates

First Hybrid, then fully Post Quantum

As we are all aware we are on the cusp of a major revolution in the auto-mobile industry. In 20 years we will all be driving electric cars and the good old petrol engine will be something we visit in museums. Already governments are legislating, and auto makers are revamping their assembly lines, to be ready in good time.

Hybrid car

In the meantime the industry has introduced a slew of “hybrid” models, which have two engines, one petrol and one electrical. This is a perfectly rational holding position to take. It avoids putting all of the eggs in one basket, so if the new electric motor fails for any reason, the car still functions.

In the world of crypto something similar is happening. We are pretty sure that in 20 years everything will have gone post-quantum, as cryptographers anticipate the invention of a quantum computer. So right now new crypto algorithms and protocols are being invented which will still be secure in the post quantum world – unlike most of the pre-quantum crypto we use today. Its not a trivial task, it will take a lot of work, but already plausible post-quantum protocols are being proposed and tested.

Modern cryptography is normally dated from the invention of the Diffie-Hellman key exchange protocol in 1976. From that simple beginning flowered the full range of modern crypto protocols. And so it is with Post Quantum crypto. Its first deliverables, in which we can have substantial faith, are in the area of simple key exchange.

Briefly by “simple key exchange” I mean that two participants, Alice and Bob, who have no prior arrangement, establish a secret key over an open channel, which allows them to communicate securely. Unfortunately it is vulnerable to the classic man-in-the-middle attack, which completely breaks it independent of the method used, but which must be launched in real-time, that is at the moment when Alice and Bob make the connection.

In the world of pre-quantum cryptography this short-coming has long been solved using more elaborate protocols, as indeed they will be in time for post-quantum crypto.

Fractal

So in the meantime how can we develop “hybrid” methods which allow us to leverage some of the advantages of post quantum crypto, without taking any unnecessary risks?

Easy. Use pre-quantum methods to establish the authenticated link and a mutual key. Then under cover of that key do a post-quantum key exchange. The bad guys have recorded the communication with a view to cracking it once a quantum computer becomes available, in say 10 years time. But when they do, they simply uncover the post quantum key exchange, and its 10 years too late to do a man-in-the-middle attack on it!

Here at MIRACL, while working in the longer term on fully post-quantum versions of our authentication protocols, we are already in a position to roll out a hybrid solution. After careful consideration we have gone with a post-quantum key exchange protocol called NewHope, proposed by Alkim, Ducas, Popplemann and Schwabe (https://eprint.iacr.org/2016/1157). We are in good company here – already Google have experimented with it. This protocol is, perhaps surprisingly, an order of magnitude faster than our existing methods, and involves the exchange of about 4k bytes of data. So we would regard its use as having a negligible impact on performance.

A full implementation of NewHope is now included in our open source AMCL crypto library (https://github.com/MIRACL/amcl), in all supported languages (C,Java, Javascript, Go, Rust and Swift).