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
>