Next Generation Cryptography
The news that many of us in the cryptographic community have been waiting for has arrived. On Aug 13th, 2024, the National Institute of Science and Technology (NIST) released Post-Quantum Cryptographic (PQC) standards for 3 algorithms. Unlike currently used public-key cryptographic algorithms, these new PQC algorithms, which can still be run on conventional computers, will not be vulnerable to attacks deployed on future large-scale quantum computers.
NIST’s PQC algorithms should not just be thought of as being secure against attacks using quantum computers; they are believed to be secure against any potential attack. It is not foreseeable that anyone could build a computer that could be used to break one of NIST’s newly standardized PQC algorithms. They are the next generation of public-key cryptography. They are cryptographic standards that will become ubiquitous.
NIST PQC Standardization Process
While these standards may seem as though they are introducing new cryptography, the algorithms are in fact a product of decades of academic research, combined with NIST’s intensive multi-year process designed to weed out any insecure algorithms.
NIST’s process to find PQC replacements started nearly a decade ago, back in 2016, with a call for proposals for both Key Encapsulation Mechanisms (KEM) for key establishment and digital signature algorithms for authentication. In 2017, there were 69 ‘complete and proper’ submissions for the NIST PQC standardization process. Since then, through multiple rounds of intense scrutiny, NIST has repeatedly narrowed the field of candidates until they were left with a few remaining algorithms.
The algorithms they have standardized are:
- Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM) defined in FIPS 203.
- Module-Lattice-Based Digital Signature (ML-DSA) defined in FIPS 204.
- Stateless Hash-Based Digital Signature (SLH-DSA) defined in FIPS 205.
Use-Cases of each Algorithms
ML-KEM and ML-DSA are:
- Trustworthy: The NSA has recommended them as stand-alone algorithms, although a hybrid solution with classical cryptography is possible for those wanting additional security.
- Easy to Implement: These lattice-based algorithms require only a small amount of knowledge of linear algebra and abstract algebra to implement. Unlike FALCON, an algorithm that NIST plans on standardizing, ML-KEM and ML-DSA do not require floating-point arithmetic, which is difficult to implement securely. Unlike the stateful hash-based algorithms LMS and XMSS, none of these new algorithms require managing a state (that is, the private key does not need to be updated after each signature).
- General Purpose: These algorithms have reasonable key sizes and are efficient, making them the favoured go-to algorithms for non-specialized applications.
SLH-DSA is:
- Hash Function as a Building Block: This is an algorithm that researchers at InfoSec Global helped develop. The algorithm SLH-DSA uses a well-known cryptographic hash function, either SHA2 or SHAKE, as a building block. As most systems have secure implementations, and in many cases secure hardware implementations of SHA2 or SHAKE, this simplifies the code base for SLH-DSA.
- Well-Understood Security: Unlike classical public-key cryptography, the hash functions SHA2 and SHAKE are not believed to be vulnerable to quantum attacks provided sufficiently large parameters are used. Moreover, the overall confidence in the classical and quantum security of the hash-functions SHA2 and SHAKE is transferred to SLH-DSA. Although SLH-DSA is less efficient than ML-DSA, for hardware applications that are difficult to reach and update, for example, it might be worth taking the performance penalty to implement SLH-DSA to gain the added confidence in its long-term security.
Time to Invest
An idea that computer scientist David Clark of MIT first described is that it is best to release standards after a large amount of research is completed and before large-scale adoption takes place.
- Research Completed Prior to Standardizaton: If a standard is written too early, then it is possible that the solution may need to be changed. In the case of ML-KEM, ML-DSA, and SLH-DSA, NIST decided to standardize them now, because NIST believes they are stable, well-vetted solutions. There are other PQC algorithms that are going through an additional round or even an additional process in NIST’s PQC standardization project to undergo sufficient examination before (potentially) being standarded.
- Corporate Investment: It is difficult to start using a new type of cryptography without a standard. For cryptography to be useful, all the parties involved must use the same algorithm, including using all the same parameters. A good analogy is that all parties in a communication using the same cryptographic standards is similar to all parties in a communication sharing the same language. Now that the standards have been finalized, everyone can start using these new algorithms without concerns about incompatibilities.
Future Algorithms and Crypto-Agility
The algorithms ML-KEM and ML-DSA are considered to be general-purpose algorithms. NIST is planning on standardizing other PQC algorithms in the upcoming years; however, in most cases those will be algorithms that are useful for particular application. As the timeline for large organizations to migrate to PQC is already fairly tight, it is reasonable to switch to the general purpose algorithms ML-KEM and ML-DSA now, and if the use case would benefit from it, switch again to another algorithm once it is standardized. Due to the potential for multiple algorithms being switched in and out, it is recommended to use products with crypto agility built in such as InfoSec Global’s AgileSec SDK.
Steps to Migrate to PQC
The question we always get asked is where to start. We have some great information on this, but the short version is:
- Categorize Your Cryptography: Finding and categorizing all of an organization’s cryptographic artifacts is an extensive task best done with a dedicated discovery solution such as InfoSec Global’s AgileSec™ Analytics that can analyze an organization’s entire digital landscape in an automated manner.
- Implement Crypto-agility: As mentioned above, implement crypto-agile solutions to plan for upcoming standards, as well as future PQC standards.
- Identify Vulnerabilities: It is important to make a plan that prioritizes applications according to their risk level and importance.
- Experiment: Run contained experiments with the new algorithms to ensure your migration is smooth.
- Start Your Migration!
