The CRYSTALS-Kyber public-key encryption and key encapsulation mechanism recommended by NIST in July 2022 for post-quantum cryptography has been broken. Researchers from the KTH Royal Institute of Technology, Stockholm, Sweden, used recursive training AI combined with side channel attacks.
A side-channel attack exploits measurable information obtained from a device running the target implementation via channels such as timing or power consumption. The revolutionary aspect of the research (PDF) was to apply deep learning analysis to side-channel differential analysis.
“Deep learning-based side-channel attacks,” say the researchers, “can overcome conventional countermeasures such as masking, shuffling, random delays insertion, constant-weight encoding, code polymorphism, and randomized clock.”
The NIST-recommended encryption algorithms are the result of a NIST competition designed to provide encryption able to withstand quantum-computer attacks. Shor’s quantum algorithm will be able to defeat current classical encryption in polynomial time when quantum computers become a reality. This is expected by some to be within the next five to ten years – and has been called the cryptopocalypse.
The NIST approach to solving this issue is to develop more complex mathematical problems that are resistant to (although not necessarily proof against) quantum decryption. Such algorithms are described as quantum safe rather than quantum secure. Safe means it is safe until it is cracked; secure means it cannot be cracked by mathematical means. Basically, any problem based on mathematics could eventually be solved by mathematics.
The importance of the Swedish research is that quantum computers are not the only threat to encryption. Rapidly improving artificial intelligence may be a significant and more imminent threat to both classical and post-quantum encryption algorithms.
“[Our] approach is not specific for CRYSTALS-Kyber and can potentially be applied to other LWE/LWR PKE/KEM schemes. The recursive learning technique might have significance beyond side-channel attacks context,” say the researchers.
Skip Sanzeri, co-founder and COO at QuSecure, has already raised alarm at AI-assisted decryption. “New approaches are being developed promising the same post-quantum cybersecurity threats as a cryptographically relevant quantum computer, only much sooner,” he told SecurityWeek.
Steve Weston, co-founder and CTO at Incrypteon, has two concerns. “Firstly, it’s around the very conscious decision that NIST made to accept semantic secrecy as the bar we should aim for, rather than perfect secrecy – meaning that it’s based on complexity of a problem to be solved; that is, it will take a lot of compute effort and / or time to solve. Why as an Industry are we not aiming for perfect secrecy?”
Semantic secrecy is analogous to ‘safe’ encryption; perfect secrecy is analogous to ‘secure’ encryption. Perfect secrecy (secure encryption) can be obtained through the one-time pad. Qrypt has a one-time pad solution based on the simultaneous generation of quantum random numbers at both source and destination.
Incrypteon’s approach is to use Shannon’s equivocation point (in a patented technique known as perpetual equivocation) to minimize the key length for a one-time pad. Both approaches will be secure against AI-based decryption.
“Secondly,” continued Weston, “we only seem to be focused on securing against quantum attacks, not AI attacks. This is a real danger, if an AI operating on a single computer can break semantic post-quantum encryption.”
Weston has a further concern, which he calls ‘moot, but important’. “Why is it any innovation that comes out of trying to solve this problem (that is, creating an AI and quantum-resistant encryption with perfect secrecy characteristics) must then be ‘given away’ to NIST to be part of the process; requiring relinquishing of all IP rights for no reward or benefit?”
This approach, he suggests, will stifle innovation. “Why in 2023, is there no hybrid approach to industry standardization and IP ownership?”
Related: NIST Announces Post Quantum Encryption Competition Winners
Related: NIST Post-Quantum Algorithm Finalist Cracked Using a Classical PC
Related: Mitigating Threats to Encryption From Quantum and Bad Random
Related: Is OTP a Viable Alternative to NIST’s Post-Quantum Algorithms?
