diff --git a/cipher/kyber.c b/cipher/kyber.c index 1018cde6..c93ab812 100644 --- a/cipher/kyber.c +++ b/cipher/kyber.c @@ -1,524 +1,530 @@ /* kyber.c - the Kyber key encapsulation mechanism (main part) * Copyright (C) 2024 g10 Code GmbH * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see . * SPDX-License-Identifier: LGPL-2.1-or-later * * Out of libgcrypt, you can also use under the same licence of original code. * SPDX-License-Identifier: CC0 OR Apache-2.0 * */ /* Original code from: Repository: https://github.com/pq-crystals/kyber.git Branch: standard Commit: 11d00ff1f20cfca1f72d819e5a45165c1e0a2816 Licence: Public Domain (https://creativecommons.org/share-your-work/public-domain/cc0/); or Apache 2.0 License (https://www.apache.org/licenses/LICENSE-2.0.html). Authors: Joppe Bos Léo Ducas Eike Kiltz Tancrède Lepoint Vadim Lyubashevsky John Schanck Peter Schwabe Gregor Seiler Damien Stehlé Kyber Home: https://www.pq-crystals.org/kyber/ */ /* * This implementation consists of four files: kyber.h (header), * kyber.c (this), kyber-common.c (common part), and kyber-kdep.c * (KYBER_K dependent part). * * It is for inclusion in libgcrypt library. Also, standalone use of * the implementation is possible. With KYBER_K defined, it can offer * the variant of that KYBER_K specified. Otherwise, three variants * are offered. * * From original code, following modification was made. * * - C++ style comments are changed to C-style. * * - No use of KYBER_NAMESPACE and FIPS202_NAMESPACE. Don't export * internal symbols. * * - "verify" routine is changed to return 1 on success, and now has * new name "verify1", so that the use of the routine won't need * negation (since negation might result non-constant-time code with * branch by some compiler). * * - For "xof" routines, definitions of xof_init and xof_close are * added, so that memory will be possible to be cleared after its * use. * * - Different external API for shake128, having _init and _close. * * - New implementation of kyber_shake128_absorb, with the shake128 * API. * * - Added an external function: shake256v with variable arguments. * * - Macro definitions of xof_squeezeblocks, prf, and rkprf are * modified to use the shake128 API and the shake256v function. * */ #ifdef HAVE_CONFIG_H #include #endif #include #include #include #ifdef _GCRYPT_IN_LIBGCRYPT #include #include #include "types.h" #include "g10lib.h" #include "gcrypt-int.h" #include "const-time.h" #include "kyber.h" static int crypto_kem_keypair_2(uint8_t *pk, uint8_t *sk); static int crypto_kem_keypair_3(uint8_t *pk, uint8_t *sk); static int crypto_kem_keypair_4(uint8_t *pk, uint8_t *sk); static int crypto_kem_enc_2(uint8_t *ct, uint8_t *ss, const uint8_t *pk); static int crypto_kem_enc_3(uint8_t *ct, uint8_t *ss, const uint8_t *pk); static int crypto_kem_enc_4(uint8_t *ct, uint8_t *ss, const uint8_t *pk); static int crypto_kem_dec_2(uint8_t *ss, const uint8_t *ct, const uint8_t *sk); static int crypto_kem_dec_3(uint8_t *ss, const uint8_t *ct, const uint8_t *sk); static int crypto_kem_dec_4(uint8_t *ss, const uint8_t *ct, const uint8_t *sk); void kyber_keypair (int algo, uint8_t *pk, uint8_t *sk) { switch (algo) { case GCRY_KEM_MLKEM512: crypto_kem_keypair_2 (pk, sk); break; case GCRY_KEM_MLKEM768: default: crypto_kem_keypair_3 (pk, sk); break; case GCRY_KEM_MLKEM1024: crypto_kem_keypair_4 (pk, sk); break; } } void kyber_encap (int algo, uint8_t *ct, uint8_t *ss, const uint8_t *pk) { switch (algo) { case GCRY_KEM_MLKEM512: crypto_kem_enc_2 (ct, ss, pk); break; case GCRY_KEM_MLKEM768: default: crypto_kem_enc_3 (ct, ss, pk); break; case GCRY_KEM_MLKEM1024: crypto_kem_enc_4 (ct, ss, pk); break; } } void kyber_decap (int algo, uint8_t *ss, const uint8_t *ct, const uint8_t *sk) { switch (algo) { case GCRY_KEM_MLKEM512: crypto_kem_dec_2 (ss, ct, sk); break; case GCRY_KEM_MLKEM768: default: crypto_kem_dec_3 (ss, ct, sk); break; case GCRY_KEM_MLKEM1024: crypto_kem_dec_4 (ss, ct, sk); break; } } static void randombytes (uint8_t *out, size_t outlen) { _gcry_randomize (out, outlen, GCRY_VERY_STRONG_RANDOM); } typedef struct { gcry_md_hd_t h; } keccak_state; static void shake128_init (keccak_state *state) { gcry_err_code_t ec; ec = _gcry_md_open (&state->h, GCRY_MD_SHAKE128, 0); if (ec) log_fatal ("internal md_open failed: %d\n", ec); } static void shake128_absorb (keccak_state *state, const uint8_t *in, size_t inlen) { _gcry_md_write (state->h, in, inlen); } static void shake128_finalize (keccak_state *state) { (void)state; } static void shake128_squeeze (keccak_state *state, uint8_t *out, size_t outlen) { _gcry_md_extract (state->h, GCRY_MD_SHAKE128, out, outlen); } static void shake128_close (keccak_state *state) { _gcry_md_close (state->h); } #define MAX_ARGS 16 static void shake256v (uint8_t *out, size_t outlen, ...) { gcry_buffer_t iov[MAX_ARGS]; va_list ap; int i; void *p; size_t len; va_start (ap, outlen); for (i = 0; i < MAX_ARGS; i++) { p = va_arg (ap, void *); len = va_arg (ap, size_t); if (!p) break; iov[i].size = 0; iov[i].data = p; iov[i].off = 0; iov[i].len = len; } va_end (ap); _gcry_md_hash_buffers_extract (GCRY_MD_SHAKE256, 0, out, outlen, iov, i); } static void sha3_256 (uint8_t h[32], const uint8_t *in, size_t inlen) { _gcry_md_hash_buffer (GCRY_MD_SHA3_256, h, in, inlen); } static void sha3_512 (uint8_t h[64], const uint8_t *in, size_t inlen) { _gcry_md_hash_buffer (GCRY_MD_SHA3_512, h, in, inlen); } #define verify1 ct_memequal #define cmov ct_memmov_cond #else #include "kyber.h" void randombytes (uint8_t *out, size_t outlen); typedef struct { uint64_t s[25]; unsigned int pos; } keccak_state; void shake128_init (keccak_state *state); void shake128_absorb (keccak_state *state, const uint8_t *in, size_t inlen); void shake128_finalize (keccak_state *state); void shake128_squeeze (keccak_state *state, uint8_t *out, size_t outlen); void shake128_close (keccak_state *state); void shake256v (uint8_t *out, size_t outlen, ...); void sha3_256 (uint8_t h[32], const uint8_t *in, size_t inlen); void sha3_512 (uint8_t h[64], const uint8_t *in, size_t inlen); /* Return 1 when success, 0 otherwise. */ unsigned int verify1 (const uint8_t *a, const uint8_t *b, size_t len); /* Conditional move. */ void cmov (uint8_t *r, const uint8_t *x, size_t len, uint8_t b); #endif /*************** kyber/ref/fips202.h */ #define SHAKE128_RATE 168 /*************** kyber/ref/params.h */ #define KYBER_N 256 #define KYBER_Q 3329 #define KYBER_SYMBYTES 32 /* size in bytes of hashes, and seeds */ #define KYBER_SSBYTES 32 /* size in bytes of shared key */ #define KYBER_POLYBYTES 384 #define KYBER_ETA2 2 #define KYBER_INDCPA_MSGBYTES (KYBER_SYMBYTES) /* KYBER_K dependent values (part 1) */ #define KYBER_ETA1_2 3 #define KYBER_ETA1_3_4 2 #define KYBER_POLYCOMPRESSEDBYTES_2_3 128 #define KYBER_POLYCOMPRESSEDBYTES_4 160 /*************** kyber/ref/poly.h */ /* * Elements of R_q = Z_q[X]/(X^n + 1). Represents polynomial * coeffs[0] + X*coeffs[1] + X^2*coeffs[2] + ... + X^{n-1}*coeffs[n-1] */ typedef struct{ int16_t coeffs[KYBER_N]; } poly; #if !defined(KYBER_K) || KYBER_K == 2 || KYBER_K == 3 static void poly_compress_128(uint8_t r[KYBER_POLYCOMPRESSEDBYTES_2_3], const poly *a); static void poly_decompress_128(poly *r, const uint8_t a[KYBER_POLYCOMPRESSEDBYTES_2_3]); #endif #if !defined(KYBER_K) || KYBER_K == 4 static void poly_compress_160(uint8_t r[KYBER_POLYCOMPRESSEDBYTES_4], const poly *a); static void poly_decompress_160(poly *r, const uint8_t a[KYBER_POLYCOMPRESSEDBYTES_4]); #endif static void poly_tobytes(uint8_t r[KYBER_POLYBYTES], const poly *a); static void poly_frombytes(poly *r, const uint8_t a[KYBER_POLYBYTES]); static void poly_frommsg(poly *r, const uint8_t msg[KYBER_INDCPA_MSGBYTES]); static void poly_tomsg(uint8_t msg[KYBER_INDCPA_MSGBYTES], const poly *r); #if !defined(KYBER_K) || KYBER_K == 2 static void poly_getnoise_eta1_2(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce); #endif #if !defined(KYBER_K) || KYBER_K == 3 || KYBER_K == 4 static void poly_getnoise_eta1_3_4(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce); #endif static void poly_getnoise_eta2(poly *r, const uint8_t seed[KYBER_SYMBYTES], uint8_t nonce); static void poly_ntt(poly *r); static void poly_invntt_tomont(poly *r); static void poly_basemul_montgomery(poly *r, const poly *a, const poly *b); static void poly_tomont(poly *r); static void poly_reduce(poly *r); static void poly_add(poly *r, const poly *a, const poly *b); static void poly_sub(poly *r, const poly *a, const poly *b); /*************** kyber/ref/ntt.h */ static const int16_t zetas[128]; static void ntt(int16_t poly[256]); static void invntt(int16_t poly[256]); static void basemul(int16_t r[2], const int16_t a[2], const int16_t b[2], int16_t zeta); /*************** kyber/ref/reduce.h */ #define MONT -1044 /* 2^16 mod q */ #define QINV -3327 /* q^-1 mod 2^16 */ static int16_t montgomery_reduce(int32_t a); static int16_t barrett_reduce(int16_t a); /*************** kyber/ref/symmetric.h */ typedef keccak_state xof_state; static void kyber_shake128_absorb (keccak_state *state, const uint8_t seed[KYBER_SYMBYTES], uint8_t x, uint8_t y) { shake128_absorb (state, seed, KYBER_SYMBYTES); shake128_absorb (state, &x, 1); shake128_absorb (state, &y, 1); shake128_finalize (state); } #define XOF_BLOCKBYTES SHAKE128_RATE #define hash_h(OUT, IN, INBYTES) sha3_256(OUT, IN, INBYTES) #define hash_g(OUT, IN, INBYTES) sha3_512(OUT, IN, INBYTES) #define xof_init(STATE) shake128_init(STATE) #define xof_close(STATE) shake128_close(STATE) #define xof_absorb(STATE, SEED, X, Y) kyber_shake128_absorb(STATE, SEED, X, Y) #define xof_squeezeblocks(OUT, OUTBLOCKS, STATE) shake128_squeeze(STATE, OUT, SHAKE128_RATE * OUTBLOCKS) -#define prf(OUT, OUTBYTES, KEY, NONCE) shake256v(OUT, OUTBYTES, KEY, KYBER_SYMBYTES, &nonce, 1, NULL, 0) -#define rkprf(OUT, KEY, INPUT) shake256v(OUT, KYBER_SSBYTES, KEY, KYBER_SYMBYTES, INPUT, KYBER_CIPHERTEXTBYTES, NULL, 0) +#define prf(OUT, OUTBYTES, KEY, NONCE) \ + shake256v(OUT, OUTBYTES, (void *)(KEY), (size_t)KYBER_SYMBYTES, \ + (void *)&(NONCE), (size_t)1, \ + NULL, (size_t)0) +#define rkprf(OUT, KEY, INPUT) \ + shake256v(OUT, KYBER_SSBYTES, (void *)(KEY), (size_t)KYBER_SYMBYTES, \ + (void *)(INPUT), (size_t)KYBER_CIPHERTEXTBYTES, \ + NULL, (size_t)0) #include "kyber-common.c" #define VARIANT2(name) name ## _2 #define VARIANT3(name) name ## _3 #define VARIANT4(name) name ## _4 /* KYBER_K dependent values (part 2) */ #define KYBER_POLYVECBYTES (KYBER_K * KYBER_POLYBYTES) #define KYBER_INDCPA_PUBLICKEYBYTES (KYBER_POLYVECBYTES + KYBER_SYMBYTES) #define KYBER_INDCPA_SECRETKEYBYTES (KYBER_POLYVECBYTES) #define KYBER_INDCPA_BYTES (KYBER_POLYVECCOMPRESSEDBYTES + KYBER_POLYCOMPRESSEDBYTES) #define KYBER_PUBLICKEYBYTES (KYBER_INDCPA_PUBLICKEYBYTES) /* 32 bytes of additional space to save H(pk) */ #define KYBER_SECRETKEYBYTES (KYBER_INDCPA_SECRETKEYBYTES + KYBER_INDCPA_PUBLICKEYBYTES + 2*KYBER_SYMBYTES) #define KYBER_CIPHERTEXTBYTES (KYBER_INDCPA_BYTES) #ifdef KYBER_K # if KYBER_K == 2 # define KYBER_POLYCOMPRESSEDBYTES 128 # define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320) # define poly_compress poly_compress_128 # define poly_decompress poly_decompress_128 # define poly_getnoise_eta1 poly_getnoise_eta1_2 # elif KYBER_K == 3 # define KYBER_POLYCOMPRESSEDBYTES 128 # define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320) # define poly_compress poly_compress_128 # define poly_decompress poly_decompress_128 # define poly_getnoise_eta1 poly_getnoise_eta1_3_4 # elif KYBER_K == 4 # define KYBER_POLYCOMPRESSEDBYTES 160 # define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 352) # define poly_compress poly_compress_160 # define poly_decompress poly_decompress_160 # define poly_getnoise_eta1 poly_getnoise_eta1_3_4 # endif # include "kyber-kdep.c" # else # define KYBER_K 2 # define KYBER_POLYCOMPRESSEDBYTES 128 # define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320) # define poly_compress poly_compress_128 # define poly_decompress poly_decompress_128 # define poly_getnoise_eta1 poly_getnoise_eta1_2 # define crypto_kem_keypair_derand VARIANT2(crypto_kem_keypair_derand) # define crypto_kem_enc_derand VARIANT2(crypto_kem_enc_derand) # define crypto_kem_keypair VARIANT2(crypto_kem_keypair) # define crypto_kem_enc VARIANT2(crypto_kem_enc) # define crypto_kem_dec VARIANT2(crypto_kem_dec) # define polyvec VARIANT2(polyvec) # define polyvec_compress VARIANT2(polyvec_compress) # define polyvec_decompress VARIANT2(polyvec_decompress) # define polyvec_tobytes VARIANT2(polyvec_tobytes) # define polyvec_frombytes VARIANT2(polyvec_frombytes) # define polyvec_ntt VARIANT2(polyvec_ntt) # define polyvec_invntt_tomont VARIANT2(polyvec_invntt_tomont) # define polyvec_basemul_acc_montgomery VARIANT2(polyvec_basemul_acc_montgomery) # define polyvec_reduce VARIANT2(polyvec_reduce) # define polyvec_add VARIANT2(polyvec_add) # define pack_pk VARIANT2(pack_pk) # define unpack_pk VARIANT2(unpack_pk) # define pack_sk VARIANT2(pack_sk) # define unpack_sk VARIANT2(unpack_sk) # define pack_ciphertext VARIANT2(pack_ciphertext) # define unpack_ciphertext VARIANT2(unpack_ciphertext) # define gen_matrix VARIANT2(gen_matrix) # define indcpa_keypair_derand VARIANT2(indcpa_keypair_derand) # define indcpa_enc VARIANT2(indcpa_enc) # define indcpa_dec VARIANT2(indcpa_dec) # include "kyber-kdep.c" # define KYBER_K 3 # define KYBER_POLYCOMPRESSEDBYTES 128 # define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 320) # define poly_compress poly_compress_128 # define poly_decompress poly_decompress_128 # define poly_getnoise_eta1 poly_getnoise_eta1_3_4 # define crypto_kem_keypair_derand VARIANT3(crypto_kem_keypair_derand) # define crypto_kem_enc_derand VARIANT3(crypto_kem_enc_derand) # define crypto_kem_keypair VARIANT3(crypto_kem_keypair) # define crypto_kem_enc VARIANT3(crypto_kem_enc) # define crypto_kem_dec VARIANT3(crypto_kem_dec) # define polyvec VARIANT3(polyvec) # define polyvec_compress VARIANT3(polyvec_compress) # define polyvec_decompress VARIANT3(polyvec_decompress) # define polyvec_tobytes VARIANT3(polyvec_tobytes) # define polyvec_frombytes VARIANT3(polyvec_frombytes) # define polyvec_ntt VARIANT3(polyvec_ntt) # define polyvec_invntt_tomont VARIANT3(polyvec_invntt_tomont) # define polyvec_basemul_acc_montgomery VARIANT3(polyvec_basemul_acc_montgomery) # define polyvec_reduce VARIANT3(polyvec_reduce) # define polyvec_add VARIANT3(polyvec_add) # define pack_pk VARIANT3(pack_pk) # define unpack_pk VARIANT3(unpack_pk) # define pack_sk VARIANT3(pack_sk) # define unpack_sk VARIANT3(unpack_sk) # define pack_ciphertext VARIANT3(pack_ciphertext) # define unpack_ciphertext VARIANT3(unpack_ciphertext) # define gen_matrix VARIANT3(gen_matrix) # define indcpa_keypair_derand VARIANT3(indcpa_keypair_derand) # define indcpa_enc VARIANT3(indcpa_enc) # define indcpa_dec VARIANT3(indcpa_dec) # include "kyber-kdep.c" # define KYBER_K 4 # define KYBER_POLYCOMPRESSEDBYTES 160 # define KYBER_POLYVECCOMPRESSEDBYTES (KYBER_K * 352) # define poly_compress poly_compress_160 # define poly_decompress poly_decompress_160 # define poly_getnoise_eta1 poly_getnoise_eta1_3_4 # define crypto_kem_keypair_derand VARIANT4(crypto_kem_keypair_derand) # define crypto_kem_enc_derand VARIANT4(crypto_kem_enc_derand) # define crypto_kem_keypair VARIANT4(crypto_kem_keypair) # define crypto_kem_enc VARIANT4(crypto_kem_enc) # define crypto_kem_dec VARIANT4(crypto_kem_dec) # define polyvec VARIANT4(polyvec) # define polyvec_compress VARIANT4(polyvec_compress) # define polyvec_decompress VARIANT4(polyvec_decompress) # define polyvec_tobytes VARIANT4(polyvec_tobytes) # define polyvec_frombytes VARIANT4(polyvec_frombytes) # define polyvec_ntt VARIANT4(polyvec_ntt) # define polyvec_invntt_tomont VARIANT4(polyvec_invntt_tomont) # define polyvec_basemul_acc_montgomery VARIANT4(polyvec_basemul_acc_montgomery) # define polyvec_reduce VARIANT4(polyvec_reduce) # define polyvec_add VARIANT4(polyvec_add) # define pack_pk VARIANT4(pack_pk) # define unpack_pk VARIANT4(unpack_pk) # define pack_sk VARIANT4(pack_sk) # define unpack_sk VARIANT4(unpack_sk) # define pack_ciphertext VARIANT4(pack_ciphertext) # define unpack_ciphertext VARIANT4(unpack_ciphertext) # define gen_matrix VARIANT4(gen_matrix) # define indcpa_keypair_derand VARIANT4(indcpa_keypair_derand) # define indcpa_enc VARIANT4(indcpa_enc) # define indcpa_dec VARIANT4(indcpa_dec) # include "kyber-kdep.c" #endif