Re: [Cfrg] Comments regarding draft-sullivan-cfrg-hash-to-curve

"Jason Resch" <jresch@us.ibm.com> Thu, 05 April 2018 03:56 UTC

Return-Path: <jresch@us.ibm.com>
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 048B212783A for <cfrg@ietfa.amsl.com>; Wed, 4 Apr 2018 20:56:43 -0700 (PDT)
X-Quarantine-ID: <AnoIuE2EiAMA>
X-Virus-Scanned: amavisd-new at amsl.com
X-Amavis-Alert: BANNED, message contains application/octet-stream,.exe,hash-to-point.py
X-Spam-Flag: NO
X-Spam-Score: 0.49
X-Spam-Level:
X-Spam-Status: No, score=0.49 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, HTML_MIME_NO_HTML_TAG=0.377, HTTPS_HTTP_MISMATCH=1.989, MIME_HTML_ONLY=0.723, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
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 AnoIuE2EiAMA for <cfrg@ietfa.amsl.com>; Wed, 4 Apr 2018 20:56:40 -0700 (PDT)
Received: from mx0a-001b2d01.pphosted.com (mx0b-001b2d01.pphosted.com [148.163.158.5]) (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 7EC3A127369 for <cfrg@irtf.org>; Wed, 4 Apr 2018 20:56:40 -0700 (PDT)
Received: from pps.filterd (m0098413.ppops.net [127.0.0.1]) by mx0b-001b2d01.pphosted.com (8.16.0.22/8.16.0.22) with SMTP id w353u7MH124393 for <cfrg@irtf.org>; Wed, 4 Apr 2018 23:56:39 -0400
Received: from smtp.notes.na.collabserv.com (smtp.notes.na.collabserv.com [192.155.248.67]) by mx0b-001b2d01.pphosted.com with ESMTP id 2h5c598946-1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NOT) for <cfrg@irtf.org>; Wed, 04 Apr 2018 23:56:38 -0400
Received: from localhost by smtp.notes.na.collabserv.com with smtp.notes.na.collabserv.com ESMTP for <cfrg@irtf.org> from <jresch@us.ibm.com>; Thu, 5 Apr 2018 03:56:38 -0000
Received: from us1a3-smtp04.a3.dal06.isc4sb.com (10.106.154.237) by smtp.notes.na.collabserv.com (10.106.227.16) with smtp.notes.na.collabserv.com ESMTP; Thu, 5 Apr 2018 03:56:36 -0000
Received: from us1a3-mail153.a3.dal06.isc4sb.com ([10.146.38.112]) by us1a3-smtp04.a3.dal06.isc4sb.com with ESMTP id 2018040503563513-10646 ; Thu, 5 Apr 2018 03:56:35 +0000
In-Reply-To: <CAO8oSXnxS4Ea89A3Yq46sPk2f8iYqiEsFwNALqAfb+2951NBsA@mail.gmail.com>
From: Jason Resch <jresch@us.ibm.com>
To: christopherwood07@gmail.com
Cc: cfrg@irtf.org
Date: Thu, 05 Apr 2018 03:56:35 +0000
Sensitivity:
MIME-Version: 1.0
References: <CAO8oSXnxS4Ea89A3Yq46sPk2f8iYqiEsFwNALqAfb+2951NBsA@mail.gmail.com>, <OF6FFC9F11.340C9F5B-ON00258255.0080017E-00258256.0002E0C9@notes.na.collabserv.com>
Importance: Normal
X-Priority: 3 (Normal)
X-Mailer: IBM Verse Build 16007-1287 | IBM Domino Build SCN1805107_20180220T0755_FP3 March 05, 2018 at 16:31
X-KeepSent: 44B5AF4A:050FAD4B-00258266:00157BE4; type=4; name=$KeepSent
X-LLNOutbound: False
X-Disclaimed: 36947
X-TNEFEvaluated: 1
Content-Type: multipart/mixed; boundary="=_mixed 0015A8F100258266_="
x-cbid: 18040503-0327-0000-0000-000004FD2D25
X-IBM-SpamModules-Scores: BY=0; FL=0; FP=0; FZ=0; HX=0; KW=0; PH=0; SC=0.384396; ST=0; TS=0; UL=0; ISC=; MB=0.189716
X-IBM-SpamModules-Versions: BY=3.00008804; HX=3.00000241; KW=3.00000007; PH=3.00000004; SC=3.00000256; SDB=6.01013286; UDB=6.00516487; IPR=6.00792549; BA=6.00005896; NDR=6.00000001; ZLA=6.00000005; ZF=6.00000009; ZB=6.00000000; ZP=6.00000000; ZH=6.00000000; ZU=6.00000002; MB=3.00020422; XFM=3.00000015; UTC=2018-04-05 03:56:37
X-IBM-AV-DETECTION: SAVI=unsuspicious REMOTE=unsuspicious XFE=unused
X-IBM-AV-VERSION: SAVI=2018-04-05 00:09:15 - 6.00008291
x-cbparentid: 18040503-0328-0000-0000-00003E794F68
Message-Id: <OF44B5AF4A.050FAD4B-ON00258266.00157BE4-00258266.0015A920@notes.na.collabserv.com>
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:, , definitions=2018-04-05_01:, , signatures=0
X-Proofpoint-Spam-Reason: safe
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/wNUIbj-dBhe-zH3eis37cEWRQsc>
Subject: Re: [Cfrg] Comments regarding draft-sullivan-cfrg-hash-to-curve
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
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, 05 Apr 2018 03:56:43 -0000

Christopher,

Thank you for your responses. I am glad that my feedback was helpful.

I recently wrote some reference implementations of my suggestion below for implementing HashToBase() for any given input string and curve.  It uses the left-most bits of HKDF applied to the input, where the number of total bits selected is determined by the size of the prime field.  I have ensured consistency via some test vectors I defined and are included in this sample code.  I tested both NIST P-256, and NIST P-521. Note that these examples only implement "Simplified SWU", but this can be easily extended to support the other algorithms.

I have attached a Python3 implementation to this e-mail, I also have a Java implementation I can send if it would be of value. Both produce consistent results as far as I have been able to test.

Also, I found something interesting in regards to supporting Koblitz curves, or other curves where a = 0 (such as BN-254).  By accident, I discovered that it didn't seem to matter whether I used "(-b / a)" or any other number.  The Simplified SWU algorithm appeared to always map to a valid point.  Does this make sense?  Is there a special motivation for using (-b / a) as opposed to some other constant?
 
Best,
 
Jason
 
----- Original message -----
From: Christopher Wood <christopherwood07@gmail.com>
To: jresch@us.ibm.com
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] Comments regarding draft-sullivan-cfrg-hash-to-curve
Date: Mon, Mar 26, 2018 8:46 AM
 
Hi Jason,
 
Thanks for the review and feedback. Please see inline below for comments.
 
On Mon, Mar 19, 2018 at 5:35 PM Jason Resch <jresch@us.ibm.com> wrote:
Comment 1: Algorithm Recommendations Table

Is there any reason not to include recommendations be made for other common curves, such as NIST P-521, Curve1174, or Koblitz curves such as secp256k1?
 
No. We didn't have an immediate use for them. That said, we should be inclusive to all curves and provide appropriate recommendations. I filed: 
 
 

Comment 2: Icart vs. SWU Simplified

Both of these are listed as having performance of "O(log^3 q)". Given this, is there a significant advantage to using Icart for P-384?  Implementation simplicity might motivate using SWU Simplified for all curves, for example, as opposed to special casing NIST P-384.
 
That may well be the case. We are still working on the analysis and cost comparison. I suspect we will prune the list of algorithms specified (in the main body) in the future. If and when that happens, we may move all other algorithms to the appendix.
 

Comment 3: Algorithm description of SWU Simplified

I did not understand this line:

"5. Output (-g * alpha) * (g * beta)"

- g was not defined here, except above as a function of x, but here it is being used in a multiplication.
- g might be confused with the generator point for the curve
- The output should be in the form of a point with coordinates x and y, should it not?
 
This is a bug in that description. I'll clean this up in the next revision.
 

Steps "19" and "20" use "//" presumably to denote division, but "//" is also used later to represent comments.  Is there any difference here between "//" and "/"?
Would it be clearer to represent these divisions as multiplications of the multiplicative inverse computed over p?
 
Good point. There is no difference as written. I will clarify this notation.
 

Step "21" indicates an equality comparison.  Unless implemented specially, these could lead to side-channel attacks as an equality check of equal values takes longer than one where the values are unequal. It might be more secure to separately compute both comparisons, i.e. also compute "e_2 = (y2 ^ 2 == h3)" as a mitigation strategy or alternative to implementing constant time equality checks, which might not be readily available in different BigInteger libraries/languages.
 
Another good point. I will make sure these are written to be constant-time comparisons. 
 

Comment 4: Definition of HashToBase

An example is given that this can be any cryptographic hash function, such as SHA-256.  However, I think it would be better if this is defined as a method supporting variable length outputs.  For example, HKDF (Hmac Key Derivation Function).  The justification being that some elliptic curves operate on fields that are too large, even for SHA-512 (e.g. NIST P-521), and naive attempts at extending the length of a hash may otherwise be designed insecurely.
 
This does in fact seem better. I'll see if we can integrate it. 
 

If the function is specified as HKDF (which operates on bytes rather than bits) there should be clarification as to which bits of the output are to be used (e.g. the left-most bits output by HKDF).

There should be some security recommendation as well, in terms of selecting hash functions with security properties appropriately matched for the security of the curve.
 
Agreed. We will add this missing information.
 

Comment 5: Clarification for supported curves

The draft indicates that Simplified SWU works for all curves where: p == 3 % 4

However, the Koblitz curve secp256k1 has a p such that p == 3 % 4, yet it does not seem to work with Simplified SWU. The problem is that it's "a" coefficient is defined as zero. Thus it isn't possible to compute (-b / a) which is required and used in the Simplified SWU method.  Is there a means around this?
 
Thanks for pointing this out. I'm not sure off hand and will investigate more.
 
Thanks again for your very thorough feedback. I will circle back with you when the next revision is made. 
 
Best,
Chris