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