Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friendly-curves-07
Michael Scott <mike.scott@miracl.com> Mon, 13 July 2020 09:18 UTC
Return-Path: <mike.scott@miracl.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 EEA343A0C8E for <cfrg@ietfa.amsl.com>; Mon, 13 Jul 2020 02:18:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.198
X-Spam-Level:
X-Spam-Status: No, score=-0.198 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, HTML_MESSAGE=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=miracl.com
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 s2sKNTpvLkXJ for <cfrg@ietfa.amsl.com>; Mon, 13 Jul 2020 02:18:22 -0700 (PDT)
Received: from mail-il1-x133.google.com (mail-il1-x133.google.com [IPv6:2607:f8b0:4864:20::133]) (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 0E8123A0C8B for <cfrg@irtf.org>; Mon, 13 Jul 2020 02:18:21 -0700 (PDT)
Received: by mail-il1-x133.google.com with SMTP id q3so10535270ilt.8 for <cfrg@irtf.org>; Mon, 13 Jul 2020 02:18:21 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=miracl.com; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=pLYAFKtNXRL8f5VMFJfDujwfUWSSI9l4gKq2ze42Qus=; b=KSTGVAebnfsbr+V59yly5lxbRae1213V0Tzme8qs5P5C5A6CICt8MT/ycJn3UwMmhz gCADCerQ9FpLkbhSZcMrKHL9LQ4J9z7q64eNNRSJv7DMh143saoamqvRvjxVS/pzsWPY c1jTz6n9iVYKeWWPAeplAdM/+bcAqPVm/PWKCGZLtodKt47cx6D+6lqDKoDJqxEXsrnY aytAm/8Hu/FEzeQaQyvS8sPH7g7TMVo/IVuTbqhP0/bwhpRYoQEKXaK7dtIWNQPrmeQ5 a80qkDDk1oVn8KZd052Cao3E0F1O0+MnTIDYZbgj4CpvjtLZqdsypVvNlA7CTbq7R/ld qbwg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=pLYAFKtNXRL8f5VMFJfDujwfUWSSI9l4gKq2ze42Qus=; b=emEfUrvq+jOQEVycKAUCjCGaArRhMWgL+/HstKJDztnNxmpmGazsETRjFY0U+sk2ed fYsT2gy4QmDho+2wU6/SRWa4ly9/LCAFUWoTDKURy/YH992dr1eiWVYUffU/5s1vKbXv dMfEV2MH1DajpEkzbpe/lf03UAWFDb+zGoyXuu1I5dw9luLy6mso/NPhFoagpP1jWdyq gGdnjP/NaFv9vPgAT++ZST6t/n2pbj/hKx0FU0G+uBulHnEbIjmKM2DB00hfMswF+ijU n0bQK+dNZcKlvfMRExgLat3b5HEt5ZDtk2fELqTXhgbK6mDWzXG65eQbOj9fIBoL/fpi gWeQ==
X-Gm-Message-State: AOAM530fu2168bdCYN2DnmDDrak2TkJaNMilmCgQaJeHlXxLe/ilL/mG wJH/ffYehuCfs9pvEkpH5Q1jRxEVKUKdt/ZLTIMUZTIWHZs=
X-Google-Smtp-Source: ABdhPJzhasqEbL+feOgiuwX5dHTgaUHpX0UdL3KZ9ZKd8+c2DojtlfWzSNyHgPwULcXMFoWS17x5JugYqTcoLgs0RNs=
X-Received: by 2002:a92:4101:: with SMTP id o1mr53243995ila.53.1594631900621; Mon, 13 Jul 2020 02:18:20 -0700 (PDT)
MIME-Version: 1.0
References: <CAMr0u6keYJZpKVTFr_2y_ZJn37acrPUy7TyMRGoNG5R2kYtoXA@mail.gmail.com> <9093e0a5-3e33-497f-1bea-aa495f992943@gmail.com>
In-Reply-To: <9093e0a5-3e33-497f-1bea-aa495f992943@gmail.com>
From: Michael Scott <mike.scott@miracl.com>
Date: Mon, 13 Jul 2020 10:20:07 +0100
Message-ID: <CAEseHRqV2Pxeev=XuZ649QL4h31kpnt7SenjH0XDbVOLKUS2Zw@mail.gmail.com>
To: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000fc066305aa4f2bf5"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/85sky0WU2du_0H2MmrcNcZpoH3c>
Subject: Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friendly-curves-07
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: Mon, 13 Jul 2020 09:18:25 -0000
Perhaps some of the reassurance sought on the difficulty of the DLP as it arises in the context of pairing-based cryptography might be found in the very last paragraph of [BD18] https://eprint.iacr.org/2017/334.pdf Appendix B "Practical improvements will continue to come but they will modify only the o(1) term. A hypothetical algorithm which would beat SexTNFS needs to produce relations faster than by enumerating all elements of a sieving space, as it happened in small characteristic with pinpointing, or it would have to completely abandon the NFS diagram. Such an algorithm would be a great discontinuity, comparable to a possible sub-exponential algorithm for DLP on elliptic curves. " Mike On Mon, Jul 13, 2020 at 12:08 AM Rene Struik <rstruik.ext@gmail.com> wrote: > Dear colleagues: > > Please find below my review of the pairing draft. If this does not display > well, please send me an offline note and I can send you the original text > file (before cut-and-paste into this email). > > I hope this helps. > > Review of draft-irtf-cfrg-pairing-friendly-curves-07 > Reviewer: Rene Struik > Assessment: not ready > > Summary: > The draft provides domain parameters for a few curves used with > pairing-based cryptography and provides some test vectors. > > General remarks: > a) While the draft suggests multiple times that the exTNFS attack (2016) > negatively impacted the bit-security level of various proposed domain > parameter sets for pairing-based curves, it does not provide any detail on > this attack itself, nor any reassurances that potential extensions of these > (only 4-yr old!) attacks on the general discrete logarithm problem of > composite degree extension fields GF(p^t) for small composite t>1 would not > be in the cards. This diminishes trust in the claimed security of these > curves and their "fitness for use" in practice. the only use of these > attacks is simply providing lengthy tables with claimed revised security > levels. Why should one have confidence in this, do advances in solving the > DLP in small degree extension fields provide the kiss of death for pairings > (or if not: why not?), etc? > b) The draft has 6 1/2 pages of references and 3 1/2 pages of tables of > "adopted parameters" on a total of 27 pages of main body text. It seems one > should be able to considerably prune both tables and references (which now > come across as unwieldy). A good starting point may be to consider that > availability of a library or standardization does not necessarily imply > that schemes are actually deployed. > c) It is unclear what motivated change in co-authorship of this draft, > e.g., when considering changes between rev04 and rev07 of this draft. It > seems more customary to credit minor contributions in the acknowledgement > section than by change of authorship. > d) Lots of specification details seems adhoc and even motivated by a > particular company's conventions. For CFRG, it may be more appopriate to > specify curves, finite fields, and objects that live herein, in a more > systematic way, rather than reinventing the wheel, thereby fostering reuse > and maintainability. > e) I am curious why this draft's intended status is "experimental" (vs. > "informational", as is far more common for IRTF documents). > > Detailed comments: > 1) Section 1.2 (and also elsewhere) seems to conflate standardization of > parameters, availability of libraries, and actual deployment, where there > is an unusual prominence (for an IRTF document) of company names. Wouldn't > it make more sense to describe potential applications of pairing based > cryptography in more technical terms, e.g., in terms of facilitating > aggregate signatures, remote attestation, etc., and provide a brief > description (and a technical reference)? > 2) Section 1.3: the main point of the extTNFS attack is that it tries and > solve the DLP in low-degree extension field GF(p^t) for small composite t>1 > faster. To bring this point accross, I suggest changing reference to "by > the attack" (l. 5 of Section 1.3) by something more closely reflecting this. > 3) Section 2.3, 4th para (top of p. 8): elaborate on the "BN curves always > have order 6 twists" remark (this seemed to have been copied ad verbatim > from the [BD18] paper). > 4) Section 2.4, 4th para: it would be good to mention that parameter t > must be 1 (mod 3), since otherwise p is not an integer. > 5) Section 2.5: the representation conventions are highly confusing, esp. > for extension fields. Why not define everything in terms of a prime field > GF(p) and extension field GF(p^t), with fixed irreducible polynomial f(z) > of degree t over GF(p)? This has been successfully used with elliptic curve > specifications (NIST, ISO, ANSI, BSI) not tailored to pairing based crypto. > This would also avoids questions that now immediately come up (such as > whether defining GF(p^{d'}) in terms of GF(p^{d}) and "inductively applying > the above convention" does yield an unambigous definition. Since all finite > fields of fixed size are isomorphic, it would be much easier to stick to > the standard way of doing this. This would also avoid messy tower of > extension field arguments and messy representations of elements hereof > (e.g., in Section 4.4). See also Appendix J on data conversions of the lwig > draft referenced in this draft. As final note, the data conversions in > that lwig draft require specifying bit/octet encodings (which, in the > pairing case, seem to be most-significant-byte-first (MSB) and > most-significant-bit-first (msb). > 6) Section 3.1, 4th para: it is unclear what the meaning of "best known" > is: is this "best-known" (i.e., most well-known) or "simply the best"? > Given the description, the first meaning should be the correct one... > 7) Section 3.2: what is missing is a section that actually describes the > attack, rather than simply plugging in some implied numbers based on a > paper (presumably [BD18]). Why not add some verbiage that explains this in > simple but roughly accurate terms ("The exTNFS Attack", or, better, > "Attacks on DLP over Low-Degree Extension Fields", or even better, "Solving > the DLP in Finite Fields" (there has been lots of progress there for > mid-size base fields too)). This is a CFRG document, so one would expect > something that provides insight, rather than simply a bombardment of > tables, some selection criteria, and a filtered list. Wouldn't the > objective of this whole effort be to educate the CFRG audience on > pairing-based crypto, rather than (say, obtaining an RFC number from an SDO > and marketing this as an implied "authoritative" approval stamp)? > 8) Section 3.2: I remember that Francisco Rodriguez-Henriquez (fix name in > references) presented attacks at the CHES 2013 rump sessions, where > question was whether this spelled trouble for pairing-based crypto. While I > do not have his presentation then on file, it may be good to dig this up or > ask him, and contemplate on wider implications of DLP progress in general > (see also first general review remark). > 9) Section 3.2, 2nd para: A natural question is what one could say about > DLP complexity for GF(p^k), in terms of dependency on p and k. > Unfortunately, this section does not provide any insight on this (it only > provides a single numerical value for BLS48 curves, without any context). I > would suspect the reader audience would appreciate such insight, without > need to wed through a whole forest (6 1/2 pages: far too much reference > stuffing!) of references by himself without any guidance as to whether this > would be time well-spent or lost. > 10) Section 4: as stated before, the selection criteria seem somewhat > arbitrary, since conflate specification text, libraries, with actual > deployment. Moreover, the most important criteria should probably be > security and speed given particular security strength, and potential > support for finite field arithmetic on platforms (speaking of which: why > not devote a section on whether one can actually implement GF(p^k) securely > using finite field libraries, including modular reductions, side channels, > etc.?). The term "adoption status" seems, in any event, misleading. > 11) Section 4.1, Table on pp. 12-15: if one strikes out domain parms > rendered immediately suspect by the exTNFS paper on DLP, this kills off 8 > out of 10 entries on p. 12 (and far more if one stikes out suspect values > accross the entire table). This makes me wonder what the technical reason > is for including this entire table. To the casual reader it now suggests > that there are huge numbers of implementations out there, whereas - perhaps > - most of those should be switched off immediately... > 12) Section 4.1.2: once again, I am wondering why there is so much > emphasis on libraries here. Isn't this an IRTF/CFRG document? > 13) Section 4.2.1: The extension field GF(p^{12}) can also be described > via GF(p) and degree-12 polynomial f(w):=(w^6-1)^2+1. This would allow > using simple conventions used in Lidl et al's finite field book [2]. It > also allows description of an element x of GF(p^{12}) as vector (x_{11}, > ..., x_1, x_0) of coefficients of GF(p) with this irreducible polynomial. > Note here that u+1:=w^6 and v:=w^2, so one can easily internally use the > more complex tower field stuff in the draft, while sticking to simple and > easy to maintain standard constructions (known for 2 centuries) for > specifications (so, nobody looses out if one has a slim interface that does > this conversion back and forth, if necessary). > 14) Section 4.2.1, bottom of p. 18: shouldn't the cofactor h be such that > h*r= # E'(GF(p^2))? {please also fix Et and use E' notation as elsewhere in > the draft} > 15) Section 4.2.1, parameter b' (bottom of p. 19): if one uses the > complicated tower construction, why then not also mention the value of u in > the enumeration? Is one actually sure this value is uniquely defined (e.g., > I did not check but wondered what would happen if one replaces u by -u in > the tower construction)? Same with end of Section 4.2.2... > 16) Section 4.2.2, 5th para: the statement "CP8_544 is more efficient" is > hard to interpret without context (e.g., half the cost, cost-1, cost - > o(log log log n)). > 17) Section 4.2.2, bottom of p. 20: with parms BN462, why not simply > introduce base point G, parameter n, h, etc., once and for all in Section > 2.1, without trying to repeat their definition in Section 4.2.2 (and later > sections)? > 18) Section 4.2.2, top of p. 21: the formula for h seems incorrect (G2 is > defined over GF(p^2), whereas the formula refers to a curve defined over > GF(p^8). > 19) The security consideration section (Section 5) is rather slim: > (speculation on my side) is the reason to label this draft as > "experimental" that design strength vs. actual strength is somewhat in > limbo due to progress on DLP problem? Why suddenly squeeze in a point > validation routine if no context is given at all of where and how pairing > based crypto is used? Wit point validation, what if an octet representation > is outside GF(p) boundary? (while the forelast para seems to imply an > attack one is completely left in the dark what is at stake here). Not sure > whether it is the role of CFRG documents to legitimize "BN254 use ... to > keep interoperability". The end of the first para ("as of 2020, as far as > we know, there are no fatal attacks that significantly reduce the security > of pairing-friendly curves after exTNFS") is entirely non-reassuring to me: > it is only four years after the DLP attack that necessitated to strike out > half of the entries in the table earlier on in the paper, not that many > people work on pairing-based algorithmic cryptanalysis in the first place, > etc., etc. Where does this confidence come from (shouldn't one be more > modest here, technically speaking???). The Cheon attack is not explained > and cannot be evaluated at all, since no context on elliptic arithmetic is > given at all in the draft. > 20) Secion 5, 3rd-last para: Why would the Montgomery ladder suddenly come > to the rescue to salvage side channel resistance? Why refer to RFC 7748: > whereas pairing-friendly curves are all Weierstrass curves, the curves in > RFC 7748 are all Montgomery curves with completely different underlying > detail on differential-addition chains). It seems that an entire section > should be devoted to how implementations coul avoid SCA attacks, esp. since > some operations take place in huge extension fields GF(p^t)... > 21) Appendix C seems to convey a particular encoding used by ZCash. I > don't think it is the role of CFRG to make those the standard way of doing > things. This being said, technically that representation is a tiny tweak of > what the SECG1 specification already stipulated in 2001 (with SEC1, one can > extract the affine/compressed encoding of an affine point and whether this > relates to the point at infinity from the leftmost octet (0x04, 0x02 or > 0x03, vs. 0x00), which more or less 1-1 corresponds to the (C_bit, I_bit, > S_bit) combinations. If so, reinventing yet another representation is hard > to defend. > 22) The parity bit notation for finite fields is highly non-standard, > compared to, e.g., what has been standard usage with compressed points for > curves over prime fields or binary extension fields. Even if this would > have some uses, why not defining things once and for all for all extension > fields of an odd prime field, so that this is a simple extension. See also > Appendix H of [1] (parity function for any field GF(p^k), where p odd). > This should also help in limiting side channel leakage from the first-half > vs. last-half of [0,p-1] test. > > Editorial comments: > > 1) Section 2.1, first para: replace "F_q" by GF(q), stipulate that > extension degree n>0. > 2) Section 2.1, first para: with defining equation, use more common domain > parameters a and b (i.e., lowercase instead of upper case). Elsewhere, do > use common nomenclature used with NIST, ANSI, SECG, ISO for 2 decades, > including n for prime-order subgroup, h for co-factor, mention irreducible > polynomial f(z) with extension field, denote fixed base point by P (instead > of BP), etc. If one wishes, refer to Appendix B.1 of [1]. > 3) Section 2.1, 2nd para: "point on" should be "point of". > 4) Section 2.1, first/3rd para: isn't it simpler to define curve over > GF(q) and then introduce curve with same domain parms, but then defined > over extension field GF(q^k)? > 5) Section 2.1, 3rd para: "group law which" should be "group law that", > "reflection about x-axis" should be "reflection around x-axis", with > "unique third point of intersection [R]" (i.e., give this a name, here R), > with [a]P, stipulate that [0]P is the identity element and that > [-a]P=-([a]P), etc. > 6) Section 2.1, terminology: fix E(F_{q^k}) (i.e., add paranthesis), fix > that this refers to GF(q^k)-rational points (rather than GF(q)-rational > points, same with cardinalities. > 7) Section 2.1, terminology: with co-factor h, doesn't one need gcd(h,n)=1 > (so, as to ensure unique order-n subgroup)? > 8) Sectioon 2.2, 2nd para "is called embedding degree of E over GF(q)" > (i.e., add curve and field over which this is defined) > 9) Section 2.2, 2nd para: the term "twist" is not defined (but often used > elsewhere in the draft), neither is the term GF(p^k)* (nonzero elements of > GF(p^k). > 10) Section 2.3, 2nd para: replace "prime p" by "prime number p (where p > at least five)". > 11) Section 2.3, 3rd para (top of p. 8): write "the multiplicative > group..." or, better still, simply state that b is a primitive element of > GF(p) (and add this to terminology). > 12) Section 2.4, 4th para: "parameterized" should read "parameters". > 13) Section 3.1, 3rd para: "paiting-based" should be "pairing-based" > (i.e., fix the typo "t" --> "r"). > 14) Section 3.1, 4th para: "to solve" should read "for solving". > 15) Section 3.2, 1st para: "the security level(s)" (i.e., make plural), > "... correspond" (i.e., use corresponding verb conjugation). > 16) Section 4.2, 2nd para: reword "more prudent option" as "more > conservative option". > 17) Section 4.2.1, 4th para: "categorized as M-type" ("as" instead of > "into"). > > Ref: > [1] draft-ietf-lwig-curve-representations-10 > [2] R. Lidl, Niederreiter, "Finite Fields", Cambridge University Press, ... > > On 2020-06-19 1:50 p.m., Stanislav V. Smyshlyaev wrote: > > Dear CFRG participants, > > This message is starting 2 weeks RGLC on > draft-irtf-cfrg-pairing-friendly-curves-07 ("Pairing-Friendly Curves"), > that will end on July 4th 2020. If you've read the document and think that > it is ready (or not ready) for publication as an RFC, please send a > message in reply to this email or directly to CFRG chairs ( > cfrg-chairs@ietf.org). If you have detailed comments, these would also be > very helpful at this point. > > > P.S.: The review on behalf of Crypto Review Panel was done by Chloe > Martindale, the comments have been addressed by the authors of the draft, > see https://mailarchive.ietf.org/arch/browse/crypto-panel/ > > > Thank you, > > Stanislav, for CFRG chairs > > _______________________________________________ > Cfrg mailing listCfrg@irtf.orghttps://www.irtf.org/mailman/listinfo/cfrg > > > -- > email: rstruik.ext@gmail.com | Skype: rstruik > cell: +1 (647) 867-5658 | US: +1 (415) 287-3867 > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > https://www.irtf.org/mailman/listinfo/cfrg >
- [Cfrg] RGLC on draft-irtf-cfrg-pairing-friendly-c… Stanislav V. Smyshlyaev
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Stanislav V. Smyshlyaev
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Armando Faz
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… rsw
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Armando Faz
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Rene Struik
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Michael Scott
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Yumi Sakemi
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Stanislav V. Smyshlyaev
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Marek Jankowski
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Yumi Sakemi
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Yumi Sakemi
- Re: [Cfrg] RGLC on draft-irtf-cfrg-pairing-friend… Yumi Sakemi