mlkem-native

mlkem-native is a secure, fast, and portable C90 implementation of ML-KEM¹. It is a fork of the ML-KEM reference implementation².

All C code in mlkem/* and mlkem/fips202/* is formally verified using CBMC to be memory-safe (no buffer overflow) and type-safe (no integer overflow). HOL-Light is used to verify the functional correctness of core AArch64 assembly routines.

mlkem-native includes fast assembly for AArch64 and AVX2, offering competitive performance on most Arm, Intel, and AMD platforms (see benchmarks).

mlkem-native is supported by the Post-Quantum Cryptography Alliance as part of the Linux Foundation.

Quickstart for Ubuntu

# Install base packages
sudo apt-get update
sudo apt-get install make gcc python3 git

# Clone mlkem-native
git clone https://github.com/pq-code-package/mlkem-native.git
cd mlkem-native

# Build and run tests
make build
make test

# The same using `tests`, a convenience wrapper around `make`
./scripts/tests all
# Show all options
./scripts/tests --help

See BUILDING.md for more information.

Applications

mlkem-native is used in libOQS of the Open Quantum Safe project, and in AWS' Cryptography library AWS-LC.

Security

All assembly in mlkem-native is constant-time in the sense that it is free of secret-dependent control flow, memory access, and instructions that are commonly variable-time, thwarting most timing side channels. C code is hardened against compiler-introduced timing side channels (such as KyberSlash³ or clangover⁴) through suitable barriers and constant-time patterns.

Absence of secret-dependent branches, memory-access patterns and variable-latency instructions is also tested using valgrind with various combinations of compilers and compilation options.

Formal Verification

We use the C Bounded Model Checker (CBMC) to prove absence of various classes of undefined behaviour in C, including out of bounds memory accesses and integer overflows. The proofs cover all C code in mlkem/* and mlkem/fips202/* involved in running mlkem-native with its C backend. See proofs/cbmc for details.

The functional correctness of core AArch64 assembly routines is established using HOL-Light and the s2n-bignum verification infrastructure. See proofs/hol_light/arm for the list of functions covered, and the proofs.

State

mlkem-native is in beta-release stage. We believe it is ready for use, and hope to spark experiments on integration into other software before issuing a stable release. If you have any feedback, please reach out! See RELEASE.md for details.

Design

mlkem-native is split into a frontend and two backends for arithmetic and FIPS202 / SHA3. The frontend is fixed, written in C, and covers all routines that are not critical to performance. The backends are flexible, take care of performance-sensitive routines, and can be implemented in C or native code (assembly/intrinsics); see mlkem/native/api.h for the arithmetic backend and mlkem/fips202/native/api.h for the FIPS-202 backend. mlkem-native currently offers three backends for C, AArch64, and x86_64 - if you'd like contribute new backends, please reach out or just open a PR.

Our AArch64 assembly is developed using the SLOTHY superoptimizer, following the approach described in the SLOTHY paper⁵: We write 'clean' assembly by hand and automate micro-optimizations (e.g. see the clean vs optimized AArch64 NTT). See dev/README.md for more details.

Usage

mlkem-native is intended as a code package: If you want to use mlkem-native, import mlkem/* into your project's source tree and build using your favourite build system. See examples/mlkem_native_as_code_package for an example. The build system provided in this repository is for development purposes only.

Can I bring my own FIPS-202?

mlkem-native relies on and comes with an implementation of FIPS202⁶. If your library has its own FIPS-202 implementation, you can use it instead of the one shipped with mlkem-native: Replace mlkem/fips202/* by your FIPS-202 implementation, and make sure to include replacements for the headers mlkem/fips202/fips202.h and mlkem/fips202/fips202x4.h and the functionalities specified therein. See FIPS202.md for details, and examples/bring_your_own_fips202 for an example using tiny_sha3⁷.

Do I need to use the assembly backends?

No. If you want a C-only build, just omit the directories mlkem/native and/or mlkem/fips202/native from your import and unset MLK_CONFIG_USE_NATIVE_BACKEND_ARITH and/or MLK_CONFIG_USE_NATIVE_BACKEND_FIPS202 in your config.h.

Do I need to setup CBMC to use mlkem-native?

No. While we recommend that you consider using it, mlkem-native will build + run fine without CBMC -- just make sure to include cbmc.h and have CBMC undefined. In particular, you do not need to remove all function contracts and loop invariants from the code; they will be ignored unless CBMC is set.

Does mlkem-native support all security levels of ML-KEM?

Yes. The security level is a compile-time parameter configured by setting MLK_CONFIG_PARAMETER_SET=512/768/1024 in config.h. If your library/application requires multiple security levels, you can build + link three instances of mlkem-native while sharing common code; this is called a 'multi-level build' and is demonstrated in examples/multilevel_build.

Can I bring my own backend?

Yes, you can add further backends for ML-KEM native arithmetic and/or for FIPS-202. Follow the existing backends as templates or see examples/custom_backend for a minimal example how to register a custom backend.

Have a Question?

If you think you have found a security bug in mlkem-native, please report the vulnerability through Github's private vulnerability reporting. Please do not create a public GitHub issue.

If you have any other question / non-security related issue / feature request, please open a GitHub issue.

Contributing

If you want to help us build mlkem-native, please reach out. You can contact the mlkem-native team through the PQCA Discord. See also CONTRIBUTING.md.

Footnotes

1. National Institute of Standards and Technology: FIPS 203 Module-Lattice-Based Key-Encapsulation Mechanism Standard, https://csrc.nist.gov/pubs/fips/203/final ↩

2. Bos, Ducas, Kiltz, Lepoint, Lyubashevsky, Schanck, Schwabe, Seiler, Stehlé: CRYSTALS-Kyber C reference implementation, https://github.com/pq-crystals/kyber/tree/main/ref ↩

3. Bernstein, Bhargavan, Bhasin, Chattopadhyay, Chia, Kannwischer, Kiefer, Paiva, Ravi, Tamvada: KyberSlash: Exploiting secret-dependent division timings in Kyber implementations, https://kyberslash.cr.yp.to/papers.html ↩

4. Antoon Purnal: clangover, https://github.com/antoonpurnal/clangover ↩

5. Abdulrahman, Becker, Kannwischer, Klein: Fast and Clean: Auditable high-performance assembly via constraint solving, https://eprint.iacr.org/2022/1303 ↩

6. National Institute of Standards and Technology: FIPS202 SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, https://csrc.nist.gov/pubs/fips/202/final ↩

7. Markku-Juhani O. Saarinen: tiny_sha3, https://github.com/mjosaarinen/tiny_sha3 ↩