Kemeleon: Obfuscated ML-KEM Encodings

This crates implements the kemeleon algorithms for secure obfuscation of ML-KEM Encapsulation Keys their corresponding Ciphertext responses which would otherwise be trivially distinguishable from bytes sampled from a uniform random source.

The original algorithm designs and security proofs can be found in the Obfuscated Key Exchange paper written by Felix Günther (IBM Research Europe – Zurich), Douglas Stebila (University of Waterloo), Shannon Veitch (ETH Zurich).

⚠️ Security Warning

🚧 UNDER CONSTRUCTION 🚧 This library is in a devloping (non-stable) condition, meaning that things will likely change. This includes API, interface, algorithms, etc. -- Feedback is welcome, but we do not guarantee support for any features / interface as currently implemented.

Usage

use kemeleon::MlKem512;
use kem::{Encapsulate, Decapsulate};

let mut rng = rand::thread_rng();
let (dk, ek) = MlKem512::generate(&mut rng);

// // Converting the Encapsulation key to bytes and back in order to be sent.
// let ek_encoded: Vec<u8> = ek.as_bytes().to_vec();

let (ct, k_send) = ek.encapsulate(&mut rng).unwrap();

// // Converting the ciphertext to bytes and back in order to be sent.
// let ct = Ciphertext::<MlKem512>::from_bytes(ct);

let k_recv = dk.decapsulate(&ct).unwrap();
assert_eq!(k_send, k_recv);

Why?

This library implements obfuscating encoding schemes for ML-KEM encapsulation keys and ciphertext messages such that they are computationally indistinguishable from random by a passive observer.

Why aren't the NTT encodings from the FIPS spec (ByteEncode_d(F), ByteDecode_d(B), etc.) sufficient?

The wire format of the encapsulation key is trivially distinguishable from uniform random becuase they values are 12 bit values where all are computed mod Q. Thus all values are 12 bits, but always less than 3329.

Minimum Supported Rust Version (MSRV)

The Minimum Supported Rust Versions (MSRV) for this crate is Rust 1.81 (currently forced by the hybrid-array dependency). This minumum version will be ensured by the test and build steps in the CI pipeline.

Going forward, the MSRV can be changed at any time, but it will be done with a minor version bump. We will not increase MSRV on PATCH releases, though downstream dependencies might.

Once this crate reaches a stable state we won't increase MSRV just because we can: we'll only do so when we have a reason. (We don't guarantee that you'll agree with our reasoning; only that it will exist.)

Roadmap

Core features

• Public interface first pass
• Interface with ml_kem
• Implement complete Encapsulation Key encoding / decoding
• Implement and test ciphertext encoding / decoding
• Pass on public docs
• Switch from using std::io::Error to a locally defined error type.
• Ciphertext encoding determinism using hkdf, hmac-drbg, or something similar
• Modify implementation to be no-std compatible
  • Swap from custom error to &str error just for simplicity (core::error::Error is too new)
• GH actions for testing, building, linting, etc.
• Use hybrid-array for all type based generics requiring sized arrays
  • Move const generics (#![feature(generics_const_exprs)]) to its own branch
    • const generics are an unstable feature, even though this is a very simple application of the feature it is bad practice to ask people use it in its current state.
  • CI tests/builds for stable releases (const generics only work on nightly)
• Nist vectors Integration tests

Cleanup -> Release 0.1.0-alpha

• Polish public interface and docs for first release
• Github actions release workflow

Heading to Release 0.1.1-alpha

• work up PR(s) for ml-kem
  • expose internal things under a dev feature
• remove as much repeated functionality as possible
• revisit secure deterministic random byte generation