From 0fb89e9a43b2db8af49cf68c883f996b7c315fd0 Mon Sep 17 00:00:00 2001
From: Paul Duncan <pabs@pablotron.org>
Date: Sat, 7 Oct 2023 12:53:59 -0400
Subject: add content/posts/2023-10-07-c11-fips203ipd.md
---
content/posts/2023-10-07-c11-fips203ipd.md | 193 +++++++++++++++++++++++++++++
1 file changed, 193 insertions(+)
create mode 100644 content/posts/2023-10-07-c11-fips203ipd.md
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"
--
cgit v1.2.3