Implementation of PQC Algorithms in libgcrypt

Mon May 15 17:39:23 CEST 2023

Hi

Thanks for feedback.  Generally I'm not sure we should consider KEM's a
subset of public-key encryption/decryption from an API point of view.
Compare KDF's relationship to MAC/hashes.  Sometimes separate APIs make
sense.

Re your point about test vectors, I agree.  Libgcrypt supports some
"selftest" code (used for FIPS mode) that seems relevant here, maybe it
is sufficient to add selftest code that hard-code the RNG stuff and
compare test vectors?  Compare how kdf.c looks.  Werner, any thoughts on
this approach?  It seems simple, and avoids exposing potentially
insecure APIs to users.  I was considering this, but didn't want to
modify any FIPS-related code.

Re API, I think *_open is fairly established in libgcrypt, so it is good
idiom to re-use.  Let's have some alternatives, right now I proposed
this:

enum gcry_kem_algos
  {
    GCRY_KEM_SNTRUP761 = 761,
  };
#define GCRY_KEM_SNTRUP761_SECRETKEY_SIZE 1763
#define GCRY_KEM_SNTRUP761_PUBLICKEY_SIZE 1158
#define GCRY_KEM_SNTRUP761_CIPHERTEXT_SIZE 1039
#define GCRY_KEM_SNTRUP761_SIZE 32
typedef struct gcry_kem_handle *gcry_kem_hd_t;
gcry_error_t gcry_kem_open (gcry_kem_hd_t *hd, int algo);
void gcry_kem_close (gcry_kem_hd_t h);
gcry_error_t gcry_kem_keypair (gcry_kem_hd_t hd,
			       size_t pklen, void *pubkey,
			       size_t sklen, void *seckey);
gcry_error_t gcry_kem_enc (gcry_kem_hd_t hd,
			   size_t pklen, const void *pubkey,
			   size_t ctlen, void *ciphertext,
			   size_t keylen, void *key);
gcry_error_t gcry_kem_dec (gcry_kem_hd_t hd,
			   size_t ctlen, const void *ciphertext,
			   size_t sklen, const void *seckey,
			   size_t keylen, void *key);

Here is minimal approach similar to KDF interface:

enum gcry_kem_algos
  {
    GCRY_KEM_SNTRUP761 = 761,
  };
#define GCRY_KEM_SNTRUP761_SECRETKEY_SIZE 1763
#define GCRY_KEM_SNTRUP761_PUBLICKEY_SIZE 1158
#define GCRY_KEM_SNTRUP761_CIPHERTEXT_SIZE 1039
#define GCRY_KEM_SNTRUP761_SIZE 32
gcry_error_t gcry_kem_keypair (int algo,
			       size_t pklen, void *pubkey,
			       size_t sklen, void *seckey);
gcry_error_t gcry_kem_enc (int algo,
			   size_t pklen, const void *pubkey,
			   size_t ctlen, void *ciphertext,
			   size_t keylen, void *key);
gcry_error_t gcry_kem_dec (int algo,
			   size_t ctlen, const void *ciphertext,
			   size_t sklen, const void *seckey,
			   size_t keylen, void *key);

Here is a more complex variant that may be more consistent with existing
APIs but has some disadvantages (more APIs are harder to analyze, makes
static allocation much harder if not impossible):

enum gcry_kem_algos
  {
    GCRY_KEM_SNTRUP761 = 761,
  };
typedef struct gcry_kem_handle *gcry_kem_hd_t;
gcry_error_t gcry_kem_open (gcry_kem_hd_t *hd, int algo);
void gcry_kem_close (gcry_kem_hd_t h);
size_t gcry_kem_pubkey_size (gcry_kem_hd_t hd);
size_t gcry_kem_seckey_size (gcry_kem_hd_t hd);
size_t gcry_kem_ciphertext_size (gcry_kem_hd_t hd);
size_t gcry_kem_output_size (gcry_kem_hd_t hd);
gcry_error_t gcry_kem_keypair (gcry_kem_hd_t hd);
void *gcry_kem_get_seckey (gcry_kem_hd_t hd);
void *gcry_kem_get_pubkey (gcry_kem_hd_t hd);
gcry_error_t gcry_kem_enc (gcry_kem_hd_t hd,
			   size_t ctlen, void *ciphertext,
			   size_t keylen, void *key);
gcry_error_t gcry_kem_dec (gcry_kem_hd_t hd,
			   size_t ctlen, const void *ciphertext,
			   size_t keylen, void *key);

Other ideas?

Does kyber have any requirements on the API that wouldn't work well with
any of these?

/Simon

Falko Strenzke <falko.strenzke at mtg.de> writes:

> Hi Simon,
>
> indeed, there is considerable overhead in our implementation of the
> S-Expressions interface for the extraction of values and MPI <-> byte
> array conversions even though each Kyber "token" is merely an opaque
> byte array. However, we don't consider it our call to divert from the
> existing API as we can't gauge the implication of that for the client
> code, e.g. GnuPG. So we basically consider this the maintainer's
> decision.
>
> I looked through your API. It is indeed much simpler. I have the
> following points, however:
>
> 1. I don't fully understand the design logic regarding the
> gcry_kem_hd_t. I understand that it makes sense to use it for the
> encryption and decryption to instantiate a particular key.  But for
> the key generation I don't per se see why it needs a handle. Is it
> required for precomputations in the case of NTRU Prime? (or
> anticipated that this is the case for other KEMs?)
>
> 2. "open" / "close" are in my opinion not the best names for the
> function to create and destroy such a handle. These terms rather
> suggest the handling of a file or a pipe. I know these terms are also
> used in the hash API, but I think more appropriate names would
> "create" / "destroy" or something similar. Maybe it makes sense to
> make the move to a new terminology here.
>
> 3. While the previous two points are rather minor or even cosmetic,
> this one is really important in my opinion: we need an API that allows
> for derandomized key generation and encapsulation to support KAT tests
> for all operations. The Kyber reference implementation already
> supports such KAT tests. I would anyway have raised the question here
> how to realize that. Signature functions in libgcrypt already support
> a "random-override" parameter, but so far I don't really understand
> how it works and whether it would be suitable to use it for the KEM
> API as well.  Ideally, I think, the new API would allow to provide an
> RNG object and to set it to a specific seed before any operation
> (possibly via the KEM handle). However, it would probably be better if
> this functionality is only supported by an internal test-API and not
> available to normal clients. But I am not sure how to realize that in
> the current design of libgcrypt.
>
> - Falko
>
> Am 15.05.23 um 16:20 schrieb Simon Josefsson:
>
>  Hi
>
> I noticed this thread just after submitting sntrup761 [1] patches.
>
> My opinion is that libgcrypt's public-key API is a bad fit for KEM's: it
> uses S-expressions and MPI data types.  I believe the crypto world
> rightly has moved away from those abstraction, towards byte-oriented
> designs instead, for simplicity and safety.  Compare gcry_ecc_mul_point
> for X25519 and gcry_kdf_derive for KDF's.  Could you implement Kyber as
> a KEM using the API that I suggested?  I think that would be
> significantly simpler, and would help validate the KEM API as supporting
> more than one KEM.  I would strongly support having a KEM API that is
> not using sexp/mpi, but I wouldn't object to a sexp/mpi API in addition
> to it, for different use-cases.
>
> /Simon
>
> [1] https://gitlab.com/jas/libgcrypt/-/commits/jas/sntrup761
>
> Falko Strenzke <falko.strenzke at mtg.de> writes:
>
>  Hi Werner,
>
> the only API change is the addition of the following interface function:
>
> gcry_err_code_t
> _gcry_pk_encap(gcry_sexp_t *r_ciph, gcry_sexp_t* r_shared_key, gcry_sexp_t s_pkey)
>
> This also means that the public key spec needs to contain this additional function. For Kyber our public key spec currently looks as follows:
>
> gcry_pk_spec_t _gcry_pubkey_spec_kyber = {
>   GCRY_PK_KYBER, {0, 1},
>   (GCRY_PK_USAGE_ENCAP),        // TODOMTG: can the key usage "encryption" remain or do we need new KU "encap"?
>   "Kyber", kyber_names,
>   "p", "s", "a", "", "p",       // elements of pub-key, sec-key, ciphertext, signature, key-grip
>   kyber_generate,
>   kyber_check_secret_key,
>   NULL,                         // encrypt
>   kyber_encap,
>   kyber_decrypt,
>   NULL,                         // sign,
>   NULL,                         // verify,
>   kyber_get_nbits,
>   run_selftests,
>   compute_keygrip
> };
>
> For the PKEs the encapsulation function would of course be NULL. Regarding the TODO on the key usage marked in the code above, this so far
> doesn't seem to have any implications for us so the decision isn't urgent from my point of view.
>
> - Falko    
>
> Am 30.03.23 um 15:43 schrieb Werner Koch:
>
>  On Wed, 29 Mar 2023 10:09, Falko Strenzke said:
>
>  While the integration of the signature algorithms is straightforward, the KEM
> requires a new interface function, as the KEM encapsulation cannot be modelled
> by a public-key encryption.
>
>
> It would be good if we can discuss a proposed API early enough, so that
> we can see how it fits into the design of Libgcrypt.  Can you already
> roughly describes the needs?
>
>
> Salam-Shalom,
>
>    Werner
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 255 bytes
Desc: not available
URL: <https://lists.gnupg.org/pipermail/gcrypt-devel/attachments/20230515/6b5d816b/attachment.sig>