Lukas' weblog

✍️ Written on 2022-09-07 in 1655 words.
Part of cs IT-security pqcrypto software-development programming-languages rustlang

Motivation

Ok, a patch release does not need its own blog post, but I want to talk about a major release. As a 2.0 release, we changed the public API. This is a followup to my classic-mceliece-rust 1.0 blogpost.

In this blogpost I describe the 2.0 API for classic-mceliece-rust, a pure-rust implementation of the Classic McEliece KEM. I would like to emphasize that most work was not done by me, but wonderful maintainers/contributors @Colfenor, @dkales, and @faern.

classic-mceliece-rust

Goals of the 2.0 release

issues #12, #11: The goal of the 1.0 release was correctness. Thus we implemented the C API analogously in rust for the easiest comparison possible for any subcomponents. Obviously this C API does not follow rust idioms.
issue #14: RustCrypto is an interesting project where contributors define generic traits for cryptographic components. Trait implementations provide exchangability for implementations. This is a necessary property since cryptographic advancements can easily render algorithms deprecated. Simultaneously you don’t want regular developers to write cryptographic code. Thus you need well-defined interfaces and what better approach exists to unite an entire community behind one project. When it comes to PQC, the interfaces are pretty new and in this 2.0 release, we only assume/implement the RNG interfaces.

A big question

One of the big questions to me is the stack versus heap discussion. Fundamentally, performant code is usually written following the “use the stack whenever possible” paradigm. If there is no sensible way to make it work on the stack, use the heap. Memory management on the heap is more expensive than on the stack. On some microcontroller platforms, a heap is not even available. From a conceptual perspective, public keys can be easily stored on the the stack since we know its size at compile time.

In the case of Classic McEliece the public key has a size between 255 KB and 1.3 MB depending on the variant. @faern reports that Windows' default stack size does not permit such an allocation.

So if we require heap allocations, you might lose performance and exclude some platforms. If we use stack allocations, we might run into OS limitations and the API is less ergonomic.

As a result, we picked both. rust allows us to provide boxed functions as part of the API, if the alloc feature is enabled. If the feature is disabled, only the stack allocation API is available.

stack API

So you have two options now. First of all, I want to give an example for the stack-based API.

[package]
name = "cme-example"
version = "0.1.0"
edition = "2021"

[dependencies]
rand = "0.8.5"
classic-mceliece-rust = { version = "2.0", default-features = false, features = ["mceliece460896"] }

We need the rand crate for random number generation.

As one can see, we still provide feature flags to enable the different variants of CME. The smallest variant mceliece348864 is enabled per default, but we explicitly select a different one. Furthermore we disable the default features to exclude the alloc feature which provides the heap-allocation API.

use classic_mceliece_rust::{keypair, encapsulate, decapsulate};
use classic_mceliece_rust::{CRYPTO_BYTES, CRYPTO_PUBLICKEYBYTES, CRYPTO_SECRETKEYBYTES};

Now we import the three functions for the three KEM steps. The names are simple keywords compared to the previous API. The constants were the same in the previous API.

fn main() {
  let mut rng = rand::thread_rng();

  // Please mind that `public_key_buf` is very large.
  let mut public_key_buf = [0u8; CRYPTO_PUBLICKEYBYTES];
  let mut secret_key_buf = [0u8; CRYPTO_SECRETKEYBYTES];
  let (public_key, secret_key) = keypair(&mut public_key_buf, &mut secret_key_buf, &mut rng);

  let mut shared_secret_bob_buf = [0u8; CRYPTO_BYTES];
  let (ciphertext, shared_secret_bob) = encapsulate(&public_key, &mut shared_secret_bob_buf, &mut rng);

  let mut shared_secret_alice_buf = [0u8; CRYPTO_BYTES];
  let shared_secret_alice = decapsulate(&ciphertext, &secret_key, &mut shared_secret_alice_buf);

  assert_eq!(shared_secret_bob.as_array(), shared_secret_alice.as_array());
}

public means that data can be shared with everyone. secret means that a party must keep the data private. And we separate the parties by their names alice and bob.

default/heap/alloc API

In this case, we need the alloc feature provided per default.

[package]
name = "cme-example"
version = "0.1.0"
edition = "2021"

[dependencies]
rand = "0.8.5"
classic-mceliece-rust = { version = "2.0", features = ["mceliece460896"] }

Since we don’t allocate manually, we don’t need constants telling us the size. Instead we only use the *_boxed functions for the three KEM steps providing the API:

use classic_mceliece_rust::{keypair_boxed, encapsulate_boxed, decapsulate_boxed};

In our example, we want to run the computation in a separate thread. The thread runs the run_kem function. This also makes the stack size explicit.

fn run_kem() {
  let mut rng = rand::thread_rng();

  // Alice computes the keypair
  let (public_key, secret_key) = keypair_boxed(&mut rng);

  // Send `secret_key` over to Bob.
  // Bob computes the shared secret and a ciphertext
  let (ciphertext, shared_secret_bob) = encapsulate_boxed(&public_key, &mut rng);

  // Send `ciphertext` back to Alice.
  // Alice decapsulates the ciphertext …
  let shared_secret_alice = decapsulate_boxed(&ciphertext, &secret_key);

  // … and ends up with the same key material as Bob.
  assert_eq!(shared_secret_bob.as_array(), shared_secret_alice.as_array());
}

fn main() {
  std::thread::Builder::new()
    .stack_size(900_000) // about 1.7 times the public key size
    .spawn(run_kem)
    .unwrap()
    .join()
    .unwrap();
}

Conclusion

It seems like Mullvad VPN wants to use our implementation which resulted in increasing attention for our crate. It is nice to see this collaboration. Thanks!

classic-mceliece-rust 2.0