Re: [lamps] [pqc-forum] RE: Whether to hash-then-sign with Dilithium and Falcon?

["Massimo, Jake" <[e-mail]>]

Thanks Mike, Scott.

I've added to the github repo so we can track discussions on this topic https://github.com/jakemas/draft-massimo-pq-pkix-00/issues/23 

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

Cheers,
Jake

------


On 17/08/2022, 10:51, "'Scott Fluhrer (sfluhrer)' via pqc-forum" <[e-mail]> wrote:

    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.



    > -----Original Message-----
    > From: 'Mike Ounsworth' via pqc-forum <[e-mail]>
    > Sent: Wednesday, August 17, 2022 1:27 PM
    > To: 'LAMPS' <[e-mail]>; [e-mail]; pqc-forum <pqc-
    > [e-mail]>; [e-mail]; [e-mail];
    > [e-mail]; [e-mail]
    > Subject: [pqc-forum] Whether to hash-then-sign with Dilithium and Falcon?
    >
    > 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.

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

    --
    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 [e-mail].
    To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CH0PR11MB5444B9D3A0CB6E447A2FA3E5C16A9%40CH0PR11MB5444.namprd11.prod.outlook.com.