by 
Getty Images
Microsoft has updated a key cryptographic library with two new encryption algorithms that are resistant to attacks from quantum computers.
The updates were made last week to SymCrypt, a core cryptographic code library for handling cryptographic functions in Windows and Linux. The library, launched in 2006, provides operations and algorithms that developers can use to 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 government environments.
Major overhaul underway
Despite its name, SymCrypt supports both symmetric and asymmetric algorithms. It is the primary cryptographic library used by Microsoft in products and services including Azure, Microsoft 365, all supported versions of Windows, Azure Stack HCI, and Azure Linux. The library provides cryptographic protection 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 the implementation of a massive overhaul of encryption protocols that include a new set of algorithms that are not vulnerable to attacks from quantum computers. Algorithms known to be vulnerable to attacks from quantum computers include RSA, Elliptic Curve, and Diffie-Hellman. These algorithms have been widely used for decades and are believed to be virtually unbreakable by classical computers if implemented correctly.
The security of these algorithms is based on mathematical problems that are easy to solve in one direction, but nearly impossible in the other. The difficulty means that adversaries attempting to decipher encrypted data by factoring or guessing the cryptographic key must randomly test trillions of combinations before finding the right one.
Quantum computing enables a new approach to cracking keys 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 the 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 exactly when those tools will be practical. Estimates range from five years to 50 years or more. Even then, encrypted data won’t be cracked all at once. The current estimate is that cracking a 1,024-bit or 2,048-bit RSA key would require a quantum computer with enormous resources.
Specifically, those estimated resources are about 20 million qubits, with about eight hours of them running in a superposition state. (A qubit is a basic unit of quantum computing, analogous to the binary bit in classical computing. But while a classical binary bit can only represent a single binary value, such as 0 or 1, a qubit is represented by a superposition of multiple possible states.) Current quantum computers reached a maximum of 433 qubits in 2022 and 1,000 qubits last year.
All of this means that even when quantum computing scales to the levels required, each individual key will need to be cracked separately using extremely expensive machines that need to run in a state of superposition for extended periods of time. Nuances like these are one reason why predictions about when practical attacks from quantum computers will be possible vary so widely.
The post-quantum algorithms are secured by problems that are not vulnerable to Shor’s algorithm. That resilience means that adversaries equipped with quantum computers would still need trillions of guesses to crack cryptographic keys based on these algorithms.
The first new algorithm Microsoft added to SymCrypt is called ML-KEM. Formerly 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 are not vulnerable to Shor’s algorithm when the keys are large enough.
The ML in the name ML-KEM refers to Module Learning with Errors, a problem that cannot be solved with Shor’s algorithm. As explained here , this problem is based on a “core computational assumption of lattice-based cryptography that offers an interesting trade-off between guaranteed security and concrete efficiency.”
ML-KEM, formally known as FIPS 203, specifies three sets of parameters with different security strengths, designated ML-KEM-512, ML-KEM-768, and ML-KEM-1024. The stronger the parameter, the more computing power is required.
The other algorithm added to SymCrypt is the NIST-recommended XMSS. This stands for eXtended Merkle Signature Scheme and is 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 use.
Monday’s announcement said that Microsoft will add additional post-quantum algorithms to SymCrypt in the coming months. They are ML-DSA, a lattice-based digital signature scheme formerly known as Dilithium, and SLH-DSA, a stateless hash-based signature scheme formerly known as SPHINCS+. Both became NIST standards last month and are formally referred to as FIPS 204 and FIPS 205.
