C11 FIPS 203 IPD

October 7, 2023

For fun and also to provide feedback during the draft phase, I created a C11 implementation of the FIPS 203 initial public draft (IPD).

FIPS 203 is a slightly modified version of Kyber, and will (eventually) become NIST’s standarized post-quantum key encapsulation mechanism (KEM).

Features

  • Full implementation of all three parameter sets from the FIPS 203 initial public draft.
  • C11, no external dependencies (other than the standard library).
  • Test suite w/ common sanitizers enabled (make test).
  • Doxygen-friendly API documentation (fips203ipd.h). Also available online here.
  • short example application (examples/0-hello-kem/).

Git Repository

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, by Dan Bernstein (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 as examples/0-hello-kem/.

Example Source Code

//
// 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;
  }
}

Example Output

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

> ./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.

 

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.

C11 SHA-3

September 5, 2023

This weekend I put together a C11 implementation of the following SHA-3 algorithms from FIPS 202 and SP 800-185:

  • SHA3-224, SHA3-256, SHA3-384, and SHA3-512
  • HMAC-SHA3-224, HMAC-SHA3-256, HMAC-SHA3-384, and HMAC-SHA3-512
  • SHAKE128, SHAKE128-XOF, SHAKE256, and SHAKE256-XOF
  • cSHAKE128, cSHAKE128-XOF, cSHAKE256, and cSHAKE256-XOF
  • KMAC128, KMAC128-XOF, KMAC256, and KMAC256-XOF
  • TupleHash128, TupleHash128-XOF, TupleHash256, and TupleHash256-XOF
  • ParallelHash128, ParallelHash128-XOF ParallelHash256, and ParallelHash256-XOF
  • TurboSHAKE128 and TurboSHAKE256
  • KangarooTwelve

Git Repository, API Documentation

Features

Example

// example.c: print hex-encode sha3-256 hash of each command-line argument
//
// build:
//   cc -o example -std=c11 -O3 -W -Wall -Wextra -Werror -pedantic -march=native -mtune=native example.c sha3.c
#include <stdint.h> // uint8_t
#include <stdio.h> // printf()
#include <string.h> // strlen()
#include "sha3.h" // sha3_256()

// print hex-encoded buffer to stdout.
static void print_hex(const uint8_t * const buf, const size_t len) {
  for (size_t i = 0; i < len; i++) {
    printf("%02x", buf[i]);
  }
}

int main(int argc, char *argv[]) {
  // loop over command-line arguments
  for (int i = 1; i < argc; i++) {
    // hash argument
    uint8_t buf[32] = { 0 };
    sha3_256((uint8_t*) argv[i], strlen(argv[i]), buf);

    // print argument and hex-encoded hash
    printf("\"%s\",", argv[i]);
    print_hex(buf, sizeof(buf));
    fputs("\n", stdout);
  }

  // return success
  return 0;
}

 

Output:

> ./example asdf foo bar
"asdf",dd2781f4c51bccdbe23e4d398b8a82261f585c278dbb4b84989fea70e76723a9
"foo",76d3bc41c9f588f7fcd0d5bf4718f8f84b1c41b20882703100b9eb9413807c01
"bar",cceefd7e0545bcf8b6d19f3b5750c8a3ee8350418877bc6fb12e32de28137355

 

Update (2023-09-07): Released v0.2 with TurboSHAKE128, TurboSHAKE256, KangarooTwelve, and an examples/ directory.

Update (2023-09-18): Released v0.3 with AVX-512 support (~3x faster) and miscellaneous small fixes.

Update (2023-10-15): Released v0.4 with lots of documentation improvements.

Update (2023-10-19): Released v0.5 with more documentation improvements and additional examples. added online API documentation.

End of May Miscellany

June 2, 2023

Bookworm Upgrades

I upgraded several more systems to Bookworm, including a Raspberry Pi 4 Model B 4GB and a Raspberry Pi Zero W.

All of the upgrades have gone smoothly except for the Pi Zero W, which failed with “Illegal instruction” errors during dist-upgrade and left the system unbootable in two separate upgrade attempts.

I don’t know if this is a pre-release issue with Bookworm or if this particular Pi Zero W is starting to fail. In either case, be sure to back up your SD card before trying to upgrade a Pi Zero Ws to Bookworm.

PNG Compressors

I tried the following PNG compressors on a set of several dozen screenshots:

  • pngcrush: Lossless PNG compression command-line tool.
  • optipng: Lossless multi-format image compression command-line tool.
  • pngquant: Lossy PNG compression command-line tool and library.

pngquant produced the smallest output images. The results were also visually indistinguishable from the source images, at least for my use case. Of the two lossless encoders, optipng produced marginally smaller images than pngcrush.

(The bitmap images on this site are served as lossless WebPs with PNG as a fallback, courtesy of the <picture> element).

Domain Registrar

I’ve been considering switching to another domain registrar for a few years. The recent .zip TLD tizzy seemed like a perfect opportunity to register a new domain through a different registrar. I’d heard good things about Namecheap, so I created an account and registered my shiny new .zip domain: fdsa.zip.

Thoughts on Namecheap so far:

  • Good prices.
  • Fast and simple interface. Account setup and domain registration only took a few minutes.
  • 2FA prominently located and easy to enable.
  • They haven’t sold, lost, or spammed my email address (yet).
  • DNS propagation only took 2 hours.

My next step will be to migrate several secondary domains from GoDaddy to Namecheap.

Update (2023-06-13): Last night I followed these instructions to migrate 7 secondary domains. This afternoon I migrated the remaining 6 domains.

If you disable locking, disable domain protection, and manually approve pending transfers, the entire process takes about an hour.

Solar: A Great Month

May 2, 2023

Last month our solar panels generated more energy than we consumed for the entire month. Here’s the Enphase dashboard for April:

April energy production and consumption.

April energy production and consumption.

 

Here is our latest power bill:

Power bill from March 21st to April 24th.

Power bill from March 21st to April 24th.

(Note: The date ranges in the two pictures overlap by 21 days but don’t match precisely, because our billing period is not quite monthly).

The highlighted sections of the bill above show the following:

  • The total was $7.14
  • We have an 18 kWh credit (e.g. net metering)

The kicker? Our car is electric; the bill includes the electricity for the house and the car.

Bookworm and Podman

May 2, 2023

I’ve spent the last couple days fiddling with Debian Bookworm RC2 in a VM. No issues to report. It’s shaping up to be a great release.

I’ve been looking for a suitable Docker replacement for a few years because of their repeated license shenanigans. Last year I tried switching to Podman, but ran into into several incompatibilities and minor annoyances.

Podman 4.3 ships with Bookworm and seems to fix all the issues I had before. Rootless containers, multi-stage builds, and all of my muscle-memory docker commands now work as expected. There is even a decent clone of docker-compose named (surprise!) podman-compose.

The only real differences I noticed are:

  1. The command is podman instead of docker.
  2. Image names must be registry-prefixed. Example: FROM docker.io/bash instead of FROM bash.
  3. Searches must be registry-prefixed. Example: podman search docker.io/pablotron.

A couple of quick tests:

Update (2023-05-05): I put together a simple web application named Bookman to put podman-compose through it’s paces. It uses multiple containers, multi-stage builds, boot dependencies, secrets, and volumes.

Here’s a log of the setup process, and here’s a screenshot of the exposed web interface.

Update (2023-05-13): I upgraded several VMs from Bullseye (and one from Stretch!?!) to Bookworm, without any significant issues.

After upgrading to Bookworm, I migrated two VMs from Docker to Podman and installed Podman on a third VM. Useful tip: Rootless Podman does not agree with an NFS-mounted home directory.

One workaround is to create a local (that is, non-NFS), user-owned directory and then symlink ~/.local/share/containers to it, like so:

# create local containers directory for user pabs,
# then symlink ~pabs/.local/share/containers to it.
sudo mkdir -pm 700 /data/containers/pabs && \
  sudo chown pabs:pabs /data/containers/pabs && \
  ln -s /data/containers/pabs ~pabs/.local/share/containers

 

Alternatively, the Podman man page and Storage Table section of the storage.conf documentation suggest editing the graphroot in ~/.config/containers/storage.conf and pointing at a local directory.

Solar: One Month

November 11, 2022

Enphase dashboard for our first month of solar:

Total energy production and consumption.

Total energy production and consumption.

The blue bars represent energy produced by the solar panels. The orange bars represent energy consumed by us. The Y axis is kilowatt-hours (pay attention to the Y axis, because the dashboard rescales it).

According to the numbers above, the solar panels generated 78% (1 - 117.4/538.6 = ~0.78) of our consumed energy for the month. Virginia has net metering, so our power bill should be 21% of what it would be otherwise.

On clear, sunny days the panels generate more energy than we consume:

Energy production and consumption on a sunny day.

Energy production and consumption on a sunny day.

And in a shocking twist that will surprise no one, on cloudy days the solar panels don’t do very well:

Energy production and consumption on a cloudy day.

Energy production and consumption on a cloudy day.

Census Geocoder Released

November 11, 2022

A couple weeks ago I released census-geocoder, a Go wrapper for the Census Geocoding Services API.

Example

Here’s an example application which geocodes the command-line argument and then prints the normalized address from the geocoding result of each address to standard output:

package main

import (
  "fmt"
  "log"
  "os"
  "pablotron.org/census-geocoder/geocoder"
)

func main() {
  for _, arg := range(os.Args[1:]) {
    // get address matches
    matches, err := geocoder.Locations(arg)
    if err != nil {
      log.Fatal(err)
    }

    // print matches
    for _, match := range(matches) {
      fmt.Println(match)
    }
  }
}

 

Pico Ws

November 11, 2022

Last month I got a reel of Raspberry Pi Pico Ws. Several will eventually be paired with BME280s and used to measure temperature, humidity, and barometric pressure throughout the house.

That project will have to wait a few weeks until I can unpack my soldering iron.

In the mean time I’ve been fiddling MicroPython. My thoughts so far are below…

Ordering and Delivery

Ordering was a bit of a headache. The sites that I normally buy from all had one or more of the following annoyances:

  • Ridiculous markup
  • Outrageous shipping fees
  • Comically low quantity limit

The Pico and Pico W are not supply chain constrained like the Raspberry Pi 4B and Raspberry Pi Zero 2 W, so I’m not sure why retailers are doing this.

I finally checked DigiKey, and they had plenty of Pico Ws in stock and none of the aforementioned shenanigans. I ordered a reel of 20 Pico Ws for $6.00 apiece on October 3rd. The package arrived on October 5th.

As of this writing, DigiKey still has over 15,000 Pico Ws in stock.

Hardware

Thoughts:

  • 264 kB of RAM feels quite roomy on a microcontroller.
  • Built-in wifi is incredibly useful because you don’t have to sacrifice a bunch of pins for external communication.
  • PIO looks promising, although I haven’t really used it yet.
  • The onboard temperature sensor is not very accurate.

Flashing MicroPython

Flashing via USB mass storage is great. I didn’t have to install an SDK, fight with finicky wiring, or use an obscure microcontroller flashing tool.

To get up and running with MicroPython, you can follow these instructions. The basic steps in Linux are as follows:

  1. Press the BOOTSEL button on the Pico W.
  2. Connect the Pico W to your computer via USB. It appears as USB mass storage device.
  3. Mount the mass storage device. Many distributions will automatically mount the device for you as /media/RPI-RP2.
  4. Copy a UF2 image to the mounted disk.
  5. The Pico W will flash itself and reboot.

If you’ve flashed MicroPython, then at this point you can connect to a REPL via USB serial (e.g. screen /dev/ttyACM0).

The Pico and Pico W have SWD pins, so you can still flash via SWD if you want to; instructions are available in the documentation.

MicroPython

MicroPython is fantastic. I was able to blink the onboard LED, read the onboard temperature sensor, connect to wifi, and make web requests less than an hour after unpacking the Pico W.

MicroPython v1.19.1 on 2022-10-06; Raspberry Pi Pico W with RP2040
Type "help()" for more information.
>>> led = machine.Pin('LED', machine.Pin.OUT) # get LED
>>> led.toggle() # enable LED
>>> led.value() # check status
1
>>> led.toggle() # disable LED
>>> led.value() # check status
0
>>>

 

Example: Connect to Wifi and send an HTTP request

MicroPython v1.19.1 on 2022-10-06; Raspberry Pi Pico W with RP2040
Type "help()" for more information.
>>> import network
>>> wifi = network.WLAN()
>>> wifi.active(True) # enable wifi
>>> wifi.connect('ssid', 'password') # replace 'ssid' and 'password' with your SSID and password
>>> wifi.status() # wait until wifi is connected (e.g., status = 3)
3
>>> import urequests
>>> data = urequests.get('https://pablotron.org/').content # send http request, get response body
>>> len(data) # print number of bytes received
48693

 

One useful tip: machine.unique_id() returns a unique ID for the device. This is useful because it allows you to flash the same image to several Pico Ws and then use machine.unique_id() to uniquely identify them. Example:

>>> import binascii
>>> binascii.hexlify(machine.unique_id())
b'e6614c311b867937'

 

Miscellaneous MicroPython notes:

Pictures

Reel of Raspberry Pi Pico Ws.

Reel of Raspberry Pi Pico Ws.

Individual Pico W.

Individual Pico W.

Advanced Pico W testing facility.

Advanced Pico W testing facility.

Description of the last picture:

Solar Panels Are Live

October 10, 2022

Last week we received permission to operate from Dominion, and this afternoon we got the final go-ahead from Solar Energy World.

Here’s a screenshot of the Enphase energy dashboard for the day:

First day of solar.

First day of solar.

Update (2022-11-11): New post with array performance for the first month.

Solar Panel Updates

October 1, 2022

Video of our solar panels:

Solar panels (video).

Solar panels (video).

The permit was approved on September 21st and our meter is in the net metering queue:

From: ...@dominionenergy.com
Sent: Friday, September 30, 2022 10:34 AM                                    
Subject: RE: Interconnection Certificate of Completion for Paul Duncan       
                                                                                
Reprogramed: A meter exchange schedule is being set for the week of 10/3
for this project. This exchange will be an over-the-air programmed
conversion and not physical.  If there are no issues with the
exchange, we will forward a PTO letter in the next 1 to 2 days.
Please let us know if you have any questions.

Kindest Regards

Net Metering
600 East Canal Street, 11^th Flr.
Richmond, VA 23219
Email: ...@dominionenergy.com

Enphase provides an optional, publicly-visible URL with solar array details and energy production. I set up a redirect here:

https://pmdn.org/solar

P.S. Here’s the high-tech method we used to create the video above:

Advanced Phone-Taped-on-Stick™ technology (patent pending).

Advanced Phone-Taped-on-Stick™ technology (patent pending).

Archived Posts...
© 1998-2023 Paul Duncan