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

Watson Ladd <watsonbladd@gmail.com> Sun, 20 July 2014 18:51 UTC

Return-Path: <watsonbladd@gmail.com>
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 2145A1B2C9A for <cfrg@ietfa.amsl.com>; Sun, 20 Jul 2014 11:51:08 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
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 mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id AomzaajKklyb for <cfrg@ietfa.amsl.com>; Sun, 20 Jul 2014 11:51:06 -0700 (PDT)
Received: from mail-yh0-x230.google.com (mail-yh0-x230.google.com [IPv6:2607:f8b0:4002:c01::230]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 12F461B2946 for <cfrg@irtf.org>; Sun, 20 Jul 2014 11:51:06 -0700 (PDT)
Received: by mail-yh0-f48.google.com with SMTP id i57so3513431yha.35 for <cfrg@irtf.org>; Sun, 20 Jul 2014 11:51:05 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=kB7Ka75JC9UhrgF8NsPfYO154jA4jgLOqM9Q2EWByNQ=; b=fKaXww3oK2ydwz5bEYezZJ9RkwkWazcQxRHvu4i2xJrOvyfcj1xKqxva4UCB2goIWO SwFQZIpYQ23Rhoinbx1wP0K043C5B4b6ZTDIZ97FuC4012ExzPY/7RIJfBy1kqI3cuPu Cxm992IZapj29Xwk8yaVEna12e/zdQjh3ilncvC7DVcduX4TQ3xxbdnVFAJpFINGwSXC tpj+h5xx4VhCEkWusX835gIJdBR9E7Ai393In3hMsKCujj1QqleC9rqdh3oKVymGQxJG QWNBKdNDWDrZhU22O5nzkh00IG9vkRrLJp0umIyRKmwi9T97yo1nJPounXQMHzroY5z1 05XA==
MIME-Version: 1.0
X-Received: by 10.236.134.208 with SMTP id s56mr31423496yhi.4.1405882265237; Sun, 20 Jul 2014 11:51:05 -0700 (PDT)
Received: by 10.170.202.8 with HTTP; Sun, 20 Jul 2014 11:51:05 -0700 (PDT)
In-Reply-To: <53CC0304.4010802@cs.bris.ac.uk>
References: <53CBDFF8.5050204@cs.bris.ac.uk> <0F4DF570-7886-4D0A-8817-DEEF64FBA8A8@shiftleft.org> <53CC0304.4010802@cs.bris.ac.uk>
Date: Sun, 20 Jul 2014 11:51:05 -0700
Message-ID: <CACsn0ckPhUobH5k3fM4fECGaBcAVhG963+fwYYHoUcLbfKR4yQ@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Nigel Smart <nigel@cs.bris.ac.uk>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ToQQ2aKHxVbcHAzp91sIzY35M9Q
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: Sun, 20 Jul 2014 18:51:08 -0000

On Sun, Jul 20, 2014 at 10:57 AM, Nigel Smart <nigel@cs.bris.ac.uk> wrote:
> Hi
>
> Various issues here....
>
> i) Is there any justification for new curves at this current point in time?
>      - My opinion is no. There is no reasonable argument which can suggest
> that
>        NIST cooked their curves. There may be better ways to generate the
> curves
>        now with extra functionality (see below), but the basic security
> criteria are
>         still valid.

Except that we want higher performance, to enable the use of TLS with
PFS in places where
it is currently not deployed. Performance matters: if you can get a
curve of size 448 to go faster
then one of size 224, and an even faster curve of size 256, this
enables the use of forwards secrecy
in places where it didn't fit before, and with bigger keys than before.

If you want to see something like tcpcrypt be ubiquitous, than every
little percent of performance matters.
Rich Salz has sent emails saying essentially that the cost of ECDH
exchanges is making it hard for CDNs
to adopt ECDHE. What's the point of cryptography if it cannot be used?

>
> ii) Should we add new SECURITY criteria on the CURVES?
>      - My opinion is that this is marginal. I see no benefit at all in twist
> security.
>        Dont get me wrong, I think twist security is a cool idea worthy of an
> academic
>        paper. Its just not practically relevant here (unless we are changing
> protocols,
>        which is not the request).

Twist security enables use of ladders without validation: assume
checks not required for interop get screwed up.

This process began with Curve25519 for TLS. Then Microsoft showed up
with substantially similar NUMS
curves. I think it was obvious that new code was going to be written
and this was understood by the TLS
1.3 WG.

>
> iii) Should we add in curves with better performance which may deviate from
> the
>       NIST choices?
>           - Only if they can represent points in Weierstrass form for
> transmission.
>           - Only if they have prime order.
>                 - Note, here I am being stronger than the ANSI/NIST criteria
> (but actually
>                   NIST curves have this property in any case).
>                 - I really think prime order curves are vital to avoid
> mistakes. I have
>                   been recommending their use in nearly 18 years of advising
> companies
>                   on ECC stuff.
>           - In other words the curve addition is OK, as long as it can
> interoperate with
>             existing software, and will not cause security/patent violation
> issues when
>             used with all possible protocols
>                  - Last point is key, as we cannot force a new curve to only
> be used
>                    with protocol X, as some idiot will use it with Y. This
> is why I think
>                    Curve25519 should be treated as a complete protocol, as
> opposed
>                    to a curve. The naming by Danja is a unfortunate in this
> respect.

DJB, not Tanja Lange, made Curve25519: he's the author on the original
(2006) paper.
Read the SEC1 and NIST standards: they do include non-prime order
curves, and picked prime order because they could.
Yes, I can make protocols where non-prime order could be an issue, but
it's a very slight change to make them work.

There isn't going to be an interop problem: TLS includes mechanisms to
negotiate the use of curves
precisely to enable the addition of new mechanisms. The only issue is
certificates, but even there there are ways
to deal with it.

>
> iv) Should we add in new FUNCTIONALITY criteria on the CURVES?
>           - Actually yes I do think this. If we were to re-do NIST like
> curves I would also
>             publish seeds for TWO base points. The reason for this is that
> many protocols
>             require two base points, and not having them defined in the
> "standard" curves
>             is a problem and we need the DLP to be unknown so we need the
> seeds to be
>             able to guarantee this.

The only protocols I've seen with that property are PAKEs, and
Pedersen commitments, neither of which has great usage
in the IETF. And it's not for lack of definition: SRP was in TLS but unused.
>
> <humour mode>
>
> My problem with the discussion is that it seems to be being conducted in
> exactly
> the way which resulted in the mess which is the current TLS. It would appear
> that
> to people (like me) who have spend years researching ECC, key agreement
> protocols,
> trying to make cryptographic sense of the current TLS protocol, etc etc, are
> being
> trolled by people on the list   :-)
>
> </humour mode>

Do you see a security issue with Curve25519, or any of the proposals?
Or is this a complaint about interoperability?
One of those you are qualified to talk about: the other one Rich Salz
and Adam Langley know far more about, because they
actually manage large deployments of TLS software.

Sincerely,
Watson Ladd

>
> Cheers
>
> Nigel
>
>
> On 20/07/2014 18:25, Michael Hamburg wrote:
>>
>> You sound a little bit like you’re trolling us, Nigel.  It’s one thing to
>> say that the marginal security and performance gains of the new curves isn’t
>> worth the complexity of supporting them in TLS.  It’s another to say that
>> every crypto curve should have all the properties that NIST chose for theirs
>> (except 512 bits instead of 521), and that it shouldn’t have any other
>> properties, even twist security.  Do you have any justification for those
>> criteria?
>>
>> — Mike
>>
>> On Jul 20, 2014, at 8:27 AM, Nigel Smart <nigel@cs.bris.ac.uk> wrote:
>>
>>> Hi
>>>
>>> It seems there is a lot of noise about new types of curves, curvexxxyy
>>> this,
>>> and NUMS that.
>>>
>>> Note the request is for new ELLIPTIC CURVES not elliptic curve PROTOCOLS
>>>
>>> Thus any curve should be IMHO usable with any STANDARD protocol, in any
>>> STANDARD way of implementing the protocol. Without this constraint one is
>>> bound to get implementation errors.
>>>
>>>   - Curve25519 is a combined curve/protocol; so is out of scope IMHO. As
>>>      someone is bound to use the underlying curve with some other
>>> protocol
>>>      and make mistakes.
>>>
>>> Benjamin Black is correct; having new types of this that and the other
>>> for
>>> a marginal security gain, and/or a marginal performance gain is IMHO
>>> inviting problems.
>>>
>>> Thus the ONLY response in my view as responsible cryptographers is
>>> to recommend curves which
>>>
>>>    i) Whose data format for point transfer/curve definition is in
>>> Weierstrass
>>>       form
>>>           - I dont care if some implementation wants to use some
>>> super-duper
>>>             form to do some calculation; the data transfer must enable
>>>             interoperability.
>>> ii) Whose group order is prime
>>>           - Not having prime group order is inviting problems. Thus
>>> Edwards
>>>             curves are out as I am sure they require non-prime group
>>> order
>>> iii) The "b" coordinate should be generated by a hash value on some
>>>       random string.
>>> iv) Usual security constraints; base field has 256 and 512 bits of
>>> security
>>>        to match AES 128 and AES 256; MOV criteria; SmartASS criteria;
>>> v) Ignore "esorteric" constrains like twist security etc.
>>>
>>> So basically I cannot see what is wrong with the NIST curves. And if
>>> people
>>> want something new then they should really come up with a credible
>>> reason for wanting something new. No argument I have seen warrants
>>> the massive change in software and infrastructure that is being proposed.
>>> If people really are that worried about this NIST curves then
>>>    i) They should probably stop using the internet full stop, as that
>>> means
>>>       the NSA probably has massive more capability than even Snowden has
>>>       revealed.
>>>   ii) Generate curves as above; and not trust some new fingle-fangled
>>> ideas
>>>       which are not supported by all the major cryptographers who have
>>>       worked on ECC.
>>>
>>> BTW I still stand by my statement that we should recommend EC-Schnorr
>>> as an extra hash function.
>>>   - Minor change in code needed to support it (compared to some of the
>>> other
>>>     proposals)
>>>   - Provides some "hedge" against future collisions in SHA-256 and SHA-3.
>>>   - Has IMHO (and this is purely subjective) better provable security
>>> than
>>>     EC-DSA
>>> But that is not what we have been asked to comment on; as this is a new
>>> "protocol" (i.e. signature scheme).
>>>
>>> Yours
>>>
>>> Nigel
>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> Cfrg@irtf.org
>>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg



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