Post-quantum cryptography new algorithm gone in 60 minutes – Naked Security

Weve written about PQC, short for post-quantum cryptography, several times before.

In case youve missed all the media excitement of the past few years about so-called quantum computing

it is (if you will pardon what some experts will probably consider a reckless oversimplification) a way of building computing devices that can keep track of multiple possible outcomes of a calculation at the same time.

With a lot of care, and perhaps a bit of luck, this means that you can rewrite some types of algorithm to home in on the right answer, or at least correctly discard a whole slew of wrong answers, without trying and testing every possible outcome one-by-one.

Two interesting cryptanalytical speedups are possible using a quantum computing device, assuming a suitably powerful and reliable one can actually be constructed:

The threat from Grovers algorithm can be countered simply by boosting the size of the the numbers youre using by squaring them, which means doubling the number of bits in your cryptographic hash or your symmetric encryption key. (In other words, if you think SHA-256 is fine right now, using SHA-512 instead would provide a PQC-resistant alternative.)

But Shors algorithm cant be countered quite so easily.

A public key of 2048 bits would need its size increased exponentially, not simply by squaring, so that instead of a key of 22048=4096 bits, either youd need a new key with the impossible size of 22048 bits

or youd have to adopt a completely new sort of post-quantum encryption system to which Shors algorithm didnt apply.

Well, US standards body NIST has been running a PQC competition since late 2017.

The process has been open to everyone, with all participants welcome, all algorithms openly published, and public scrutiny not merely possible but actively encouraged:

Call for Proposals. [Closed 2017-11-30]. [] It is intended that the new public-key cryptography standards will specify one or more additional unclassified, publicly disclosed digital signature, public-key encryption, and key-establishment algorithms that are available worldwide, and are capable of protecting sensitive government information well into the foreseeable future, including after the advent of quantum computers.

After three rounds of submissions and discussions, NIST announced, on 2022-07-05, that it had chosen four algorithms that it considered standards with immediate effect, all with delighful-sounding names: CRYSTALS-KYBER, CRYSTALS-Dilithium, FALCON, and SPHINCS+.

The first one (CRYSTALS-KYBER) is used as whats called a Key Agreement Mechanism (KEM), where two ends of a public communication channel securely concoct a one-time private encryption key for exchanging a sessions worth of data confidentially. (Simply put: snoopers just get shredded cabbage, so they cant eavesdrop on the conversation.)

The other three algorithms are used for Digital Signatures, whereby you can ensuring that the data you got out at your end matches exactly what the sender put in at the other, thus preventing tampering and assuring integrity. (Simply put: if anyone tries to corrupt or mess with the data, youll know.)

At the same timeas announcing the new standards, NIST also announced a fourth round of its competition, putting a further four algorithms forward as possible alternative KEMs. (Remember that, at the time of writing, we already have three approved digital signature algorithms to choose from, but only one official KEM.)

These were: BIKE, Classic McEliece, HQC and SIKE.

Intriguingly, the McEliece algorithm was invented way back in the 1970s by American cryptographer Robert Mc Eliece, who died in 2019, well after NISTs contest was already underway.

It never caught on, however, because it required huge amounts of key material compared to the popular alternative of the day, the Diffie-Hellman-Merkle algorithm (DHM, or sometimes just DH).

Unfortunately, one of the three Round Four algorithms, namely SIKE, appears to have been cracked.

In a brain-twisting paper entitled AN EFFICIENT KEY RECOVERY ATTACK ON SIDH (PRELIMINARY VERSION), Belgian cryptographers Wouter Castryk and Thomas Decru seem to have dealt something of a deadly blow to the SIKE algorithm

In case youre wondering, SIKE is short for Supersingular Isogeny Key Encapsulation, and SIDH stands for Supersingular Isogeny Diffie-Hellman, a specific use of the SIKE algorithm whereby two ends of a communication channel perform a DHM-like cryptodance to exchange a bunch of public data that allows each end to derive a private value to to use as a one-time secret encryption key.

Were not going to try to explain the attack here; well just repeat what the paper claims, namely that:

Very loosely put, the inputs here include the public data provided by one of the participants in the key establishment cryptodance, along with the pre-determined (and therefore publicly-known) parameters used in the process.

But the output thats extracted (the information referred to as the isogeny above) is supposed to be the never-revealed part of the process the so-called private key.

In other words, from public information alone, such as the data exchanged opnely during key setup, the cryptographers claim to be able to recover the private key of one of the participants.

And once you know my private key, you can easily and undetectably pretend to be me, so the encryption process is broken.

Apparently, the key-cracking algorithm takes about an hour to do its work, using just a single CPU core with the kind of processing power youd find in an everyday laptop.

Thats against the SIKE algorithm when configured to meet Level 1, NISTs basic grade of encryption security.

Nothing!

(Thats the good news.)

As the authors of the paper suggest, after noting that their result is still preliminary, with the current state of affairs, SIDH appears to be fully broken for any publicly generated base curve.

(Thats the bad news.)

However, give that the SIKE algorithm isnt officially approved yet, it can now either be adapted to thwart this particular attack (something that the authors admit may be possible), or simply dropped altogether.

Whatever finally happens to SIKE, this is an excellent reminder of why trying to invent your own encryption algorithms is fraught with danger.

Its also a pointed example of why proprietary encryption systems that rely on the secrecy of the algorithm itself to maintain their security are simply unacceptable in 2022.

If a PQC algorithm such as SIKE survived persual and probing by experts from around the globe for more than five years, despite being disclosed specifically so that it could be subjected to public scrutiny

then theres no need to ask yourself how well your home-made, hidden-from-view encryption algorithms are likely to fare when released into the wild!

See the original post here:
Post-quantum cryptography new algorithm gone in 60 minutes - Naked Security