Deterministic KEM key generation

[Karolin Varner]

Morning all,

I would like to bring an issue to the forum's attention: The difficulty imposed by having the KEM interface be nondeterministic.
As far as I can see, the interface is:

keypair() -> (sk, pk)
enc(pk) -> (ss, ct)
dec(ct, sk) -> ss

Of these, only dec(…) is deterministic.

I propose that providing a properly specified, standardized, deterministic variant of the interface. Something like

keypair(coins) -> (sk, pk)
enc(coins, pk) ->ss, ct)
dec(ct, sk) -> ss

where coins is a fixed size, random string. To my knowledge, some construction such as this already tends to be used internally by KEMs
usually involving deterministic expansion into a stream of random bytes using the SHAKE XOF.

This would help the implementation of reliable software modules by allowing cross-implementation test vectors to be provided.
As a previous thread on this forum indicated, some implementations are already doing something like this in practice[0].

I also know of at least one protocol (pq wireguard by Hülsing, Ning et al.) that explicitly requires a KEM with coins argument[1].

Best,
Karolin Varner

[0]: https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/AjK3wpZFBDA/m/clPnXzdTBwAJ
[1]: https://eprint.iacr.org/2020/379

[Kris Kwiatkowski]

I doesn't seem to me that such implementation
is disallowed.

[Markku-Juhani O. Saarinen]

Hi Kris,

I think the question is mainly about testing; whether or not NIST will specify the exact deterministic methods for key generation (and other functions requiring randomness -- encapsulation, signatures) as a function of a short "seed" and without internal direct invocations of (D)RBGs.

I think that would be very helpful from a testing viewpoint; I have publicly encouraged it (e.g. at ICMC 2021 and just yesterday at the ECW PQC workshop: See slides 11,15 on https://mjos.fi/doc/20211118-ewcpqc-saarinen-specifying.pdf ). This would mean that the primitives can be plugged into automated testing frameworks (such as NIST's own ACVTS) more easily. Furthermore, I hope that the methods are well-considered from a correctness viewpoint; the FIPS key generation (e.g. uniform random and primality testing) procedures have historically been surprisingly problematic, sometimes requiring implementations to be effectively weakened for FIPS.

However, I do not think that NIST should make the deterministic approach mandatory for FIPS 140-3 compliance: side-channel secure, masked implementations benefit greatly from having some freedom for generating random samples and other quantities (shares) directly without such "determinism".

Cheers,

- markku

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

Dr. Markku-Juhani O. Saarinen <mj...@iki.fi>

--
You received this message because you are subscribed to the Google Groups "pqc-forum" group.
To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+...@list.nist.gov.
To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/bff5d43d-2687-c170-b749-7188a5c240f4%40amongbytes.com.

[Kris Kwiatkowski]

> However, I do not think that NIST should make the deterministic approach mandatory for FIPS 140-3 compliance

Me too. Currently if such determinism is required by FIPS certification, then I have to include "coins" into my API. But,
I would prefer having freedom of choice. Having centralized "get_random_bytes()" in some cases is very useful. Still,
nothing stops me from designing API in a way that it supports deterministic keygen or encaps (i.e. bssl does it here [1]).

[1] https://boringssl.googlesource.com/boringssl/+/refs/heads/master/crypto/hrss/hrss.c#1991

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CA%2BiU_qmY5pVpQrJunvOmB8eLAGkkjCkBvGEsArbCxAn2BQkLdA%40mail.gmail.com.

-- 
Kris Kwiatkowski

Senior Cryptography Engineer
PQShield, LTD

E:   kr...@pqshield.com
W:   www.pqshield.com

This email and any attachment contain information that is private 
and confidential and is intended for the addressee only. If you are not 
an addressee, you are not authorised to read, copy or use the email or 
any attachment, If you have received this email in error, please notify 
the sender by return email and then destroy it. Any views expressed 
in this e-mail are not that of PQShield Ltd or its employees unless 
specifically stated. As e-mail communications are known to be unsecure, 
we accept no liability for any legal issues that may arise as a result 
of this e-mail. It is advised that you carry out a virus check with 
your own software before opening any attachments sent to you."

[Kris Kwiatkowski]

In the case of ECDSA (non-deterministic signature generation), NIST has defined KAT vectors
for signature generation (SigGen.txt in [1], it defines 'k' value). But during the validation process of
FIPS 186-4, the signature generation with fixed 'k' is not required (see 6 in [2]).

In the case of KEMs I would expect a similar data is provided and a similar process is followed.
It would be very useful to have KATs for keygen and encaps (with "coins"). But it would be also
useful if deterministic implementation of keygen and encapsulation is not required.

Kind regards,
Kris

[1] https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Algorithm-Validation-Program/documents/dss/186-4ecdsatestvectors.zip
[2] https://csrc.nist.gov/CSRC/media/Projects/Cryptographic-Algorithm-Validation-Program/documents/dss2/ecdsa2vs.pdf

[D. J. Bernstein]

An RSA key generator calls a prime generator, which in turn calls an RNG
as many times as necessary to find primes. The RNG specification and RNG
state management shouldn't be baked into the key generator; the prime
generator should simply call a separate RNG module. (See, e.g., how
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5-draft.pdf uses
any "approved RBG" as a subroutine.)

For various ways that specifications and software---like the algorithms
literature more broadly---benefit from this modularization, see my
pqc-forum messages dated 31 Oct 2016 08:56:39 +0000, 27 Mar 2017
13:50:51 +0000, and 8 Sep 2021 01:34:22 +0200.

Karolin Varner writes:
[ proposal: add a fixed-length coins input to keypair and enc ]

> This would help the implementation of reliable software modules by
> allowing cross-implementation test vectors to be provided.

NIST's KATs and SUPERCOP's checksums are cross-implementation test
vectors that don't require this complication.

Having a central testing framework provide a deterministic substitute
for randombytes() is much simpler than putting the RNG burden onto many
different implementations of cryptographic primitives. Any framework
that can generate test vectors is somehow generating deterministic
inputs, so why shouldn't it be generating randombytes() results?

> To my knowledge, some construction such as this already tends to be
> used internally by KEMs usually involving deterministic expansion into
> a stream of random bytes using the SHAKE XOF.

This is correct for Kyber and SABER, but not for the other finalists;
e.g., SUPERCOP records 2445 for ntruhps2048509 keypair_randombytes.

Skimming SUPERCOP's records for the alternates finds already at the top
of the list that the BIKE _decapsulation_ software is using randomness.
Maybe BIKE doesn't need to do this, but there are papers saying that
randomness can save time (this is a recurring theme in the algorithms
literature), and there are many papers saying that randomness can help
stop side-channel attacks. I expect to see increasing use of randomness
in post-quantum subroutines that people think of as deterministic.

With the randombytes() API, all of this is straightforwardly testable. A
module that adds randomness doesn't have to pester the functions that
call it; this simplification is an example of Parnas information hiding.

> I also know of at least one protocol (pq wireguard by Hülsing, Ning et
> al.) that explicitly requires a KEM with coins argument[1].

To the extent that such things are required, they're compatible with the
randombytes() interface: simply plug in a randombytes() that provides
the specified coins. This is better than adding complications into every
layer of cryptographic primitives that _might_ be directly or indirectly
calling randomized subroutines. The primitives are already painful to
review; further complications are making the review job even harder.

It's also worth noting that the reason coins are made explicit in [1] is
to try to use a separate secret to limit the damage done by a broken
RNG. To the extent that we've seen NIST approving structurally broken
RNGs such as Dual EC, centrally fixing the RNG standards is simpler and
less error-prone than complicating every protocol to try to compensate.
To the extent that there are concerns about inadequate entropy, NIST's
RNG standards already allow "additional input" (and promise to keep such
inputs secret!); using this already-standardized mechanism is again
simpler than complicating every protocol.

---Dan

[Scott Fluhrer (sfluhrer)]

In practice, the NIST validation procedure (current ACVP) will give all the parameters to the crypto routine being tested (including any random coins), and it’ll expect one specific response – any other response will be considered an error.  That’s how it’s done today, and I don’t expect that to change.

 

On the other hand, there’s no specific reason why this testing needs to be done using the public APIs; you can use a backdoor API (that sets the randomness), and NIST is OK with that.

 

From: pqc-...@list.nist.gov <pqc-...@list.nist.gov> On Behalf Of Kris Kwiatkowski
Sent: Friday, November 19, 2021 12:29 PM
To: pqc-...@list.nist.gov
Subject: Re: [pqc-forum] Deterministic KEM key generation

 

> However, I do not think that NIST should make the deterministic approach mandatory for FIPS 140-3 compliance

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/b2235fc0-e249-3819-20d7-34b5b337f164%40pqshield.com.

[Karolin Varner]

Thank you for your very detailed response!

Agreed to your points! It is certainly nicer to avoid forcing primitives to define their own randomness expansion method.

> To the extent that such things are required, they're compatible with the
> randombytes() interface: simply plug in a randombytes() that provides
> the specified coins.

It is true that a deterministic API taking coins can be constructed from the randombytes API,
although let me point out that this is quite involved:

1. Have randombytes() be backed by some run-time polymorphic interface (e.g. with function pointers)
2. Before calling the KEM functions, replace the RNG with a seeded one
3. Call the KEM function
4. Restore the original RNG

Thread safety could be achieved by making the function pointer a thread local variable, complicating the implementation even more.
The entire thing seems fairly brittle; something that might work, but coincidentally. The inverse transform would be trivial regardless
of whether the deterministic API takes a seed or whether it is polymorphic over the RNG.

I don't doubt that there will always be a way to get an implementation to produce predictable results by controlling the
execution environment; my question concerns more whether the standard will include or exclude how the entropy is used.

For a NIST standardized KEM, I can expect compliant implementations to be interoperable; i.e.

1. Keys generated by one implementation can be used by another
2. Ciphertexts generated by one implementation can be decrypted by another

Stated succinctly: Applying the above coinedness-transform (or an analogue for the given implementation), can I expect two compliant implementations to produce the same output given the same entropy?

Yes, this would be mainly useful for testing, but testing goes beyond just a specific implementation; my use case is protocol definition:
Protocols could come with test vectors as part of the specification, but only if the KEM is deterministic (because otherwise there would exist valid implementations that produce different vectors).

Libraries implementing KEMs could be replaced more easily by utilizing determinism: Matching test data before and after a library exchange
does not provide a proof-of-equivalence or a proof-of-absence-of-timing-side-channels, but still reduces the amount of
wiggle room for mistakes more than just relying on the above stated KEM interoperability properties.

I expect similar arguments would apply to signatures, but I am not as familiar with those.

> It's also worth noting that the reason coins are made explicit in [1] is
> to try to use a separate secret to limit the damage done by a broken
> RNG.

Choosing the pqwg paper as an example here was admittedly misleading, as the paper constructs a
more secure RNG from a less secure one. As you said, the technique does not actually rely on determinism of the KEM
and comping up with a randombytes() implementation utilizing the technique to the same effect would be trivial.

In the classical realm, hashing to elliptic curve points seems to enjoy some popularity according to the number of citations of [0];
that should be sort-of analogue to KEM encryption and decryption taking coins. I suspect we could come up with some
commitment scheme, where proving after the fact that a KEM ciphertext or keypair was generated using a specific string of entropy would be useful.
The FO-Transform does just that internally AFAICR.

Although, I do think this goes beyond what uses a standard should currently consider…

> Skimming SUPERCOP's records for the alternates finds already at the top
> of the list that the BIKE _decapsulation_ software is using randomness.

I didn't know that! Thank you! I'd be fine with decapsulation using entropy too, as long as the output (and even low probability decryption failure) is deterministic given the same entropy.

Best,
KV

[0]: https://www.degruyter.com/document/doi/10.1515/JMC.2009.022/html

The messages Dan referenced:

31 Oct 2016 08:56:39 +0000 – https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/QufjmfhuRcs
27 Mar 2017 13:50:51 +0000 - I could not find this.
8 Sep 2021 01:34:22 +0200 - https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/AjK3wpZFBD

[D. J. Bernstein]

Karolin Varner writes:
> Stated succinctly: Applying the above coinedness-transform (or an
> analogue for the given implementation), can I expect two compliant
> implementations to produce the same output given the same entropy?

The software for NISTPQC submissions generally aims for a "yes" answer
(although because of bugs it can fail). This is partially tested by the
NIST KATs, and more comprehensively tested by the SUPERCOP checksums.

Some specifications aim for a "yes" answer, fully specifying how each
random object is computed from RNG output. This is explicit in, e.g.,
https://classic.mceliece.org/nist/mceliece-20201010.pdf, and motivated
in Section 4.4 of that document as a way to stop ROCA-type failures. I
would be supportive of asking for all standards to have a "yes" answer.

A subtlety here (noted in https://blog.cr.yp.to/20170719-pqbench.html)
is that SUPERCOP's randombytes() computes an infinite stream of bytes,
returned upon demand. NIST's randombytes() doesn't do this. NIST's RNGs
produce different output depending on how the RNG requests happen to be
bundled, and become impressively slow if, e.g., there's a frequently
used uint32_random() subroutine. This performance problem creates an
unfortunate speed incentive to complicate specifications so as to bundle
RNG requests. As with other RNG problems, the simplest solution is to
fix the RNG---which doesn't require changing NIST's RNG standards; a
wrapper that pulls fixed-size RNG output into a buffer is good enough.

> Protocols could come with test vectors as part of the specification,
> but only if the KEM is deterministic (because otherwise there would
> exist valid implementations that produce different vectors).

A randomized protocol using a randomized KEM can be tested the same way
that the KEM is tested, with a deterministic randombytes() substitute.

> 27 Mar 2017 13:50:51 +0000 - I could not find this.

Hmmm. NIST gave the impression of having moved all the messages over to
Google in late 2017, but I also don't see this message in Google's
archive. A copy of the message (as received from the list at the time)
appears below.

---Dan

D. J. Bernstein writes:
> Subject: Re: [Pqc-forum] ANSI C and Randomness
> From: "D. J. Bernstein" <d...@cr.yp.to>
> Date: Mon, 27 Mar 2017 13:50:51 +0000
> To: pqc-...@nist.gov
> Message-ID: <2017032713505...@cr.yp.to>
>
> There's a synchronized core API used for NaCl (production), libsodium
> (production), TweetNaCl (production), and SUPERCOP (benchmarking of
> thousands of implementations of various cryptographic primitives). Let
> me explain exactly how randomness works in this API.
>
> I recommend that NIST follow the same details. This means minor tweaks
> to the currently specified API; the main benefits are (1) simplicity for
> submitters and (2) usability in production. If there's consensus on the
> principles then I'll be happy to do the work to draft a tweaked spec.
>
> In this API, a caller who wants to (e.g.) generate a signing key calls
> crypto_sign_keypair as documented in https://nacl.cr.yp.to/sign.html:
>
> #include "crypto_sign.h"
>
> unsigned char pk[crypto_sign_PUBLICKEYBYTES];
> unsigned char sk[crypto_sign_SECRETKEYBYTES];
>
> crypto_sign_keypair(pk,sk);
>
> Obviously, if you're implementing the crypto_sign_keypair function, you
> need to generate some number of random bytes; concretely, let's say 32
> bytes for 256-bit ECC keys. The recommended way to do this---what all
> NaCl implementations and many SUPERCOP implementations do---looks like
> this:
>
> #include "crypto_sign.h"
> #include "randombytes.h"
>
> int crypto_sign_keypair(unsigned char *pk,unsigned char *sk)
> {
> ...
> randombytes(sk,32);
> ...
> }
>
> See, e.g., crypto_sign/ed25519/ref/keypair.c in NaCl, which includes
> these lines; or the same file in SUPERCOP. The randombytes.h prototype
> for randombytes() is
>
> extern void randombytes(unsigned char *,unsigned long long)
>
> which, like the rest of the API, uses "long long" rather than "size_t"
> to reduce the chance that programmers bump into a common class of 32-bit
> integer overflows on 32-bit machines.
>
> In NaCl (production), the randombytes() implementation simply reads from
> /dev/urandom. Actually, it isn't quite so simple---for example, opening
> /dev/urandom can fail, and then randombytes() pauses and tries again.
>
> The randombytes() implementation in future versions of NaCl will prefer
> getentropy()/getrandom() when they're available. These calls are simpler
> than /dev/urandom, and they avoid a dangerous misfeature of /dev/urandom
> on Linux, namely returning non-random data if the system setup or reboot
> process never put randomness into the OS kernel's entropy pool.
>
> The randombytes() implementation is linked separately from libnacl.a, so
> it's easy to substitute other implementations of randombytes(). Older
> crypto libraries typically have their own code to maintain their own
> entropy pools (separate from the OS kernel's entropy pool), and of
> course randombytes() could be implemented to do the same thing. However,
> this has historically been a security nightmare. The main argument for
> an application-level entropy pool is speed, but
>
> (1) kernels are upgrading to fast stream ciphers,
> (2) getentropy()/getrandom() already have fairly low overhead, and
> (3) it's hard to find evidence of users noticing this overhead.
>
> If you're using randombytes() and notice its cost, you might be tempted
> to build your own entropy pool on top of randombytes(), but this is
> clearly worse from a software-engineering perspective than replacing the
> randombytes() implementation with something that maintains its own pool.
> In the long run I expect that everyone will converge on simply using the
> kernel's entropy pool, as we already do in NaCl.
>
> For SUPERCOP (benchmarking), the story is different. We want to measure
> the speed of the fastest _working_ implementation; we run a known-answer
> test (or more precisely what NIST calls an "MCT") to catch non-working
> implementations. Of course, implementations can slip past these tests,
> and then we think about whether to change the tests or apply different
> verification/validation techniques, but what matters here is that we
> want to see all the implementations producing known outputs from known
> inputs.
>
> Obviously a randomized function such as crypto_sign_keypair() _doesn't_
> produce the same outputs when we give it the same inputs---unless we
> replace its randomness with something deterministic. So SUPERCOP has a
> deterministic randombytes() used to generate known answers.
>
> This deterministic randombytes() in SUPERCOP is, obviously, different
> from the randombytes() used for production in NaCl. It could be faster
> or slower---which doesn't matter for known-answer tests, but does matter
> for benchmarking, since the point of benchmarking is to predict the
> performance that users will see. We're planning to upgrade SUPERCOP to
>
> * use a state-of-the-art stream cipher for an RNG for benchmarking,
> since this is the RNG speed users should get in the long run; and
>
> * to report statistics on the number of random bytes consumed and the
> number of randombytes() calls, so that it's easy to predict the
> impact of slower RNGs.
>
> Simply subtracting the time used inside randombytes() would be a worse
> predictor, since RNGs _do_ cost something. There's a real cost in (e.g.)
> lattice software typically using much more randomness than ECC software,
> and we don't want people playing games with hiding this cost inside a
> caller setting up random data.
>
> Some SUPERCOP implementations actually generate randomness in other ways
> (e.g., through OpenSSL), as indicated by an absence of "checksumsmall"
> and "checksumbig" files. SUPERCOP skips the known-answer requirement for
> those implementations, and of course those implementations also won't
> work with other proposed known-answer APIs.
>
> Bassham, Lawrence E (Fed) writes:
> > The API is for testing purposes only.
>
> I understand that this is NIST's sole short-term goal. However, the
> success of the NaCl/libsodium/TweetNaCl API shows that this API style is
> also very well suited for production. There are significant benefits to
> having a unified code base for tests, benchmarks, and production. The
> only cost is a bit more attention to the API details.
>
> Hars, Laszlo writes:
> [ regarding reading (e.g.) 32 bytes and expanding as necessary ]
> > This seems to extend the tasks for the submitter to design a faster DRBG, too.
>
> Yes, and surely this is _not_ what we want to force submitters to be
> spending time on. Simply calling randombytes() lets the post-quantum
> experts focus on doing post-quantum stuff, while delegating the
> randombytes() implementation to the RNG experts.
>
> Of course if some submitter _does_ want to use an ad-hoc DRBG, perhaps
> eliminating many cipher rounds for speed and arguing that this is safe
> in the context of a particular public-key system, then the submitter can
> call randombytes() for a seed and then apply this DRBG, and of course
> also define the public-key system to use this DRBG. Formally, this looks
> just like any other public-key system starting from some random bytes;
> the use of the DRBG is inside the specification of the system.
>
> Nigel Smart writes:
> > b) It would not be the call someone would use "in real
> > life", where they would actually get entropy externally
> > and then feed it into the function. Which is a better
> > design
>
> This is a worse design both for semantics and for syntax.
>
> Regarding semantics, there's a long history of cryptographic functions
> that use rejection sampling and thus can use any number of random bits.
> If we insist on partitioning the call into first generating some number
> of independent uniform random bits and then calling a deterministic
> function, then we're demanding that the function
>
> * include its own DRBG, which again is surely _not_ what we want to
> force submitters to be spending time on; or
>
> * take an excessive number of input bits to reach (say) rejection
> probability 2^(-128), which looks like it would be a serious
> slowdown for many primitives of interest.
>
> There's a much cleaner semantics that's sometimes used in mathematically
> _defining_ the concept of a randomized algorithm: namely, provide an
> _infinite_ string of independent uniform random bits as input to a
> deterministic function. But this isn't the semantics provided by any of
> the external-entropy C API proposals; it hides the question of how many
> bits to actually generate.
>
> As for syntax, there's a fringe argument that a randomized algorithm
> should be _presented_ as a deterministic function applied to a random
> string---that any other syntax for algorithms should be disallowed. As
> noted in my email dated 31 Oct 2016 08:56:39 +0000, this argument is
> ignored by approximately 100% of algorithm designers and programmers.
> Passing an RNG argument around through all the layers of subroutines
> that need (or might need) the RNG is obviously worse syntax than having
> each subroutine generate its own random bytes as needed.
>
> > as it separates entropy generation from use
> > of such entropy in the code (i.e. one would not be dependent
> > on the other).
>
> Isolating the RNG in a separate randombytes() library achieves the same
> separation with better semantics and better syntax.
>
> ---Dan
> _______________________________________________
> pqc-forum mailing list
> pqc-...@nist.gov
> (_internal_name)s