path: root/content/posts/2023-10-07-c11-fips203ipd.md

---
slug: C11 Implementation of FIPS 203 IPD
title: "C11 FIPS 203 IPD"
date: "2023-10-07T12:19:48-04:00"
---
For fun and also to provide feedback during the draft phase, I created a
[C11][] implementation of the [FIPS 203 initial public draft
(IPD)][fips203ipd].

[FIPS 203][fips203ipd] is a slightly modified version of [Kyber][], and
will (eventually) become [NIST's][nist] standarized post-quantum [key
encapsulation mechanism (KEM)][kem].

### Features

* Full implementation of all three parameter sets from the [FIPS 203
  initial public draft][fips203ipd].
* [C11][], no external dependencies (other than the standard library).
* Constant-time [Barrett reduction][].  Not vulnerable to [KyberSlash][].
* Test suite w/ common sanitizers enabled (`make test`).
* Doxygen-friendly API documentation (`fips203ipd.h`).  Also available
  online [here][api-docs].
* Short example application (`examples/0-hello-kem/`).
* Independent implementation. Not based on other libraries.

[Git Repository][github], [API Documentation][api-docs]

**Note:** This is an initial release based on the draft standard with no
real optimization; it is probably slower than other implementations.

**Another Note:** Worth reading before relying on any [Kyber][]
implementation: [2020.10.03: The inability to count
correctly][djb-kyber], by [Dan Bernstein (djb)][djb].

## Example

Below is the source code and output of a minimal [C11][] example
application which demonstrates the following:

1. Alice generates a random KEM512 encapsulation/decapsulation key pair.
2. Alice sends the encapsulation key to Bob.
3. Bob uses the encapsulation key sent by Alice to encapsulate a random shared secret as ciphertext.
4. Bob sends the ciphertext to Alice.
5. Alice uses the decapsulation key to decapsulate the shared secret from the ciphertext sent by Bob.
6. Application verifies that the shared secrets from steps #3 and #5 match.

This example is also included in the [git repository][github] as
`examples/0-hello-kem/`.

### Example Source Code

```c
//
// hello.c: minimal example of a two parties "alice" and "bob"
// generating a shared secret with KEM512.
//
// Build by typing `make` and run by typing `./hello`.
//

#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 decapsultion 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: example only; memcmp() is 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;
  }
}
```

### Example Output

Output of `./hello` with longer lines truncated for brevity:

```sh
> ./hello
alice: keygen random (64 bytes) = d656012a9eb09aa50e77a205188f0156e98276a584dcc11c2dfef0c06003ca38b233fab93e9f8dd5adec32278c8d091190112285b7389510bd610ec7b23376b2
alice: generated encapsulation key `ek` and decapsulation key `dk`:
alice: ek (800 bytes) = af3b0497f6 ... (omitted) ... 31f0f62cbd
alice: dk (1632 bytes) = e598a49eb0 ... (omitted) ... c06003ca38
alice: sending encapsulation key `ek` to bob

bob: encaps random (32 bytes) = 0db6c39742ba8cb8d9a1c437d62fed4c7fa04e944a47a73a94426dd3c33e6213
bob: generated secret `b_key` and ciphertext `ct`:
bob: b_key (32 bytes) = 32c9eb490db7e8500d9b209d78a9367fd73a967d8d58edff8655273c8d4ce8d5
bob: ct (768 bytes) = bd39ae1157 ... (omitted) ... 9b5751fc34
bob: sending ciphertext `ct` to alice

alice: used `dk` to decapsulate secret from `ct` into `a_key`:
alice: a_key (32 bytes) = 32c9eb490db7e8500d9b209d78a9367fd73a967d8d58edff8655273c8d4ce8d5

SUCCESS! alice secret `a_key` and bob secret `b_key` match.
```
&nbsp;

**Update (2023-10-10):** Fixed typos, added rationale to intro, and
added a brief explanation to the example section.

**Update (2023-10-19):** Released v0.2 with documentation improvements,
speed improvements, a new example, and [online API
documentation][api-docs].

**Update (2024-02-14):** Added [Barrett reduction][] and independent
implementation to feature list.  Minor wording fixes.

**Update (2024-03-04):** Released v0.3.  Added [AVX-512][] polynomial
arithmetic, speed improvements, the [NIST draft ML-KEM test
vectors][nist-tests], and documentation updates.

**Update (2024-04-08):** Released v0.4.  Added [AVX-512][] NTT and
inverse NTT, add "Benchmarks" and "AVX-512 Backend" sections to
README.md.

**Update (2024-04-28):** Released v0.5.  Much faster ([AVX-512][]: ~27%
reduction in median CPU cycles, scalar: ~13% reduction in median CPU
cycles), code cleanup, internal documentation improvements.

**Update (2024-05-15):** Released v0.6.  Added [Neon][] backend, backend
auto-detection, test suite MacOS support, [Raspberry Pi 5][pi5]
benchmarks, documentation improvements.

[c11]: https://en.wikipedia.org/wiki/C11_(C_standard_revision)
  "ISO/IEC 9899:2011"
[SHA-3]: https://en.wikipedia.org/wiki/SHA-3
  "Secure Hash Algorithm 3"
[sha3-mine]: https://github.com/pablotron/sha3
  "My FIPS 202 (SHA-3) implementation."
[fips203ipd]: https://csrc.nist.gov/pubs/fips/203/ipd
  "FIPS 203 (Initial Public Draft): Module-Lattice-Based Key-Encapsulation Mechanism Standard"
[fips202]: https://csrc.nist.gov/pubs/fips/202/final
  "SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions"
[pqc-forum-decode-comment]: https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/ZRQvPT7kQ51NIRyJ%40disp3269
  "pqc-forum mailing list discussion about reducing coefficients modulo Q during deserialization."
[nist]: https://nist.gov/
  "National Institute of Standards and Technology"
[kyber]: https://pq-crystals.org/kyber/
  "Kyber: post-quantum key encapsulation mechanism based on the hardness of the module learning with errors (m-LWE) problem."
[kem]: https://en.wikipedia.org/wiki/Key_encapsulation_mechanism
  "Key encapsulation mechanism."
[gcc]: https://en.wikipedia.org/wiki/GNU_Compiler_Collection
  "GNU Compiler Collection."
[clang]: https://en.wikipedia.org/wiki/Clang
  "LLVM compiler front end."
[github]: https://github.com/pablotron/fips203ipd
  "fips203ipd github repository."
[djb-kyber]: https://blog.cr.yp.to/20231003-countcorrectly.html
  "2023.10.03: The inability to count correctly, by Dan Bernstein."
[djb]: https://en.wikipedia.org/wiki/Daniel_J._Bernstein
  "Daniel J. Bernstein"
[api-docs]: https://pmdn.org/api-docs/fips203ipd/
  "online API documentation"
[kyberslash]: kyberslash.cr.yp.to/
  "Timing vulnerability in many implementations of Kyber and FIPS203"
[barrett reduction]: https://en.wikipedia.org/wiki/Barrett_reduction
  "Barrett modular reduction"
[nist-tests]: https://csrc.nist.gov/Projects/post-quantum-cryptography/post-quantum-cryptography-standardization/example-files
  "NIST: Intermediate Values for draft ML-KEM and draft ML-DSA"
[avx-512]: https://en.wikipedia.org/wiki/AVX-512
  "Advanced Vector Extensions (AVX) SIMD instructions."
[neon]: https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)
  "Advanced SIMD extension for ARM CPUs"
[pi5]: https://en.wikipedia.org/wiki/Raspberry_Pi
  "Raspberry Pi"