Pre-hash options for SLH-DSA

[David A. Cooper]

As was previously announced on the pqc-forum, SLH-DSA will specify separate "pure" and "pre-hash" versions. For the pre-hash versions, each of the OIDs that NIST will assign will specify both the SLH-DSA parameter set and the function to use for pre-hashing. Given the number of SLH-DSA parameter sets and the number of NIST approved hash functions and XOFs, there is a very large number of potential combinations. While assigning OIDs for more combinations would allow for more flexibility, we believe there is a benefit in minimizing the number of options in order to facilitate interoperability.

For SLH-DSA, we are currently considering assigning an OID for one pre-hash option for each parameter set, as in the table below. For the SHA2 parameter sets, SHA-512 would be used for the pre-hash at all security levels. While SHA-256 would provide sufficient security for the category 1 parameter sets, SHA-512 is faster than SHA-256 on many platforms when hashing large messages. SHA-512 is also a more conservative option, which many people have requested. For the SHAKE parameter sets, SHAKE256 would be used with the category 3 and 5 parameter sets. For the category 1 parameter sets, SHAKE128 would be used, since it is faster than SHAKE256 and it provides sufficient security for category 1.

A slightly different approach that could be followed is the one recommended in Section 4 of https://www.ietf.org/archive/id/draft-ietf-lamps-cms-sphincs-plus-07.html for selecting a digest algorithm to use in CMS. The recommendations in that draft are the same as in the table below, with the exception that SHA-256 is recommended when using the SLH-DSA-SHA2-128s and SLH-DSA-SHA2-128f parameter sets.

We would appreciate any feedback people may have about what OIDs to assign for pre-hash versions of SLH-DSA.

Thank you,

David

parameter set	pre-hash function
SLH-DSA-SHA2-128s	SHA-512
SLH-DSA-SHA2-128f	SHA-512
SLH-DSA-SHA2-192s	SHA-512
SLH-DSA-SHA2-192f	SHA-512
SLH-DSA-SHA2-256s	SHA-512
SLH-DSA-SHA2-256f	SHA-512
SLH-DSA-SHAKE-128s	SHAKE128 with 256 bits of output
SLH-DSA-SHAKE-128f	SHAKE128 with 256 bits of output
SLH-DSA-SHAKE-192s	SHAKE256 with 512 bits of output
SLH-DSA-SHAKE-192f	SHAKE256 with 512 bits of output
SLH-DSA-SHAKE-256s	SHAKE256 with 512 bits of output
SLH-DSA-SHAKE-256f	SHAKE256 with 512 bits of output

[Markku-Juhani O. Saarinen]

Thanks David,

Collision resistance assumptions aside, let's look at these technical choices:

SLH-DSA-SHA2-128s and SLH-DSA-SHA2-128f versions would currently *not* require an implementation of SHA-512 -- the proposed prehashing option would make SHA-512 necessary for the 128s and 128f variants too. Other SHA2 versions of SLH_DSA require both algorithms. I'd think that it would be better if the SHA2-128s and SHA2-128f variants used SHA-256 as a prehash, as was suggested in the cited internet draft.

Rationale: As everyone knows, SHA-256 and SHA-512 are two different algorithms from an implementation viewpoint; they have different block sizes and state sizes. SHA-256 works on 32-bit words, SHA-512 works on 64-bit words; the SHA-512 round constants require more than twice ROM bits, etc. SHA-512 has faster throughput on regular 64-bit PCs but not on smaller units like security controllers, which are an important use case for these two variants (OpenTitan already supports 128s). Requiring SHA-512 complicates hardware implementations of these smaller variants significantly and more than doubles its size ( https://ia.cr/2024/367 ). With the current generation, acceleration on microcontrollers is often available for SHA-256 but not SHA-512. The vast majority of the internal hash ops is SHA-256 for all security levels anyway, and SHA-256 is usually faster for those tasks.

On internal hashing of SLH-DSA-SHAKE-128s and 128f: Your posting didn't clarify this, but I assume you're planning to keep the *internal* hashes of SLH-DSA-SHAKE-128s and 128f as SHAKE256, as per Section 10.1 of the FIPS 205 ipd. For SLH-DSA's internal hashing (actually generating and verifying hash-based signatures), SHAKE128 and SHAKE256 are essentially the same algorithm. For these hashes the difference ends up being the contents and location of a few padding bits within a block -- there is no security or performance difference between SHAKE128 and SHAKE256 for single-block messages.

Hence there should be no complication in using the faster-throughput SHAKE128 for SLH-DSA-SHAKE-128 *external* prehashing (as proposed) while all of the internal hashing is kept as SHAKE256 as it currently is.

Cheers,

- markku

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/60e9e8ca-3318-4017-b11a-7be327b90d75%40nist.gov.

[Kampanakis, Panos]

+1 on Markku’s points. I was initially advocating for simplicity and SHA512 and SHAK256 for the SHA2 and SHAKE SLH-DSA parameters respectively. But I was convinced while discussing draft-ietf-lamps-cms-sphincs-plus that SH256 and SHAKE128 make sense for the Level 1 as Markku is also pointing out.

 

 

From: Markku-Juhani O. Saarinen <mjos....@gmail.com>
Sent: Tuesday, July 30, 2024 2:51 PM
To: David A. Cooper <david....@nist.gov>
Cc: pqc-forum <pqc-...@list.nist.gov>; sp...@ietf.org
Subject: [EXTERNAL] [lamps] Re: [pqc-forum] Pre-hash options for SLH-DSA

 

CAUTION: This email originated from outside of the organization. Do not click links or open attachments unless you can confirm the sender and know the content is safe.

[Simon Hoerder]

Hi,

aside from the points raised by Markku, is SHAKE now officially a hash function in NIST’s definition?

I know the difference between SHA3 and SHAKE is minimal and SHAKE can indeed be used for hashing but if I understand FIPS202 correctly, it does insist on the difference between XOF and hash function and a hypothetical cipher suite that uses SHAKE as hash function would run into certification trouble.

Best,

Simon

On 30 Jul 2024, at 17:38, 'David A. Cooper' via pqc-forum <pqc-...@list.nist.gov> wrote:

 As was previously announced on the pqc-forum, SLH-DSA will specify separate "pure" and "pre-hash" versions. For the pre-hash versions, each of the OIDs that NIST will assign will specify both the SLH-DSA parameter set and the function to use for pre-hashing. Given the number of SLH-DSA parameter sets and the number of NIST approved hash functions and XOFs, there is a very large number of potential combinations. While assigning OIDs for more combinations would allow for more flexibility, we believe there is a benefit in minimizing the number of options in order to facilitate interoperability.

[Markku-Juhani O. Saarinen]

Hi Simon,

You would run into FIPS 140-3 certification problems if your module used SHA-3 as an XOF, i.e., extracted more than the designated amount of output bits while the SHA3 (rather than SHAKE) domain separation bits are set in the padding. The other way around (XOF as a hash, as is done here) is fine as long as you know what you're doing (hash length is appropriate for the security level and preimage/collision assumptions, etc.). Precise quote: "The [SHAKE] XOFs can be specialized to hash functions, subject to additional security considerations." per https://csrc.nist.gov/projects/hash-functions

Very concrete example: IETF RFC 8391 has XMSS parameter sets where SHAKE is used as a hash function "wrong" and too many bytes are extracted from it. As discussed before, SHAKE128 has only 128-bit preimage security; hence, if your design is relying on preimage security, parameters with n > 16 just make hash-based signatures unnecessarily bigger without really growing the security level. An XMSS module with those RFC 8391 SHAKE parameter sets would *not* pass certification against NIST SP 208 which has different XMSS parameter sets -- even though the NIST XMSS standard refers to RFC 8391 for algorithmic definitions. The IETF RFC has not been updated (those can only be superseded), but there's errata (thanks to Kaveh B. for noting this): https://www.rfc-editor.org/errata/eid6024  "The reason is that SHAKE allows for meet-in-the-middle preimage attacks that reduce to a collision search on the internal state."

Anyway, in this case, David A.C. from NIST proposed this modification to FIPS  205. NIST also runs the FIPS 140-3 system, which is designed to certify NIST cryptography such as FIPS 205. Of course, there may be other certification systems.

Cheers,

-armku

[Scott Fluhrer (sfluhrer)]

I would disagree with the idea that a specific parameter set necessarily needs to be paired with a specific hash function.

 

After all, the most common case where you use prehashing is because have two different computational devices A and B; A with access to the data being signed, and B with access to the private key (and with a narrow data pipe connecting the two).  In this case, A and B might have different trade-offs in terms of hash functions, and it would make sense to allow the implementor to select things appropriately (as long as security concerns are addressed).

 

If you’re worried about “interoperability”, that is, the verifier knowing what the prehash function is, this needs to be addressed already (because, for example, SLH-DSA-SHA2-128s and SLH-DSA-SHAKE-128s signatures and public keys look exactly the same, and so any such communication requirement needs to be addressed anyways…

--

[Scott Fluhrer (sfluhrer)]

Actually, I doubt that SLH-DSA will often be used within protocols (except possibly as something such as root certs, where prehashing would not be likely) – I’d expect implementers would find that the signing performance is not sufficient for most interactive protocol uses.

 

Instead, the use of SLH-DSA with prehashing would be more likely be image signing (where interoperability is less of a concern).

 

 

From: Dang, Quynh H. (Fed) <quynh...@nist.gov>
Sent: Wednesday, July 31, 2024 1:27 PM
To: Scott Fluhrer (sfluhrer) <sflu...@cisco.com>; Cooper, David (Fed) <david....@nist.gov>; pqc-forum <pqc-...@list.nist.gov>
Subject: RE: [pqc-forum] Pre-hash options for SLH-DSA

 

Hi Scott,

 

Let me try to understand your suggestion.

 

An OID for a specific SLH-DSA-prehash signature and an OID for a pre-hash hash function when interoperability is a concern in a protocol for signature verification.

 

Is my understanding correct here ?

 

Regards,

Quynh.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB544442CC5ED7AE1B73A14E10C1B12%40CH0PR11MB5444.namprd11.prod.outlook.com.

[Perlner, Ray A. (Fed)]

Dear all,

As with SLH-DSA, and as previously announced, ML-DSA will have domain separated pure and pre-hash variants. We are currently considering specifying OIDs for the pure variant of ML-DSA and a pre-hash variant using SHA512 for the pre-hash. We plan to do this for each of the 3 parameter sets of ML-DSA (ML-DSA-44, ML-DSA-65 and ML-DSA-87).

We would appreciate any feedback people may have about which OIDs to specify for ML-DSA

Thank you,
Ray

[Mike Ounsworth]

Hi Ray,

 

Can you comment on the choice to use SHA2 for the prehash despite the fact that ML-DSA internally uses SHA3 (SHAKE)? I don’t necessarily disagree with the decision, but I would like to hear the rationale from NIST.

 

---

Mike Ounsworth

--

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

[Perlner, Ray A. (Fed)]

Hi Mike,

 

The main thinking for focusing on SHA512 for pre-hash was that even pure ML-DSA essentially pre-hashes the message with SHAKE256 when computing the message representative µ, and the FIPS already includes allowances for the message representative to be computed in a different cryptographic module from the one that uses the private key. While we are aware that the inclusion of a public key hash in the computation of the message representative could break some applications that don’t have access to the public key when doing pre-hash, we were thinking the more likely scenario where an additional pre-hash step would be desirable is when dealing with large messages on platforms with SHA2 hardware support, but not SHA3 hardware support.

 

We are open to the possibility that additional OIDs may need to be defined now or in the future, but all else being equal, our preference would be for fewer options.

 

Best,

Ray

[Markku-Juhani O. Saarinen]

Hi,

Kind of makes sense -- For ML-DSA, prehashing just seems to be a way of using SHA2 with ML-DSA. We were expecting this based on CNSA announcements, but I still don't understand their rationale for demanding SHA2.. perhaps some legacy integration stuff as it makes ML-DSA more of a "drop-in replacement" for existing CNSA -- while sacrificing some security properties.

And, as noted, there is less of a technical need for prehashing with ML-DSA, which does not mandate two hash passes (and hence keeping the message in memory) in signing like SLH-DSA does -- you just need to know the "tr" prefix. I tend to agree that if you want to use SHAKE with ML-DSA, you can use the pure version in almost all applications, which is more secure anyway (or rather, can't be less secure).

Ray wasn't exactly clear about the OIDs and how they are to be used -- I suppose he means just some domain separation identifiers (reserved numbers) rather than actual globally unique ASN.1 OIDs as in X.509?

It may have been discussed on the list but I couldn't find a definitive answer -- My assumption is that the pure version would compute the 512-bit message representative mu something like mu = SHAKE256( "pure oid" | tr | M ), and the proposed prehash version would compute mu = SHAKE256( "SHA512 prehash oid" | tr |  SHA512(M) ). These OIDs are just some byte constants. Is this correct? One could also put the domain separation OID in the commitment hash ~c (line 15 in signing) /  ~c' (line 12 in verify) but that would seem more cumbersome and I don't see any advantages.

I like that the drivers can just pass the 512-bit "mu" hash ("actual message hash" ) to the core ML-DSA lattice crypto module for signing or verification and do all this hash/prehash/OID logic outside it.

Cheers,

-markku

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

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB4855424DA9DB254DCDB136589CB12%40DM6PR09MB4855.namprd09.prod.outlook.com.

[David A. Cooper]

The OIDs that we are discussing are the globally unique ASN.1 OIDs, such as would appear in the signature field of an X.509 certificate.

The domain separation will be addressed as described in https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/JKMh0D0pa30/m/vbflXolxAQAJ. For ML-DSA, the message representative will still be computed as mu = SHAKE256(tr || M), but M will be modified to include the domain separation information.

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

[Sophie Schmieg]

I would consider anything the "protocol layer" that describes how the signature is used in context, not just protocols that are executed interactively. So I would count a standard that describes, say, software signatures, a protocol. This is where my initial criticism of the prehashing in the primitive came from, in my opinion this is a question of whether the input to the signature scheme has been hashed or not, at least in the case of SLH-DSA, where the signature internal hashes cannot be externally executed, and as such a decision that is made in a higher layer, a decision the protocol makes, along with things like which representation of the data is signed. To stay with the example of a software signature, one could for example want to sign the root of a Merkle tree in this case, to parallelize the hashing. Would we then case call the usage of SLH-DSA prehashed or not? On the one hand, the input clearly is a hash, but on the other hand, it is not the hash of the message itself. What if we want to sign the name of a file together with a hash representing its contents? In the end, I can live with the domain separator, but I do think it is not very well-defined, and would not be surprised if we mainly see uses of the non-prehashed variant, even if the input is a hash.

This fundamentally differs from prehashing in RSA/ECDSA/ML-DSA, since there the primitive needs to operate on a hash, which merely can be externally supplied. So whether say the root of a Merkle tree was prehashed depends on how the primitive was called, and is not merely a protocol decision.

To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB5444AB79F4C156238C2D78CDC1B12%40CH0PR11MB5444.namprd11.prod.outlook.com.

--

Sophie Schmieg | Information Security Engineer | ISE Crypto | ssch...@google.com

[David A. Cooper]

Hi Scott,

FIPS 204 and 205 will allow pre-hashing to be performed using any approved hash function or XOF that provides at least as much security strength (against both collision and second preimage attacks) as the corresponding parameter set. Some applications will not use OIDs to indicate how a signature was created, and for those that do, anyone can assign an OID from their own arc. So, NIST's choices will not restrict what can be done.

NIST, however, has been asked to assign OIDs for ML-DSA and SLH-DSA (and ML-KEM), and we believe that having too many choices is bad for interoperability. One of the reasons that some people were against having separate pure and pre-hash modes was that it increased the number of options, and so either created more work for the verifier to support all of the options or a greater risk that the verifier would not support the option chosen by the signer. Having more choices for the pre-hash function just makes it more likely that the verifier will not support all of them.

So, while NIST cannot limit what combinations are used, if implementers of signers and verifiers choose from the list that NIST defines, then having that list be smaller makes it easier to achieve interoperability.

[Scott Fluhrer (sfluhrer)]

Ok, so we’re talking about assigning OIDs, rather than what combinations are allowed (other than what is required for security – I have no issues with those constraints).

 

I then have no objection…

[Andrey Jivsov]

Instead, the use of SLH-DSA with prehashing would be more likely be image signing (where interoperability is less of a concern).

I don't see it this way at least for some major uses of image signing, e.g. for boot chain security. A typical signed message in the boot chain is a digitally signed block of data that, among other fields, contains hashes of images.

So, the "protocol" there essentially includes prehashing that is outside of the view of SLH-DSA primitive, and the pure version of SLH-DSA can be used without a clear benefit for a pre-hashed version. (This is similar to the Merkle tree argument; here we have a two-level tree).

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

[Markku-Juhani O. Saarinen]

Thanks David. Somehow that got buried for me.

The proposed formatting ( in https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/JKMh0D0pa30/m/vbflXolxAQAJ ) seems sensible as the way it's specified there one doesn't need an actual ASN.1 encoder for this, just hard-coded byte sequences for OIDs.

If I was handed this spec, I'd guess that the OID would be "id-sha512" defined in Appendix B of RFC 8017 (PKCS #1 v 2.2). https://www.rfc-editor.org/rfc/rfc8017.html#appendix-B.1

 id-sha512    OBJECT IDENTIFIER ::= {
           joint-iso-itu-t (2) country (16) us (840) organization (1)
           gov (101) csor (3) nistalgorithm (4) hashalgs (2) 3
       }

I'd absolutely specify the actual DER encoding in the FIPS spec ..  Unless I'm mistaken, in this case that would be 11 bytes (0x) 06 09 60 86 48 01 65 03 04 02 03.

This same OID (2.16.840.1.101.3.4.2.3) / id-sha512 already appeared 20 years ago in RFC 3560. In IETF specs this is wrapped in various ways which seem redundant. Avoiding more complicated ASN.1 encodings and is ok as long there will *never* be any other data following M in the hash in this encoding. The length of M is only authenticated by the hash function itself, not by domain separators.

One can try this out with OpenSSL asn1 parser with most Linux systems:
   $ echo -en '\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03' | openssl asn1parse -inform der
Which outputs
    0:d=0  hl=2 l=   9 prim: OBJECT            :sha512

The proposed  pre-hash sequence  M' = octet(1) || octet(OLEN(ctx)) || ctx || OID_PH || PH(M) would then typically (without ctx -- length 0) turn out to be in case of PH=SHA512

M' = (0x) 01 00 06 09 60 86 48 01 65 03 04 02 03 || SHA512(M)

right ?

Cheers,
-markku

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

[David A. Cooper]

Yes, that is the correct OID for SHA-512. We do plan to specify in the FIPS the DER encodings of the OIDs of hash functions and XOFs that we think are most likely to be used. In addition to the sources that you mentioned, the OIDs for all of the NIST approved hash functions and XOFs are available at https://csrc.nist.gov/projects/computer-security-objects-register/algorithm-registration. This is also where the OIDs for ML-DSA, ML-KEM, and SLH-DSA will be posted.

The value for M' in the case of SHA-512 and an empty context string also seem correct.

[Markku-Juhani O. Saarinen]

Thanks David!

I think this is sufficient for the LAMPS IETF "PQC Certificate Interop Hackathon" group to create some test certificates etc.

What names should we use ? It is of course important from security viewpoint that no application will create or accept "pure" signatures without the domain separation prefix, so we wouldn't want to even give that a name. Hence a natural option would seem to be for pure version to just use the parameter set as an identifier:
 
Signing M' = (0x) 00 00 || M
 
 ML-DSA-44
 ML-DSA-65
 ML-DSA-87
 

Signing M' = (0x) 01 00 06 09 60 86 48 01 65 03 04 02 03 || SHA512(M)
 
 ML-DSA-44-SHA512
 ML-DSA-65-SHA512
 ML-DSA-87-SHA512

That is, if and only if a prehash is used, the hash name is added at the end. Additionally, if the context is used for <something> then that could perhaps be ML-DSA-<something>-<hash> ? 

From Dustin's original message I understand that SLH-DSA prehashing would be handled exactly the same way, so a prehashed version could have a name like SLH-DSA-SHA2-256s-SHA512 ?

Best Regards,

-markku

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