Skip to content
POST-QUANTUM COMPUTING

As quantum computing threats loom, Microsoft updates its core crypto library

Two algorithms added so far, two more planned in the coming months.

Dan Goodin – | 45
Credit: Getty Images
Credit: Getty Images
Story text

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.

Listing image: Getty Images

Photo of Dan Goodin
Dan Goodin Senior Security Editor
Dan Goodin is Senior Security Editor at Ars Technica, where he oversees coverage of malware, computer espionage, botnets, hardware hacking, encryption, and passwords. In his spare time, he enjoys gardening, cooking, and following the independent music scene. Dan is based in San Francisco. Follow him at here on Mastodon and here on Bluesky. Contact him on Signal at DanArs.82.
45 Comments
Staff Picks
p
pabs
Close friend of mine from college works as a cryptographer for some government agency (he jokes he can't tell me which one it actually is...he went straight there from his Stanford PhD) and he tried to explain ML-KEM to me a couple weeks ago in "simple" language and my brain gave up after about 2 minutes.
This might help: Kyber - How does it work?

One thing that is different about ML-KEM compared to finite-field Diffie-Hellman (DH) and Elliptic-Curve Diffie-Hellman (ECDH) is that the former is a Key Encapsulation Mechanism (KEM) and the latter are key-agreement protocols.

In DH and ECDH:
  1. Alice generates a keypair which consists of a public key and a private key.
  2. Alice keeps the private key to herself and sends the public key to Bob.
  3. Bob generates a keypair which consists of a public key and a private key.
  4. Bob keeps the private key to himself and sends the public key to Alice.
  5. Alice combines her private key from step #1 with Bob's public key from step #4 and produces a shared value.
  6. Bob combines his private key from step #3 with Alice's public key from step #2 and produces the same shared value that Alice produced in step #5.

In ML-KEM things work a bit differently:
  1. The first party (Alice) generates an keypair which consists of an encapsulation key (analagous to a public key in DH) and a decapsulation key (analagous to a private key in DH).
  2. Alice sends an encapsulation key to the second party (Bob).
  3. Bob generates a random value, which is hashed with a hash of Alice's encapsulation key from step #2 to generate a shared value (32 bytes in ML-KEM).
  4. Bob uses Alice's encapsulation key from step #2 to encapsulate the random value, producing a ciphertext.
  5. Bob sends the ciphertext from step #4 back to Alice.
  6. Alice uses the decapsulation key from step #1 to decapsulate the random value generated by Bob in step #3 from the ciphertext sent by Bob in step #5.
  7. Alice hashes the random value from step #6 with the hash of the encapsulation key to generate the shared value.
So in DH and ECDH, both parties contribute equally to the shared value. In ML-KEM, one party (Bob) generates a random value which is hashed with a hash of the other party's (Alice) encapsulation key to produce the shared value.

Another difference between DH/ECDH and ML-KEM is this: the shared value produced by DH and ECDH cannot be safely used as the secret key for a symmetric cipher (e.g. AES) because the shared value is biased (some values are much more likely than others). To safely derive a secret key (or keys) for use with a symmetric cipher, the shared value produced by DH and ECDH needs to be passed through a key derivation function (KDF) like HKDF.

The shared value derived in ML-KEM is uniformly random and can be used directly as the key for a symmetric cipher (FIPS 203, section 3.1). In practice I expect the ML-KEM shared value to be passed to a KDF anyway, because many protocols (for example, TLS) need to derive several keys in order to establish a secure channel.

DH, ECDH, and ML-KEM all rely on "hard" problems based on trapdoor functions.

"Hard" in this context means "computationally infeasible to solve without an implausible amount of computational resources or time".

A trapdoor function is a function that is easy to compute in one direction but hard to compute in the other direction without some additional information. For example, it is easy to calculate 61*71 and hard to calculate the integer factors of 4331. However, ff I tell you that one of the factors of 4331 is 61, then it is easy for you to calculate the other factor: 4331 / 61 = 71. This is the integer factorization problem, and it's the basis for RSA.

The hard problem that Finite-Field Diffie-Hellman (FFDH) key exchange is based on is the discrete logarithm problem, which is this:

Given b = gs mod p, it is hard to calculate s, where:​
  • s is a large randomly chosen positive integer that is secret
  • g is a fixed positive integer that is publicly known and carefully chosen by cryptographers
  • p is a fixed large prime number that is publicly known and carefully chosen by cryptographers
The hard problem that Elliptic-Curve Diffie-Hellman (ECDH) key exchange is based on is known as the elliptic curve discrete logarithm problem (ECDLP), which is this:

Given b = sG, it is hard to calculate s, where:​
  • s is a large randomly chosen positive integer that is secret, and
  • G is a fixed, publicly known point on an elliptic curve over a finite field. The point, elliptic curve, and field are all carefully chosen by cryptographers.
The hard problem that ML-KEM is based on is the Module Learning With Errors (MLWE) problem, which is derived from the Learning With Errors (LWE) problem. A simplified version of the LWE problem is this:

Given t = As + e, it is hard to calculate s, where:​
  • t is a public vector with integer elements
  • A is a public square matrix with elements that are random integer values
  • s is a secret vector with elements that are small integer values (the secret)
  • e is a secret vector with elements that are small integer values (the error)
Note that if you remove "e" from the equation above, then solving for s becomes very easy:
  1. Calculste A-1 using Gaussian elimination.
  2. Multiply by A-1 from the left: A-1t = A-1As
  3. Solution: s = A-1t
The important bit here is that the error vector is critical to making the problem hard.

In the Module Learning With Errors (MLWE) problem that is used by ML-KEM, the integers from the simplified LWE explanation above are replaced by polynomials with 256 coefficients.

(This is explained cryptically in FIPS 203, section 3.2)

Unfortunately the large polynomials make it difficult to visualize ML-KEM. There is a simplified implementation of Kyber called Baby Kyber in the Kyber - How does it work? article linked above that is easier to understand.

One problem with using 256-element polynomials is multiplication. Adding polynomials is done coefficient-wise, so adding two polynomials with 256 integer coefficients requires 256 integer additions.

Polynomial multiplication, on the other hand, requires multiplying every coefficient by every other coefficient. This means that multiplying two polynomials with 256 integer coefficients requires 256*256 = 65536 integer multiplications.

To work around this, ML-KEM a trick called the Number-Theoretic Transform (NTT, FIPS 203, section 4.3). This allows polynomial multiplication to be done (almost) coefficient-wise and drastically reduces the number of integer multiplications needed.

Using polynomials instead of large multi-word integers like DH and ECDH might seem confusing at first, but it actually simplifies a lot of the implementation because it enables SIMD optimizations and you don't have to deal with carry propagation.

Another neat trick used by ML-KEM is compressing the A matrix in the encapsulation key by including a 32-byte seed (rho) instead of the actual polynomial coefficients. This seed value is expanded with SHAKE128 to pseudorandomly generate the coefficients for the polynomial elements of the A matrix (FIPS 203, SampleNTT() in section 4.2.2 and section 5.1).

There are a lot of other details but hopefully this gives you enough to start to get your head around ML-KEM.

If you want to see some source code, here is a self-contained, single-file, dependency-free C11 implementation of the FIPS 203 initial public draft (IPD) that I wrote last year. It includes test vectors, SIMD acceleration, and the necessary bits of FIPS 202 (SHA3-256, SHA3-512, SHAKE128, and SHAKE256), but it has not been updated to reflect the changes in the final version of FIPS 203. I mainly wrote it for fun, to learn, and to provide public comments to NIST during the standardization process.
Prev story
Next story