Re: [Cfrg] A big, big Elliptic Curve

Ilari Liusvaara <ilariliusvaara@welho.com> Sun, 10 April 2016 17:31 UTC

Return-Path: <ilariliusvaara@welho.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 E2ECB12D61C for <cfrg@ietfa.amsl.com>; Sun, 10 Apr 2016 10:31:53 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.896
X-Spam-Level:
X-Spam-Status: No, score=-2.896 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.996] autolearn=ham autolearn_force=no
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 4c_ip35CwKGB for <cfrg@ietfa.amsl.com>; Sun, 10 Apr 2016 10:31:51 -0700 (PDT)
Received: from welho-filter1.welho.com (welho-filter1.welho.com [83.102.41.23]) by ietfa.amsl.com (Postfix) with ESMTP id B8FCA12D095 for <cfrg@irtf.org>; Sun, 10 Apr 2016 10:31:51 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by welho-filter1.welho.com (Postfix) with ESMTP id 548543550; Sun, 10 Apr 2016 20:31:50 +0300 (EEST)
X-Virus-Scanned: Debian amavisd-new at pp.htv.fi
Received: from welho-smtp1.welho.com ([IPv6:::ffff:83.102.41.84]) by localhost (welho-filter1.welho.com [::ffff:83.102.41.23]) (amavisd-new, port 10024) with ESMTP id RZAiZtoEiRmz; Sun, 10 Apr 2016 20:31:50 +0300 (EEST)
Received: from LK-Perkele-V2 (87-100-143-35.bb.dnainternet.fi [87.100.143.35]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by welho-smtp1.welho.com (Postfix) with ESMTPSA id 04F4D27F; Sun, 10 Apr 2016 20:31:50 +0300 (EEST)
Date: Sun, 10 Apr 2016 20:31:48 +0300
From: Ilari Liusvaara <ilariliusvaara@welho.com>
To: Mike Hamburg <mike@shiftleft.org>
Message-ID: <20160410173148.GA8578@LK-Perkele-V2.elisa-laajakaista.fi>
References: <CAMm+LwgK6rxuwT23+OsBB1Z1=GEd2JmawrjVFDcAqgEQWcpNJg@mail.gmail.com> <858AE939-7119-49DA-A9C2-79B1DF5DC8BB@shiftleft.org>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
In-Reply-To: <858AE939-7119-49DA-A9C2-79B1DF5DC8BB@shiftleft.org>
User-Agent: Mutt/1.5.24 (2015-08-30)
Sender: ilariliusvaara@welho.com
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/ihm4v5u1jSuM0Vr3MxKQFIOwrn8>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] A big, big Elliptic Curve
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
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: Sun, 10 Apr 2016 17:31:54 -0000

On Sun, Apr 10, 2016 at 10:12:39AM -0700, Mike Hamburg wrote:
> 
> > On Apr 10, 2016, at 07:59, Phillip Hallam-Baker <phill@hallambaker.com> wrote:
> > 
> > Following our discussion on QC hardening. Among the range of
> > responses, perhaps we should consider an Elliptic Curve with a QC
> > difficulty comparable to that of RSA.
> > 
> > Interpreting the NSA advice is error prone. But the straight reading
> > would be 'we think it more likely that a quantum computer will be
> > built that can break current ECC schemes before someone works out how
> > to break RSA 3096.

My interpretation of NSA position & announcements is:
- QC is coming sufficently soon (and here "soon" can mean 30 years or
  so) that there is no point in transitioning to ECC anymore.
- NSA thinks that multiplicative-DH is significantly harder than what
  "open literature" considers.

> > So maybe what we need is Curve2048 or Curve3096, just to be sure. It
> > would be slow of course. But it could be useful.
>
> At that point, wouldn't the multiplicative group of a prime field be a better choice?

Yes, I think that if you want maximum speed for given qbit bound,
multiplicative groups are faster than ECC.

However, once one has gotten to the point where QC of hundreds of
fully-coupled gbits can be built, things are looking _very_ dire,
for both.



-Ilari