From nobody Wed Aug 17 22:12:11 2022 Return-Path: X-Original-To: spasm@ietfa.amsl.com Delivered-To: spasm@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3F7F9C14CE3F for ; Wed, 17 Aug 2022 22:12:08 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.104 X-Spam-Level: X-Spam-Status: No, score=-2.104 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=unavailable autolearn_force=no Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from mail.ietf.org ([50.223.129.194]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id HyQoSkeS8AxL for ; Wed, 17 Aug 2022 22:12:04 -0700 (PDT) Received: from mail-qt1-x830.google.com (mail-qt1-x830.google.com [IPv6:2607:f8b0:4864:20::830]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 0DB8CC152597 for ; Wed, 17 Aug 2022 22:12:04 -0700 (PDT) Received: by mail-qt1-x830.google.com with SMTP id c20so400955qtw.8 for ; Wed, 17 Aug 2022 22:12:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc; bh=vFkOORmrQYRBeEC8CtirJ+WVugTCw6RonNr+ivGTWIc=; b=HVAFgd90xkkEAN6V8RcAa8ArClVA1XEtmNkVtx+hyJjm5DymU//3BFhdCeHa9HVExF fec+pTVDCKZR1dpJQvp1fGJr8Uc0K0ySBNawvRHExBXcEJa6wsavsFPR6+ZHc+HpjBtj HDLRd+ob8eWB4hIpjpBKOJ89YGPiMrjp9V9UOqY7QWHMOkpYysyIKx0BJFX+K1gfYpjj /7AFe8DOitDW2Wk+SmZ8EO2jBjYlq47ZIG6IO8CjFz0MhG3gsaHedamo7kgQDuDtpgCP 0K2a9MnQPJqbDJ7vrpOOrDpk33p9pcnXh8qVWcNDY7OqeeCZk+NBpN+FHSYSJzxmvnz/ HFRg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc; bh=vFkOORmrQYRBeEC8CtirJ+WVugTCw6RonNr+ivGTWIc=; b=DjijWKgMYzzwpEMwHA321AJdKE8r863XxpCMDrtnT98bi8vQyVkH+6iFtLOGhOoG1x KqZ0Q9AtI9s66wd2VxFOUkSVE68X8eDnWikBjBAtiZJ6Aa06VNxOX5lFCD2r1O6ltVQN 3rPAsz8lPAScZgZUpirQOX9VnYnKu+Kpu623n1Swz50/3fFGIVIrZfpfZPOjCy1mMNFT Uoy/tLi0RZ474AVCHIdxYNjlKU05yz3EkeBwYf6/VS9AxiauoXouGW9a5/Is4hbR5aYL hz4alCycH97WAaW4pP8L63kOM/JSEGsckL1JAfaT9gPKHR4D3bv6cP8Q13xzuFlqIDVD PCPw== X-Gm-Message-State: ACgBeo3zZOLh9cXRKcybQs5tNP7GhzjG6xrfveYCDn2gWMmie593Jcn/ rCWDYHHbyTWdYKXAil9Ihx1VAXhXJzC3BNiWnNU= X-Google-Smtp-Source: AA6agR6cgdlCiTDvNk1SuazIqMrF2vg+ZS8NLuPiY0LpJoU0yxqK4SkBdqaTKKnu8vB8eIzrXYCmoJL4+hR/MeKUaQg= X-Received: by 2002:ac8:5c03:0:b0:343:6db0:58e2 with SMTP id i3-20020ac85c03000000b003436db058e2mr1249658qti.311.1660799522734; Wed, 17 Aug 2022 22:12:02 -0700 (PDT) MIME-Version: 1.0 References: <88358933-A540-4000-9C7D-D248F670122F@amazon.com> In-Reply-To: <88358933-A540-4000-9C7D-D248F670122F@amazon.com> From: Tadahiko Ito Date: Thu, 18 Aug 2022 14:11:51 +0900 Message-ID: To: "Massimo, Jake" Cc: "Scott Fluhrer (sfluhrer)" , Mike Ounsworth , LAMPS , "cfrg@irtf.org" , pqc-forum , "Kampanakis, Panos" , "sean@ssn3rd.com" , "bas@westerbaan.name" Content-Type: multipart/alternative; boundary="00000000000098880605e67d0549" Archived-At: Subject: Re: [lamps] [CFRG] [pqc-forum] RE: Whether to hash-then-sign with Dilithium and Falcon? X-BeenThere: spasm@ietf.org X-Mailman-Version: 2.1.39 Precedence: list List-Id: "This is a venue for discussion of doing Some Pkix And SMime \(spasm\) work." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 18 Aug 2022 05:12:08 -0000 --00000000000098880605e67d0549 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable > 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. When we were trying to implement PQC in functional module of HSM for our use case, It was pain. I believe HSM vender will implement much better, but It may still have problem. Hash then Sign was great that we can separate key management (and signing) function from data management (and hashing) function. It seems crypto module producer might need to implement scheduling function for data management function. I far those problems decrease efficiency, but we might need to care that. >> (=E2=80=A6) Assuming our understanding below is correct, a direct-sign a= lgorithm >> would require the entire thing to be streamed to a network HSM for signing >> and to a TPM for verification. Currently, I am doubting that we might not have that many protocols with direct-signing algorithm which would sign intolerable large data. For those protocol with direct-signing, I believe we can have several approaches. 1) Sign to smaller compressed data (e.g. by using CMS) instead of raw data. It was biggest feedback I got so far, when I told about those stuff on IETF last year. For this option, Users may need to change data structure, but If we cannot find that much direct-signing use case, it might be reasonable. Direct-signing use case holders may need to take other option. In addition, when I ask our engineer for our use case, he said that was long recognized issue, and it might be good chance to do so. 2) Use pre-hash Users do not need to change data structure, but we may meet interoperability challenge. 3) Separate PQC into key management function and data management function, I tried, but I believe It was not good choice. < https://eprint.iacr.org/2020/990.pdf> (I am sorry that we have not updates that document.) 4) Ask NIST to make hash-and-sign PQC If they make one, it would be easy. (well.. I believe we should not assume that) Regards Tadahiko 2022=E5=B9=B48=E6=9C=8818=E6=97=A5(=E6=9C=A8) 4:41 Massimo, Jake : > 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 stat= e > 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 repeate= d > 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 applicatio= ns > (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 w= as > deprecated. I can imagine that the code-signing community will decide tha= t > 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 her= e. > > >> 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 signe= d. > > >Rather, it limits the usability of any found collision to a specific > public key; however it does nothing to frustrate a collision attack again= st > 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/K66= R_ftNBwAJ. > It was this discussion I was trying to encompass in the draft. > > Cheers, > Jake > > ------ > > > =EF=BB=BFOn 17/08/2022, 10:51, "'Scott Fluhrer (sfluhrer)' via pqc-forum"= < > pqc-forum@list.nist.gov> 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 > > Sent: Wednesday, August 17, 2022 1:27 PM > > To: 'LAMPS' ; cfrg@irtf.org; pqc-forum > forum@list.nist.gov>; jakemas@amazon.com; kpanos@amazon.com; > > sean@ssn3rd.com; bas@westerbaan.name > > 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 th= e > > message during the signing procedure (at the point in which the > challenge > > polynomial). > > > However, due to the fact that Dilithium signatures may require th= e > > > 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 t= o > 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 wi= th > > ECDSA and RSA. We came out with a different conclusion; that > hash-then- > > sign reduces the security properties of Dilithium and Falcon down t= o > 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 :=3D 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 again= st > 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 use= s > (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 =3D > 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) =3D=3D 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 an= d > 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 implemento= r > 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, sen= d > 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/CH0PR11MB5444= B9D3A0CB6E447A2FA3E5C16A9%40CH0PR11MB5444.namprd11.prod.outlook.com > . > > _______________________________________________ > CFRG mailing list > CFRG@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg > --00000000000098880605e67d0549 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

>=C2=A0It was my understanding that the= signing procedure may need to be=C2=A0

> repeated s= everal times to produce a signature, and thus pre-hashing=C2=A0

<= p class=3D"MsoNormal" align=3D"left" style=3D"margin:0mm;font-size:10.5pt;f= ont-family:=E6=B8=B8=E6=98=8E=E6=9C=9D,serif;color:rgb(0,0,0)">> would prevent the need to individually hash the input messag= e with=C2=A0

> each attempt.

= =C2=A0

When we were trying to implement PQC = in functional module of HSM for our use case, It was pain. I believe HSM ve= nder will implement much better, but It may still have problem.

<= p class=3D"MsoNormal" style=3D"margin:0mm;text-align:justify;font-size:10.5= pt;font-family:=E6=B8=B8=E6=98=8E=E6=9C=9D,serif;color:rgb(0,0,0)">Hash then Sign was great that we can separate key management (= and signing) function from data management (and hashing) function. It seems= crypto module producer might need to implement scheduling function for dat= a management function. I far those problems decrease efficiency, but we mig= ht need to care that.

=C2=A0

>= > (=E2=80=A6) Assuming our understanding below is correct, a direct-sign= algorithm

=

>> would require the entire thing to be streamed to a networ= k HSM for signing

>> and to a TPM for verification.= =C2=A0

=C2=A0

Currently, I a= m doubting that we might not have that many protocols with direct-signing a= lgorithm which would sign intolerable large data. For those protocol with d= irect-signing, I believe we can have several approaches.

=C2=A0

1)=C2=A0=C2=A0=C2=A0=C2=A0Sign to smaller compressed data (e.g. by using CMS= ) instead of raw data.
It was biggest feedback I got so far, when I told= about those stuff on IETF last year.
For this option, Users may need to= change data structure, but If we cannot find that much direct-signing use = case, it might be reasonable. Direct-signing use case holders may need to t= ake other option.=C2=A0
In addition, when I ask our engineer for our use= case, he said that was long recognized issue, and it might be good chance = to do so.

2)=C2=A0=C2=A0=C2=A0=C2=A0<= /span>Use pre-hash=C2=A0
Users do not need t= o change data structure, but we may meet interoperability challenge.

3)= =C2=A0=C2=A0=C2=A0=C2=A0Separate PQC into key management function and data manage= ment function,=C2=A0
I tried, but I believe It was not good choice. <= https://= eprint.iacr.org/2020/990.pdf> =C2=A0(I am sorry that we have not upd= ates that document.)

4)=C2=A0=C2=A0= =C2=A0=C2=A0Ask NIST to make hash-and-si= gn PQC

<= span lang=3D"EN-US">If they make one, it would be easy. (well.. I believe w= e should not assume that)

=C2=A0

Regards Tadahiko


2022=E5=B9=B48=E6=9C=8818=E6=97=A5(=E6= =9C=A8) 4:41 Massimo, Jake <jakemas=3D40amazon.com@dmarc.ietf.org>:
Thanks Mike, Scott.

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

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

=C2=A0 =C2=A0 > Hmmm, I don't see that in Dilithium; are they referr= ing to the internal ExpandMask function?=C2=A0 That isn't applied to th= e input message.
=C2=A0 =C2=A0 >In any case, it's easy to derive SHAKE( M || 1 ), SHA= KE( M || 2 ), ... without multiple passes through M; you compute the partia= l 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. Fo= r reference, my security consideration was referring to page 4 of the Dilit= hium 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 atte= mpt." 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 th= e 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.

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

=C2=A0 =C2=A0>Expanding on the code-signing example: the messages to be = signed can be very large; consider a several GB firmware image. Assuming ou= r 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-si= gnatures from Time Stamping Authorities which protect against future discov= ery of collision attacks against the hash function -- as an example, Window= s still accepts RSA-SHA1 signatures produced before SHA1 was deprecated. I = can imagine that the code-signing community will decide that the performanc= e gains of hash-then-sign outweigh the security loss.

=C2=A0>So, will NIST standardize both direct-sign and some variant of ha= sh-then-sign for PQC signature primitives?

I do agree that there may be optimizations that users may wish to make depe= ndent on the context, i.e., hash-then-sign vs direct-sign. It's for thi= s 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 regardi= ng NISTs perspective on what should be explicitly standardized here.

=C2=A0 =C2=A0 >> This provides strong security against pre-computed =C2=A0 =C2=A0 >> collision attacks since an attacker has no a-priori = knowledge of `r` and
=C2=A0 =C2=A0 >> provides per-key hash-domain separation of the messa= ge to be signed.

=C2=A0 =C2=A0 >Rather, it limits the usability of any found collision to= a specific public key; however it does nothing to frustrate a collision at= tack against a specific public key.

Right, more details on the advantages of message binding on the PQC-forum f= rom C. Peikert's https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/eAaiJO1qzkA/m/K6= 6R_ftNBwAJ. It was this discussion I was trying to encompass in the dra= ft.

Cheers,
Jake

------


=EF=BB=BFOn 17/08/2022, 10:51, "'Scott Fluhrer (sfluhrer)' via= pqc-forum" <pqc-forum@list.nist.gov> wrote:

=C2=A0 =C2=A0 CAUTION: This email originated from outside of the organizati= on. Do not click links or open attachments unless you can confirm the sende= r and know the content is safe.



=C2=A0 =C2=A0 > -----Original Message-----
=C2=A0 =C2=A0 > From: 'Mike Ounsworth' via pqc-forum <pqc-forum@list.nist.g= ov>
=C2=A0 =C2=A0 > Sent: Wednesday, August 17, 2022 1:27 PM
=C2=A0 =C2=A0 > To: 'LAMPS' <spasm@ietf.org>; cfrg@irtf.org; pqc-forum <pqc-
=C2=A0 =C2=A0 > forum@list.nist.gov>; jakemas@amazon.com; kpanos@amazon.com;
=C2=A0 =C2=A0 > sea= n@ssn3rd.com; = bas@westerbaan.name
=C2=A0 =C2=A0 > Subject: [pqc-forum] Whether to hash-then-sign with Dili= thium and Falcon?
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > Hi Jake, Panos, Sean, Bas,
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > We notice that your IETF draft-massimo-lamps-pq-sig-cert= ificates-00 has the
=C2=A0 =C2=A0 > following security consideration:
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > > Within the hash-then-sign paradigm, hash functions = are used as a
=C2=A0 =C2=A0 > > domain restrictor over the message to be signed. By= pre-hashing, the
=C2=A0 =C2=A0 > > onus of resistance to existential forgeries becomes= heavily reliant on
=C2=A0 =C2=A0 > > the collision-resistance of the hash function in us= e. As well as this security
=C2=A0 =C2=A0 > goal, the hash-then-sign paradigm also has the ability t= o improve
=C2=A0 =C2=A0 > performance by reducing the size of signed messages. As = a corollary, hashing
=C2=A0 =C2=A0 > remains mandatory even for short messages and assigns a = further
=C2=A0 =C2=A0 > computational requirement onto the verifier. This makes = the performance of
=C2=A0 =C2=A0 > hash-then-sign schemes more consistent, but not necessar= ily more efficient.
=C2=A0 =C2=A0 > > Dilithium diverges from the hash-then-sign paradigm= by hashing the
=C2=A0 =C2=A0 > message during the signing procedure (at the point in wh= ich the challenge
=C2=A0 =C2=A0 > polynomial).
=C2=A0 =C2=A0 > > However, due to the fact that Dilithium signatures = may require the
=C2=A0 =C2=A0 > > signing procedure to be repeated several times for = a signature to be
=C2=A0 =C2=A0 > produced, Dilithium implementations can make use of pre-= hashing the
=C2=A0 =C2=A0 > message to prevent rehashing with each attempt.
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > First, quoting from the Dilithium NIST Round 3 submissio= n documents:
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > > Since our signing procedure may need to be repeated= several times
=C2=A0 =C2=A0 > > until a signature is produced, we also append a cou= nter in order to
=C2=A0 =C2=A0 > > make the SHAKE-256 output differ with each signing = attempt of the same
=C2=A0 =C2=A0 > message.
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > So it seems like the Dilithium designers explicitly want= the hash to differ
=C2=A0 =C2=A0 > across repeated attempts.
=C2=A0 =C2=A0 >

=C2=A0 =C2=A0 Hmmm, I don't see that in Dilithium; are they referring t= o the internal ExpandMask function?=C2=A0 That isn't applied to the inp= ut message.

=C2=A0 =C2=A0 In any case, it's easy to derive SHAKE( M || 1 ), SHAKE( = M || 2 ), ... without multiple passes through M; you compute the partial SH= AKE state after process M, and then apply that partial state to 1, 2, ...
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > Second, we had a similar discussion within the context o= f composite
=C2=A0 =C2=A0 > signatures when figuring out how to combine Dilithium an= d Falcon with
=C2=A0 =C2=A0 > ECDSA and RSA. We came out with a different conclusion; = that hash-then-
=C2=A0 =C2=A0 > sign reduces the security properties of Dilithium and Fa= lcon down to the
=C2=A0 =C2=A0 > collision resistance of the hash function used to pre-ha= sh.
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > We would like community opinion on this.
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > Here's the Security Consideration text that we'r= e working on:
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > In the hash-then-sign paradigm, the message to be signed= is hashed
=C2=A0 =C2=A0 > externally to the signature primitive, and then the hash= value is signed.
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > The hash-then-sign paradigm is required, for example, wi= th RSA signatures in
=C2=A0 =C2=A0 > order to sign messages larger than the RSA modulus. Hash= -then-sign also
=C2=A0 =C2=A0 > gives performance and bandwidth benefits, for example, w= hen the signature
=C2=A0 =C2=A0 > is performed by a networked cryptographic appliance sinc= e you only need to
=C2=A0 =C2=A0 > send a small hash value rather than streaming the entire= message.
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > With Dilithium and Falcon signatures it is not recommend= ed to pre-hash for
=C2=A0 =C2=A0 > the following reasons:
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > The Dilithium construction includes
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > ~~~
=C2=A0 =C2=A0 > Sign(sk,M):
=C2=A0 =C2=A0 > 10: mu \in {0, 1}^384 :=3D CRH(tr || M)
=C2=A0 =C2=A0 > ~~~
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > where `CRH` is any collision-resistant hash function and= `tr` is a component
=C2=A0 =C2=A0 > of the secret key.

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

=C2=A0 =C2=A0 > This provides strong security against pre-computed
=C2=A0 =C2=A0 > collision attacks since an attacker has no a-priori know= ledge of `r` and
=C2=A0 =C2=A0 > provides per-key hash-domain separation of the message t= o be signed.

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

=C2=A0 =C2=A0 Now, it does probably add a constant factor to any attack tha= t searches for a simultaneous collision between the hash that RSA/ECDSA use= s (without the prepend) and the hash that Dilithium uses (with the known pr= epend) - I would hesitate to give a value to that constant factor, but it i= s likely not large.

=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > The Falcon construction includes
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > ~~~
=C2=A0 =C2=A0 > Sign (m, sk, beta^2):
=C2=A0 =C2=A0 > 1: r <- {0, 1}^320 uniformly
=C2=A0 =C2=A0 > 2: c <- HashToPoint(r || m, q, n)
=C2=A0 =C2=A0 > ~~~
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > where `HashToPoint` is a SHAKE-256-based construct. This= provides strong
=C2=A0 =C2=A0 > security against pre-computed collision attacks since an= attacker has no a-
=C2=A0 =C2=A0 > priori knowledge of `r` and provides per-signature hash-= domain separation
=C2=A0 =C2=A0 > of the message to be signed.
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > If the message to be signed is pre-hashed, for example `= m0 =3D SHA256(m)`
=C2=A0 =C2=A0 > and then m0 provided to Dilithium or Falcon to sign, the= n you have re-
=C2=A0 =C2=A0 > introduced the collision problem since two messages m1 a= nd m2 where
=C2=A0 =C2=A0 > SHA256(m1) =3D=3D SHA256(m2) hash value will result a si= ngle Falcon or Dilithium
=C2=A0 =C2=A0 > signature value which is simultaneously valid for both m= 1 and m2. This
=C2=A0 =C2=A0 > removes the extra collision resistance built in to the D= ilithium and Falcon
=C2=A0 =C2=A0 > primitives and reduces it to the collision resistance st= rength of the underlying
=C2=A0 =C2=A0 > hash function. For this reason it is in general not reco= mmended to pre-hash
=C2=A0 =C2=A0 > when using Dilithium or Falcon except in cases where the= implementor is
=C2=A0 =C2=A0 > comfortable with this reduction in security.
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 > Therefore, for the purpose of interoperability of compos= ite signatures,
=C2=A0 =C2=A0 > implementations MUST NOT pre-hash messages for Dilithium= and Falcon. If
=C2=A0 =C2=A0 > pre-hashed versions of these signatures are desired, the= n separate signature
=C2=A0 =C2=A0 > algorithms will need to be defined.
=C2=A0 =C2=A0 >
=C2=A0 =C2=A0 >

=C2=A0 =C2=A0 --
=C2=A0 =C2=A0 You received this message because you are subscribed to the G= oogle Groups "pqc-forum" group.
=C2=A0 =C2=A0 To unsubscribe from this group and stop receiving emails from= it, send an email to pqc-forum+unsubscribe@list.nist.gov.
=C2=A0 =C2=A0 To view this discussion on the web visit https://groups.google.com/a/list.nist.gov/d/msgid/pqc-f= orum/CH0PR11MB5444B9D3A0CB6E447A2FA3E5C16A9%40CH0PR11MB5444.namprd11.prod.o= utlook.com.

_______________________________________________
CFRG mailing list
CFRG@irtf.org
https://www.irtf.org/mailman/listinfo/cfrg
--00000000000098880605e67d0549--