First PQC standards released: a data security landmark
Publié le 05/9/2024
Author : Arnaud DUFOURNET, Chief Marketing Officer
The IT security industry had been eagerly awaiting their arrival. Visiting London in May this year, Anne Neuberger, the United States’ deputy national security advisor, had announced they would be published in July. And NIST (the US National Institute of Standards and Technology) did eventually release the finalized version of its first three post-quantum encryption algorithm standards in the middle of the summer. The issuing of these standards marks a major turning point in data security. As researchers around the world are racing to build quantum computers, which would be able to break the encryption we currently use, any doubts over the urgent need to transition to new encryption methods have surely evaporated.
A selection process that started in 2016
NIST consequently officially released the first three PQC standards on August 13, 2014. They are the outcome of a world-wide competitive process started by NIST in 2016 to counter the quantum threat. After examining 82 algorithms from 25 countries, the competition produced four: two to protect public key exchanges, and two others to protect digital signatures.
As you may know, public-key cryptography, which is mainly used to protect digital signatures, key transport and identity authentication, is vulnerable to quantum attacks. Bearing in mind the prospect of HNDL* attacks, protecting the first two of these usages is a priority. As regards authentication of identities, attacks can only actually occur after Q-day, i.e. once quantum computers are powerful enough to run Shor’s algorithm and break asymmetric encryption systems.
The four algorithms selected after three rounds of assessment are the result of collaboration between a number of academic institutions and research organizations, among which IBM Research can boast of being involved in three of the four algorithms selected to serve as standards.
Algorithm name changes
In the wake of announcing the results of the third round of its competition, NIST published draft standards on August 24, 2023, for three of the four algorithms selected, namely CRYSTALS-Kyber, CRYSTALS-Dilithium and SPHINCS+. These are now to be known as standards FIPS** 203, FIPS 204, and FIPS 205 respectively. NIST had set a deadline of November 22, 2023, for experts to submit comments and suggestions, and had then taken several months to digest feedback and add some details and clarifications. Ultimately, one year on, there are relatively few differences between the draft and published versions of the standards. The main change is in fact that the algorithms have been renamed:
CRYSTALS-KYBER becomes ML-KEM
Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM) is a mechanism to encapsulate keys that is used to share a secret key over a public channel. This algorithm is based on structured Euclidian lattice problems, in particular how difficult it is to find short vectors. Selected by NIST on the basis of the security level and performance offered, ML-KEM presents a number of advantages, including the relatively small size of its encryption keys and execution speed. Three levels of security are available, i.e. ML-KEM 512, ML-KEM 768, and ML-KEM 1024, with the keys becoming larger at each level.
CRYSTALS-DILITHIUM becomes ML-DSA
Module-Lattice-Based Digital Signature Algorithm (ML-DSA) is a digital signature mechanism designed to authenticate the integrity of signed data and the identity of the signatory. Like ML-KEM, this algorithm is based on Euclidean lattice problems. Selected by NIST on the basis of its security level and efficiency, ML-DSA stands out for its speed and efficiency in terms of computation and signature size, particularly compared with PQC algorithms based on hash functions. It is also relatively simple to implement. Three levels of security are available, i.e. ML-DSA-44, ML-DSA-65, and ML-DSA-87, each with a key size larger than that for pre-quantum algorithms.
SPHINCS+ BECOMES SLH-DSA
Stateless Hash-Based Digital Signature Algorithm (SLH-DSA) is a digital signature algorithm based on hash tree structures. Suggested as an alternative to ML-DSA, NIST deemed this algorithm to be sufficiently secure. It is particularly recommended for use cases such as software, document, and email signatures.
Algorithms we are already using without knowning it
Major US companies haven’t waited for standards to be published before implementing quantum-resistant cryptography. Anticipated for months as the recommended algorithm for encrypting key exchanges, ML-KEM (formerly Kyber) has already been deployed by the tech giants.
In September 2023, Signal announced it had integrated post-quantum cryptography to protect its communications, using a hybrid approach blending Kyber and Diffie-Hellman. Apple followed suit in February 2024, announcing that the PQ3 protocol was available for its iMessage messaging service on iOS 17.4 and macOS 14.4, also blending Kyber with elliptic-curve cryptography. More recently, in May 2024, Meta said it was migrating to Kyber for key exchanges in TLS protocols. Likewise, Google announced that Google Chrome version 124 is using the KEM Kyber768 algorithm for TLS 1.3 and QUIC connections, to protect Chrome TLS traffic against quantum attacks.
Protecting online communication is obviously becoming a priority for the sector’s giants. The adoption of PQC, although transparent to users, is increasingly visible in the internet traffic operated by Cloudflare, already standing at 17% of HTTPS requests over the last three months. The United States seems to be fully aware of the quantum threat, whereas Europe is lagging behind. Experts nonetheless reckon that Q-day could occur at some point in the next decade. The issuing of standards for ready-to-use algorithms is the starting gun for migration to this new cryptography. The first step is to produce an inventory of the cryptographic systems at risk (see our blog post here).
NIST, meanwhile, is continuing to select algorithms to bring about some diversity. A fourth round is underway to make substitutes for ML-KEM available. A draft standard based on FALCON (FN-DSA) is planned for late 2024, but at the same time, a fresh digital signature competition has begun. The aim is to continue to assess other algorithms that could potentially become standards that are not based on Euclidean lattices. And as ever, underpinned by the idea that in cryptography, greater diversity of problems equals greater security.
Learn more on NIST press release here
* Harvest Now, Decrypt Later: an attack whereby encrypted communications are collected now for decryption at some future time
** FIPS: Federal Information Processing Standards