hash-then-sign or not

[csosto-pk]

From Mike Ounsworth

Hi Jake, Panos, Sean, Bas,

We notice that your IETF draft-massimo-lamps-pq-sig-certificates-00 has the following security consideration:

Within the hash-then-sign paradigm, hash functions are used as a
domain restrictor over the message to be signed. By pre-hashing, the
onus of resistance to existential forgeries becomes heavily reliant on
the collision-resistance of the hash function in use. As well as this security goal, the hash-then-sign paradigm also has the ability to improve performance by reducing the size of signed messages. As a corollary, hashing remains mandatory even for short messages and assigns a further computational requirement onto the verifier. This makes the performance of hash-then-sign schemes more consistent, but not necessarily more efficient.
Dilithium diverges from the hash-then-sign paradigm by hashing the message during the signing procedure (at the point in which the challenge polynomial).
However, due to the fact that Dilithium signatures may require the
signing procedure to be repeated several times for a signature to be produced, Dilithium implementations can make use of pre-hashing the message to prevent rehashing with each attempt.

First, quoting from the Dilithium NIST Round 3 submission documents:

Since our signing procedure may need to be repeated several times
until a signature is produced, we also append a counter in order to
make the SHAKE-256 output differ with each signing attempt of the same message.

So it seems like the Dilithium designers explicitly want the hash to differ across repeated attempts.

Second, we had a similar discussion within the context of composite signatures when figuring out how to combine Dilithium and Falcon with ECDSA and RSA. We came out with a different conclusion; that hash-then-sign reduces the security properties of Dilithium and Falcon down to the collision resistance of the hash function used to pre-hash.

We would like community opinion on this.

Here's the Security Consideration text that we're working on:

In the hash-then-sign paradigm, the message to be signed is hashed externally to the signature primitive, and then the hash value is signed.

The hash-then-sign paradigm is required, for example, with RSA signatures in order to sign messages larger than the RSA modulus. Hash-then-sign also gives performance and bandwidth benefits, for example, when the signature is performed by a networked cryptographic appliance since you only need to send a small hash value rather than streaming the entire message.

With Dilithium and Falcon signatures it is not recommended to pre-hash for the following reasons:

The Dilithium construction includes

Sign(sk,M):
10: mu \in {0, 1}^384 := CRH(tr || M)

where CRH is any collision-resistant hash function and tr is a component of the secret key. This provides strong security against pre-computed collision attacks since an attacker has no a-priori knowledge of r and provides per-key hash-domain separation of the message to be signed.

The Falcon construction includes

Sign (m, sk, beta^2):
1: r <- {0, 1}^320 uniformly
2: c <- HashToPoint(r || m, q, n)

where HashToPoint is a SHAKE-256-based construct. This provides strong security against pre-computed collision attacks since an attacker has no a-priori knowledge of r and provides per-signature hash-domain separation of the message to be signed.

If the message to be signed is pre-hashed, for example m0 = SHA256(m) and then m0 provided to Dilithium or Falcon to sign, then you have re-introduced the collision problem since two messages m1 and m2 where SHA256(m1) == SHA256(m2) hash value will result a single Falcon or Dilithium signature value which is simultaneously valid for both m1 and m2. This removes the extra collision resistance built in to the Dilithium and Falcon primitives and reduces it to the collision resistance strength of the underlying hash function. For this reason it is in general not recommended to pre-hash when using Dilithium or Falcon except in cases where the implementor is comfortable with this reduction in security.

Therefore, for the purpose of interoperability of composite signatures, implementations MUST NOT pre-hash messages for Dilithium and Falcon. If pre-hashed versions of these signatures are desired, then separate signature algorithms will need to be defined.

Third, I can imagine that some applications (like TLS) will want to use non-pre-hashed versions of Dilithium and Falcon, but other applications (like code-signing) would prefer pre-hashed versions. These are not interoperable with each other. Is NIST planning to produce algorithm definitions, OIDs, Codepoints, etc, for both versions?

More details in the thread https://mailarchive.ietf.org/arch/msg/spasm/PT7jTztNfI1K6DkS7bQ_SkljoVI/

[csosto-pk]

More details on the advantages of message binding on C. Peikert's https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/eAaiJO1qzkA/m/FIYT_anuAAAJ

[jakemas]

From Scott Fluhrer

Hi Jake, Panos, Sean, Bas,

We notice that your IETF draft-massimo-lamps-pq-sig-certificates-00 has the
following security consideration:

Within the hash-then-sign paradigm, hash functions are used as a
domain restrictor over the message to be signed. By pre-hashing, the
onus of resistance to existential forgeries becomes heavily reliant on
the collision-resistance of the hash function in use. As well as this security
goal, the hash-then-sign paradigm also has the ability to improve
performance by reducing the size of signed messages. As a corollary, hashing
remains mandatory even for short messages and assigns a further
computational requirement onto the verifier. This makes the performance of
hash-then-sign schemes more consistent, but not necessarily more efficient.
Dilithium diverges from the hash-then-sign paradigm by hashing the
message during the signing procedure (at the point in which the challenge
polynomial).
However, due to the fact that Dilithium signatures may require the
signing procedure to be repeated several times for a signature to be
produced, Dilithium implementations can make use of pre-hashing the
message to prevent rehashing with each attempt.

First, quoting from the Dilithium NIST Round 3 submission documents:

Since our signing procedure may need to be repeated several times
until a signature is produced, we also append a counter in order to
make the SHAKE-256 output differ with each signing attempt of the same
message.

So it seems like the Dilithium designers explicitly want the hash to differ
across repeated attempts.

Hmmm, I don't see that in Dilithium; are they referring to the internal ExpandMask function? That isn't applied to the input message.

In any case, it's easy to derive SHAKE( M || 1 ), SHAKE( M || 2 ), ... without multiple passes through M; you compute the partial SHAKE state after process M, and then apply that partial state to 1, 2, ...

Second, we had a similar discussion within the context of composite
signatures when figuring out how to combine Dilithium and Falcon with
ECDSA and RSA. We came out with a different conclusion; that hash-then-
sign reduces the security properties of Dilithium and Falcon down to the
collision resistance of the hash function used to pre-hash.

We would like community opinion on this.

Here's the Security Consideration text that we're working on:

In the hash-then-sign paradigm, the message to be signed is hashed
externally to the signature primitive, and then the hash value is signed.

The hash-then-sign paradigm is required, for example, with RSA signatures in
order to sign messages larger than the RSA modulus. Hash-then-sign also
gives performance and bandwidth benefits, for example, when the signature
is performed by a networked cryptographic appliance since you only need to
send a small hash value rather than streaming the entire message.

With Dilithium and Falcon signatures it is not recommended to pre-hash for
the following reasons:

The Dilithium construction includes

Sign(sk,M):
10: mu \in {0, 1}^384 := CRH(tr || M)

where CRH is any collision-resistant hash function and tr is a component
of the secret key.

A hash of the public key, actually; see line 7 of the key generation process (which explicitly computes it from the components of the public key) - Dilithium stores it in the private key so the signer doesn't need to recompute it every time.

This provides strong security against pre-computed
collision attacks since an attacker has no a-priori knowledge of r and
provides per-key hash-domain separation of the message to be signed.

Rather, it limits the usability of any found collision to a specific public key; however it does nothing to frustrate a collision attack against a specific public key.

Now, it does probably add a constant factor to any attack that searches for a simultaneous collision between the hash that RSA/ECDSA uses (without the prepend) and the hash that Dilithium uses (with the known prepend) - I would hesitate to give a value to that constant factor, but it is likely not large.

[jakemas]

From Mike Ounsworth:
I want to break out and expand our third point as it is actually a question to NIST and not to the IETF authors.

Third, I can imagine that some applications (like TLS) will want to use non-pre-hashed versions of Dilithium and Falcon, but other applications (like code-signing) would prefer pre-hashed versions. These are not interoperable with each other. Is NIST planning to produce algorithm definitions, OIDs, Codepoints, etc, for both versions?

Expanding on the code-signing example: the messages to be signed can be very large; consider a several GB firmware image. Assuming our understanding below is correct, a direct-sign algorithm would require the entire thing to be streamed to a network HSM for signing and to a TPM for verification. Conversely code-signing environments often include counter-signatures from Time Stamping Authorities which protect against future discovery of collision attacks against the hash function -- as an example, Windows still accepts RSA-SHA1 signatures produced before SHA1 was deprecated. I can imagine that the code-signing community will decide that the performance gains of hash-then-sign outweigh the security loss.

So, will NIST standardize both direct-sign and some variant of hash-then-sign for PQC signature primitives?

[jakemas]

So it seems like the Dilithium designers explicitly want the hash to differ across repeated attempts.

Hmmm, I don't see that in Dilithium; are they referring to the internal ExpandMask function? That isn't applied to the input message.
In any case, it's easy to derive SHAKE( M || 1 ), SHAKE( M || 2 ), ... without multiple passes through M; you compute the partial SHAKE state after process M, and then apply that partial state to 1, 2, ...

I think we are referring to different parts of the signing process here. For reference, my security consideration was referring to page 4 of the Dilithium spec that states:
"Our full scheme in Fig. 4 also makes use of basic optimizations such as pre-hashing the message M so as to not rehash it with every signing attempt." and Figure 4 itself.

It was my understanding that the signing procedure may need to be repeated several times to produce a signature, and thus pre-hashing would prevent the need to individually hash the input message with each attempt. I believe the desired differing of the hash you mentioned is within the internals of the signing procedure and not on the input message itself.

Third, I can imagine that some applications (like TLS) will want to use non-pre-hashed versions of Dilithium and Falcon, but other applications (like code-signing) would prefer pre-hashed versions. These are not interoperable with each other. Is NIST planning to produce algorithm definitions, OIDs, Codepoints, etc, for both versions?

Expanding on the code-signing example: the messages to be signed can be very large; consider a several GB firmware image. Assuming our understanding below is correct, a direct-sign algorithm would require the entire thing to be streamed to a network HSM for signing and to a TPM for verification. Conversely code-signing environments often include counter-signatures from Time Stamping Authorities which protect against future discovery of collision attacks against the hash function -- as an example, Windows still accepts RSA-SHA1 signatures produced before SHA1 was deprecated. I can imagine that the code-signing community will decide that the performance gains of hash-then-sign outweigh the security loss.

So, will NIST standardize both direct-sign and some variant of hash-then-sign for PQC signature primitives?

I do agree that there may be optimizations that users may wish to make dependent on the context, i.e., hash-then-sign vs direct-sign. It's for this reason I tried to give an overview of the security of each option in the draft, but ultimately leave that up to the user. It is a good point regarding NISTs perspective on what should be explicitly standardized here.

This provides strong security against pre-computed
collision attacks since an attacker has no a-priori knowledge of r and
provides per-key hash-domain separation of the message to be signed.

Rather, it limits the usability of any found collision to a specific public key; however it does nothing to frustrate a collision attack against a specific public key.

Right, more details on the advantages of message binding on the PQC-forum from C. Peikert's https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/eAaiJO1qzkA/m/K66R_ftNBwAJ. It was this discussion I was trying to encompass in the draft.

[csosto-pk]

Doing a thorough analysis on the topic, it seems the best approach is to follow EdDSA and do not digest. There is no practical performance impact for most X.509 usecases and even for PKCS#11 with incremental APIs and big messages there will be no issue just for Dilithium. More details in the doc written for NCCOE.

Keeping it as pure Dilithium, no digest.