Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

Benjamin Black <b@b3k.us> Sat, 19 July 2014 23:10 UTC

Return-Path: <b@b3k.us>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 870241B2AA7 for <cfrg@ietfa.amsl.com>; Sat, 19 Jul 2014 16:10:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.977
X-Spam-Level:
X-Spam-Status: No, score=-1.977 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7] autolearn=ham
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 nZtpUV8fQDmi for <cfrg@ietfa.amsl.com>; Sat, 19 Jul 2014 16:10:04 -0700 (PDT)
Received: from mail-wg0-f52.google.com (mail-wg0-f52.google.com [74.125.82.52]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 366011B2AA8 for <cfrg@irtf.org>; Sat, 19 Jul 2014 16:10:04 -0700 (PDT)
Received: by mail-wg0-f52.google.com with SMTP id a1so4838185wgh.11 for <cfrg@irtf.org>; Sat, 19 Jul 2014 16:10:02 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=yqCPOA0fEJuBbOAGwET5rc6b7xuJzK3QKbsyuGLQ3Wo=; b=JjiF7ZIBXeBKwVsKDKyJ6WU6P/epY3MrmYCkj0pgB0Rh8vPUY+dXS5WASJo1dlUOon UZuGMFLYf/4IXaCBSQOgDA71IY6qtUwWOBIBIsTIUn2LDshTeFzTr0TROQvnF/Jijb9B IyUtzB/IfWfha3zS1mmSqePCB60w8RTX++wDhVXMDpmYZ6h7LYEJsg/bQnsnjvKnTVqx 4HVIAXYkSNn3Yxkz0uvfjOee3re5ckq3yWKb7QAsMtjCr0qAToU+BGdbeaa2zxqd1Bww 7q0GmyC2FYvhQ2YTg4C0/zhCP3GGwfgO2eIwSHi8lrCHzKhKd20bDxEX5bd34weXGF9H +DSQ==
X-Gm-Message-State: ALoCoQlwVXyk6kWt62KD40gjaDtXJUK8bwgjV80Jnnb4okBHo2VXN/SwxQjIsaetHfoC6BVCcr41
X-Received: by 10.180.10.166 with SMTP id j6mr13942451wib.73.1405811402803; Sat, 19 Jul 2014 16:10:02 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.216.44.138 with HTTP; Sat, 19 Jul 2014 16:09:42 -0700 (PDT)
In-Reply-To: <CFEF5C78.27B54%kenny.paterson@rhul.ac.uk>
References: <CFE9F2DE.26E5A%kenny.paterson@rhul.ac.uk> <CA+Vbu7zQ-k5i74ZpoOyNPoFJqjWKYVkHwkAYD+1uyAvtMmTBmg@mail.gmail.com> <CFEF5C78.27B54%kenny.paterson@rhul.ac.uk>
From: Benjamin Black <b@b3k.us>
Date: Sat, 19 Jul 2014 16:09:42 -0700
Message-ID: <CA+Vbu7yVm5TPNoe=erPvUsq8P7vXj2HmauG2PpzPtKuvCsdSkA@mail.gmail.com>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
Content-Type: multipart/alternative; boundary=001a11c2441249224904fe93f93d
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/7U5rqYB64iCbgfNqDY2MgB5RTcw
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sat, 19 Jul 2014 23:10:09 -0000

"This stems from the fact that in some specific cases an algorithm and a
curve are closely linked, with the two in some sense being carefully
co-designed to gain security and performance."

I am aware of claims to this effect, but I have seen no evidence of
meaningful security or performance gains that would be seen in practical
deployments in TLS. Similar claims have been made about the dramatic
performance gains from certain curve forms, but the MSR research that
produced the NUMS curves shows only slight performance advantages for those
forms and only at low security levels. The ECCLib implementations support
the conclusion that there is little benefit. Please provide specific
supporting documentation for claims of significant, not incremental,
performance or security gains for TLS from this.

If we had evidence of radically improved security or radically improved
performance at a given security level I would agree it would be worth
exploring. For less than 10% performance gain and no security gain I see no
reason to even consider adopting a new signature algorithm. In the abstract
it might seem plausible, but when faced with updating a billion devices
along with all of the supporting infrastructure previously hinted at, it
has to be excluded.

"My own view is that we should broaden our interpretation of the scope of the
request to accommodate this fact, providing both new curves, and where
appropriate,
pointers to algorithms for those curves."

There are multiple available options that support all relevant security
levels, are faster than the NIST curves, and are compatible with existing
infrastructure. There will always be new curves published. Their existence
cannot mean we constantly push incompatible algorithms with enormous
adoption costs at scale. If the goal is radically higher performance at a
given security level and we don't care at all about compatibility, then why
not consider genus 2 curves or other forms which are known to be enormously
faster than even the twisted Edwards curves on the table? Throwing out
compatibility is a very slippery slope.

I ask once again that you and the rest of the CFRG leadership along with
the TLS leadership focus on practical, clear, and specific requirements for
elimination of the NIST curves. Expanding the scope beyond that either
means a hasty process producing something we are likely to regret in a few
years (this is a 15+ year commitment!), or a long and careful process
producing something we will still want around in a few years. Pushing new
crypto on vendors and customers for the sake of maybe a few percent
performance improvement, and that is exactly what we are discussing here,
should alarm everyone.

I will unfortunately not be in Toronto, but a number of others from
Microsoft will be and I hope there can be productive discussion on this
grounded a bit more in the facts of performance, security, and practice.


Ben



On Fri, Jul 18, 2014 at 3:29 PM, Paterson, Kenny <Kenny.Paterson@rhul.ac.uk>;
wrote:

> Hi Ben,
>
> Thanks for your questions. I agree there is ambiguity. This stems from the
> fact that in some specific cases an algorithm and a curve are closely
> linked, with the two in some sense being carefully co-designed to gain
> security and performance.
>
> I understand very well your point that if it is "curves only", then
> certain curves which are incompatible with existing standardized and
> widely deployed algorithms would need to be excluded.
>
> My own view is that we should broaden our interpretation of the scope of
> the request to accommodate this fact, providing both new curves, and where
> appropriate, pointers to algorithms for those curves. (Note that CFRG is
> not being asked to produce I-Ds for either curves or algorithms, though
> that kind of work might inevitably follow depending on the exact choices
> we recommend.) Of course, we can and should have discussion on this
> question of broadening of scope, as you rightly suggest below.
>
> Concerning your second question, yes, in an ideal world we would reach
> rough consensus on the requirements, and they would be clear, complete and
> unambiguous.
>
> If you are in Toronto next week, I'd be glad to continue the conversation,
> otherwise, let's do it on the list.
>
> Regards
>
> Kenny
>
>
> On 18/07/2014 06:51, "Benjamin Black" <b@b3k.us>; wrote:
>
> >Kenny,
> >
> >
> >There is rather a lot of ambiguity in these various versions of the
> >requirements. It would be helpful to get clarity on at least two points:
> >
> >
> >1) Is this request for _only_ new curves, as the subject line of your
> >email indicates, or for new "ECC mechanisms" as in the included list from
> >David McGrew? If it is the former, then curves which are incompatible
> >with existing standardized and widely
> > deployed algorithms, at least including ECDHE and ECDSA, must be
> >excluded. If it is the latter, then this request goes far beyond some
> >curves and I suggest deserves a lot more debate on how far down the new
> >cryptography rabbit hole CFRG and the IETF wish to
> > go.
> >
> >
> >2) Is the process here to agree on clear, complete, unambiguous
> >requirements against which candidate curves will be evaluated? I believe
> >the answer is, or should be, yes. However, based on ambiguities in the
> >stated requirements and the subsequent further
> > blurring of those requirements on the mailing list, it seems that might
> >not be the consensus view.
> >
> >
> >
> >
> >Ben
> >
> >
> >
> >
> >On Mon, Jul 14, 2014 at 12:49 PM, Paterson, Kenny
> ><Kenny.Paterson@rhul.ac.uk>; wrote:
> >
> >Dear CFRG,
> >
> >CFRG has received a formal request from the TLS Working Group for
> >recommendations for new elliptic curves. Specifically, the TLS WG would
> >like CFRG to recommend:
> >
> >- Curves suitable for both key establishment and digital signature
> >  (though the same curves need not be used for both purposes).
> >
> >- One proposed curve or set of curves at the following security
> >  levels: 128-bit (~256-bit curve) and 256-bit (~512 bit curve).
> >  192-bit security is optional.
> >
> >Note that these curves are not intended to supplant current curves in
> >widespread use, but rather to supplement them. Full details of the request
> >can be found in the e-mail from the TLS WG chairs below.
> >
> >The CFRG chairs will coordinate a response to this request from the CFRG
> >readership. Ideally we will reach a rough consensus through discussion on
> >the
> >list and at the upcoming IETF 90 meeting in Toronto. While no deadline is
> >set for our response to the TLS WG, we should aim to have one ready within
> >2 months.
> >
> >We regard this as a major work item for CFRG and one where CFRG can
> >provide real value to the TLS WG and the IETF more widely. So we encourage
> >(and indeed request) active participation from the widest set of
> >participants on this project.
> >
> >As a first step, we propose to discuss the requirements for new curves for
> >a period of 2 weeks. Using an agreed set of requirements, in a second
> >step, we will then evaluate different curve proposals (including extant
> >proposals and any emerging ones) for a period of 4 weeks. In a final
> >period of 2 weeks, we will produce a proposal for the TLS WG and seek
> >consensus on it.
> >
> >
> >The first step, running for 2 weeks, begins here.
> >
> >A starting point for requirements can be found in David McGrew's recent
> >CFRG post
> >(http://www.ietf.org/mail-archive/web/cfrg/current/msg04461.html) and
> >reproduced here:
> >
> >----
> >
> >Simplicity
> >
> >   R1.  Desired: easy to understand and implement [1]
> >
> >Efficiency
> >
> >   R2.  Required: amenable to compact implementations and fast
> >   implementations, across both small and large processors [1]
> >
> >   R3.  Desired: re-use components between signatures and key exchange
> >   algorithms [3]
> >
> >Intellectual Property
> >
> >   R4.  Required: available worldwide under reasonable and well
> >   understood licensing terms [1]
> >
> >   R5.  Desired: available worldwide under royalty-free licensing
> >   terms [1]
> >
> >Interoperability
> >
> >   R6.  Desired: can be used with current software implementations
> >   (using different curve parameters) of TLS, PKIX, SSH, and IKE [4]
> >
> >   R7.  Desired: can be used within current ECC standards of TLS,
> >   PKIX, SSH, and IKE [4]
> >
> >Security
> >
> >   R8.  Required: amenable to constant-time implementations, to avoid
> >   side channel attacks [2]
> >
> >   R9.  Required: resist twist attacks [2]
> >
> >   R10.  Required: curve parameters should have good provenance;
> >   random curves should be provably pseudorandom [5]
> >
> >   R11.  Desired for key exchange: resist invalid curve attacks [2];
> >   note that complete addition laws help and are thus desirable [2].
> >   (Note that the use of ephemeral keys also resist such attacks.)
> >
> >   R12.  Required for PAKE: indistinguishability of curve points from
> >   random strings [2]
> >
> >Footnotes:
> >
> >   [1] Original criteria set out for the Advanced Encryption Standard,
> >       which is equally applicable to ECC.  National Institute of
> >       Standards and Technology (NIST) of the United States, 1998.
> >
> >   [2] Daniel J. Bernstein and Tanja Lange. SafeCurves: choosing safe
> >       curves for elliptic-curve cryptography.
> >       http://safecurves.cr.yp.to <http://safecurves.cr.yp.to/>
> ><http://safecurves.cr.yp.to/>, accessed
> >April 2014.
> >
> >   [3] Criteria identified by David McGrew, 2014.
> >
> >   [4] Criteria identified by Russ Housley, TLS WG meeting at IETF89.
> >
> >   [5] Criteria widely acknowledged on CFRG email list during 2014.
> >
> >----
> >
> >
> >Our first request, then, is that you consider these requirements, and
> >provide your views on their appropriateness, completeness, and individual
> >classifications (required/desired). We will continue that discussion for 2
> >weeks, until the end of the IETF meeting in Toronto. The chairs will then
> >compile a consensus-based list of requirements of the above form, after
> >which we will move to the second step.
> >
> >We thank you in advance for your participation in this important task.
> >
> >Regards
> >
> >Alexei, Kenny and Kevin (CFRG co-chairs)
> >
> >
> >
> >
> >On 11/07/2014 05:44, "Joseph Salowey (jsalowey)" <jsalowey@cisco.com>;
> >wrote:
> >
> >>CFRG Chairs and Security ADs,
> >>
> >>TLS WG would like to formally request that the
> >>CFRG make a recommendation for new ECC group support for TLS
> >>and other similar applications. Specifically, we request that CFRG
> >>recommend the following:
> >>
> >>- Curves suitable for both key establishment and digital signature
> >>  (though the same curves need not be used for both purposes).
> >>
> >>- One proposed curve or set of curves at the following security
> >>  levels: 128-bit (~256-bit curvee) and 256-bit (~512 bit curve).
> >>  192-bit security is optional.
> >>
> >>If the same curves are used for key establishment and signature, this
> >>would be a recommendation for two curves.  If different curves are
> >>used, this would be a recommendation for four curves.
> >>
> >>In addition to a recommendation, we also request that the CFRG provide
> >>a technical rationale for their selection.
> >>
> >>If the CFRG does not feel comfortable making a single set of
> >>selections, we propose that they select a small number of potential
> >>choices with a detailed technical analysis of the advantages and
> >>disadvantages of each selection and that the Security ADs sponsor a
> >>process (perhaps via SAAG) to narrow it down to the specification
> >>above.
> >>
> >>For clarity, we are not currently requesting that CFRG replace or
> >>profile the existing curves in RFC4492 and RFC 7027, although we are
> >>also not ruling out such an effort in the future. The current request
> >>is for a new set of curves to complement the existing ones.
> >>
> >>Please reach out to us if this is unclear or further information is
> >>required.
> >>
> >>Thanks,
> >>
> >>TLS Chairs
> >>
> >>
> >
> >
> >
> >_______________________________________________
> >Cfrg mailing list
> >Cfrg@irtf.org
> >http://www.irtf.org/mailman/listinfo/cfrg
> >
> >
> >
> >
> >
>
>