As Quantum Computing Threats Evolve, Microsoft Updates Its Core Crypto Library

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

Updates were made last week to SimCrypt, the main cryptographic code library for providing cryptographic functions on Windows and Linux. Launched in 2006, the library provides functions and algorithms that developers can use to securely implement secure encryption, decryption, signing, verification, hashing, and key exchange in the applications they build. The library supports federal certification requirements for cryptographic modules used in some government environments.

Major renovations are underway

Despite the name, SymCrypt supports both symmetric and asymmetric algorithms. It is the core 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 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 to implement a massive overhaul of encryption protocols that include new algorithms that are not vulnerable to attack by quantum computers.

In Monday’s post, Microsoft Principal Product Manager Lead Aba Thibsey wrote: “PQC algorithms offer a promising solution for the future of cryptography, but they come with some trade-offs. For example, it typically requires larger key sizes, longer computation time, and higher bandwidth than classical algorithms, Implementing PQC in real-world applications requires careful optimization and integration with existing systems and standards.”

Algorithms that are 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 nearly incorruptible by classical computers when properly implemented.

The security of these algorithms is based on mathematical problems that are easy to solve in one direction but impossible to solve in the other. The difficulty is 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 is developing 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 not possible 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 it will be practical with enough quantum computing resources.

No one knows exactly when those resources will come into play. Ratings range from five years to 50 or more. Even so, the encrypted data will not be decrypted at once. According to current estimates, breaking a 1,024-bit or 2,048-bit RSA key would require a quantum computer with vast resources.

Specifically, those estimated sources are about 20 million qubits and about eight hours of them run in the superposition state. (A qubit is the basic unit of quantum computing, analogous to a binary bit in classical computing. But a classical binary bit represents only a single binary value, such as 0 or 1. A qubit is represented by multiple possible superpositions.) Current quantum computers have a maximum of 433 qubits in 2022. and 1,000 kwt last year.

All of this, even if quantum computing reaches the required scale, each individual key must be decoded separately using very expensive machines that must operate in a state of superposition for extended periods of time. Such nuances are one of the reasons why predictions of when practical attacks from quantum computers are possible vary so widely.

Post-quantum algorithms are protected using problems not affected by Shor’s algorithm. The drawback is that adversaries equipped with quantum computers would need trillions more guesses to crack cryptographic keys based on these algorithms.

The first new algorithm Microsoft added to SymCrypt is called ML-KEM. ML-KEM, formerly known as Crystals-Kyber, is one of three post-quantum standards formalized by the National Institute of Standards and Technology (NIST) last month. KEM in the new name stands for Key Link. KEMs can be used by two parties to negotiate a shared secret over a public channel. Shared secrets generated by KEM can be used with symmetric-key encryption operations, not affected by Shor’s algorithm when the keys are large enough.

The ML in the name ML-KEM stands for module learning with errors, which refers to a problem that cannot be cracked by Shor’s algorithm. As explained here, this problem “is based on a key computational assumption of lattice-based cryptography, which provides an interesting trade-off between guaranteed security and robust performance.”

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

The other algorithm included in SymCrypt is the NIST-recommended XMSS. Short for Extended Merkle Signature Scheme, it 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 general applications.

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 formerly known as DiLithium, and SLH-DSA, a transient 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.