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

Nigel Smart <nigel@cs.bris.ac.uk> Sun, 20 July 2014 17:57 UTC

Return-Path: <csnps@bristol.ac.uk>
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 DD9DF1B2928 for <cfrg@ietfa.amsl.com>; Sun, 20 Jul 2014 10:57:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Level:
X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3] 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 8cPHNY3ezY_C for <cfrg@ietfa.amsl.com>; Sun, 20 Jul 2014 10:57:31 -0700 (PDT)
Received: from eu1sys200aog123.obsmtp.com (eu1sys200aog123.obsmtp.com [207.126.144.155]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DE1281B2925 for <cfrg@irtf.org>; Sun, 20 Jul 2014 10:57:30 -0700 (PDT)
Received: from mail-we0-f178.google.com ([74.125.82.178]) (using TLSv1) by eu1sys200aob123.postini.com ([207.126.147.11]) with SMTP ID DSNKU8wDBrNsZDN+d5tTND+h44UpmXg2J3qS@postini.com; Sun, 20 Jul 2014 17:57:30 UTC
Received: by mail-we0-f178.google.com with SMTP id w61so6575759wes.23 for <cfrg@irtf.org>; Sun, 20 Jul 2014 10:57:26 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:sender:message-id:date:from:user-agent :mime-version:to:cc:subject:references:in-reply-to:content-type :content-transfer-encoding; bh=erZpGYwwNirK8SFMcsjK1W289DXBoZIKs8rDQl6w3FQ=; b=iCEcpID8kmfAHO82K1PiKjtRrR0wv+GQ72QDN22zwDmKwdK8QefHnRqV0CxwN1R/Wo Istw5OLsAG1UBcZ0rCsfR5NYAQu0KEN4Ser+BXnwFFMedet+CYVWZjr31NsIt2I2HCGJ Vqtxajo9trhhH2kMGqL9dARw9a0ZvXM22LrzLYkE0QR4kmg84j00O1ze/t+zudFJPOhA D8vSgum1HJcdIC8fsspt+IqBYFXcj+sfxzFa0Na3uSTzulQn3unHMVEY12SYgsAblAtg 5C1O5DGEMI9RGLWWpa58JUreobtwkMeynmgC6mFXNd6FZcXMyHpYtk7GjC3MpRn452Dy JTsA==
X-Gm-Message-State: ALoCoQkYMguZ1qUVacuXJIdu2iL7GpEaf+MI1fh/IihH6kWgNjT12kINx7qUPi1KHal2DNHsMptPeBJ4aLcNRXX+kInazBdsU/0SF/RbQfILCAXzO8Jqo5D+Thh32STA1cSk5Ct5DPWd
X-Received: by 10.180.90.233 with SMTP id bz9mr25676691wib.42.1405879046693; Sun, 20 Jul 2014 10:57:26 -0700 (PDT)
X-Received: by 10.180.90.233 with SMTP id bz9mr25676675wib.42.1405879046521; Sun, 20 Jul 2014 10:57:26 -0700 (PDT)
Received: from [192.168.1.78] (host86-168-27-89.range86-168.btcentralplus.com. [86.168.27.89]) by mx.google.com with ESMTPSA id ey16sm32405516wid.14.2014.07.20.10.57.25 for <multiple recipients> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 20 Jul 2014 10:57:25 -0700 (PDT)
Sender: Nigel Smart <csnps@bristol.ac.uk>
Message-ID: <53CC0304.4010802@cs.bris.ac.uk>
Date: Sun, 20 Jul 2014 18:57:24 +0100
From: Nigel Smart <nigel@cs.bris.ac.uk>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Michael Hamburg <mike@shiftleft.org>
References: <53CBDFF8.5050204@cs.bris.ac.uk> <0F4DF570-7886-4D0A-8817-DEEF64FBA8A8@shiftleft.org>
In-Reply-To: <0F4DF570-7886-4D0A-8817-DEEF64FBA8A8@shiftleft.org>
Content-Type: text/plain; charset="windows-1252"; format="flowed"
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/F_5fu7yZF6Qkq0DLSEKcv7eDBLM
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 17:57:34 -0000

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.

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).

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.

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.

<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>

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
>