Microsoft has updated a key cryptographic library with two new encryption algorithms designed to withstand attacks from quantum computers.

The updates were made last week to SymCrypt, a core cryptographic code library for handing cryptographic functions in Windows and Linux. The library, started in 2006, provides operations and algorithms developers can use to safely implement secure encryption, decryption, signing, verification, hashing, and key exchange in the apps they create. The library supports federal certification requirements for cryptographic modules used in some governmental environments.

Massive overhaul underway

Despite the name, SymCrypt supports both symmetric and asymmetric algorithms. It’s the main cryptographic library Microsoft uses in products and services including Azure, Microsoft 365, all supported versions of Windows, Azure Stack HCI, and Azure Linux. The library provides cryptographic security used in email security, cloud storage, web browsing, remote access, and device management. Microsoft documented the update in a post on Monday.

The updates are the first steps in implementing a massive overhaul of encryption protocols that incorporate a new set of algorithms that aren’t vulnerable to attacks from quantum computers.

In Monday's post, Microsoft Principal Product Manager Lead Aabha Thipsay wrote: "PQC algorithms offer a promising solution for the future of cryptography, but they also come with some trade-offs. For example, these typically require larger key sizes, longer computation times, and more bandwidth than classical algorithms. Therefore, implementing PQC in real-world applications requires careful optimization and integration with existing systems and standards."

Algorithms known to be vulnerable to quantum computing attacks include RSA, Elliptic Curve, and Diffie-Hellman. These algorithms have been widely used for decades and are believed to be virtually uncrackable with classical computers when implemented correctly.

The security of these algorithms is based on mathematical problems that are easy to solve in one direction but are nearly impossible to solve in the other. The difficulty means that adversaries trying to decipher encrypted data by factoring or guessing the cryptographic key must randomly test trillions of combinations before finding the correct one.

Quantum computing makes a new approach to cracking keys possible based on these vulnerable algorithms. The approach, known as Shor’s algorithm, relies on properties of quantum physics, such as superposition and entanglement, that are impossible with today’s classical computers. The inability to implement Shor’s algorithm today means that this approach is still theoretical, but most, if not all, cryptography experts believe that it will be practical with sufficient quantum computing resources.

No one knows precisely when those resources will be practical. Estimates range from five years to as many as 50 or more. Even then, encrypted data won’t be cracked all at once. The current estimate is that breaking a 1,024-bit or 2,048-bit RSA key will require a quantum computer with vast resources.

Specifically, those estimated resources are about 20 million qubits and about eight hours of them running in a state of superposition. (A qubit is a basic unit of quantum computing, analogous to the binary bit in classical computing. But whereas a classic binary bit can represent only a single binary value such as a 0 or 1, a qubit is represented by a superposition of multiple possible states.) Current quantum computers maxed out at 433 qubits in 2022 and 1,000 qubits last year.

All of that means that even when the scale of quantum computing reaches the required levels, each individual key will have to be cracked separately by using extremely expensive machines that must run in a state of superposition for sustained periods. Nuances such as these are one of the reasons predictions vary so widely for when practical attacks from quantum computers will be possible.

The post-quantum algorithms are secured using problems that aren’t vulnerable to Shor’s algorithm. That resilience means that adversaries equipped with quantum computers will still require trillions of guesses to crack cryptographic keys based on these algorithms.

The first new algorithm Microsoft added to SymCrypt is called ML-KEM. Previously known as CRYSTALS-Kyber, ML-KEM is one of three post-quantum standards formalized last month by the National Institute of Standards and Technology (NIST). The KEM in the new name is short for key encapsulation. KEMs can be used by two parties to negotiate a shared secret over a public channel. Shared secrets generated by a KEM can then be used with symmetric-key cryptographic operations, which aren’t vulnerable to Shor’s algorithm when the keys are of a sufficient size.

The ML in the ML-KEM name refers to Module Learning with Errors, a problem that can’t be cracked with Shor’s algorithm. As explained here, this problem is based on a “core computational assumption of lattice-based cryptography which offers an interesting trade-off between guaranteed security and concrete efficiency.”

ML-KEM, which is formally known as FIPS 203, specifies three parameter sets of varying security strength denoted as ML-KEM-512, ML-KEM-768, and ML-KEM-1024. The stronger the parameter, the more computational resources are required.

The other algorithm added to SymCrypt is the NIST-recommended XMSS. Short for eXtended Merkle Signature Scheme, it’s based on “stateful hash-based signature schemes.” These algorithms are useful in very specific contexts such as firmware signing, but are not suitable for more general uses.

Monday’s post said Microsoft will add additional post-quantum algorithms to SymCrypt in the coming months. They are ML-DSA, a lattice-based digital signature scheme, previously called Dilithium, and SLH-DSA, a stateless hash-based signature scheme previously called SPHINCS+. Both became NIST standards last month and are formally referred to as FIPS 204 and FIPS 205.