### [Cfrg] [CFRG] [hash2curve-05] Suggestions regarding modifications of the "external API"

Björn Haase <bjoern.m.haase@web.de> Thu, 02 January 2020 14:36 UTC

Return-Path: <bjoern.m.haase@web.de>

X-Original-To: cfrg@ietfa.amsl.com

Delivered-To: cfrg@ietfa.amsl.com

Received: from localhost (localhost [127.0.0.1])
by ietfa.amsl.com (Postfix) with ESMTP id 00538120018
for <cfrg@ietfa.amsl.com>; Thu, 2 Jan 2020 06:36:42 -0800 (PST)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -2.697

X-Spam-Level:

X-Spam-Status: No, score=-2.697 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_LOW=-0.7,
RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001,
SPF_PASS=-0.001] autolearn=ham autolearn_force=no

Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key)
header.d=web.de

Received: from mail.ietf.org ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id BACWuaXTZDZ7 for <cfrg@ietfa.amsl.com>;
Thu, 2 Jan 2020 06:36:39 -0800 (PST)

Received: from mout.web.de (mout.web.de [212.227.17.12])
(using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits))
(No client certificate requested)
by ietfa.amsl.com (Postfix) with ESMTPS id 4805912004F
for <cfrg@irtf.org>; Thu, 2 Jan 2020 06:36:38 -0800 (PST)

DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de;
s=dbaedf251592; t=1577975795;
bh=+g33LUGAFp0gPli3pKhIFOCR5zfYbW+UTKByOAbg4kE=;
h=X-UI-Sender-Class:Subject:From:To:References:Date:In-Reply-To;
b=EISHA/gpkvvfZP0Hghk/UeM+nxqBLB9PHPOIWyGZG2CtpwxFB24ITjIdUYKcX1kKc
3QIZqYc7CBpGDX0/Hc+ojcJLjqqh1XOQuktXrRkjDGrLb36vwz1JYYDM7bkG4851Od
ckVaK8cmO2ihiG9Jcq37ErafSkFVPrx6JJBmKCbg=

X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9

Received: from [192.168.2.161] ([188.110.251.139]) by smtp.web.de (mrweb102
[213.165.67.124]) with ESMTPSA (Nemesis) id 0MhDkj-1j8f2J34QD-00MHc7 for
<cfrg@irtf.org>; Thu, 02 Jan 2020 15:36:35 +0100

From: =?UTF-8?Q?Bj=c3=b6rn_Haase?= <bjoern.m.haase@web.de>

To: cfrg <cfrg@irtf.org>

References: <F3F5E4C7-1C0D-420F-8F6A-83A624602250@ieee.org>
<22347eb8-da6d-06ef-20ef-6e8d93a6417e@web.de>

Message-ID: <ee74c9f2-bd6a-9115-5ccc-2bf3b866bd1c@web.de>

Date: Thu, 2 Jan 2020 15:36:23 +0100

User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101
Thunderbird/60.9.1

MIME-Version: 1.0

In-Reply-To: <22347eb8-da6d-06ef-20ef-6e8d93a6417e@web.de>

Content-Type: text/plain; charset=utf-8; format=flowed

Content-Transfer-Encoding: quoted-printable

X-Provags-ID: V03:K1:fkJMfMYeXQMQuFjauhI3S6El+mkly6/dHR81YjM3HtjJfzJkL+8
K+btWkGpiZmP+wWx2zxevbZbpxmyRL+GzTi/k5beF9IHBqwCazhNc1p5qZrqMKBST4OEP+6
gvC3accjcrSg7dDodRPrQ2nPljW2OkhRh/STpAZLGKzQoDQIzXMkEg2A7R0wmXarjveMk9b
oDfVL9noRudEdnST7MxBA==

X-UI-Out-Filterresults: notjunk:1;V03:K0:Or7ric9bCHI=:Zu64fcfzSYf98TRDIwCktd
Pcv6J71N0uv2E2Tce8Mpkf/OtvbE9ezMIUpMquBXDHIVKjTCdaaZJXBTamQYhMOuVdJWC05kb
3Y5plUywHkA70o1CjyGLhMp/khPyQUW9WD3K59cdzS16q2OjOAP2P83FMQEcqb1Q/JpxcIgi8
vtcY1+BwBDgslfG4C7HaPtwoLKvBgk2dNQUeruc4gSTKx+cvVIPHbWicsR0u7WRSevONcH6yd
+33Sf3RihkCfQDuzELLtrNCrrhvUuPHOP6IVu51A9nTyYmS/NNhlbDnfCSODzUNC2ahR0IwD5
rR4jSzPAlfxWrH0o3jIg91qxK9HsxLOLyP/IdhnoRQjmHoHbV6HDy4EVEN8MfItWQSKlglzvD
uGPXTIMmN8/R+9kWy9WP/lGqziuLHMezCCjQwg6oauW4BY0NveOGuQgOmRqT8gOOgX3rlY56K
jjWe1VZa1PHLR9zM3hh5wU/0tppRzqhnODfl5NnTWn/eq7brqkABeYKRcNVr23Lhziy57WAap
sbWn8QSTlbpmB2ZnCj3ZPboQhhcS9bVuwQnY3DLIEKgbsbp9lrNo00tN2RTiPHDIEoqG4TfOf
CBAp+DC1DMRVuWhSPFve+EK0C6I815cuhAyVFAj1UFtEqPNyGOIVaICCDrN9Y5ZnauLZv4gx2
3svP5eFV61tIZNu+2DGGbArUOYV48DsdOiWwCFbIeolPkh/81JG2wZxngXLddlUbyx/N8P1zZ
YZeS+eJoJe9fEdWjBDNhKxxdlnCg4wi3BYUluMAXFbnF9/jWx/yAnrzVRO3b0jA4eDAla5AzQ
XUN/JvG+CP1wsevrJlBpLeaqYe3S3U3aowZQ6iOGZpaFGS5Ej3mmoSPtQGfCulgUja64GN4S/
I6tKaMirduJ0t7fIptlKWMn4KXcwFXvAEZ3PRgjlDshxK8/+3fUkicwyI/DuFpjQHO93OfygD
WtiInvlaHCk9SNVoBMR0k5PUKasgly4pM6PCNEUT1FXphw6EixX0Vgt08IUdajQCb0Rwd9aAD
1A80jEqGuj83ZxSIv33ykpCKaMffkuOVskc83ZFcYx5RoKE3NOdo13eIHBwamYgHglJKKbk36
nnlIDIkGXKAqytMwkHuShPlvDlYmLiMq754pJFtBxCZuuYetRVKuFd3076O7uYT63HdFYe94T
W6bm9DSGAp9rSQwNxu5LWFhaFzEJIbrmVCS7uO83WbrHmBJ9BRdlbwSxrSeshGF1nPgVrG07z
jDNEBnlmjTcBSc5QGKkqgUxyK4tmjLKU/uT9xWSuYF3pj4vzD6vXelI/dXsM=

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/taczBPmjF4YxJKgEATOf4vkJEyY>

Subject: [Cfrg] [CFRG] [hash2curve-05] Suggestions regarding modifications
of the "external API"

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.29

Precedence: list

List-Id: Crypto Forum Research Group <cfrg.irtf.org>

List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>,
<mailto:cfrg-request@irtf.org?subject=unsubscribe>

List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>

List-Post: <mailto:cfrg@irtf.org>

List-Help: <mailto:cfrg-request@irtf.org?subject=help>

List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>,
<mailto:cfrg-request@irtf.org?subject=subscribe>

X-List-Received-Date: Thu, 02 Jan 2020 14:36:42 -0000

Hello hash2curve team, I am currently reviewing the current draft-irtf-cfrg-hash-to-curve-05 in the context of a "user" of the operations that you specify. After trying to re-use the definitions as-is for the CPace and AuCPace RFC that I am currently writing, I would like to come up with two suggestions. As a first general remark, I would like to give the feedback that it is written very clearly (IMO). Also I am now convinced that the patent pitfalls are avoided also for SSWU! Suggestions: 1.) Don't make the co-factor clearing mandatory for encode_to_curve I noticed some diffculty coming with the currently specified API for non-prime-order curves such as Curve25519 or Ed448. Currently, two different "public APIs" are suggested, one for returing a point in the (secure) cryptographic subgroup of the curve (encode_to_curve) and one for true hashing onto the curve involving one additional point additions (hash2curve). As a final step both currently mandatorily involve co-factor clearing. While I agree that co-factor-clearing is mandatory in most applications, specifying this as mandatory on the encode_to_curve level makes problems for me. Note that protocols designed for non-prime-order curves, such as X25519 already include co-factor clearing themselves by the "scalar clamping" operation that precedes any scalar multiplication. The problem with co-factor clearing is that unlike for Elligator 2 the co-factor clearing algorithm returns the result in projective coordinates. Consider the case of a point generated by encode_to_point as a secret generator used in CPace for Diffie-Hellman using X25519 on Curve25519. One of the most efficient X25519 Diffie-Hellman implementations that use a x-coordinate-only Montgomery ladder requires an *affine* base-point as input. The alternative addition formulas that take a projective point as an input require ~256 additional field multiplications in comparison with an algorithm taking an *affine* base point input. Using a projective input point is, thus, more costly than using an inversion (~256 field squarings) and an affine base point. In order to input the output of encode_to_curve() for CPace as it is defined currently, you need a superflous field inversion to be run on the output of the co-factor-clearing algorithm, accounting for an computational overhead of roughly 20%. Elligator2 -> Result in affine coordinates Co-Factor-CLearing -> Result in projective coordinates Inversion -> Conversion to affine coordinates X25519-> Scalarmultiplication which itself clears the co-factor a second time In order to circumvent this problem for the CPace definition, I will not refer to encode_to_curve but only use the hash_to_base and map_to_curve definitions. I would like to suggest to remove the clear_cofactor step from encode to point. encode_to_curve(alpha) Input: alpha, an arbitrary-length bit string. Output: P, a point in G. Steps: 1. u = hash_to_base(alpha, 2) 2. Q = map_to_curve(u) // remove 3. P = clear_cofactor(Q) // remove 4. return P 3. return Q This also would simplify the hash_to_curve definition by refering to encode_to_curve. hash_to_curve(alpha) Input: alpha, an arbitrary-length bit string. Output: P, a point in G. Steps: 1. Q0 = encode_to_curve(alpha, 0) 2. Q1 = encode_to_curve(alpha, 1) 3. R = Q0 + Q1 // Point addition 4. P = clear_cofactor(R) 5. return P 2.) Use SHA512 as "natural" choice for the hash function for Curve25519 Usually, a hash function and elliptic curve are used in conjunction with the same "security bit level". E.g. for P-256 one would usually use SHA-256 and for Brainpool-512, SHA-512. Both, signature algorithm and Diffie-Hellman operations will likely use the "128-bit security" hash. However, in the case of Curve25519, in my opinion the "natural" choice would be SHA-512, because the default signature algorithm Ed25519, will not use SHA-256 but rather SHA-512. Note that SHA-512 is not significantly more expensive than SHA-256 on constrained small targets according to my implementation study on an ARM Cortex M0. Assume a constrained device that uses Ed25519 as efficient algorithm for verifying firmware signatures and another protocol that uses mappings. In this case, the designer would rather like to use SHA-512. I would therefore like to suggest to add a cipher suite for encode_to_point for Curve25519 based on SHA-512. This will also allow for a more efficient version of hash_to_base for the case of Curve25519, since we dont mandatorily need the "HKDF-extract"/"HKDF-expand" sequence. Here one could just use the sufficiently long result of a single SHA-512 (H) invokation, interpret the 512 bit result as un-reduced fe25519 field element and reduce the output to 255 bits in order to remove any statistical bias. Thus, my suggestion for map_to_base would be to use HDKF-extract/HKDF-expand only when the hash output is not sufficiently long for the required output of the current HKDF-expand operation. In case that the base-line hash function H output is already sufficiently long, I'd recommend to use it's hash output as-is. (Note that, while typically using HKDF should not be considered of negligible cost in comparison to a single hash function invokation, there might be applications where this is not the case. E.g. for the mapping used in CPace I have suggested in the submitted documents to CFRG for PAKE to use a masked side-channel-protected implementation based on SHA-3 if SPA/Faults become relevant. When considering masking for DPA protection, the hash operation could rapidly turn out to be a *very* complex part, specifically, when considering ARX-constructions such as SHA-256. Such masking operation might actually be particularly important on smallest/constrained devices that are often more exposed to invasive side-channel attacks than typical desktops/laptops.) Yours, Björn.

- [Cfrg] PAKE review Bjoern Tackmann
- Re: [Cfrg] PAKE review Hugo Krawczyk
- Re: [Cfrg] PAKE review Hao, Feng
- Re: [Cfrg] PAKE review // CPace without the sessi… Björn Haase
- Re: [Cfrg] PAKE review Bjoern Tackmann
- [Cfrg] [CFRG] [hash2curve-05] Suggestions regardi… Björn Haase