Norbert Pócs norbertpocs0@gmail.com writes:

I took an another look at the PR, if there is anything possible to delete without loosing the functionality, but unfortunately didn't find anything.

To get a better understanding of the HPKE spec and its complexities, I've tried to implement KEM x25519-sha256 (and nothing else from the spec). Patch below.

Some notes:

1. Nettle's hkdf interface isn't that a good fit, if one wants to avoid memcpy calls to assemble the inputs. Below, I haven't used Nettle's hkdf_extract / hkdf_expand, instead doing corresponding operations directly on hmac_sha256. Unless I'm missing something, it seems a LabeledExpand function limited to at most 32 octets of output (the sha256 digest size) is sufficient for everything in hpke, except for the Export feature.

2. I don't quite like that some functions (in particular DeriveKeyPair) are defined so that it can fail (not for x25519, though). Having a success/failure indication there forces applications to have an error handling path, that it's rather difficult to test. I see no obvious way for Nettle to shield applications from that, though.

3. For those of you who have looked closer at proposed post-quantum KEM mechanisms, is the interface suitable for those too?

4. It seems that HPKE defines a very clean interface between the KEM and the rest of the message handling, with the shared_secret the only piece of data shered between KEM and the rest of the processing.

Regards, /Niels

diff --git a/Makefile.in b/Makefile.in index f027e762..eb520f7a 100644 --- a/Makefile.in +++ b/Makefile.in @@ -225,7 +225,8 @@ hogweed_SOURCES = sexp.c sexp-format.c \ ed25519-sha512.c ed25519-sha512-pubkey.c \ ed25519-sha512-sign.c ed25519-sha512-verify.c \ ed448-shake256.c ed448-shake256-pubkey.c \ - ed448-shake256-sign.c ed448-shake256-verify.c + ed448-shake256-sign.c ed448-shake256-verify.c \ + kem-x25519-sha256.c

OPT_SOURCES = fat-arm.c fat-arm64.c fat-ppc.c fat-s390x.c fat-x86_64.c mini-gmp.c

diff --git a/hpke-kem.h b/hpke-kem.h new file mode 100644 index 00000000..00b4610b --- /dev/null +++ b/hpke-kem.h @@ -0,0 +1,71 @@ +/* hpke-kem.h + + Key encapsulation mechanism, suitable for HPKE (RFC 9180). + + Copyright (C) 2024 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle 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 + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#ifndef NETTLE_HPKE_KEM_H_INCLUDED +#define NETTLE_HPKE_KEM_H_INCLUDED + +#include "nettle-types.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* Name mangling */ +#define get_kem_x25519_sha256 nettle_get_kem_x25519_sha256 + +typedef int kem_derive_keypair_func (uint8_t *public_key, uint8_t *private_key, + size_t seed_size, const uint8_t *seed); +/* Take randomness source instead? Passing seed suites deterministic tests. */ +typedef void kem_encapsulate_func (uint8_t *shared_secret, uint8_t *encapsulation, + const uint8_t *receiver_public_key, + void *random_ctx, nettle_random_func *random); +typedef void kem_decapsulate_func (uint8_t *shared_secret, const uint8_t *encapsulation, + const uint8_t *private_key); + +struct hpke_kem { + unsigned public_key_size; + unsigned private_key_size; + unsigned encapsulation_size; + unsigned shared_secret_size; + kem_derive_keypair_func *derive_keypair; + kem_encapsulate_func *encapsulate; + kem_decapsulate_func *decapsulate; +}; + +const struct hpke_kem *get_kem_x25519_sha256 (void); + +#ifdef __cplusplus +} +#endif + +#endif /* NETTLE_HPKE_KEM_H_INCLUDED */ diff --git a/kem-x25519-sha256.c b/kem-x25519-sha256.c new file mode 100644 index 00000000..186ced6c --- /dev/null +++ b/kem-x25519-sha256.c @@ -0,0 +1,170 @@ +/* kem-x25519-sha256.c + + KEM using curve25519, suitable for HPKE (RFC 9180). + + Copyright (C) 2024 Niels Möller + + This file is part of GNU Nettle. + + GNU Nettle is free software: you can redistribute it and/or + modify it under the terms of either: + + * the GNU Lesser General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your + option) any later version. + + or + + * the GNU General Public License as published by the Free + Software Foundation; either version 2 of the License, or (at your + option) any later version. + + or both in parallel, as here. + + GNU Nettle 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 + General Public License for more details. + + You should have received copies of the GNU General Public License and + the GNU Lesser General Public License along with this program. If + not, see http://www.gnu.org/licenses/. +*/ + +#if HAVE_CONFIG_H +# include "config.h" +#endif + +#include <string.h> + +#include "curve25519.h" +#include "hpke-kem.h" +#include "hmac.h" + +static void +labeled_extract (struct hmac_sha256_ctx *ctx, + size_t salt_size, const uint8_t *salt, + size_t label_size, const uint8_t *label, + size_t secret_size, const uint8_t *secret) +{ + static const uint8_t extract_info[] = { + 'H', 'P', 'K', 'E', '-', 'v', '1', /* Fix prefix for LabeledExpand */ + 'K', 'E', 'M', 0, 0x20, /* suite_id for x25519-HKDF-SHA256 */ + }; + uint8_t prk[SHA256_DIGEST_SIZE]; + /* Don't call hkdf_extract, to avoid explicit concatenation. */ + hmac_sha256_set_key (ctx, salt_size, salt); + hmac_sha256_update (ctx, sizeof(extract_info), extract_info); + hmac_sha256_update (ctx, label_size, label); + hmac_sha256_update (ctx, secret_size, secret); + hmac_sha256_digest (ctx, SHA256_DIGEST_SIZE, prk); + + hmac_sha256_set_key (ctx, SHA256_DIGEST_SIZE, prk); +} + +/* Specialization of labeled_expand for output size of exactly + SHA256_DIGEST_SIZE. The label and info should be passed to + hmac_sha256_update between these _init and _digest calls. */ +static void +labeled_expand_32_init (struct hmac_sha256_ctx *ctx) +{ + static const uint8_t expand_info[] = { + 0, SHA256_DIGEST_SIZE, /* Expand size. */ + 'H', 'P', 'K', 'E', '-', 'v', '1', /* Fix prefix for LabeledExpand */ + 'K', 'E', 'M', 0, 0x20, /* suite_id for x25519-HKDF-SHA256 */ + }; + hmac_sha256_update (ctx, sizeof(expand_info), expand_info); +} + +static void +labeled_expand_32_digest (struct hmac_sha256_ctx *ctx, + uint8_t *dst) +{ + static const uint8_t one = 1; /* hkdf expand counter */ + hmac_sha256_update (ctx, 1, &one); + + hmac_sha256_digest (ctx, SHA256_DIGEST_SIZE, dst); +} + +static int +x25519_sha256_derive_keypair (uint8_t *public_key, uint8_t *private_key, + size_t seed_size, const uint8_t *seed) +{ + struct hmac_sha256_ctx ctx; + labeled_extract (&ctx, 0, NULL, + 7, (const uint8_t *) "dkp_prk", + seed_size, seed); + labeled_expand_32_init (&ctx); + hmac_sha256_update (&ctx, 2, (const uint8_t *) "sk"); + labeled_expand_32_digest (&ctx, private_key); + + /* Mask private key here? See RFC9180 errata. */ + curve25519_mul_g (public_key, private_key); + return 1; +} + +static void +x25519_sha256_derive_shared_secret (uint8_t *shared_secret, + const uint8_t *dh, + const uint8_t *encapsulation, + const uint8_t *public_key) +{ + struct hmac_sha256_ctx ctx; + + labeled_extract (&ctx, 0, NULL, + 7, (const uint8_t *) "eae_prk", + CURVE25519_SIZE, dh); + + labeled_expand_32_init (&ctx); + hmac_sha256_update (&ctx, 13, (const uint8_t *) "shared_secret"); /* label */ + hmac_sha256_update (&ctx, CURVE25519_SIZE, encapsulation); /* kem_context */ + hmac_sha256_update (&ctx, CURVE25519_SIZE, public_key); + labeled_expand_32_digest (&ctx, shared_secret); +} + +static void +x25519_sha256_encapsulate (uint8_t *shared_secret, uint8_t *encapsulation, + const uint8_t *receiver_public_key, + void *random_ctx, nettle_random_func *random) +{ + uint8_t private_key[CURVE25519_SIZE]; + uint8_t dh[CURVE25519_SIZE]; + + random (random_ctx, sizeof(private_key), private_key); + curve25519_mul_g (encapsulation, private_key); + + curve25519_mul (dh, private_key, receiver_public_key); + + x25519_sha256_derive_shared_secret (shared_secret, dh, encapsulation, receiver_public_key); +} + +static void +x25519_sha256_decapsulate (uint8_t *shared_secret, + const uint8_t *encapsulation, + const uint8_t *private_key) +{ + uint8_t public_key[CURVE25519_SIZE]; + uint8_t dh[CURVE25519_SIZE]; + curve25519_mul (dh, private_key, encapsulation); + curve25519_mul_g (public_key, private_key); + + x25519_sha256_derive_shared_secret (shared_secret, + dh, encapsulation, public_key); +} + +static const struct hpke_kem +kem_x25519 = { + CURVE25519_SIZE, + CURVE25519_SIZE, + CURVE25519_SIZE, + CURVE25519_SIZE, + x25519_sha256_derive_keypair, + x25519_sha256_encapsulate, + x25519_sha256_decapsulate, +}; + +const struct hpke_kem * +get_kem_x25519_sha256 (void) +{ + return &kem_x25519; +} diff --git a/testsuite/Makefile.in b/testsuite/Makefile.in index bd630524..95c89c48 100644 --- a/testsuite/Makefile.in +++ b/testsuite/Makefile.in @@ -57,7 +57,8 @@ TS_HOGWEED_SOURCES = sexp-test.c sexp-format-test.c \ eddsa-compress-test.c eddsa-sign-test.c \ eddsa-verify-test.c ed25519-test.c ed448-test.c \ gostdsa-sign-test.c gostdsa-verify-test.c \ - gostdsa-keygen-test.c gostdsa-vko-test.c + gostdsa-keygen-test.c gostdsa-vko-test.c \ + hpke-kem-test.c

TS_SOURCES = $(TS_NETTLE_SOURCES) $(TS_HOGWEED_SOURCES) CXX_SOURCES = cxx-test.cxx diff --git a/testsuite/hpke-kem-test.c b/testsuite/hpke-kem-test.c new file mode 100644 index 00000000..d09d8220 --- /dev/null +++ b/testsuite/hpke-kem-test.c @@ -0,0 +1,146 @@ +#include "testutils.h" + +#include "hpke-kem.h" + +static void +test_derive_key (const struct hpke_kem *kem, + const struct tstring *ikm, + const struct tstring *exp_pub, + const struct tstring *exp_priv) +{ + uint8_t *pub = xalloc (kem->public_key_size); + uint8_t *priv = xalloc (kem->private_key_size); + int res; + ASSERT (kem->private_key_size == exp_priv->length); + ASSERT (kem->public_key_size == exp_pub->length); + + res = kem->derive_keypair (pub, priv, ikm->length, ikm->data); + ASSERT (res == 1); + if (!MEMEQ (kem->private_key_size, priv, exp_priv->data)) + { + fprintf(stderr, "kem->derive_keypair failed private:\ngot: "); + print_hex(kem->private_key_size, priv); + fprintf(stderr, " exp: "); + tstring_print_hex(exp_priv); + FAIL(); + } + if (!MEMEQ (kem->public_key_size, pub, exp_pub->data)) + { + fprintf(stderr, "kem->derive_keypair failed public:\ngot: "); + print_hex(kem->public_key_size, pub); + fprintf(stderr, " exp: "); + tstring_print_hex(exp_pub); + FAIL(); + } + free (pub); + free (priv); +} + +static void +test_random(void *p, size_t size, uint8_t *dst) +{ + const struct tstring *s = (const struct tstring *) p; + ASSERT (size <= s->length); + memcpy (dst, s->data, size); +} + +static void +test_encapsulate(const struct hpke_kem *kem, + const struct tstring *ephemeral_priv, + const struct tstring *receiver_pub, + /* const struct tstring *info, */ + const struct tstring *exp_encapsulation, + const struct tstring *exp_shared_secret) +{ + uint8_t *encapsulation = xalloc (kem->encapsulation_size); + uint8_t *shared_secret = xalloc (kem->shared_secret_size); + ASSERT (kem->private_key_size == ephemeral_priv->length); + ASSERT (kem->public_key_size == receiver_pub->length); + ASSERT (kem->encapsulation_size == exp_encapsulation->length); + ASSERT (kem->shared_secret_size == exp_shared_secret->length); + + kem->encapsulate (shared_secret, encapsulation, + receiver_pub->data, + (void *) ephemeral_priv, test_random); + + if (!MEMEQ (kem->encapsulation_size, encapsulation, exp_encapsulation->data)) + { + fprintf(stderr, "kem->encapsulation failed, encap:\ngot: "); + print_hex(kem->encapsulation_size, encapsulation); + fprintf(stderr, " exp: "); + tstring_print_hex(exp_encapsulation); + FAIL(); + } + if (!MEMEQ (kem->shared_secret_size, shared_secret, exp_shared_secret->data)) + { + fprintf(stderr, "kem->encapsulation failed, secret:\ngot: "); + print_hex(kem->shared_secret_size, shared_secret); + fprintf(stderr, " exp: "); + tstring_print_hex(exp_shared_secret); + FAIL(); + } + free (encapsulation); + free (shared_secret); +} + +static void +test_decapsulate(const struct hpke_kem *kem, + const struct tstring *receiver_priv, + const struct tstring *encapsulation, + const struct tstring *exp_shared_secret) +{ + uint8_t *shared_secret = xalloc (kem->shared_secret_size); + ASSERT (kem->private_key_size == receiver_priv->length); + ASSERT (kem->encapsulation_size == encapsulation->length); + ASSERT (kem->shared_secret_size == exp_shared_secret->length); + + kem->decapsulate (shared_secret, encapsulation->data, + receiver_priv->data); + if (!MEMEQ (kem->shared_secret_size, shared_secret, exp_shared_secret->data)) + { + fprintf(stderr, "kem->decapsulate failed, secret:\ngot: "); + print_hex(kem->shared_secret_size, shared_secret); + fprintf(stderr, " exp: "); + tstring_print_hex(exp_shared_secret); + FAIL(); + } + free (shared_secret); +} + +void +test_main(void) +{ + /* RFC 9180 A.1.1 */ + test_derive_key (get_kem_x25519_sha256(), + SHEX("7268600d403fce431561aef583ee1613" + "527cff655c1343f29812e66706df3234"), + SHEX("37fda3567bdbd628e88668c3c8d7e97d" + "1d1253b6d4ea6d44c150f741f1bf4431"), + SHEX("52c4a758a802cd8b936eceea31443279" + "8d5baf2d7e9235dc084ab1b9cfa2f736")); + test_derive_key (get_kem_x25519_sha256(), + SHEX("6db9df30aa07dd42ee5e8181afdb977e" + "538f5e1fec8a06223f33f7013e525037"), + SHEX("3948cfe0ad1ddb695d780e59077195da" + "6c56506b027329794ab02bca80815c4d"), + SHEX("4612c550263fc8ad58375df3f557aac5" + "31d26850903e55a9f23f21d8534e8ac8")); + + test_encapsulate (get_kem_x25519_sha256(), + SHEX("52c4a758a802cd8b936eceea31443279" + "8d5baf2d7e9235dc084ab1b9cfa2f736"), + SHEX("3948cfe0ad1ddb695d780e59077195da" + "6c56506b027329794ab02bca80815c4d"), + SHEX("37fda3567bdbd628e88668c3c8d7e97d" + "1d1253b6d4ea6d44c150f741f1bf4431"), + SHEX("fe0e18c9f024ce43799ae393c7e8fe8f" + "ce9d218875e8227b0187c04e7d2ea1fc")); + + test_decapsulate (get_kem_x25519_sha256(), + SHEX("4612c550263fc8ad58375df3f557aac5" + "31d26850903e55a9f23f21d8534e8ac8"), + SHEX("37fda3567bdbd628e88668c3c8d7e97d" + "1d1253b6d4ea6d44c150f741f1bf4431"), + SHEX("fe0e18c9f024ce43799ae393c7e8fe8f" + "ce9d218875e8227b0187c04e7d2ea1fc")); +}