Implementation of PQC Algorithms in libgcrypt

[Stephan Mueller]

Am Dienstag, 16. Mai 2023, 08:09:23 CEST schrieb Simon Josefsson:

Hi Simon,

> Stephan Mueller <smueller at chronox.de> writes:
> > Am Montag, 15. Mai 2023, 17:39:23 CEST schrieb Simon Josefsson via Gcrypt-
> > devel:
> > 
> > Hi Simon,
> > 
> >> Does kyber have any requirements on the API that wouldn't work well with
> >> any of these?
> > 
> > I am experimenting with Kyber in [1]. For KEM, your API would work.
> 
> Thanks for confirming this!  Looking at the code, it seems Kyber KEM has
> exactly the same API as sntrup761, which probably was a NIST PQCS
> requirement, and we should expect that other KEM's follow a similar
> approach.
> 
> I think that sntrup761 can be added to libgcrypt now since it has been
> stable since 2017, but I'm less sure about Kyber since it is stuck in
> the NIST process -- aren't there some risk that NIST will modify the
> parameters again?

I have no insight into the process. I expect, though, that only Kyber/
Dilithium with security strength of 256 bits will be allowed. I would not 
expect that internal parameters would change, though.

However, NIAP / NSA now starts mandating Kyber / Dilithium with 256 bits 
strength as a replacement for *all* general-purpose asymmetric algorithms by 
2035. There are no options for other algorithms! This is now spawning 
discussions especially around the network protocols. Especially Kyber KEX is 
no direct-fit replacement for DH which implies that all network protocols must 
change.

I.e. RSA, (EC)DSA, (EC)DH shall be completely replaced by Kyber and Dilithium.

This is also an interesting catch-22 for NIST's competition. NIST did not 
decide yet, but it may be hard for them to ignore the new ruling my NSA.

> 
> > There you see that I use an additional parameter, an RNG context. This
> > allows me to also derive Kyber keys straight from a KDF (which is
> > accessed like an RNG context). But that is not really needed.
> 
> Right, I use the RNG context internally in sntrup761.c as well, but I
> don't think it should be exposed to libgcrypt callers. 

I can live with that, no doubts. But it makes life (at least for keygen) 
significantly easier :-)

Anyhow, considering that libgcrypt also wants to comply with FIPS rules, it is 
not permissible to allow the user to specify the rng context. So, your 
approach fits even the FIPS considerations (whereas mine does not).

> The internal RNG
> context will be useful for self-testing.  This is especially true since
> I think test vectors for KEM's are implementation-specific: if you
> optimize the implementation to re-order RNG calls, the test vectors will
> no longer work.  Thus, you can't really do black-box testing with KEM
> KATs.  The libgcrypt selftest() approach is perfectly suited for doing a
> whitebox test internally though.

Agreed.
> 
> > However, how do you propose to handle the KEX scenario? See [2] for the
> > full Kyber KEX exchange and the API. I think the KEX is much more
> > important than the KEM, as the KEX is conceptually what is DH today.
> > Kyber KEM can be used in an integrated encryption schema as suggested in
> > [3].
> > 
> > Unfortunately, the Kyber KEX cannot be acting as a direct replacement for
> > DH. Due to its 7 total steps. However, it is possible to coalescing all
> > of them into 2 handshake network exchanges and one final data blob that
> > is sent along with the already encrypted first payload.
> 
> I think this should be through a completely different API than for KEM
> or public-key encrypt/decrypt, and an API that is customized for the KEX
> functionality.  The properties are different from existing APIs, similar
> to how AEAD ciphers differs from ECB ciphers, and how KDF differs from
> MAC/hashes.  Also compare how libgcrypt contains an API for X25519/X448
> curve operations.

Sounds good from my side.

Ciao
Stephan