Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

Björn Haase <Bjoern.M.Haase@web.de> Fri, 09 April 2021 21:07 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 270F73A113E; Fri, 9 Apr 2021 14:07:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.517
X-Spam-Level:
X-Spam-Status: No, score=-0.517 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_MESSAGE=0.001, MIME_HTML_ONLY=0.1, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, RCVD_IN_SORBS_WEB=1.5, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no 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 YYz_2YFLOSxL; Fri, 9 Apr 2021 14:07:53 -0700 (PDT)
Received: from mout.web.de (mout.web.de [212.227.17.11]) (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 B90F03A113C; Fri, 9 Apr 2021 14:07:52 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=web.de; s=dbaedf251592; t=1618002470; bh=wF0Q3BAoxPEC+BQPws5dCWZDOcLC7p8wyF5BIAvjegA=; h=X-UI-Sender-Class:From:To:Cc:Subject:Date:In-Reply-To:References; b=PyxA71gyiyrJgBzOGhKH5I9hnBHvl9nibmvPrbTEqAZNNtHXag9+i/Ya4VDrNGhg8 9Rh1Hb6Q0E2tVbYsf70pbQEXZxeEmy1OlvOltpX/KPaTsA38WTefaGVa+gZf1McNgI 0LkG+XQsc1HCV3nNCX2FVYk55hL/2f+osnKRcFtA=
X-UI-Sender-Class: c548c8c5-30a9-4db5-a2e7-cb6cb037b8f9
Received: from [37.201.195.106] ([37.201.195.106]) by web-mail.web.de (3c-app-webde-bap03.server.lan [172.19.172.3]) (via HTTP); Fri, 9 Apr 2021 23:07:49 +0200
MIME-Version: 1.0
Message-ID: <trinity-f323065e-9f30-48fd-9ead-0865e8f877eb-1618002469856@3c-app-webde-bap03>
From: =?UTF-8?Q?Bj=C3=B6rn_Haase?= <Bjoern.M.Haase@web.de>
To: "Hao, Feng" <Feng.Hao=40warwick.ac.uk@dmarc.ietf.org>
Cc: CFRG <cfrg@irtf.org>
Content-Type: text/html; charset=UTF-8
Date: Fri, 9 Apr 2021 23:07:49 +0200
Importance: normal
Sensitivity: Normal
In-Reply-To: <VI1SPR01MB03573585C37B871D200ECC23D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
References: <e270e62d-941d-0a87-7dc9-cf80f73b5aeb@jacaranda.org> <d0778523-5f5d-4327-b795-279918c1899c@www.fastmail.com> <CAMr0u6=PBX1W5zQFmpxKQ=ViUXN9QK00BREL4M0=2HOkaXaiZw@mail.gmail.com> <VI1SPR01MB03573585C37B871D200ECC23D6739@VI1SPR01MB0357.eurprd01.prod.exchangelabs.com>
X-UI-Message-Type: mail
X-Priority: 3
X-Provags-ID: V03:K1:7jdap+5srVCx6H/kCQNUeXYIHmbXrX+5LtS5dfTBKqHujgdgvhTmOYdhQvWGP6TXYUQfT uej1jMMrWEqk2LO5pxbVWVAEqgbe/yHDuQY3VcmzrlRU2cArAIM7SbA3eCQA7D+wUjXkrHwh4moc HjJJnzBiOrFWP/0Ym5fYtrYZspOR/CDw/Xel+5B1ThDfHGdLnAgbo8wYDlhRTpat1+V4mJE/rQgD NHRBCAMtnKFISgD9ZrBpjLwbD669iGkAtt7Znp9PcfX1AvySg8y9U52afFklrXtMejaLgnB60QYv yk=
X-UI-Out-Filterresults: notjunk:1;V03:K0:o8YLLborY6A=:IcXNHy5SLlntN/p3wresTi RNe9AfskxytW2hHRNHmO5ZKyqzPH5zU/1KKx+e2RF/tyv3yNbCEgnLYJSQIHr4MFNhXopKJOF estOSn4qDk6549R5tawsQmUjoBun+grv0QFwuPf1AFWerlA/p8f385CXAU4ATWkbA7TJ+iXXQ D6f8LjQw+r/zhprs+0dvYNdfwKVWRs9lEECJJ+j6ry9HmCZr/G+xBOZwI4FMks6FD7VYb7PPr 8ifL6us0RBJ/r42t3/FtTySYNFIahh/XEOYtX2VyIW/PTMW6SEz/JGxHxYG8kFOqIMK7/xJwO I3xRFV9oWWrhNNKcNqmt1pcC+u2VrgrF+HB5AD0jEmKoC5QN4UlNXpNkDHAdtcTltNojvaHNG rFYvJxwEyqGLUfQvaroOiXt6tqAXyZdgJqqBnUw1prRW8j35XOGkFeDgACTYCgS5ae4vXzhT+ FetZDyYGqVCLewgnrexmMsu+OSBrx/Yz0fEc5E4ODg1BKIcfH33JFkw7JuQsl1BVzG7tmZL95 t8WDtLxoU497nqMTPvyEj8yGfmY3TfrboaIB3Fk5oGU3IXERNJXuGHhVJ02ax0Gy5plUHO47W lxEcSuS2Cel67H9heybQYtlguRe+f1bh8S1e/2ddr8K2ZDUEGF00+Q7o6KH0uJS38ddxhr0r6 o4ymiavWWYPi/EHIJyGSSlv1GgHhi43G2+3AWVkD2a2FHH07TYFJfndBXeqohtMHJE9OqeqJV OeVohtb41/1dOGjTN2bU/+gvjdCFxT9WqlsrfcybT81j1uh0oJPpA0tbfmpnbRP1+vH0kU1mI Er3kAeUaOWFJ6OtL2zukjELRQpqsc3J8ShltU/fptVGk066F1mNnOIyHuDXKfm9osgTwcKr/7 d6pKmxuuJktixTbx5Nflo5O5OWlGIWAIMxVyjDl/ZOj0FwVRlX76t5HM3KSUBdkoG2mfsZf4P HG1FHryzNmw==
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/ZF3FSC2l_rAxEnxKLbU6xJkw3Ug>
Subject: Re: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve
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: Fri, 09 Apr 2021 21:07:58 -0000

Dear Hao,
 
>In CPace and OPAQUE, both protocols use the output of hash-to-curve as a base generator.
>The implicit assumption is that the returned value from hash-to-curve must be a non-identity
>point in a subgroup of the large prime order. This doesn’t match what is actually provided by the current hash-to-curve ID.

>Has this issue been considered? Apologies if I missed any discussion on this before.

for CPace this has been considered in https://eprint.iacr.org/2021/114.pdf in the context of the proof for theorem 3.6 (and  correspondingly theorem 6.1, "Security of CPace with Map2Point") and become part of the (negligible) loss due to  the increased collision probability for the hash H_1.
 
So yes, for CPace this has been analyzed and quantified, and according to my assessment a corresponding approach will also apply for DH-OPRF-based constructions such as OPAQUE given that the map is "probabilistically invertible" according to the definition in https://eprint.iacr.org/2021/114.pdf  and that it is hard to find pre-images for the hash function used for the map-to-field operation (which is e.g. implied by modeling this as random oracle).
 
I don't identify the need of considering this aspect in the hash2curve level, but I agree that this should be covered by the security analysis of protocols that use the maps.
 
Yours,
 
Björn.
Gesendet: Freitag, 09. April 2021 um 15:44 Uhr
Von: "Hao, Feng" <Feng.Hao=40warwick.ac.uk@dmarc.ietf.org>
An: "CFRG" <cfrg@irtf.org>
Betreff: [CFRG] Small subgroup question for draft-irtf-cfrg-hash-to-curve

Hi all,

 

I just read through the latest version of the hash-to-curve ID (v10) and have a question.

 

The methods defined in the draft map field elements in F_p to points on elliptic curves. But the points include small subgroup (low-order) points. What if the mapped point on the curve falls into a small subgroup? The clearing-the-co-factor step (section 7) does no help at all here as it only turns the small subgroup point to an identity point.

 

The chance of falling into a small subgroup is extremely small, but for the completeness of the algorithm specification and the analysis, it’s still necessary to explicitly specify what to do in this case.

 

If the mapping function gives a small subgroup point, you cannot re-run the function to generate another point, as that will defeat the constant time principle. But obviously, a small subgroup point (or an identity point after the co-factor clearing) can’t be used safely for any protocol. It seems we have a failure mode which is “non-recoverable”.

 

In CPace and OPAQUE, both protocols use the output of hash-to-curve as a base generator. The implicit assumption is that the returned value from hash-to-curve must be a non-identity point in a subgroup of the large prime order. This doesn’t match what is actually provided by the current hash-to-curve ID.

 

Has this issue been considered? Apologies if I missed any discussion on this before.

 

Cheers,

Feng

 

_______________________________________________ CFRG mailing list CFRG@irtf.org https://www.irtf.org/mailman/listinfo/cfrg" target="_blank" rel="nofollow">https://www.irtf.org/mailman/listinfo/cfrg