More details on a "derandomized" layer for the API for FIPS 203, 204, and 205

[Moody, Dustin (Fed)]

Hi all,

 

This post will outline one of the changes NIST is planning for FIPS 203, 204, and 205. This change would add a “derandomized” layer to the API; it was briefly introduced at the recent workshop.

 

In the current drafts of all three FIPS, there are top-level algorithms that generate randomness as an internal step. (By “top-level”, we mean the three main algorithms of the scheme, e.g., KeyGen, Encaps, and Decaps for KEMs.) In FIPS 203, for example, both ML-KEM.KeyGen() and ML-KEM.Encaps(ek) begin by generating random byte strings. This approach has some disadvantages:

• CMVP testing is inconvenient, as known-answer testing naturally expects deterministic functions.
• it is not entirely clear how one can store seeds instead of private keys while remaining FIPS-compliant.

 

The proposed change would alter the internal algorithms of all three FIPS as follows. Roughly speaking, each top-level algorithm would be split into two stages:

Stage 1: Receive INPUT; call the RNG to generate COINS; throw an exception if a failure occurs.

Stage 2: Call a deterministic subroutine with input (INPUT, COINS) and output what the subroutine outputs.

This would be done in such a way that the functionality of the top-level algorithms is identical. (This means that the functionality of the schemes ML-KEM, ML-DSA, and SLH-DSA would not change in any way.) Of course, this change would necessitate adding at least three new algorithms to each FIPS. These new algorithms would specify the deterministic subroutines mentioned in Stage 2 above.

 

Continuing with FIPS 203 as the example, the new “API” would now look like the below. (Analogous interfaces for ML-DSA and SLH-DSA will be shared in a reply to this post.)

 

ML-KEM.KeyGen_internal(d, z)                 

ML-KEM.Encaps_internal(ek, m)               

ML-KEM.Decaps_internal(dk, c)                // Decaps already deterministic; only added for consistency

 

ML-KEM.KeyGen()           // generate random 32-byte d, z; call KeyGen_internal(d,z)

ML-KEM.Encaps(ek)        // generate random 32-byte m; call Encaps_internal(ek, m)

ML-KEM.Decaps(dk, c)   // call Decaps_internal(dk, c)

 

Some points:

• this facilitates CMVP testing on the *_internal functions, as they are all deterministic.
• it is now easy to store dk as a seed: simply keep the seed (d, z), and run KeyGen_internal(d, z) to generate dk as needed.
• with the previous point as an exception, the *_internal functions should not be available in non-test mode.

 

Any feedback on the above is most welcome. (Note that a recent post suggests using a single 32-byte seed instead of the two 32-byte seeds d and z above. Please discuss that specific suggestion in that thread, so we can keep this thread on the general topic of derandomization for all three FIPS.)

 

Best,

Gorjan

(on behalf of NIST PQC group.)

 

[dustin...@nist.gov]

Details for ML-DSA and SLH-DSA:

New ML-DSA interface:

ML-DSA.KeyGen_internal(\xi)

ML-DSA.Sign_internal(sk, M’, rnd )

ML-DSA.Verify_internal(pk, M’, \sigma)

 

ML-DSA.KeyGen() \\ generate random 32-byte seed, \xi; call ML-DSA.KeyGen_internal(\xi)

ML-DSA.Sign(sk, M, ctx) \\ Either randomly generate a 32 byte random value rnd (default, hedged case) or use a 32-byte all-zeroes string for rnd (deterministic case); Generate M’ from M and ctx; call ML-DSA.Sign_internal(sk, M’, rnd )

HashML-DSA.Sign(sk, M, ctx, PH) \\ Either randomly generate a 32 byte random value rnd (default, hedged case) or use a 32-byte all-zeroes string for rnd (deterministic case); Generate M’ from M, ctx, and PH; call ML-DSA.Sign_internal(sk, M’, rnd )

ML-DSA.Verify(pk, M, \sigma, ctx) \\ Generate M’ from M and ctx; call ML-DSA.Verify_internal (pk, c)

HashML-DSA.Verify(sk, M, ctx, PH) \\ Generate M’ from M, ctx, and PH; call ML-DSA.Verify_internal (pk, M’)

 

New SLH-DSA interface:

slh_keygen_internal(SK.seed, SK.prf, PK.seed)

slh_sign_internal(M, SK, addrnd)                          // opt_rand <- addrnd

slh_sign_internal(M, SK)                                       // opt_rand <- PK.seed

sig_verify_internal(M, SIG, PK)

 

slh_keygen()              // generate random SK.seed, SK.pdf, and PK.seed. call slh_keygen_internal(SK.seed, SK.prf, PK.seed)

slh_sign(M, ctx, SK)  // optionally generate random addrnd. Construct domain separated message M'. call slh_sign_internal(M', SK, addrnd) or slh_sign_internal(M', SK)

hash_slh_sign(M, ctx, PH, SK) // optionally generate random andrnd. Construct domain separated message M' from PH(M). call slh_sign_internal(M', SK, addrnd) or slh_sign_internal(M', SK)

slh_verify(M, SIG, cts, PK) // Construct domain separated message M'. call sig_verify_internal(M', SIG, PK)

hash_slh_verify(M, SIG, ctx, PH, PK) // Construct domain separated message M' from PH(M). call slh_verify_internal(M', SIG, PK)

// See slide 11 of https://csrc.nist.gov/csrc/media/Presentations/2024/fips-205/images-media/kelsey-fips-205-pqc2024.pdf for illustration of construction of domain separated message M'

[Blumenthal, Uri - 0553 - MITLL]

Nice to hear! This API change is definitely a move in the right direction.

 

Considering that the recently-announced CNSA-2.0 does not include SHAKE or SHA-3, would NIST consider using SHA-2-based XOF?

 

Thanks!

-- 

V/R,

Uri

 

 

From: 'Moody, Dustin (Fed)' via pqc-forum <pqc-...@list.nist.gov>
Date: Friday, April 19, 2024 at 14:06
To: pqc-forum <pqc-...@list.nist.gov>
Subject: [EXT] [pqc-forum] More details on a "derandomized" layer for the API for FIPS 203, 204, and 205

Hi all, This post will outline one of the changes NIST is planning for FIPS 203, 204, and 205. This change would add a “derandomized” layer to the API; it was briefly introduced at the recent workshop. In the current drafts of all three FIPS,

ZjQcmQRYFpfptBannerStart

This Message Is From an External Sender This message came from outside the Laboratory.

ZjQcmQRYFpfptBannerEnd

--
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/SA1PR09MB86698E602A2BD77A095475B9E50D2%40SA1PR09MB8669.namprd09.prod.outlook.com.

[D. J. Bernstein]

'Moody, Dustin (Fed)' via pqc-forum writes:
> This change would add a “derandomized” layer to the API

Does this mean _requiring_ implementations to have that layer? Or
pressuring implementations to have that layer, by saying validation
won't be allowed otherwise?

Either way, is this something NIST-wide, where, e.g., RSA key generation
will also ask for such a layer? Or is it specific to NISTPQC? Or just
these three FIPS?

> known-answer testing naturally expects deterministic functions

SUPERCOP carries out known-answer tests on randomized functions. This is
a simple matter of intercepting the calls to randombytes(). This is done
centrally, so all of the implementations in SUPERCOP are free to simply
call randombytes() whenever they want, the same way that algorithms in
books and papers generate randomness whenever they want.

I see more than a thousand calls to randombytes() in the implementations
currently in SUPERCOP. Of course, there are many functions similar to
randombytes() in cryptographic libraries, such as RAND_bytes() in
OpenSSL; these are used all over the place in cryptographic software.

The opposite approach of testing only deterministic functions, and
requiring randomized functions to be expressed as "generate N bytes of
randomness and call a deterministic function" wrappers, has the
following software-engineering disadvantages:

* Bugs in the wrappers (e.g., not generating enough randomness, or
passing a pointer to something other than the randomness buffer)
aren't caught. This is a failure of code coverage.

* Any primitive that naturally uses unbounded amounts of randomness
has to do extra work to maintain its own PRNG. For example, an RSA
key generator can't simply generate a random number, test whether
the number is prime, and try again as often as necessary; the RSA
key generator also needs code to maintain a PRNG.

* The PRNG management creates coupling across functions that would
otherwise be independent. For example, an RSA key-generation
function can't simply make two calls to an RSA prime-generation
function that calls randombytes(); a PRNG needs to be initialized
by the high-level function and passed around between the functions.

_Some_ cryptographic implementations have little or no penalty here, but
overall the cryptographic ecosystem becomes more complicated, with less
testing and more ways to get things wrong.

The number of implementations of randomized cryptographic primitives is
much larger than the number of cryptographic test frameworks. If some
frameworks are inadequate, the right way forward is to centrally fix
those frameworks, not to impose complications upon the whole ecosystem.

---D. J. Bernstein

P.S. For further comments and examples, see my postings dated 27 Mar
2017 13:50:51 +0000, 31 Mar 2017 22:35:27 +0000, 11 Apr 2017 16:36:46
+0000, 11 Apr 2017 20:35:57 +0000, 26 Apr 2017 09:37:45 +0000, and 27
Apr 2017 21:12:18 +0000.

[Watson Ladd]

How about the following:

If we want the deencapsulation key to be a seed for exchange between
systems we can do that, and let implementations store the expanded
form as an optimization. Similarly we permit RSA implementations that
compute auxiliary data to assist in CRT on decryption. This
complicates the API only insofar as it adds an additional function to
expand the private key and then use it.

The question of testing only interfaces creates some challenges for
libraries: there's not a great way to do this in some programming
environments, so the CMVP tests would have to be internal to the
library rather than a framework the artifact plugs into. That's
manageable, but might complicate ACVP depending on how exactly its
done. I think we absolutely need to avoid exposing the derandomization
to applications: it would create many bugs, although occasionally
useful for some advanced tricks.

Sincerely,
Watson

--
Astra mortemque praestare gradatim

[Filippo Valsorda]

This is excellent news. As an implementer and as a contributor and maintainer of test vector suites, this will make my life significantly easier and expand real-world test coverage.

Without specified derandomized interfaces, there is no fixed target for test vectors, which discourages test vector sharing. Many real-world vulnerabilities in signature algorithm implementations could have been avoided with the right reusable test vectors. Most recently, the PuTTY P-521 nonce bias: it would have been immediately noticeable with a test vector for an equivalent ECDSA.Sign_internal, but since the details of the DRBG are unspecified, these vectors are not readily available.

Does NIST intend to provide derandomized interfaces for existing algorithms, too? I ask because if NIST doesn't plan to, maybe we should start an effort to agree on such interfaces in the context of a project such as Wycheproof.

[Filippo Valsorda]

About the extent to which the derandomized interfaces may be exposed to applications, should a distinction be made between the derandomized keygen functions and the rest?

Exposing derandomized signing or encapsulation as non-test interfaces sounds undesirable, but exposing derandomized keygen is indirectly necessary to expand private keys stored as seeds, and directly to perform deterministic key generation. Is the latter an allowed use case?