add content/posts/2023-10-07-c11-fips203ipd.md

1 files changed, 193 insertions, 0 deletions

diff --git a/content/posts/2023-10-07-c11-fips203ipd.md b/content/posts/2023-10-07-c11-fips203ipd.md
new file mode 100644
index 0000000..cacd82e
--- /dev/null
+++ b/content/posts/2023-10-07-c11-fips203ipd.md
@@ -0,0 +1,193 @@
+---
+slug: C11 Implementation of FIPS 203 IPD
+title: "C11 FIPS 203"
+date: "2023-10-07T12:19:48-04:00"
+---
+I created a [C11][] implementation of the KEM512, KEM768, and KEM1024
+parameter sets from the [FIPS 203 initial public draft
+(IPD)][fips203ipd].
+
+[FIPS 203][fips203ipd] is (or will be) [NIST's][nist] standardized
+version of [Kyber][], a 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
+* Test suite w/ common sanitizers enabled (`make test`)
+* API documentation (`fips203ipd.h`)
+* short example application (`examples/0-hello-kem/`).
+
+[Git Repository][github]
+
+**Note:** This is an initial release based on the draft standard with no
+real optimization; it is slow and memory-intensive.
+
+**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
+
+This example application is also included in the [git
+repository][github] as `examples/0-hello-kem/`.
+
+### Source
+
+```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
+  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;
+  }
+}
+```
+
+### Output
+
+Output of `./hello` with longer lines truncated for brevity:
+
+```sh
+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.
+```
+
+### 
+
+[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 Institutes of Science 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"