[lamps] Whether to hash-then-sign with Dilithium and Falcon?

Mike Ounsworth <Mike.Ounsworth@entrust.com> Wed, 17 August 2022 17:26 UTC

Return-Path: <Mike.Ounsworth@entrust.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 9EBABC1524B8; Wed, 17 Aug 2022 10:26:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.806
X-Spam-Level:
X-Spam-Status: No, score=-2.806 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, RCVD_IN_DNSWL_LOW=-0.7, 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=entrust.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 g_tzfMjofTpK; Wed, 17 Aug 2022 10:26:54 -0700 (PDT)
Received: from mx07-0015a003.pphosted.com (mx07-0015a003.pphosted.com [185.132.183.227]) (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 D9A35C1524C1; Wed, 17 Aug 2022 10:26:52 -0700 (PDT)
Received: from pps.filterd (m0242864.ppops.net [127.0.0.1]) by mx08-0015a003.pphosted.com (8.17.1.5/8.17.1.5) with ESMTP id 27HH1PTb006895; Wed, 17 Aug 2022 12:26:47 -0500
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=entrust.com; h=from : to : subject : date : message-id : content-type : content-transfer-encoding : mime-version; s=mail1; bh=H4f/N7YVi8DFsgFrDeDZNGl5voEgWkasruqBDdf6ywU=; b=Aexq1SrqSIIbUzuS2fLmpeOuX8LlvX08GeDKlimuGlKtJ+UGBJFV1z2o1TpCbDXgnlhK MQqcveN7uRLu47G7oeHzP3Q8v+cnB/Z38+Dc7FBa4/H5v03C5N43ppyAPMqTKsDqTBjZ 2qmy9dIYPq+w7/eAdoHg1CeGen7cpmeM5fexkid3bSzsojWkEhMMO0KzORecSVwD2YRT ob1puIxayj9lD/MFdkPQaV+hO4ViEW4wtKgIQIs1zgIBfRlwKFw5PHbJceWnGYqedhoH VIzDamTXtLx5q02/54vqBmSA+yv3e3tgB76okm1zrkyA7pCOv8yYrpghEYdMEo95T/cg /g==
Received: from nam02-bn1-obe.outbound.protection.outlook.com (mail-bn1nam07lp2043.outbound.protection.outlook.com [104.47.51.43]) by mx08-0015a003.pphosted.com (PPS) with ESMTPS id 3hyv2mxt7p-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT); Wed, 17 Aug 2022 12:26:47 -0500
ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=l6f5t8x1gd+vZnvIocD6AZwpBgdGlw7lsKS3XYN/tASHPqVEXpOQfziaDAkxJ3tTpy97hg0/qnazyHCvwiV/UyEe0lH8trvlG23xCpi8SqeBaXhDrPH8ph6CcRBmY7Z9mJwmnxWUkLqyjmV1Ky7ozmBxM3dG4wbA/nMgxzXf2FkCKUWVacR4fq9DgSBsRuzHIBDBDs+SZprwvgelH22wixR6L+UH3sPgsumPMpGLmMqOs16rdMVK6PauTFQvlz+uby+x0Dft59OwLc38Yf7p5vRFvDQu/knONo4RTvnSfXHfSsNb++jJYsPkZjslj7CfZcWvuep3xWy5Nl2SkXDaYw==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=H4f/N7YVi8DFsgFrDeDZNGl5voEgWkasruqBDdf6ywU=; b=JfClem0w7WDP9nnkjeiZGYTjNSiJjS2wXYtIuUdQSbjWsTz9BmaKZQOSEY6VB8DzY/s9JJ17+qAXkc0WD4CdW3f7TcCHdf2ZfhafahEFXNB4xYg92ICbtLL+cav2pRGeri4wU3PaAFimZppO6hecckfpojL9ndfT3KCP5yAvCvN3azRFXUDaudLQ7Ljeq/VN/7SnwTtiYL1pMv5nxV9OXdtLjljd8czlO1hJXmc9E+hGkGkULEYiHuzzFI8frTdglMsnSUOsqTvxkdGArF1mszQc3JD84kvZGOenrdYmZKS52taMvf3KefgqQ34QUocY/uWB26tTxG/QaUBMSfVHcg==
ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=entrust.com; dmarc=pass action=none header.from=entrust.com; dkim=pass header.d=entrust.com; arc=none
Received: from CH0PR11MB5739.namprd11.prod.outlook.com (2603:10b6:610:100::20) by MN2PR11MB4253.namprd11.prod.outlook.com (2603:10b6:208:18d::11) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.5525.19; Wed, 17 Aug 2022 17:26:44 +0000
Received: from CH0PR11MB5739.namprd11.prod.outlook.com ([fe80::ed02:6e67:98f7:f33d]) by CH0PR11MB5739.namprd11.prod.outlook.com ([fe80::ed02:6e67:98f7:f33d%8]) with mapi id 15.20.5525.010; Wed, 17 Aug 2022 17:26:42 +0000
From: Mike Ounsworth <Mike.Ounsworth@entrust.com>
To: 'LAMPS' <spasm@ietf.org>, "cfrg@irtf.org" <cfrg@irtf.org>, pqc-forum <pqc-forum@list.nist.gov>, "jakemas@amazon.com" <jakemas@amazon.com>, "kpanos@amazon.com" <kpanos@amazon.com>, "sean@ssn3rd.com" <sean@ssn3rd.com>, "bas@westerbaan.name" <bas@westerbaan.name>
Thread-Topic: Whether to hash-then-sign with Dilithium and Falcon?
Thread-Index: AdiyWmrrCCvkDLBiTn2DcOMWvaOQ/g==
Date: Wed, 17 Aug 2022 17:26:42 +0000
Message-ID: <CH0PR11MB5739393F19DD5282E3D7EF549F6A9@CH0PR11MB5739.namprd11.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
x-ms-publictraffictype: Email
x-ms-office365-filtering-correlation-id: 70ec907d-d3d9-46bf-0f58-08da8075a6c8
x-ms-traffictypediagnostic: MN2PR11MB4253:EE_
x-ms-exchange-senderadcheck: 1
x-ms-exchange-antispam-relay: 0
x-microsoft-antispam: BCL:0;
x-microsoft-antispam-message-info: TKbguU2AUkwlnxw0MUfMgUbiLRhvHPjqQa+6USQCJKo51U2gOm8L0G7xOSITKuW9Lfmlx4DZyRuM+bcKMhvrfNwIqPGm45PdTLYWeE/82rcm7xcby0Rx1PyIL44vSiVSmzgtiAGU82rpRvMA8UX2UYuHk/PpMExCgRNnYk/sGUUaZAIeVckohdu94MxdoziRqlfH6XBuhjbrc6H3r2cK2PAHIdhwuXhRYZEHoEdHCQJ4qTtjQ/Nm2adeNThqPX4hPci5IZFAu0EAHyPV1splfk/Ud4H7opgZU3RimDHUlLohYW1BBfDCPNTlMTJp9n/p01kb7rgOZ2P5cOhr7XyJ7mIFU/euyxlwI890YFDjC9Q8W+6DV9x04B/FyMudeAq8+/jSaUF4d1vAnkF/EADghOKxlGtPpCW8F7nqjeI+zPzUcgRZubQS1XaO5+iW1Yl6KwTChJfiUkW02N1no4GIyIpK2y7galOIqDFCaeIGjASzxkdQhhKwtzh0vj+fc7glR9NdXRmN6v66BU95gAB2qmSeZhbav4pBZFoIWOEAl1/Q2sCro9j3hMJmWplQ0/JchBhqYn4/3b4cZmm8/VXxGFpdKCI5eelyzukZfcraY1nH+wHokga+VORJECLJsnOvFXRKNvcbeoSUfG6E6mwAoMhzQOn1I9tvFFdT3xASunq2chy6qrilS3eOGtk0MGMml1wgS/9sYbOofkz/Pok4dfoRfdVLGLy/ugQi/njFflX1IitFKMK8ZpqxWu9ccRSQEH7I/md35lBxOmRqnbu52LHO10g+K0lN2hhEjnBJKfxivz0JqiLm36bqR7sNbxXM
x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:CH0PR11MB5739.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFS:(13230016)(39860400002)(396003)(346002)(136003)(366004)(376002)(186003)(110136005)(38070700005)(316002)(71200400001)(122000001)(41300700001)(26005)(55016003)(76116006)(66946007)(8676002)(9686003)(83380400001)(64756008)(66476007)(66446008)(66556008)(7696005)(6506007)(38100700002)(478600001)(2906002)(33656002)(5660300002)(8936002)(86362001)(52536014); DIR:OUT; SFP:1102;
x-ms-exchange-antispam-messagedata-chunkcount: 1
x-ms-exchange-antispam-messagedata-0: Xyx0eTnvZYij2oUgN2F1Br76ZiQkmlx3m3a/K4DIn4ce7nTe2IUInkW9D53ecNcrMSTjqf35yILJkjronT5x0h97WSf6vchF9jia9+22pXx0cnp8MKEYykb2PJBz14LcF3BXTeM1B3VbWGLn4BfaZpjHVg/A+VfytKLML+hvqqucWZDddCKkKUBEVwqDnpvgLv2PJy+dYReQm9DTqP3F86jwMenRhRv0cNRJZkOcNTFiStuI4dqrgnBErDJtFPQJawWhQnRhYJela9NTaBvsHcDaUWEYB7e1Ca7DfDuZXjbqaxsepRNLJZVsLwo0LN3NHtVnuCwapm/KUuBl4avEt5Jg7jWCAHWIXue1PTM5zxU+mgIPrFZmkNNWIGrkUbddIxbufSXiGaI1ZUOsxdZBoyi8XnyAEftwUa9V7PqAF9fqzUCFKfPWon2GwqQ2j/AVZMYxT40XKakx6s4hfusTFf8rL3SICXdHM8usC7wvGJphvHxTLlQSEYhDEuY39UJAYDEZZclGWslEP6y9LnWjsQ+GN1op37Gsc9Ak3Q8jXQdEFTD4y+QgE1DFBUk29TUZZIJ0d4lDcCBuJMf/n/2nsGcKx+c56Jp44igWJY1IOd5HFQPGz+bwlQlJnYT0BVkrIy2TmfEgqsnlpCWCAakgKXxHj+aNhn7ngHP4RqH6d8H/r6Znv0ftTfxaB4dej4bw5u5i74tr5ShBQH98z0Aez1kB4ItzLYbA9/Aq6tkBoPDP3b+3HUwjTp/6RlQZtr6zsZx0IPL47yTfZY8jGzj5oak4MYKDRes2rrF08Shubdji05BXzecLL3oNwV4sdU+1L7bAqLkwH8Rt+r9VDiKYmSFC3jwGx767sZgcyWCj257Tg8oNWdvc9GDqScWuHS3gFf8fq4CrYDvpiVKrdyv75xk1WJqpEGq2fmGhjxuJH58HkPuLtSmNtOLZS0JPchxVgj2nnr5TF40fD6rqTwaQ4f9tEnejAD4iFUUpFT6FxknoiWhR1qsAeYoQXuTb7MNRQ7Z1EAKSqETUT50e78ZQ0ohrzXzOfVsCnyuQaF9K68BGJKRM6sDJ5cfHfPvVIOuMt7QIm/fhFMMsgUQV4nyAJK9lqNZuX36aGQb+GJ8BlDoFTGZUUgC3zsR9uN8SKPKPLYIQ17h5U/uYjf6+AsQYZua33g12qhGdm5PQwLSfv9aCMN2Rjo3HIMH2rT3/1zSg2wd5uKR/jliChvW2SQpyDa8UBtSvaOV6LAtRGVnYAL8MtPmoJ96IJjkHqPIknsrcTlJtplq4U2+n1oPJMbNDzK3dhL7N4v90xk/WYfcVyQD3/d/+ONp8EGjqUclyaDxehKjSv5gzo9hp5zbfcsxbnXd83mZPl8I5SLngWRV9wMCTLX8JOA7R71pfwEaHHqq1Oawv/E/cUCgeUV+H74appO4yzbMvzBzti1Zd9+JE7BLZbB/SLGh5sBPTnePfRAyS+y3pIlfaPW6zX9/X0f1tKyPeAg5b/mTgRprumCieTeIUhKrqNVSEds3/tv/Sp2aKRo3wCnVsWzCPzSg8nKIL7de3+2nYOehp3t3+ztGj292ePtIx47NCXcg7VD75SlGjSYLCWRCGvt3dhDPy2G0ODQ==
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-OriginatorOrg: entrust.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-AuthSource: CH0PR11MB5739.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-Network-Message-Id: 70ec907d-d3d9-46bf-0f58-08da8075a6c8
X-MS-Exchange-CrossTenant-originalarrivaltime: 17 Aug 2022 17:26:42.3379 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: f46cf439-27ef-4acf-a800-15072bb7ddc1
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: PcqnIn3PY3F2XxVvTrfrPXwA8GEFSElwSGzcR0dceFvvyLQpxbEb2S1rWzWzUlA5MCTSoWQSbfbZQTkHPC4QI1gdg9EuhoyUdcm1EXL+F1E=
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR11MB4253
X-Proofpoint-ORIG-GUID: ahvklnajxopcLkKu8BjfMXW4zkBTP2Jm
X-Proofpoint-GUID: ahvklnajxopcLkKu8BjfMXW4zkBTP2Jm
X-Proofpoint-Virus-Version: vendor=baseguard engine=ICAP:2.0.205,Aquarius:18.0.883,Hydra:6.0.517,FMLib:17.11.122.1 definitions=2022-08-17_11,2022-08-16_02,2022-06-22_01
X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 impostorscore=0 lowpriorityscore=0 bulkscore=0 clxscore=1011 phishscore=0 mlxlogscore=760 adultscore=0 mlxscore=0 spamscore=0 priorityscore=1501 suspectscore=0 malwarescore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=8.12.0-2207270000 definitions=main-2208170065
Archived-At: <https://mailarchive.ietf.org/arch/msg/spasm/w6l1VbJ0rCVSl55XGJRr5yfP6Ys>
Subject: [lamps] 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 17:26:58 -0000

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.



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


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.






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?


---
Mike Ounsworth
Software Security Architect, Entrust

John Gray
Sr Prin Software Developer, Entrust
Any email and files/attachments transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If this message has been sent to you in error, you must not copy, distribute or disclose of the information it contains. Please notify Entrust immediately and delete the message from your system.