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

Phillip Hallam-Baker <phill@hallambaker.com> Fri, 19 August 2022 03:29 UTC

Return-Path: <hallam@gmail.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 5488DC15258B for <spasm@ietfa.amsl.com>; Thu, 18 Aug 2022 20:29:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.408
X-Spam-Level:
X-Spam-Status: No, score=-1.408 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FORGED_FROMDOMAIN=0.248, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.249, HTML_MESSAGE=0.001, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=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] autolearn=no autolearn_force=no
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 XZZZ9UrG2IzF for <spasm@ietfa.amsl.com>; Thu, 18 Aug 2022 20:29:26 -0700 (PDT)
Received: from mail-oa1-f42.google.com (mail-oa1-f42.google.com [209.85.160.42]) (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 7BCEFC152587 for <spasm@ietf.org>; Thu, 18 Aug 2022 20:29:26 -0700 (PDT)
Received: by mail-oa1-f42.google.com with SMTP id 586e51a60fabf-11cab7d7e0fso2778767fac.6 for <spasm@ietf.org>; Thu, 18 Aug 2022 20:29:26 -0700 (PDT)
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=TTEbZxljqRUyXOPOIvLIA3NJjhOh8Jt94gFUeK2/VhQ=; b=uRAf9K9zqHtUcOTonnSglmJ7/oDSZUb7TIpKOnM+Gu/0RrfqghUYW6IV0ieeyVkZg7 gZqs+MQJeBjlfPi41qiof9hCcxWVx2sKcl9iyvi54LNPMvOARTOEcbg5y3ZEtvJli5Cx ru7G6cAlGL7m6Gryua6mHv1LE38PVdRQm2FlDuvZGvv0bch8IrxvU/10r8KLVllQ+rTS 3hjdjgfwyYwqFCmQn1hCrGnxGJbdk45mzEDLM++hVjJ1pwi8tjLX/JfEPJn9E5wIlOGW RtTc+DhkATFfDlGy9ZE06XlL0mJDelPJjxe4ZQ55YXEmmuRWrUDWXjZVux6paBSuoqpt /uug==
X-Gm-Message-State: ACgBeo25iLhnUtsVUS9P8FouGl6NIWHn6BJCQAg8pCb/cRE5eDYQ1ssY Nj0PoTOnWFbp4MsmooH9pcThPUYWVZ9EH6gHZwA=
X-Google-Smtp-Source: AA6agR7xOppjWP6v8IMcEX0Ac9N/+4KPhsgYhDmADW7SK+Og7HROfgGCOpbhnAWNxRrJPo6ol+mMatOrSNkgjTdUrHM=
X-Received: by 2002:a05:6870:1601:b0:101:5e61:d8ee with SMTP id b1-20020a056870160100b001015e61d8eemr2800339oae.244.1660879765631; Thu, 18 Aug 2022 20:29:25 -0700 (PDT)
MIME-Version: 1.0
References: <CH0PR11MB5739393F19DD5282E3D7EF549F6A9@CH0PR11MB5739.namprd11.prod.outlook.com> <CH0PR11MB5444B9D3A0CB6E447A2FA3E5C16A9@CH0PR11MB5444.namprd11.prod.outlook.com> <88358933-A540-4000-9C7D-D248F670122F@amazon.com> <CAFTXyYC=Zt0hhk5G2A6b6AOM6Aww7jL3CwUmcZfNpmsWW0cpGQ@mail.gmail.com> <DM6PR11MB2585E47B6D7D92EBC1E71A29EA6D9@DM6PR11MB2585.namprd11.prod.outlook.com>
In-Reply-To: <DM6PR11MB2585E47B6D7D92EBC1E71A29EA6D9@DM6PR11MB2585.namprd11.prod.outlook.com>
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Thu, 18 Aug 2022 23:29:14 -0400
Message-ID: <CAMm+LwiCxwv6smMSL4u+3dnBYWDkStE4pBXh25GKAuaVj+nehg@mail.gmail.com>
To: John Gray <John.Gray=40entrust.com@dmarc.ietf.org>
Cc: Tadahiko Ito <tadahiko.ito.public@gmail.com>, "Massimo, Jake" <jakemas=40amazon.com@dmarc.ietf.org>, "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>
Content-Type: multipart/alternative; boundary="00000000000071f8d705e68fb421"
Archived-At: <https://mailarchive.ietf.org/arch/msg/spasm/6R-KJTGW3k2l9zbIck7_BSAO7G4>
X-Mailman-Approved-At: Fri, 19 Aug 2022 08:40:39 -0700
Subject: Re: [lamps] [EXTERNAL] Re: [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." <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: Fri, 19 Aug 2022 03:29:27 -0000

On Thu, Aug 18, 2022 at 11:29 AM John Gray <John.Gray=
40entrust.com@dmarc.ietf.org> wrote:

> Thanks Tadahiko,
>
>
>
> I read through your paper, and it covers exactly the usability issues we
> have come across!   We were wondering if it is possible to perform the
> specific hashing external to the server (which could be an HSM as in your
> paper, or timestamp server, etc).   For example, for Dilithium the mu :=
> CRH( tr || M) and for Falcon it would be  c <- HashToPoint(r || m, q, n).
>   Your paper answers that question, it can be done for Falcon, but  not
> Dilithium (without changing the signature output).   So part of our
> question is whether using a regular external Hash as we do today for RSA
> and ECDSA (and what you call a boundary type B) somehow reduces the
> security and we shouldn’t recommend it.   We are interested in this because
> we are looking at defining composite pairs or triples which combine
> existing signature algorithms like RSAWithSHA256 and ECDSAWithSHA256 with
> Falcon or Dilithium.    Having to change the operational paradigm for an
> HSM or something like a timestamping server would result in large amounts
> of data having to be piped across the internet for signatures (as you point
> out in your paper).
>
>
>
> For our composite signature use case it brings up similar questions.   We
> can support a mode where external hashing is done once, and then
> individually signed by the components (this makes it much more efficient)
> both internally and externally for the HSM, timestamping, code signing
> use-cases.   However, in the case of Dilithium there would need to be two
> signature modes Sig = Dilithium (Message) and the other would be Sig =
> Dilithium ( HASH (Message)).   I don’t think that is necessarily a bad
> thing as long as it is standardized and secure.   Alternatively, we could
> support independent hashing for each component, but that gets strange if
> you are doing an external hash for ECDSA, but then need to send the whole
> data for Dilithium.   We would likely have to end up supporting sending the
> whole data if external hashing compromises security of the PQC composites,
> but then it is even more inefficient as each component would need to hash
> independently.    You also covers this in section 4.3 your paper:
>
>
>
> “We can construct type B cryptographic boundaries by adding one more hash
> function before the execution of PQC’s signature generation algorithm… This
> approach would improve the efficiency of lattice based digital signature
> schemes deployed in HSM. It would have a greater impact on Dilithium, but
> also be applicable to Falcon and other digital signature schemes. Two modes
> of PQC algorithms utilizing this approach will be able to exist, namely, a
> PQC algorithm without an additional hash (i.e. original PQC algorithm) and
> a PQC algorithm with an additional hash. If there are two modes of a
> digital signature scheme, then the asymmetric operation for those two modes
> must not be identical. The reason is that, obtaining a signature from the
> mode with an additional hash function would help attackers who can attack
> another mode which is without the additional hash function.”
>

That is not a new issue and it is one that we discussed at great length for
RSA. The hash of the digest is part of the signature payload to prevent
substitution attacks.

I am finding the description of the problem here to be making assumptions
about what 'formal proofs' are demonstrating that are probably
demonstrating something else. If you assume there is only one true digest
function, you 'solve' the digest substitution problem by pretending it does
not exist...


In my view, the signature function should be over the payload and the
additional authenticated data. Whether this is the OID of the digest
algorithm alone or something more depends on the signature scheme. That is
what JOSE etc. have to sort out.

Preventing a digest downgrade attack may be considered the concern of the
cryptographic envelope format because there may be more than one form of
downgrade attack to be considered. But it is also something we have
traditionally included in the signature...