[lamps] Re: [pqc-forum] RE: Pre-hash options for ML-DSA

"Markku-Juhani O. Saarinen" <mjos.crypto@gmail.com> Thu, 01 August 2024 15:04 UTC

Return-Path: <mjos.crypto@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 96582C1519B6 for <spasm@ietfa.amsl.com>; Thu, 1 Aug 2024 08:04:11 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.002
X-Spam-Level:
X-Spam-Status: No, score=-2.002 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_FONT_LOW_CONTRAST=0.001, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=0.1, RCVD_IN_DNSWL_BLOCKED=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, URIBL_BLOCKED=0.001, URIBL_DBL_BLOCKED_OPENDNS=0.001, URIBL_ZEN_BLOCKED_OPENDNS=0.001] autolearn=ham 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 bUFLonGAcPN0 for <spasm@ietfa.amsl.com>; Thu, 1 Aug 2024 08:04:07 -0700 (PDT)
Received: from mail-pl1-x62b.google.com (mail-pl1-x62b.google.com [IPv6:2607:f8b0:4864:20::62b]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature ECDSA (P-256) server-digest SHA256) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 46BE3C15171B for <spasm@ietf.org>; Thu, 1 Aug 2024 08:04:07 -0700 (PDT)
Received: by mail-pl1-x62b.google.com with SMTP id d9443c01a7336-1ff3d5c6e9eso25402565ad.1 for <spasm@ietf.org>; Thu, 01 Aug 2024 08:04:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1722524646; x=1723129446; darn=ietf.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=uwCRWStyjAnzzDSS3FufkNOlRcIgEArAJGltPXbG8Yw=; b=cXlONL7K5AsYxE41/4WRDuMQI31w1IdfsReeo+cGM7ccWIi6GBuwn8v9fEmqyk6+l6 QAeH1mGOmjHxUj8yuMsVEUoQJluu1aEcrnNPfHn/Cej2HzVT5IxAiyKaXTxcQtl4LGA+ HVI9RVAUBFffY83EragBuzdJrCaPapEWmcieO4A1Ck4MTlia7/XFns89nOjos3PHZxnm RfgxpQbX+dWakgcoeix6CEC+BFiKOec+Nrdr1I6sBf4T8EjavB7TSNFBIt7y/lQDuWkw vWJ/hj/4q0C005yvYDHYzYP7t3ZfE00e1NFsbKDKk8qwAgP/hcZOo3yiNNp0I0Yh5VJD cG/w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722524646; x=1723129446; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=uwCRWStyjAnzzDSS3FufkNOlRcIgEArAJGltPXbG8Yw=; b=o28RdLrjgalxyrwWfBgNTeLneARGfcfwsDyR2J9DSG2flnaalE5+shPD6ac4wePMFA LAk+eDnQKQlK68CT/Nu2HuwcdQxhgycsHsz/KoZU+eTm2Hx0KqP61oD0Oc94IeDs5Hao 1v86f39iq+1X1xF+2xep4goHD2xpx/7jnBNfpDCYKpSaEzFHKTh7yBAlx8rYSuc9tnAV qQHe7FIwxHSeG+jd6xFM9izA/8mP6B9aBr6nrKQU+leeRCHboJXmEy7jHNu5t7iv3+0M pTbsDtjdGVrTwuF5FDAXa6LmzsNVjVKqlYAellW4zfghpHcfjJM5LgS/EFvZ/+djmJmB fhtQ==
X-Forwarded-Encrypted: i=1; AJvYcCVD7DX1RhOaIjDl4Fy3qLfCvV+WZUoVQUNpf+444AhhfnKYw0EU8WmEEJhGtJA+RZgt0v9AE8j3LTCzX0HbBw==
X-Gm-Message-State: AOJu0YyRNSpHJ49kOME4UWVMM1isEd4QpbhxIqCSTAAIshYd0OXEH0ls yCCfhGOrqdP8XSM6vpWTpkZDxcVxdgO4DaFh7oQD9JiCiYDXMep/msalzSD8FBwmp7GGcuz0+wZ cU0R6Q9KYyMDBXcq5azdQFKTPkSk=
X-Google-Smtp-Source: AGHT+IHbqYK8QqGSAvaYPiwQog7JOzA01ajnGPaIQvSag68+V6HZYzpcsYaqh4PFjcMbJTAiExWDq7BeZaOVsCrNT5w=
X-Received: by 2002:a17:902:e54e:b0:1fd:7fac:a539 with SMTP id d9443c01a7336-1ff572a2c53mr6000675ad.16.1722524642935; Thu, 01 Aug 2024 08:04:02 -0700 (PDT)
MIME-Version: 1.0
References: <f26dc8c7-d7b3-4fb5-8189-55ffb2d99332@nist.gov> <60e9e8ca-3318-4017-b11a-7be327b90d75@nist.gov> <CH0PR11MB544442CC5ED7AE1B73A14E10C1B12@CH0PR11MB5444.namprd11.prod.outlook.com> <MW4PR09MB10059657D1F7892DEE045A9E6F3B12@MW4PR09MB10059.namprd09.prod.outlook.com> <CH0PR11MB5444AB79F4C156238C2D78CDC1B12@CH0PR11MB5444.namprd11.prod.outlook.com> <DM6PR09MB485527D4EAB537B60FDCB8A59CB12@DM6PR09MB4855.namprd09.prod.outlook.com> <CH0PR11MB573969D387738BBB9E2FFAF49FB12@CH0PR11MB5739.namprd11.prod.outlook.com> <DM6PR09MB4855424DA9DB254DCDB136589CB12@DM6PR09MB4855.namprd09.prod.outlook.com> <CA+iU_qkxFEY2jhYYoMy79g-GOp9kuzygatM+Cw39nQQxJ5NpwA@mail.gmail.com> <bfa3601d-b8b7-470c-a74b-3d1bc7358d1a@nist.gov> <CA+iU_qkdk3gOwL0ck1Hvg=apAvsyrCUX++g3PR0HwXAEKxOWVA@mail.gmail.com> <da0985b5-a058-4910-8319-c334b236bba8@nist.gov>
In-Reply-To: <da0985b5-a058-4910-8319-c334b236bba8@nist.gov>
From: "Markku-Juhani O. Saarinen" <mjos.crypto@gmail.com>
Date: Thu, 01 Aug 2024 15:03:51 +0000
Message-ID: <CA+iU_qkkzu-=XduXu3=eh6=neFX_zaypiKEJgyd8iKbi+n_Hxw@mail.gmail.com>
To: "David A. Cooper" <david.cooper@nist.gov>
Content-Type: multipart/alternative; boundary="000000000000758eb7061ea08539"
Message-ID-Hash: ZXS57DOWOWCKEH2NENBIETXN7RFZXQUV
X-Message-ID-Hash: ZXS57DOWOWCKEH2NENBIETXN7RFZXQUV
X-MailFrom: mjos.crypto@gmail.com
X-Mailman-Rule-Misses: dmarc-mitigation; no-senders; approved; emergency; loop; banned-address; member-moderation; header-match-spasm.ietf.org-0; nonmember-moderation; administrivia; implicit-dest; max-recipients; max-size; news-moderation; no-subject; digests; suspicious-header
CC: Mike Ounsworth <Mike.Ounsworth@entrust.com>, pqc-forum <pqc-forum@list.nist.gov>, spasm@ietf.org, "Perlner, Ray A. (Fed)" <ray.perlner@nist.gov>
X-Mailman-Version: 3.3.9rc4
Precedence: list
Subject: [lamps] Re: [pqc-forum] RE: Pre-hash options for ML-DSA
List-Id: This is the mail list for the LAMPS Working Group <spasm.ietf.org>
Archived-At: <https://mailarchive.ietf.org/arch/msg/spasm/d81eGNx-zKu3RO0OPz69k0EjL5w>
List-Archive: <https://mailarchive.ietf.org/arch/browse/spasm>
List-Help: <mailto:spasm-request@ietf.org?subject=help>
List-Owner: <mailto:spasm-owner@ietf.org>
List-Post: <mailto:spasm@ietf.org>
List-Subscribe: <mailto:spasm-join@ietf.org>
List-Unsubscribe: <mailto:spasm-leave@ietf.org>

Thanks David!

I think this is sufficient for the LAMPS IETF "PQC Certificate Interop
Hackathon" group to create some test certificates etc.

What names should we use ? It is of course important from security
viewpoint that no application will create or accept "pure" signatures
without the domain separation prefix, so we wouldn't want to even give that
a name. Hence a natural option would seem to be for pure version to just
use the parameter set as an identifier:

Signing M' = (0x) 00 00 || M

 ML-DSA-44
 ML-DSA-65
 ML-DSA-87


Signing M' = (0x) 01 00 06 09 60 86 48 01 65 03 04 02 03 || SHA512(M)

 ML-DSA-44-SHA512
 ML-DSA-65-SHA512
 ML-DSA-87-SHA512

That is, if and only if a prehash is used, the hash name is added at the
end. Additionally, if the context is used for <something> then that could
perhaps be ML-DSA-<something>-<hash> ?

>From Dustin's original message I understand that SLH-DSA prehashing would
be handled exactly the same way, so a prehashed version could have a name
like SLH-DSA-SHA2-256s-SHA512 ?

Best Regards,
-markku

Dr. Markku-Juhani O. Saarinen <mjos@iki.fi>


On Thu, Aug 1, 2024 at 2:07 PM David A. Cooper <david.cooper@nist.gov>
wrote:

> Yes, that is the correct OID for SHA-512. We do plan to specify in the
> FIPS the DER encodings of the OIDs of hash functions and XOFs that we think
> are most likely to be used. In addition to the sources that you mentioned,
> the OIDs for all of the NIST approved hash functions and XOFs are available
> at
> https://csrc.nist.gov/projects/computer-security-objects-register/algorithm-registration.
> This is also where the OIDs for ML-DSA, ML-KEM, and SLH-DSA will be posted.
>
> The value for M' in the case of SHA-512 and an empty context string also
> seem correct.
>
> On 7/31/24 1:48 PM, Markku-Juhani O. Saarinen wrote:
>
> Thanks David. Somehow that got buried for me.
>
> The proposed formatting ( in
> https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/JKMh0D0pa30/m/vbflXolxAQAJ
> ) seems sensible as the way it's specified there one doesn't need an actual
> ASN.1 encoder for this, just hard-coded byte sequences for OIDs.
>
> If I was handed this spec, I'd guess that the OID would be "id-sha512"
> defined in Appendix B of RFC 8017 (PKCS #1 v 2.2).
> https://www.rfc-editor.org/rfc/rfc8017.html#appendix-B.1
>
>  id-sha512    OBJECT IDENTIFIER ::= {
>            joint-iso-itu-t (2) country (16) us (840) organization (1)
>            gov (101) csor (3) nistalgorithm (4) hashalgs (2) 3
>        }
>
> I'd absolutely specify the actual DER encoding in the FIPS spec ..  Unless
> I'm mistaken, in this case that would be 11 bytes (0x) 06 09 60 86 48 01 65
> 03 04 02 03.
>
> This same OID (2.16.840.1.101.3.4.2.3) / id-sha512 already appeared 20
> years ago in RFC 3560. In IETF specs this is wrapped in various ways which
> seem redundant. Avoiding more complicated ASN.1 encodings and is ok as long
> there will *never* be any other data following M in the hash in this
> encoding. The length of M is only authenticated by the hash function
> itself, not by domain separators.
>
> One can try this out with OpenSSL asn1 parser with most Linux systems:
>    $ echo -en '\x06\x09\x60\x86\x48\x01\x65\x03\x04\x02\x03' | openssl
> asn1parse -inform der
> Which outputs
>     0:d=0  hl=2 l=   9 prim: OBJECT            :sha512
>
> The proposed  pre-hash sequence  M' = octet(1) || octet(OLEN(ctx)) || ctx
> || OID_PH || PH(M) would then typically (without ctx -- length 0) turn out
> to be in case of PH=SHA512
>
> M' = (0x) 01 00 06 09 60 86 48 01 65 03 04 02 03 || SHA512(M)
>
> right ?
>
> Cheers,
> -markku
> Dr. Markku-Juhani O. Saarinen <mjos@iki.fi>
>
>
> On Wed, Jul 31, 2024 at 7:44 PM David A. Cooper <david.cooper@nist.gov>
> wrote:
>
>> The OIDs that we are discussing are the globally unique ASN.1 OIDs, such
>> as would appear in the signature field of an X.509 certificate.
>>
>> The domain separation will be addressed as described in
>> https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/JKMh0D0pa30/m/vbflXolxAQAJ.
>> For ML-DSA, the message representative will still be computed as mu =
>> SHAKE256(tr || M), but M will be modified to include the domain separation
>> information.
>>
>> On 7/31/24 11:58 AM, Markku-Juhani O. Saarinen wrote:
>>
>> Hi,
>>
>> Kind of makes sense -- For ML-DSA, prehashing just seems to be a way of
>> using SHA2 with ML-DSA. We were expecting this based on CNSA announcements,
>> but I still don't understand *their *rationale for demanding SHA2..
>> perhaps some legacy integration stuff as it makes ML-DSA more of a "drop-in
>> replacement" for existing CNSA -- while sacrificing some security
>> properties.
>>
>> And, as noted, there is less of a technical need for prehashing with
>> ML-DSA, which does not mandate two hash passes (and hence keeping the
>> message in memory) in signing like SLH-DSA does -- you just need to know
>> the "tr" prefix. I tend to agree that if you want to use SHAKE with ML-DSA,
>> you can use the pure version in almost all applications, which is more
>> secure anyway (or rather, can't be less secure).
>>
>> Ray wasn't exactly clear about the OIDs and how they are to be used -- I
>> suppose he means just some domain separation identifiers (reserved numbers)
>> rather than actual globally unique ASN.1 OIDs as in X.509?
>>
>> It may have been discussed on the list but I couldn't find a definitive
>> answer -- My assumption is that the pure version would compute the 512-bit
>> message representative mu something like mu = SHAKE256( "pure oid" | tr | M
>> ), and the proposed prehash version would compute mu = SHAKE256( "SHA512
>> prehash oid" | tr |  SHA512(M) ). These OIDs are just some byte constants.
>> Is this correct? One could also put the domain separation OID in the
>> commitment hash ~c (line 15 in signing) /  ~c' (line 12 in verify) but that
>> would seem more cumbersome and I don't see any advantages.
>>
>> I like that the drivers can just pass the 512-bit "mu" hash ("actual
>> message hash" ) to the core ML-DSA lattice crypto module for signing or
>> verification and do all this hash/prehash/OID logic outside it.
>>
>> Cheers,
>> -markku
>>
>> Dr. Markku-Juhani O. Saarinen <mjos@iki.fi>
>>
>>
>> On Wed, Jul 31, 2024 at 6:39 PM 'Perlner, Ray A. (Fed)' via pqc-forum <
>> pqc-forum@list.nist.gov> wrote:
>>
>>> Hi Mike,
>>>
>>>
>>>
>>> The main thinking for focusing on SHA512 for pre-hash was that even pure
>>> ML-DSA essentially pre-hashes the message with SHAKE256 when computing the
>>> message representative µ, and the FIPS already includes allowances for
>>> the message representative to be computed in a different cryptographic
>>> module from the one that uses the private key. While we are aware that the
>>> inclusion of a public key hash in the computation of the message
>>> representative could break some applications that don’t have access to the
>>> public key when doing pre-hash, we were thinking the more likely scenario
>>> where an additional pre-hash step would be desirable is when dealing with
>>> large messages on platforms with SHA2 hardware support, but not SHA3
>>> hardware support.
>>>
>>>
>>>
>>> We are open to the possibility that additional OIDs may need to be
>>> defined now or in the future, but all else being equal, our preference
>>> would be for fewer options.
>>>
>>>
>>>
>>> Best,
>>>
>>> Ray
>>>
>>>
>>>
>>>
>>>
>>> *From:* Mike Ounsworth <Mike.Ounsworth@entrust.com>
>>> *Sent:* Wednesday, July 31, 2024 1:59 PM
>>> *To:* Perlner, Ray A. (Fed) <ray.perlner@nist.gov>; pqc-forum <
>>> pqc-forum@list.nist.gov>
>>> *Subject:* RE: Pre-hash options for ML-DSA
>>>
>>>
>>>
>>> Hi Ray,
>>>
>>>
>>>
>>> Can you comment on the choice to use SHA2 for the prehash despite the
>>> fact that ML-DSA internally uses SHA3 (SHAKE)? I don’t necessarily disagree
>>> with the decision, but I would like to hear the rationale from NIST.
>>>
>>>
>>>
>>> ---
>>>
>>> *Mike* Ounsworth
>>>
>>>
>>>
>>> *From:* 'Perlner, Ray A. (Fed)' via pqc-forum <pqc-forum@list.nist.gov>
>>> *Sent:* Wednesday, July 31, 2024 12:54 PM
>>> *To:* pqc-forum <pqc-forum@list.nist.gov>
>>> *Subject:* [EXTERNAL] [pqc-forum] Pre-hash options for ML-DSA
>>>
>>>
>>>
>>> Dear all, As with SLH-DSA, and as previously announced, ML-DSA will have
>>> domain separated pure and pre-hash variants. We are currently considering
>>> specifying OIDs for the pure variant of ML-DSA and a pre-hash variant using
>>> SHA512 for the pre-hash.
>>>
>>>
>>>
>>> Dear all,
>>>
>>> As with SLH-DSA, and as previously announced, ML-DSA will have domain
>>> separated pure and pre-hash variants. We are currently considering
>>> specifying OIDs for the pure variant of ML-DSA and a pre-hash variant using
>>> SHA512 for the pre-hash. We plan to do this for each of the 3 parameter
>>> sets of ML-DSA (ML-DSA-44, ML-DSA-65 and ML-DSA-87).
>>>
>>> We would appreciate any feedback people may have about which OIDs to
>>> specify for ML-DSA
>>>
>>> Thank you,
>>> Ray
>>>
>>> --
>>> 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/DM6PR09MB485527D4EAB537B60FDCB8A59CB12%40DM6PR09MB4855.namprd09.prod.outlook.com
>>> <https://urldefense.com/v3/__https:/groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB485527D4EAB537B60FDCB8A59CB12*40DM6PR09MB4855.namprd09.prod.outlook.com?utm_medium=email&utm_source=footer__;JQ!!FJ-Y8qCqXTj2!YiGSkO7sDPLXu3-0404-VGoLKGnkqbVqM-7RHOEFCvlK2lZrz9OsnKQZB3u3A6OkjXdDcsZgK65JLsazIJB-8zogaBl1$>
>>> .
>>> --
>>> 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/DM6PR09MB4855424DA9DB254DCDB136589CB12%40DM6PR09MB4855.namprd09.prod.outlook.com
>>> <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/DM6PR09MB4855424DA9DB254DCDB136589CB12%40DM6PR09MB4855.namprd09.prod.outlook.com?utm_medium=email&utm_source=footer>
>>> .
>>>
>> --
>> 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/CA%2BiU_qkxFEY2jhYYoMy79g-GOp9kuzygatM%2BCw39nQQxJ5NpwA%40mail.gmail.com
>> <https://groups.google.com/a/list.nist.gov/d/msgid/pqc-forum/CA%2BiU_qkxFEY2jhYYoMy79g-GOp9kuzygatM%2BCw39nQQxJ5NpwA%40mail.gmail.com?utm_medium=email&utm_source=footer>
>> .
>>
>>
>>
>