Two implementation vulnerabilities have been reported in the Kyber key encapsulation mechanism (KEM), an encryption standard designed to protect networks against future attacks by quantum computers. Collectively referred to as “KyberSlash,” these flaws could lead to attackers discovering encryption keys.
The vulnerabilities, known as KyberSlash 1 and KyberSlash 2, consist of timing-based attacks wherein attackers observe how long Kyber performs specific division operations in its decapsulation process, according to BleepingComputer, which broke the story. “Timing attacks of this nature are a derivative of broader ‘side channel’ attacks, which can be used to undermine any type of encryption, including both classical and post-quantum algorithms,” Andersen Cheng, founder of Post-Quantum, explained to Tech Monitor. “With this type of attack, the adversaries send fake (and known) ciphertext and measure how long it takes to decipher. They can then infer the timings for each attempt and reverse engineer the actual key-pair.”
The flaws were reported to Kyber’s development team by Franziskus Kiefer, Goutam Tamvada and Karthikeyan Bhargavan, all researchers at cybersecurity firm Cryspen, on 1 December. A patch was immediately issued for the encryption standard, but as it wasn’t labelled as a security issue, Cryspen began to proactively inform projects that they needed to apply the fix from 15 December.
Versions of the Kyber post-quantum encryption standard have been adopted by Google, Signal and Mullvad VPN, though the latter has since confirmed that its services are not impacted by the vulnerability.
Post-quantum encryption rush
Kyber was first submitted for review to the US National Institute of Standards and Technology (NIST) in 2017, as part of a competition convened by the organisation to test and finalise an encryption standard capable of defending networks against future attacks by a quantum computer. Though a machine with the requisite number of qubits capable of using Shor’s algorithm to break RSA encryption and similar standards has yet to be developed, recent breakthroughs in scaling quantum computers and mounting speculation about “Harvest Now, Decrypt Later” attacks have led to increased interest in adopting post-quantum standards by governments and major corporations.
Several algorithms entered into NIST’s competition have been proven vulnerable to conventional attacks. These include the standards Rainbow and SIKE, the latter of which was defeated by researchers at KU Leuven in 2022 in under an hour using a classical computer. The official implementation of Kyber, CRYSTALS-Kyber, was also undermined in February 2023 using highly complex deep learning-based side-channel attacks by a team from Sweden’s KTH Royal Institute of Technology. Nevertheless, the algorithm was one of several for which NIST released draft standards last summer, intending to finalise its competition later this year.
In the meantime, several major organisations have adopted versions of the Kyber KEM. In August 2023, Google announced its implementation of Kyber-768 as part of a hybrid mechanism to secure the transport layer security traffic on its Chrome browser. Similarly in September, Signal adopted Kyber-1024 in combination with an elliptic curve key agreement protocol to help secure its “Signal Protocol,” which is also used to guarantee end-to-end encryption in WhatsApp and Google messages.
This hybrid approach to using post-quantum encryption standards is meant to ensure that network traffic is protected from attack should new vulnerabilities in post-quantum standards be discovered. Since the KyberSlash vulnerabilities were uncovered, the team behind the discovery claim that patches have now been implemented by the Kyber development team and by AWS. A GitHub library created by Kudelski Security was also listed by the team. When Tech Monitor contacted the cybersecurity firm, it confirmed that the code listed was not used in any of its commercial products and should not be used in production, but that it had nevertheless implemented a patch for the KyberSlash vulnerabilities in a new version of the library.
Nevertheless, Cheng considers it an important step forward for the post-quantum encryption community that its focus on flaws has moved on from vulnerabilities in the mathematics underpinning the standards toward implementation attacks. “It will be the responsibility of each organisation implementing new encryption to ensure the implementation is robust,” says Cheng. “That’s why it is so important that teams working on the migration to post-quantum encryption have deep engineering understanding and ideally, existing experience in deploying the cryptographic algorithms. “