OIDs for "pre-hash" ML-DSA and SLH-DSA

1,298 views
Skip to first unread message

David A. Cooper

unread,
Aug 30, 2024, 1:04:02 PM8/30/24
to pqc-forum
Hello all,

The OIDs for "pre-hash" ML-DSA and SLH-DSA signatures are now available
at
https://csrc.nist.gov/projects/computer-security-objects-register/algorithm-registration.
Based on the feedback received on this list, public keys that are used
to verify pre-hash signatures are identified with the pre-hash OIDs.

As the public keys and signatures are the same for "pure" and
"pre-hash," the encodings of public keys and signatures within ASN.1
structures that are being defined in the IETF for "pure" signatures will
apply for "pre-hash" signatures are well.


niux_d...@icloud.com

unread,
Aug 31, 2024, 1:19:34 AM8/31/24
to David A. Cooper, pqc-forum
I think we're missing OIDs for ML-DSA with SHA-3/SHAKE parameters.
> --
> 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/222995c2-1d4a-4b2d-b1bc-2a120e58268c%40nist.gov.

Markku-Juhani O. Saarinen

unread,
Aug 31, 2024, 3:21:41 AM8/31/24
to niux_d...@icloud.com, David A. Cooper, pqc-forum
On Sat, Aug 31, 2024 at 5:19 AM niux_dannyniu via pqc-forum <pqc-...@list.nist.gov> wrote:
I think we're missing OIDs for ML-DSA with SHA-3/SHAKE parameters.


Yep, or at least a slight clarification for the outside-of-module hashing architecture.

ML-DSA, of course, uses SHAKE in pure mode, so it would make sense to try to avoid unnecessarily pre-hashing with SHAKE if one can. There are some security properties that are lost, albeit a bit obscure ones. I guess this is why they left it out..


My impression is that SHA2 is available for ML-DSA via prehash because of legacy systems (CNSA) where a need to sign plain SHA2 message hashes exists. I also doubt that there are similar legacy systems with SHA3 or SHAKE. SLH-DSA has a pre-hash for an additional reason, to avoid hashing the entire message twice (and have it entirely in memory) when signing. So, it has more OIDs.


Another reason to do pre-hashing is to be able to hash outside the signing module. This is especially relevant for hardware signing modules with low-bandwidth interfaces like smartcards (typically serial) or Root-of-Trust (typically mailbox). There is one confusing/contradictory aspect related to this in the spec:


Step 6 of the ML-DSA internal signing function (Algorithm 7) and Step 7 of the internal verification function (Algorithm 8) have a comment about variable mu: "message representative that may optionally be computed in a different cryptographic module."  This implies that the entire padding (with "tr" and "ctx" variables) can be done outside the module.


Now, if "mu" is coming from the outside, this means that the outside module can bypass the wrapper functions such as ML-DSA.Sign() (Algorithm 2), and HashML-DSA.Sign (Algorithm 4) as the external-facing wrapper functions don't have such an input.


However, Section 6 (Internal Functions) states "Other than for testing purposes, the interfaces for key generation and signature generation specified in this section should not be made available to applications,"


So this leaves open the question about passing the variable "mu" to the internal functions.


Or perhaps this is as simple as not considering the external hash function (which is also assumed to be FIPS 140-3 certified, i.e., a "module") as a part of the "application." However, additional interfaces must be exposed since these modules are physically separate (example: you're a release engineer and your PC is hashing your gigabyte app update, and then you use your closely guarded smart card key to sign it.)


Cheers,
-markku

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

niux_d...@icloud.com

unread,
Sep 3, 2024, 8:50:23 AM9/3/24
to Markku-Juhani O. Saarinen, David A. Cooper, pqc-forum


2024年8月31日 15:21,Markku-Juhani O. Saarinen <mjos....@gmail.com> 写道:

SLH-DSA has a pre-hash for an additional reason, to avoid hashing the entire message twice (and have it entirely in memory) when signing. 

Can you explain more? It appears to me that the same reason is equally applicable to ML-DSA.

And the only place the message gets an extra hashing in SLH-DSA is when generating R - the randomization string, which I think can be replaced with a TRNG if one wants to avoid hedged and deterministic signing; and this is equally applicable to ML-DSA.

Markku-Juhani O. Saarinen

unread,
Sep 3, 2024, 12:49:32 PM9/3/24
to niux_d...@icloud.com, David A. Cooper, pqc-forum
On Tue, Sep 3, 2024, 06:50 niux_dannyniu via pqc-forum <pqc-...@list.nist.gov> wrote:
2024年8月31日 15:21,Markku-Juhani O. Saarinen <mjos....@gmail.com> 写道:

SLH-DSA has a pre-hash for an additional reason, to avoid hashing the entire message twice (and have it entirely in memory) when signing. 

Can you explain more? It appears to me that the same reason is equally applicable to ML-DSA.

Hi,

So.. ML-DSA core requires only the "mu" value for signing and verification in all instances, so the message itself needs to be processed only once. The message hash is hashed again in case of pre-hashing, and of course processed further internally, but that's a different matter.

Otoh, the SLH-DSA signing pseudocode requires two processing passes, on lines 3 and 5 of Algorithm 19, where entire message M/M' ishashes with different hash prefixes in case of pure SLH-DSA. As you note, the first pass to compute R is basically redundant in the case of randomized signing (R is randomized anyway). We have commented to NIST about this, but the operation ended up in the standard anyway. Just using a random R would be completely interoperable in practice, but would fail CAVP testing,.

For deterministic mode the R computation hash makes sense (or if the developer is not so sure about random numbers -- in which case one probably should disable most crypto functions anyway. ML-KEM encaps, any kind of keygen, etc. wouldn't be secure either.)

Cheers,
Markku



And the only place the message gets an extra hashing in SLH-DSA is when generating R - the randomization string, which I think can be replaced with a TRNG if one wants to avoid hedged and deterministic signing; and this is equally applicable to ML-DSA.

--
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.

David A. Cooper

unread,
Sep 4, 2024, 11:58:24 AM9/4/24
to Markku-Juhani O. Saarinen, niux_d...@icloud.com, pqc-forum
Ray Perlner explained the reason that SHAKE256 was not listed in the switch statements in FIPS 204 in his presentation at the 5th PQC Standardization Conference and also in https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/HmSNaPpX214/m/53Zbf7CVBQAJ.

When defining OIDs for the "pre-hash" versions of ML-DSA and SLH-DSA, NIST defined one OID for each parameter set. So, SLH-DSA only has more OIDs because it has more parameter sets.

While the "switch" statements in HashML-DSA.Sign, HashML-DSA.Verify, hash_slh_sign, and hash_slh_verify only list a few hash functions and XOFs, the text of the FIPS note that other (approved) hash functions or XOFs may be used.

Markku-Juhani O. Saarinen

unread,
Sep 4, 2024, 9:23:44 PM9/4/24
to David A. Cooper, niux_d...@icloud.com, pqc-forum
Thanks David,

So how about that  "message representative that may optionally be computed in a different cryptographic module" line in the ML-DSA spec for which no interface is defined. Can I actually FIPS-certify a module that does this as there is no defined interface to pass that message representative into the module in the spec?

Cheers,
-markku

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


kisley

unread,
Sep 24, 2024, 3:51:54 PM9/24/24
to pqc-forum, Markku-Juhani O. Saarinen, niux_d...@icloud.com, pqc-forum, David A. Cooper
I am sure this is a stupid/basic question, but there seems to be a conflict between FIPS 204 and the OID specifications.

FIPS 204 section 5.4 indicates that multiple hash algorithms are supported, subject to the strength guideline. 

However, the only pre-hash OIDs defined (https://csrc.nist.gov/projects/computer-security-objects-register/algorithm-registration) encode the pre-hash method: id-hash-ml-dsa-[44 | 65 | 87]-with-sha512 - and limit it to SHA512.  Moreover, the OID assignment seems to preclude any modification or invention: the sigAlgs are assigned sequentially without gaps across HashML-DSA and SLH-DSA:
  • ML-DSA: sigAlgs 17,18,19
  • SLH-DSA: sigAlgs 10-31
  • HashML-DSA: sigAlgs 32,33,34
  • HashSLH-DSA: sigAlgs 35-46

It really seems that the binding is intentional, excluding all ML-DSA pre-hash mechanisms other than SHA-512. 

My understanding of the strength calculation is that especially for ML-DSA-44 and ML-DSA-65, other hash algorithms would be usable. 

Are we missing OIDs, or am I missing something?

R Kisley, IBM

David A. Cooper

unread,
Sep 24, 2024, 5:00:29 PM9/24/24
to kisley, pqc-forum
The choice of object identifiers (OID) to define is something that was discussed on the pqc-forum previously. While FIPS 204 does not restrict which approved hash function or XOF is used for pre-hashng, NIST chose to define OIDs for only one option for each parameter set, as fewer options makes interoperability easier. However, the fact that sigAlgs are assigned sequentially has no meaning. The only requirement for an OID is that it unambiguously identify one thing. The form of the OID helps to allocate from the space of all possible OIDs in a way that prevents an OID from being assigned two different meanings, but the value of the OID has no relation to its meaning. So, NIST could define new OIDs for HashML-DSA. The new OIDs just wouldn't be numbered sequentially with the current ones.

While NIST only defined one OID for each parameter set, anyone can define OIDs. There are places where you can obtain an OID arc (i.e., a subspace from the OID space) from which you could assign your own OIDs with whatever meaning you want, including specifying different options for pre-hash algorithms to use with ML-DSA. Of course, if you define your own OID, it is less likely that others will recognize it, so that would be a barrier to interoperability.

Many protocols do not use OIDs to identify signature algorithms (e.g., ones based on XML or JSON). For such protocols, the set of identifiers to define would be determined by organizations other than NIST (e.g., IETF).

Ben Livelsberger

unread,
Nov 8, 2024, 4:47:23 PM11/8/24
to pqc-forum, Markku-Juhani O. Saarinen, niux_d...@icloud.com, pqc-forum, David A. Cooper
Hi Markku,

I’m a member of the CAVP team at NIST. From our perspective, yes. We interpret the "message representative that may optionally be 
computed in a different cryptographic module" comments in L6 of Algorithm 7 and L7 of Algorithm 8 as allowing alternate interfaces 
for those algorithms. That is, we interpret FIPS 204 as allowing ML-DSA.Sign_internal(sk, mu, rnd) in addition to 
ML-DSA.Sign_internal(sk, 𝑀 ′, rnd) and ML-DSA.Verify_internal(𝑝𝑘, mu, 𝜎) in addition to ML-DSA.Verify_internal(𝑝𝑘, 𝑀 ′, 𝜎). We do 
not currently support testing ML-DSA.Sign_internal(sk, mu, rnd) and ML-DSA.Verify_internal(𝑝𝑘, mu, 𝜎) via ACVTS, but this is 
something we will add.

Thank you,

Ben

On Wednesday, September 4, 2024 at 9:23:44 PM UTC-4 Markku-Juhani O. Saarinen wrote:
> To unsubscribe from this group and stop receiving emails from it, send an email to pqc-forum+unsubscribe@list.nist.gov.

> To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/222995c2-1d4a-4b2d-b1bc-2a120e58268c%40nist.gov.

--
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+unsubscribe@list.nist.gov.
Reply all
Reply to author
Forward
0 new messages