chromium/third_party/boringssl/src/crypto/mlkem/mlkem.cc

/* Copyright (c) 2024, Google Inc.
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */

#include <openssl/mlkem.h>

#include <assert.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#include <openssl/base.h>
#include <openssl/bytestring.h>
#include <openssl/mem.h>
#include <openssl/rand.h>

#include "../internal.h"
#include "../keccak/internal.h"
#include "./internal.h"


// See
// https://csrc.nist.gov/pubs/fips/203/final

static void prf(uint8_t *out, size_t out_len, const uint8_t in[33]) { … }

// Section 4.1
static void hash_h(uint8_t out[32], const uint8_t *in, size_t len) { … }

static void hash_g(uint8_t out[64], const uint8_t *in, size_t len) { … }

// This is called `J` in the spec.
static void kdf(uint8_t out[MLKEM_SHARED_SECRET_BYTES],
                const uint8_t failure_secret[32], const uint8_t *ciphertext,
                size_t ciphertext_len) { … }

// Constants that are common across all sizes.
#define DEGREE …
static const size_t kBarrettMultiplier = …;
static const unsigned kBarrettShift = …;
static const uint16_t kPrime = …;
static const int kLog2Prime = …;
static const uint16_t kHalfPrime = …;
// kInverseDegree is 128^-1 mod 3329; 128 because kPrime does not have a 512th
// root of unity.
static const uint16_t kInverseDegree = …;

// Rank-specific constants.
#define RANK768 …
static const int kDU768 = …;
static const int kDV768 = …;
#define RANK1024 …
static const int kDU1024 = …;
static const int kDV1024 = …;

constexpr size_t encoded_vector_size(int rank) { … }

constexpr size_t encoded_public_key_size(int rank) { … }

static_assert …;
static_assert …;

constexpr size_t compressed_vector_size(int rank) { … }

constexpr size_t ciphertext_size(int rank) { … }

static_assert …;
static_assert …;

scalar;

template <int RANK>
struct vector { … };

template <int RANK>
struct matrix { … };

// This bit of Python will be referenced in some of the following comments:
//
// p = 3329
//
// def bitreverse(i):
//     ret = 0
//     for n in range(7):
//         bit = i & 1
//         ret <<= 1
//         ret |= bit
//         i >>= 1
//     return ret

// kNTTRoots = [pow(17, bitreverse(i), p) for i in range(128)]
static const uint16_t kNTTRoots[128] = …;

// kInverseNTTRoots = [pow(17, -bitreverse(i), p) for i in range(128)]
static const uint16_t kInverseNTTRoots[128] = …;

// kModRoots = [pow(17, 2*bitreverse(i) + 1, p) for i in range(128)]
static const uint16_t kModRoots[128] = …;

// reduce_once reduces 0 <= x < 2*kPrime, mod kPrime.
static uint16_t reduce_once(uint16_t x) { … }

// constant time reduce x mod kPrime using Barrett reduction. x must be less
// than kPrime + 2×kPrime².
static uint16_t reduce(uint32_t x) { … }

static void scalar_zero(scalar *out) { … }

template <int RANK>
static void vector_zero(vector<RANK> *out) { … }

// In place number theoretic transform of a given scalar.
// Note that MLKEM's kPrime 3329 does not have a 512th root of unity, so this
// transform leaves off the last iteration of the usual FFT code, with the 128
// relevant roots of unity being stored in |kNTTRoots|. This means the output
// should be seen as 128 elements in GF(3329^2), with the coefficients of the
// elements being consecutive entries in |s->c|.
static void scalar_ntt(scalar *s) { … }

template <int RANK>
static void vector_ntt(vector<RANK> *a) { … }

// In place inverse number theoretic transform of a given scalar, with pairs of
// entries of s->v being interpreted as elements of GF(3329^2). Just as with the
// number theoretic transform, this leaves off the first step of the normal iFFT
// to account for the fact that 3329 does not have a 512th root of unity, using
// the precomputed 128 roots of unity stored in |kInverseNTTRoots|.
static void scalar_inverse_ntt(scalar *s) { … }

template <int RANK>
static void vector_inverse_ntt(vector<RANK> *a) { … }

static void scalar_add(scalar *lhs, const scalar *rhs) { … }

static void scalar_sub(scalar *lhs, const scalar *rhs) { … }

// Multiplying two scalars in the number theoretically transformed state. Since
// 3329 does not have a 512th root of unity, this means we have to interpret
// the 2*ith and (2*i+1)th entries of the scalar as elements of GF(3329)[X]/(X^2
// - 17^(2*bitreverse(i)+1)) The value of 17^(2*bitreverse(i)+1) mod 3329 is
// stored in the precomputed |kModRoots| table. Note that our Barrett transform
// only allows us to multipy two reduced numbers together, so we need some
// intermediate reduction steps, even if an uint64_t could hold 3 multiplied
// numbers.
static void scalar_mult(scalar *out, const scalar *lhs, const scalar *rhs) { … }

template <int RANK>
static void vector_add(vector<RANK> *lhs, const vector<RANK> *rhs) { … }

template <int RANK>
static void matrix_mult(vector<RANK> *out, const matrix<RANK> *m,
                        const vector<RANK> *a) { … }

template <int RANK>
static void matrix_mult_transpose(vector<RANK> *out, const matrix<RANK> *m,
                                  const vector<RANK> *a) { … }

template <int RANK>
static void scalar_inner_product(scalar *out, const vector<RANK> *lhs,
                                 const vector<RANK> *rhs) { … }

// Algorithm 6 from the spec. Rejection samples a Keccak stream to get
// uniformly distributed elements. This is used for matrix expansion and only
// operates on public inputs.
static void scalar_from_keccak_vartime(scalar *out,
                                       struct BORINGSSL_keccak_st *keccak_ctx) { … }

// Algorithm 7 from the spec, with eta fixed to two and the PRF call
// included. Creates binominally distributed elements by sampling 2*|eta| bits,
// and setting the coefficient to the count of the first bits minus the count of
// the second bits, resulting in a centered binomial distribution. Since eta is
// two this gives -2/2 with a probability of 1/16, -1/1 with probability 1/4,
// and 0 with probability 3/8.
static void scalar_centered_binomial_distribution_eta_2_with_prf(
    scalar *out, const uint8_t input[33]) { … }

// Generates a secret vector by using
// |scalar_centered_binomial_distribution_eta_2_with_prf|, using the given seed
// appending and incrementing |counter| for entry of the vector.
template <int RANK>
static void vector_generate_secret_eta_2(vector<RANK> *out, uint8_t *counter,
                                         const uint8_t seed[32]) { … }

// Expands the matrix of a seed for key generation and for encaps-CPA.
template <int RANK>
static void matrix_expand(matrix<RANK> *out, const uint8_t rho[32]) { … }

static const uint8_t kMasks[8] = …;

static void scalar_encode(uint8_t *out, const scalar *s, int bits) { … }

// scalar_encode_1 is |scalar_encode| specialised for |bits| == 1.
static void scalar_encode_1(uint8_t out[32], const scalar *s) { … }

// Encodes an entire vector into 32*|RANK|*|bits| bytes. Note that since 256
// (DEGREE) is divisible by 8, the individual vector entries will always fill a
// whole number of bytes, so we do not need to worry about bit packing here.
template <int RANK>
static void vector_encode(uint8_t *out, const vector<RANK> *a, int bits) { … }

// scalar_decode parses |DEGREE * bits| bits from |in| into |DEGREE| values in
// |out|. It returns one on success and zero if any parsed value is >=
// |kPrime|.
static int scalar_decode(scalar *out, const uint8_t *in, int bits) { … }

// scalar_decode_1 is |scalar_decode| specialised for |bits| == 1.
static void scalar_decode_1(scalar *out, const uint8_t in[32]) { … }

// Decodes 32*|RANK|*|bits| bytes from |in| into |out|. It returns one on
// success or zero if any parsed value is >= |kPrime|.
template <int RANK>
static int vector_decode(vector<RANK> *out, const uint8_t *in, int bits) { … }

// Compresses (lossily) an input |x| mod 3329 into |bits| many bits by grouping
// numbers close to each other together. The formula used is
// round(2^|bits|/kPrime*x) mod 2^|bits|.
// Uses Barrett reduction to achieve constant time. Since we need both the
// remainder (for rounding) and the quotient (as the result), we cannot use
// |reduce| here, but need to do the Barrett reduction directly.
static uint16_t compress(uint16_t x, int bits) { … }

// Decompresses |x| by using an equi-distant representative. The formula is
// round(kPrime/2^|bits|*x). Note that 2^|bits| being the divisor allows us to
// implement this logic using only bit operations.
static uint16_t decompress(uint16_t x, int bits) { … }

static void scalar_compress(scalar *s, int bits) { … }

static void scalar_decompress(scalar *s, int bits) { … }

template <int RANK>
static void vector_compress(vector<RANK> *a, int bits) { … }

template <int RANK>
static void vector_decompress(vector<RANK> *a, int bits) { … }

template <int RANK>
struct public_key { … };

static struct public_key<RANK768> *public_key_768_from_external(
    const struct MLKEM768_public_key *external) { … }

static struct public_key<RANK1024> *
public_key_1024_from_external(const struct MLKEM1024_public_key *external) { … }

template <int RANK>
struct private_key { … };

static struct private_key<RANK768> *private_key_768_from_external(
    const struct MLKEM768_private_key *external) { … }

static struct private_key<RANK1024> *
private_key_1024_from_external(const struct MLKEM1024_private_key *external) { … }

void MLKEM768_generate_key(uint8_t out_encoded_public_key[MLKEM768_PUBLIC_KEY_BYTES],
                           uint8_t optional_out_seed[MLKEM_SEED_BYTES],
                           struct MLKEM768_private_key *out_private_key) { … }

int MLKEM768_private_key_from_seed(struct MLKEM768_private_key *out_private_key,
                                   const uint8_t *seed, size_t seed_len) { … }

void MLKEM1024_generate_key(
    uint8_t out_encoded_public_key[MLKEM1024_PUBLIC_KEY_BYTES],
    uint8_t optional_out_seed[MLKEM_SEED_BYTES],
    struct MLKEM1024_private_key *out_private_key) { … }

int MLKEM1024_private_key_from_seed(
    struct MLKEM1024_private_key *out_private_key, const uint8_t *seed,
    size_t seed_len) { … }

template <int RANK>
static int mlkem_marshal_public_key(CBB *out,
                                    const struct public_key<RANK> *pub) { … }

template <int RANK>
void mlkem_generate_key_external_seed(uint8_t *out_encoded_public_key,
                                      private_key<RANK> *priv,
                                      const uint8_t seed[MLKEM_SEED_BYTES]) { … }

void MLKEM768_generate_key_external_seed(
    uint8_t out_encoded_public_key[MLKEM768_PUBLIC_KEY_BYTES],
    struct MLKEM768_private_key *out_private_key,
    const uint8_t seed[MLKEM_SEED_BYTES]) { … }

void MLKEM1024_generate_key_external_seed(
    uint8_t out_encoded_public_key[MLKEM1024_PUBLIC_KEY_BYTES],
    struct MLKEM1024_private_key *out_private_key,
    const uint8_t seed[MLKEM_SEED_BYTES]) { … }

void MLKEM768_public_from_private(
    struct MLKEM768_public_key *out_public_key,
    const struct MLKEM768_private_key *private_key) { … }

void MLKEM1024_public_from_private(
    struct MLKEM1024_public_key *out_public_key,
    const struct MLKEM1024_private_key *private_key) { … }

// Encrypts a message with given randomness to
// the ciphertext in |out|. Without applying the Fujisaki-Okamoto transform this
// would not result in a CCA secure scheme, since lattice schemes are vulnerable
// to decryption failure oracles.
template <int RANK>
static void encrypt_cpa(uint8_t *out, const struct public_key<RANK> *pub,
                        const uint8_t message[32],
                        const uint8_t randomness[32]) { … }

// Calls |MLKEM768_encap_external_entropy| with random bytes from |RAND_bytes|
void MLKEM768_encap(uint8_t out_ciphertext[MLKEM768_CIPHERTEXT_BYTES],
                    uint8_t out_shared_secret[MLKEM_SHARED_SECRET_BYTES],
                    const struct MLKEM768_public_key *public_key) { … }

void MLKEM1024_encap(uint8_t out_ciphertext[MLKEM1024_CIPHERTEXT_BYTES],
                     uint8_t out_shared_secret[MLKEM_SHARED_SECRET_BYTES],
                     const struct MLKEM1024_public_key *public_key) { … }

// See section 6.2.
template <int RANK>
static void mlkem_encap_external_entropy(
    uint8_t *out_ciphertext,
    uint8_t out_shared_secret[MLKEM_SHARED_SECRET_BYTES],
    const struct public_key<RANK> *pub,
    const uint8_t entropy[MLKEM_ENCAP_ENTROPY]) { … }

void MLKEM768_encap_external_entropy(
    uint8_t out_ciphertext[MLKEM768_CIPHERTEXT_BYTES],
    uint8_t out_shared_secret[MLKEM_SHARED_SECRET_BYTES],
    const struct MLKEM768_public_key *public_key,
    const uint8_t entropy[MLKEM_ENCAP_ENTROPY]) { … }

void MLKEM1024_encap_external_entropy(
    uint8_t out_ciphertext[MLKEM1024_CIPHERTEXT_BYTES],
    uint8_t out_shared_secret[MLKEM_SHARED_SECRET_BYTES],
    const struct MLKEM1024_public_key *public_key,
    const uint8_t entropy[MLKEM_ENCAP_ENTROPY]) { … }

template <int RANK>
static void decrypt_cpa(uint8_t out[32], const struct private_key<RANK> *priv,
                        const uint8_t ciphertext[MLKEM768_CIPHERTEXT_BYTES]) { … }

// See section 6.3
template <int RANK>
static void mlkem_decap(uint8_t out_shared_secret[MLKEM_SHARED_SECRET_BYTES],
                        const uint8_t *ciphertext,
                        const struct private_key<RANK> *priv) { … }

int MLKEM768_decap(uint8_t out_shared_secret[MLKEM_SHARED_SECRET_BYTES],
                   const uint8_t *ciphertext, size_t ciphertext_len,
                   const struct MLKEM768_private_key *private_key) { … }

int MLKEM1024_decap(uint8_t out_shared_secret[MLKEM_SHARED_SECRET_BYTES],
                    const uint8_t *ciphertext, size_t ciphertext_len,
                    const struct MLKEM1024_private_key *private_key) { … }

int MLKEM768_marshal_public_key(CBB *out,
                                const struct MLKEM768_public_key *public_key) { … }

int MLKEM1024_marshal_public_key(
    CBB *out, const struct MLKEM1024_public_key *public_key) { … }

// mlkem_parse_public_key_no_hash parses |in| into |pub| but doesn't calculate
// the value of |pub->public_key_hash|.
template <int RANK>
static int mlkem_parse_public_key_no_hash(struct public_key<RANK> *pub,
                                          CBS *in) { … }

template <int RANK>
static int mlkem_parse_public_key(struct public_key<RANK> *pub, CBS *in) { … }

int MLKEM768_parse_public_key(struct MLKEM768_public_key *public_key, CBS *in) { … }

int MLKEM1024_parse_public_key(struct MLKEM1024_public_key *public_key,
                               CBS *in) { … }

template <int RANK>
static int mlkem_marshal_private_key(CBB *out,
                                     const struct private_key<RANK> *priv) { … }

int MLKEM768_marshal_private_key(
    CBB *out, const struct MLKEM768_private_key *private_key) { … }

int MLKEM1024_marshal_private_key(
    CBB *out, const struct MLKEM1024_private_key *private_key) { … }

template <int RANK>
static int mlkem_parse_private_key(struct private_key<RANK> *priv, CBS *in) { … }

int MLKEM768_parse_private_key(struct MLKEM768_private_key *out_private_key,
                               CBS *in) { … }

int MLKEM1024_parse_private_key(struct MLKEM1024_private_key *out_private_key,
                                CBS *in) { … }