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

"Massimo, Jake" <jakemas@amazon.com> Wed, 17 August 2022 19:40 UTC

Return-Path: <prvs=221163758=jakemas@amazon.com>
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 EAB90C1522AA for <spasm@ietfa.amsl.com>; Wed, 17 Aug 2022 12:40:23 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -10.181
X-Spam-Level:
X-Spam-Status: No, score=-10.181 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_HIGH=-0.571, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_MSPIKE_H2=-0.001, RCVD_IN_ZEN_BLOCKED_OPENDNS=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, T_SCC_BODY_TEXT_LINE=-0.01, USER_IN_DEF_SPF_WL=-7.5] autolearn=unavailable autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=amazon.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 RDYg8JY-Axo5 for <spasm@ietfa.amsl.com>; Wed, 17 Aug 2022 12:40:22 -0700 (PDT)
Received: from smtp-fw-33001.amazon.com (smtp-fw-33001.amazon.com [207.171.190.10]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A5417C14F741 for <spasm@ietf.org>; Wed, 17 Aug 2022 12:40:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=amazon.com; i=@amazon.com; q=dns/txt; s=amazon201209; t=1660765223; x=1692301223; h=from:to:date:message-id:references:in-reply-to: content-id:content-transfer-encoding:mime-version:subject; bh=kjr2FRBYJnkdM1QZG9Ac7wBmh0oukzLRRnzLxKn/W3A=; b=XrhBJJ9FOJsTSmHBDpaYxhLlDOhy3UifSycyewh3ZeNiJchW4GyMO9hM 0SWYQC2JizvONXMLQ/zGCW6NZow+MGfpZpYudAP8olStGOFjE3XQqYYlN qP8o6b8aDxH2kLUNxcjmyYM8gpGz4bJRj/D8NhcYYNQb/p8TFJ95Ek3Fq Y=;
X-IronPort-AV: E=Sophos;i="5.93,244,1654560000"; d="scan'208";a="218762772"
Thread-Topic: [pqc-forum] RE: Whether to hash-then-sign with Dilithium and Falcon?
Received: from iad12-co-svc-p1-lb1-vlan3.amazon.com (HELO email-inbound-relay-pdx-2c-388992e0.us-west-2.amazon.com) ([10.43.8.6]) by smtp-border-fw-33001.sea14.amazon.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 17 Aug 2022 19:40:06 +0000
Received: from EX13MTAUWB001.ant.amazon.com (pdx1-ws-svc-p6-lb9-vlan3.pdx.amazon.com [10.236.137.198]) by email-inbound-relay-pdx-2c-388992e0.us-west-2.amazon.com (Postfix) with ESMTPS id 8A898E0B1D; Wed, 17 Aug 2022 19:40:04 +0000 (UTC)
Received: from EX19D001ANC002.ant.amazon.com (10.37.240.218) by EX13MTAUWB001.ant.amazon.com (10.43.161.207) with Microsoft SMTP Server (TLS) id 15.0.1497.38; Wed, 17 Aug 2022 19:40:02 +0000
Received: from EX13D46EUA004.ant.amazon.com (10.43.165.216) by EX19D001ANC002.ant.amazon.com (10.37.240.218) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA) id 15.2.1118.12; Wed, 17 Aug 2022 19:40:00 +0000
Received: from EX13D46EUA004.ant.amazon.com ([10.43.165.216]) by EX13D46EUA004.ant.amazon.com ([10.43.165.216]) with mapi id 15.00.1497.040; Wed, 17 Aug 2022 19:39:58 +0000
From: "Massimo, Jake" <jakemas@amazon.com>
To: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>, Mike Ounsworth <Mike.Ounsworth@entrust.com>, 'LAMPS' <spasm@ietf.org>, "cfrg@irtf.org" <cfrg@irtf.org>, pqc-forum <pqc-forum@list.nist.gov>, "Kampanakis, Panos" <kpanos@amazon.com>, "sean@ssn3rd.com" <sean@ssn3rd.com>, "bas@westerbaan.name" <bas@westerbaan.name>
Thread-Index: AQHYsmHsqI72UStsqk2jJOUfUo/Ds62zCCUA
Date: Wed, 17 Aug 2022 19:39:58 +0000
Message-ID: <88358933-A540-4000-9C7D-D248F670122F@amazon.com>
References: <CH0PR11MB5739393F19DD5282E3D7EF549F6A9@CH0PR11MB5739.namprd11.prod.outlook.com> <CH0PR11MB5444B9D3A0CB6E447A2FA3E5C16A9@CH0PR11MB5444.namprd11.prod.outlook.com>
In-Reply-To: <CH0PR11MB5444B9D3A0CB6E447A2FA3E5C16A9@CH0PR11MB5444.namprd11.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-GB
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-exchange-messagesentrepresentingtype: 1
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [10.43.166.209]
Content-Type: text/plain; charset="utf-8"
Content-ID: <18346F9A71D7E747AE0CA9A4A7725124@amazon.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/spasm/qsxVkvKvERXAPBXSQzKeCQd09rM>
Subject: Re: [lamps] [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." <spasm.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/spasm>, <mailto:spasm-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/spasm/>
List-Post: <mailto:spasm@ietf.org>
List-Help: <mailto:spasm-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/spasm>, <mailto:spasm-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 17 Aug 2022 19:40:24 -0000

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" <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 <pqc-forum@list.nist.gov>
    > Sent: Wednesday, August 17, 2022 1:27 PM
    > To: 'LAMPS' <spasm@ietf.org>; cfrg@irtf.org; pqc-forum <pqc-
    > 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 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 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/CH0PR11MB5444B9D3A0CB6E447A2FA3E5C16A9%40CH0PR11MB5444.namprd11.prod.outlook.com.