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