Re: [TLS] Safe ECC usage

Nico Williams <nico@cryptonector.com> Thu, 17 October 2013 16:39 UTC

Return-Path: <nico@cryptonector.com>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6AE7B11E82A4 for <tls@ietfa.amsl.com>; Thu, 17 Oct 2013 09:39:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level:
X-Spam-Status: No, score=-2.1 tagged_above=-999 required=5 tests=[AWL=-0.123, BAYES_00=-2.599, FM_FORGED_GMAIL=0.622]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id t-jsjkbVgslB for <tls@ietfa.amsl.com>; Thu, 17 Oct 2013 09:38:56 -0700 (PDT)
Received: from homiemail-a95.g.dreamhost.com (caiajhbdcbef.dreamhost.com [208.97.132.145]) by ietfa.amsl.com (Postfix) with ESMTP id 84DA911E829C for <tls@ietf.org>; Thu, 17 Oct 2013 09:38:56 -0700 (PDT)
Received: from homiemail-a95.g.dreamhost.com (localhost [127.0.0.1]) by homiemail-a95.g.dreamhost.com (Postfix) with ESMTP id 24E1C1E07C for <tls@ietf.org>; Thu, 17 Oct 2013 09:38:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=cryptonector.com; h= mime-version:in-reply-to:references:date:message-id:subject:from :to:cc:content-type; s=cryptonector.com; bh=AdK/jnUQL3BgWuQCLvpS WpXVNWo=; b=J2dZs15x+M7B5mTQSWcn+I1/Du5/KVkBOdSmoJIUxgM6aK9xehGJ SVj31DDYs3mQyE16WKUHaVG+ZHedC6G6ntpHMbUokFH4JVLMy4KbuyRaJk6hSOTv 04+YuoBslCNEfWhWIKhZkB+WhuGHAxJemjIjRRwLj2uvhoOFAE3DHak=
Received: from mail-we0-f176.google.com (mail-we0-f176.google.com [74.125.82.176]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (No client certificate requested) (Authenticated sender: nico@cryptonector.com) by homiemail-a95.g.dreamhost.com (Postfix) with ESMTPSA id 9D5D01E071 for <tls@ietf.org>; Thu, 17 Oct 2013 09:38:55 -0700 (PDT)
Received: by mail-we0-f176.google.com with SMTP id w62so2569712wes.35 for <tls@ietf.org>; Thu, 17 Oct 2013 09:38:53 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=a6cX49TGEKt6GvFTSyanN96WkMv6ZgLopzw9rJFU9Hs=; b=nISvGURvpTu6lsvQGd2xcmBHA/fIHCFWfzbTkptE+b5Xpc0n+hvxKJ6nYk1LLMw8hY sseUvzL6YnhoK6u2ekHDXM44C8kc1g2fh7z3Zpc5MGUQ2FIwuaG/ivYGp/LH466Sk2gH 3xD9ZHDvho3AvvZE/0Nx6aT06dkkh6hIZmdNKgzB4IdaRVk0IutIaX9keCfphzy37/zc E5pDhTxK+RHYeQJVpItcjR77+cBeh1ybEn1Ul66Fw0dwncJ30byNmMeFMPmq9s4l1RF7 1NM92hS0TvDEgKGqjVoIkv0KeFPX7vNq/aFdVo3Xfm/hSqcYhUSsCsTa2Sr/eMcpuIvN POIA==
MIME-Version: 1.0
X-Received: by 10.180.198.79 with SMTP id ja15mr7683382wic.36.1382027933955; Thu, 17 Oct 2013 09:38:53 -0700 (PDT)
Received: by 10.216.151.136 with HTTP; Thu, 17 Oct 2013 09:38:53 -0700 (PDT)
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF5BEC2EC@XMB117CNC.rim.net>
References: <523E176F.3050304@gmail.com> <9A043F3CF02CD34C8E74AC1594475C7355674EE0@uxcn10-6.UoA.auckland.ac.nz> <20130926152757.15842.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BDB49B@XMB116CNC.rim.net> <20130928223648.1113.qmail@cr.yp.to> <20130929025714.5578895.47771.4422@certicom.com> <20131001143511.11010.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BDE21E@XMB116CNC.rim.net> <20131002161944.8125.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BDE90F@XMB116CNC.rim.net> <20131003010455.17185.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BDECA6@XMB116CNC.rim.net> <20131005192950.27059.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BE4A9D@XMB116CNC.rim.net> <20131012003058.669.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BEBAA5@XMB117CNC.rim.net> <CACsn0c=bSTMWwuHxD3eE3ABC_AxVRt-BOTybEr7umPQD5NB+cA@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF5BEC2EC@XMB117CNC.rim.net>
Date: Thu, 17 Oct 2013 11:38:53 -0500
Message-ID: <CAK3OfOhH8xORP9YbGaf5Ly59oJGddeqi4-bZt5TZcQWP=WAqng@mail.gmail.com>
From: Nico Williams <nico@cryptonector.com>
To: Dan Brown <dbrown@certicom.com>
Content-Type: text/plain; charset="UTF-8"
Cc: "djb@cr.yp.to" <djb@cr.yp.to>, "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] Safe ECC usage
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 17 Oct 2013 16:39:01 -0000

On Thu, Oct 17, 2013 at 10:46 AM, Dan Brown <dbrown@certicom.com> wrote:
> Why couldn't a new attack just work on one curve, namely Curve25519?  If I
> understand correctly, DJB has argued that the ECC theory and experience would
> be evidence for a claim similar, but perhaps not as strong, as your claim.

Let's say that there are single-curve attacks.  We don't know how many
curves have such attacks, nor how hard it is to find such attacks for
specific curves, or specific curves with such attacks.  Perhaps DJB
does know, but either he got spectacularly lucky (if such attack/curve
pairs are rare) or such attack/curve pairs are very common.  The
latter would imply that all ECC is busted, in which case we needn't
worry about whether Curve25519 is weak because we have bigger
problems, so we must ignore this possibility when comparing curves to
one another.  That leaves the former, and now we need some estimate of
frequency of such attack/curve pairs in order to decide if any one
curve is weak.

We don't have such an estimate, but surely whatever that frequency is,
it's the same for all cryptographers.  That means that for any one
standard curve, the likelihood of it being weak this way is about the
same if the possible attacks for each curve were not known at the time
they were discovered.  Now we just need to know whether the curves in
question were selected with or without such knowledge, but we can't
know this [yet], so instead we must estimate the likelihood that the
authors selected a weak curve on purpose.  An estimate of weak curve
distribution/frequency would allow us to estimate the likelihood that
a curve was selected because it was weak.

If some curve required specifying N bits of information, then it must
have been picked from a range of 1..2^2N or so curves (the 2^2N upper
bound is an estimate), *roughly*.  The larger the N, the larger the
freedom the author has/had in selecting a weak curve.  Whatever the
frequency of weak curves, the smaller the N, the more luck an author
needs to pick a weak curve.

That, I think, is the argument for why DJB curves' selection criteria
are more rigid (i.e., less subject to manipulation) than Brainpool
curves.

Now, if one out of every 5 curves are weak, then clearly there's a
great chance that DJB curves are weak.  If, for small Ns, one out of
every 5 curves are weak, while for large Ns one out of every trillion
curves are weak, then Brainpool curves are stronger than DJB curves.
I.e., the distribution of weak curves matters.  We know nothing about
the distribution of such weak curves -- the associated attacks are not
known, they are merely conjectured for the sake of argument after all.

It seems unlikely that there's a class of attacks on curves where the
distribution of weak curves tails off as curve complexity (size of
constants) increases.  But we can't really know anything about this
conjectured class of attacks each limited to one or few curves.

I'm not sure what we should assume, but all else being equal my
conclusion is that we should prefer curves whose selection criteria
left very little freedom to those doing the selection.  This might
include Brainpool-like (i.e., with large constants) curves, but I'd
want the selection to work as follows: one small group of people
publicly select a hash function, another disjoint set of people
independently, publicly (videotaped), and concurrently select a short,
simple, and *meaningful* English language string ("hello world"), then
pick the largest constants smaller than bounds computed from that hash
applied to that string.  In the meantime DJB curves were clearly
selected with very little freedom to select for rare weak curves,
therefore I believe we can trust them.

Nico
--