fips203ipd
C11 implementation of FIPS 203 initial public draft (IPD).
fips203ipd

Embeddable, dependency-free C11 implementation of ML-KEM from the FIPS 203 initial public draft (IPD) with scalar and AVX-512 backends.

FIPS 203 is (or will be) NIST's standardized version of Kyber, a post-quantum key encapsulation mechanism (KEM).

Notes on this implementation:

Use make to build a minimal self test application, make doc to build the HTML-formatted API documentation, and make test to run the test suite.

Example

Minimal example of Alice and Bob exchanging a shared secret with KEM512:

//
// hello.c: minimal example of a two parties "alice" and "bob"
// generating a shared secret with KEM512.
//
#include <stdio.h> // fputs()
#include <string.h> // memcmp()
#include "hex.h" // hex_write()
#include "rand-bytes.h" // rand_bytes()
#include "fips203ipd.h" // fips203ipd_*()
int main(void) {
//
// alice: generate keypair
//
uint8_t ek[FIPS203IPD_KEM512_EK_SIZE] = { 0 }; // encapsulation key
uint8_t dk[FIPS203IPD_KEM512_DK_SIZE] = { 0 }; // decapsulation key
{
// alice: get 64 random bytes for keygen()
uint8_t keygen_seed[64] = { 0 };
rand_bytes(keygen_seed, sizeof(keygen_seed));
fputs("alice: keygen random (64 bytes) = ", stdout);
hex_write(stdout, keygen_seed, sizeof(keygen_seed));
fputs("\n", stdout);
// alice: generate encapsulation/decapsulation key pair
fips203ipd_kem512_keygen(ek, dk, keygen_seed);
}
fputs("alice: generated encapsulation key `ek` and decapsulation key `dk`:\n", stdout);
printf("alice: ek (%d bytes) = ", FIPS203IPD_KEM512_EK_SIZE);
hex_write(stdout, ek, sizeof(ek));
printf("\nalice: dk (%d bytes) = ", FIPS203IPD_KEM512_DK_SIZE);
hex_write(stdout, dk, sizeof(dk));
fputs("\n", stdout);
// alice send `ek` to bob
fputs("alice: sending encapsulation key `ek` to bob\n\n", stdout);
//
// bob: generate shared secret and ciphertext
//
uint8_t b_key[32] = { 0 }; // shared secret
uint8_t ct[FIPS203IPD_KEM512_CT_SIZE] = { 0 }; // ciphertext
{
// bob: get 32 random bytes for encaps()
uint8_t encaps_seed[32] = { 0 };
rand_bytes(encaps_seed, sizeof(encaps_seed));
fputs("bob: encaps random (32 bytes) = ", stdout);
hex_write(stdout, encaps_seed, sizeof(encaps_seed));
fputs("\n", stdout);
// bob:
// 1. get encapsulation key `ek` from alice.
// 2. generate random shared secret.
// 3. use `ek` from step #1 to encapsulate the shared secret from step #2.
// 3. store the shared secret in `b_key`.
// 4. store the encapsulated shared secret (ciphertext) in `ct`.
fips203ipd_kem512_encaps(b_key, ct, ek, encaps_seed);
}
fputs("bob: generated secret `b_key` and ciphertext `ct`:\nbob: b_key (32 bytes) = ", stdout);
hex_write(stdout, b_key, sizeof(b_key));
printf("\nbob: ct (%d bytes) = ", FIPS203IPD_KEM512_CT_SIZE);
hex_write(stdout, ct, sizeof(ct));
fputs("\n", stdout);
// bob sends ciphertext `ct` to alice
fputs("bob: sending ciphertext `ct` to alice\n\n", stdout);
//
// alice: decapsulate shared secret
//
// alice:
// 1. get ciphertext `ct` from bob.
// 2. use decapsulation key `dk` to decapsulate shared secret from `ct`.
// 2. store shared secret in `a_key`.
uint8_t a_key[32] = { 0 };
fips203ipd_kem512_decaps(a_key, ct, dk);
fputs("alice: used `dk` to decapsulate secret from `ct` into `a_key`:\nalice: a_key (32 bytes) = ", stdout);
hex_write(stdout, a_key, sizeof(a_key));
fputs("\n\n", stdout);
// check result
// (note: don't use memcmp() in real applications; it's not constant-time)
if (!memcmp(a_key, b_key, sizeof(a_key))) {
// success: alice and bob have the same shared secret
fputs("SUCCESS! alice secret `a_key` and bob secret `b_key` match.\n", stdout);
return 0;
} else {
// failure: alice and bob do not have the same shared secret
fputs("FAILURE! alice secret `a_key` and bob secret `b_key` do not match.\n", stdout);
return -1;
}
}
C11 implementation of ML-KEM from the FIPS 203 initial public draft.
#define FIPS203IPD_KEM512_DK_SIZE
Size of KEM512 decapsulation key, in bytes (768 * K + 96).
Definition: fips203ipd.h:79
#define FIPS203IPD_KEM512_CT_SIZE
Size of KEM512 ciphertext, in bytes (32 * (DU * K + DV)).
Definition: fips203ipd.h:85
#define FIPS203IPD_KEM512_EK_SIZE
Size of KEM512 encapsulation key, in bytes (384 * K + 32).
Definition: fips203ipd.h:73
void fips203ipd_kem512_keygen(uint8_t ek[static FIPS203IPD_KEM512_EK_SIZE], uint8_t dk[static FIPS203IPD_KEM512_DK_SIZE], const uint8_t seed[static FIPS203IPD_KEYGEN_SEED_SIZE])
Generate KEM512 encapsulation key ek and decapsulation key dk from 64 byte random seed seed.
void fips203ipd_kem512_encaps(uint8_t key[static FIPS203IPD_KEY_SIZE], uint8_t ct[static FIPS203IPD_KEM512_CT_SIZE], const uint8_t ek[static FIPS203IPD_KEM512_EK_SIZE], const uint8_t seed[static FIPS203IPD_ENCAPS_SEED_SIZE])
Generate KEM512 shared key key and ciphertext ct from given encapsulation key ek and randomness seed.
void fips203ipd_kem512_decaps(uint8_t key[static FIPS203IPD_KEY_SIZE], const uint8_t ct[static FIPS203IPD_KEM512_CT_SIZE], const uint8_t dk[static FIPS203IPD_KEM512_DK_SIZE])
Decapsulate shared key key from ciphertext ct using KEM512 decapsulation key dk with implicit rejecti...

See examples/0-hello-kem/ for the full buildable example, including a Makefile and support files.

Documentation

API documentation is available online here and also in fips203ipd.h. If you have Doxygen installed, you can build HTML-formatted API documentation by typing make doc.

Tests

Use make test to build and run the test suite.

The test suite checks each component of this implementation for expected answers and is built with common sanitizers supported by both GCC and Clang. The source code for the test suite is embedded at the bottom of fips203ipd.c behind a TEST_FIPS203IPD define.

You can also build a quick test application by typing make in the top-level directory. The test application does the following 1000 times for each parameter set:

  1. Generate a random encapsulation/decapsulation key pair.
  2. Encapsulate a secret using the encapsulation key.
  3. Decapsulate the secret using the decapsulation key.
  4. Verify that the secrets generated in steps #2 and #3 match.

Usage

There are safer and faster alternatives, but if you want to use this library anyway:

  1. Copy fips203ipd.h and fips203ipd.c into your source tree.
  2. Update your build system to compile fips203ipd.o.
  3. Include fips203ipd.h in your application.
  4. Use fips203ipd_*() functions in your code.

Benchmarks

A minimal libcpucycles-based benchmarking tool is available in examples/3-bench/. The bench tool repeatedly measures the number of CPU cycles used for the key generation, encapsulation, and decapsulation functions for each parameter set and then prints summary statistics to standard output in CSV format.

The results from running bench on a couple of my systems are available in the tables below.

Lenovo ThinkPad X1 Carbon, 6th Gen (x86-64, i7-1185G7, AVX-512 backend)

set function median mean stddev min max
kem512 keygen 26213 26366 829 25787 77486
kem512 encaps 27783 27950 933 27359 98549
kem512 decaps 36595 36805 1260 36025 106029
kem768 keygen 42545 42686 840 41834 141156
kem768 encaps 42037 42179 799 41413 99132
kem768 decaps 54145 54237 972 53241 104424
kem1024 keygen 57576 57828 1156 56668 129521
kem1024 encaps 58111 58368 1205 57193 122737
kem1024 decaps 73894 74139 1410 72419 135592

Odroid N2L (ARM64, Cortex-A73, scalar backend)

set function median mean stddev min max
kem512 keygen 246960 247080 764 245026 261638
kem512 encaps 253445 253570 738 251716 268071
kem512 decaps 356719 356873 800 355008 376107
kem768 keygen 381157 381370 1128 378007 400920
kem768 encaps 386998 387212 1106 384123 402892
kem768 decaps 529516 529751 1200 526635 555099
kem1024 keygen 552952 553232 1510 549059 574011
kem1024 encaps 550178 550473 1514 546348 570717
kem1024 decaps 733125 733417 1615 728842 757292

AVX-512 Backend

This library includes a compile-time AVX-512 backend, implemented via intrinsics. When the AVX-512 backend is enabled, the following functions are replaced with AVX-512-accelerated equivalents:

Functions Description
permute() block permutation for SHA3-256 and SHA3-512
poly_{ntt,inv_ntt}() Number-Theoretic Transform (NTT) and inverse NTT
poly_{add,sub,mul}() Polynomial arithmetic
poly_encode(), poly_encode_{11,10,5,4,1}bit() Polynomial encoding
pke{512,768,1024}_keygen_avx512() Key generation (see below)
pke{512,768,1024}_encrypt_avx512() Encryption (see below)

The AVX-512-enabled key generation and encryption functions perform coefficient sampling in stages and use the 64-bit lanes of 25 512-bit registers to permute and sample from up to 8 SHAKE128 and SHAKE256 contexts at once.

Here are how the lanes of the AVX-512 registers are used for each parameter set, function, and stage:

Parameter Set Function Stage Lane 0 Lane 1 Lane 2 Lane 3 Lane 4 Lane 5 Lane 6 Lane 7
KEM512 keygen 1 A[0,0] A[0,1] A[1,0] A[1,1] s[0] s[1] e[0] e[1]
KEM512 encrypt 1 A[0,0] A[1,0] A[0,1] A[1,1] r[0] r[1] n/a n/a
KEM512 encrypt 2 e1[0] e1[1] e2 n/a n/a n/a n/a n/a
KEM768 keygen 1 A[0,0] A[0,1] A[0,2] A[1,0] A[1,1] A[1,2] A[2,0] A[2,1]
KEM768 keygen 2 A[2,2] s[0] s[1] s[2] e[0] e[1] e[2] n/a
KEM768 encrypt 1 A[0,0] A[1,0] A[2,0] A[0,1] A[1,1] A[2,1] A[0,2] A[1,2]
KEM768 encrypt 2 A[2,2] r[0] r[1] r[2] e1[0] e1[1] e1[2] e2
KEM1024 keygen 1 A[0,0] A[0,1] A[0,2] A[0,3] A[1,0] A[1,1] A[1,2] A[1,3]
KEM1024 keygen 2 A[2,0] A[2,1] A[2,2] A[2,3] A[3,0] A[3,1] A[3,2] A[3,3]
KEM1024 keygen 3 s[0] s[1] s[2] s[3] e[0] e[1] e[2] e[3]
KEM1024 encrypt 1 A[0,0] A[1,0] A[2,0] A[3,0] A[0,1] A[1,1] A[2,1] A[3,1]
KEM1024 encrypt 2 A[0,2] A[1,2] A[2,2] A[3,2] A[0,3] A[1,3] A[2,3] A[3,3]
KEM1024 encrypt 3 r[0] r[1] r[2] r[3] e1[0] e1[1] e1[2] e1[3]
KEM1024 encrypt 4 e2 n/a n/a n/a n/a n/a n/a n/a

References

License

MIT No Attribution (MIT-0)

Copyright 2023-2024 Paul Duncan

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.