Re: [Cfrg] Progress on curve recommendations for TLS WG

Watson Ladd <> Tue, 29 July 2014 00:17 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id C286C1A03A2 for <>; Mon, 28 Jul 2014 17:17:25 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id Id5H3YEmNemB for <>; Mon, 28 Jul 2014 17:17:24 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:4002:c01::232]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id CC30A1A02C1 for <>; Mon, 28 Jul 2014 17:17:23 -0700 (PDT)
Received: by with SMTP id v1so5357352yhn.37 for <>; Mon, 28 Jul 2014 17:17:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=W/mJipu8VeqySwBqzHHjjApYKXtcBsBtk/F6Lm6MgN0=; b=U5Y2RmCzinSKy5Fa31hNOzq4u11TlXJc/BYYosvAQMAPO1wwaq8RUPS1JgLE9WVrom QIqwGiLtnVcbwUMV042PQ05aNhLBYoWQgVMXV4qHgB8otoSpRGSJYxv4xL2h65CvtK2O b0Vg12BtJjn2sMvzP6K0OrRry9FBvMGF9ZAT3lvup9VZqsMZbCaRs9e9kLYubOPw0gKf YSEQnqzNVsq3+7DEzNY2QLaAPqa4IB8ZjkHA2z9/POp8wDopVcDbTTeHbccAgLuhj58b 1YlEz1jXUJquxi97GfNYD9BB9hgGOXN/iIvosgHrSymtyHGaGI6ykfwfixutSyVxX430 3f/g==
MIME-Version: 1.0
X-Received: by with SMTP id e24mr47391275yhm.78.1406593042914; Mon, 28 Jul 2014 17:17:22 -0700 (PDT)
Received: by with HTTP; Mon, 28 Jul 2014 17:17:22 -0700 (PDT)
In-Reply-To: <>
References: <>
Date: Mon, 28 Jul 2014 17:17:22 -0700
Message-ID: <>
From: Watson Ladd <>
To: "Paterson, Kenny" <>
Content-Type: text/plain; charset="UTF-8"
Cc: "" <>
Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 29 Jul 2014 00:17:25 -0000

On Sun, Jul 27, 2014 at 1:04 PM, Paterson, Kenny
<> wrote:
> Dear CFRG,
> We made good progress last week in Toronto and on the mailing list in
> discussing requirements for curve selection, as well as getting into some
> of the specifics of the different curve options.
> The chairs have had requests to increase the time given to our discussion
> of requirements in the light of the Toronto meeting, and we are happy to
> accommodate that. We therefore plan to extend the previously announced
> schedule so that this initial phase will run for another 2 weeks (until
> Friday 8th August). We will then run the second phase (focussing on
> concrete curve proposals) for 4 weeks, as previously planned.
> Whilst it may be tempting to jump in and start discussing concrete
> performance aspects of the different, specific curve proposals, or drift
> off onto other topics entirely, the chairs would like to ask everyone to
> try to focus on requirements for a bit longer. Here are a few questions to
> help keep things on track and seed further discussion:
> - What is the cost of keeping backwards compatibility with existing
> defined point formats in RFC 4492, if any, for different curve shapes
> (Edwards, twisted Edwards, Montgomery, Weierstrass-only form)?

The cost is the cost of the isogeny in and out. It should be possible
to make a table of isogenies between each format
and when they exist: the information is out there but scattered.

However, RFC 4492 treats point formats as opaque, and while crypto
libraries may assume all curves use a particular
format, this hasn't stopped them from adding Curve25519 support
through different API paths.

> - If ephemeral really means ephemeral, what are the implications for the
> mix of fixed-base/variable-base computations in ECDHE and what, if any,
> are the implications for the choice of curve type?

If ephemeral means ephemeral, then we have 1 fixed+1 variable
multiplication. Variable multiplication alone no longer is as

> - Correspondingly, what are the implications for our choices if we accept
> that ephemeral reuse is the expected behaviour?

If all multiplications are variable base for ECDHE, Montgomery is the
clear winner here. (Actually, Gaudry genus 2, but
people seem less excited by it)

> - Do the current proposals (Curve25519 and friends, and the NUMS curves)
> provide an adequate degree of rigidity that is likely to satisfy the
> widest set of commentators? Or should we be thinking about generating
> fresh curves using a public process having verifiably random inputs? What
> would the likely impact be on performance?

I think minimal parameter is enough rigidity. Random inputs would have
to be the closing price and daily trade volumes of all S&P 500
constituents on some day in the fall: no one can manipulate that
because it is in the future. The impact of random primes would be
pretty bad:
the best reduction algorithms take quadratic time in the number of digits.
> - Would selecting curves that are not in Weierstrass form materially slow
> down deployment?

I don't know the answer to this question.

Watson Ladd
> Thanks for your considered inputs so far.
> Regards,
> Kenny (for the chairs)
> _______________________________________________
> Cfrg mailing list

"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin