From 0fb89e9a43b2db8af49cf68c883f996b7c315fd0 Mon Sep 17 00:00:00 2001 From: Paul Duncan 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 // fputs() +#include // 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