Re: [TLS] Safe ECC usage

Dan Brown <dbrown@certicom.com> Fri, 18 October 2013 18:42 UTC

Return-Path: <dbrown@certicom.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 D66AC11E8243 for <tls@ietfa.amsl.com>; Fri, 18 Oct 2013 11:42:26 -0700 (PDT)
X-Quarantine-ID: <z8Gs31KRIhDN>
X-Virus-Scanned: amavisd-new at amsl.com
X-Amavis-Alert: BAD HEADER SECTION, Duplicate header field: "MIME-Version"
X-Spam-Flag: NO
X-Spam-Score: -2.199
X-Spam-Level:
X-Spam-Status: No, score=-2.199 tagged_above=-999 required=5 tests=[AWL=-0.200, BAYES_00=-2.599, J_CHICKENPOX_31=0.6]
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 z8Gs31KRIhDN for <tls@ietfa.amsl.com>; Fri, 18 Oct 2013 11:42:21 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id 64A8911E81B8 for <tls@ietf.org>; Fri, 18 Oct 2013 11:42:21 -0700 (PDT)
Content-Type: multipart/mixed; boundary="===============1062121819=="
MIME-Version: 1.0
Received: from xct101cnc.rim.net ([10.65.161.201]) by mhs210cnc.rim.net with ESMTP/TLS/AES128-SHA; 18 Oct 2013 14:42:17 -0400
Received: from XMB117CNC.rim.net ([fe80::24f3:cc30:b596:7ca0]) by XCT101CNC.rim.net ([fe80::9c22:d9c:c906:c488%16]) with mapi id 14.03.0123.003; Fri, 18 Oct 2013 14:42:16 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'nico@cryptonector.com'" <nico@cryptonector.com>
Thread-Topic: [TLS] Safe ECC usage
Thread-Index: AQHOxuJRxn3XJXmgAkKRAg2ZE6kwf5n3qq2ggAC0kACAAKQ6QIAAYI2AgAEXd7CAAHAUAP//2cVA
Date: Fri, 18 Oct 2013 18:42:16 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5BEDD49@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> <CAK3OfOhH8xORP9YbGaf5Ly59oJGddeqi4-bZt5TZcQWP=WAqng@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF5BEDA76@XMB117CNC.rim.net> <CAK3OfOhmZSspUnZvae2BuHfKBuRM7GzQf9yd1VjFWYAHZ3eaXg@mail.gmail.com>
In-Reply-To: <CAK3OfOhmZSspUnZvae2BuHfKBuRM7GzQf9yd1VjFWYAHZ3eaXg@mail.gmail.com>
Accept-Language: en-CA, en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
MIME-Version: 1.0
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: Fri, 18 Oct 2013 18:42:27 -0000

Nico Williams wrote:
> Dan Brown <dbrown@certicom.com> wrote:
> > Nico Williams wrote:
>
> Random attacks are the reason to want rigid curve selection processes.

Yes, good point and sentence.

Special attacks are the reason to want random curve selection.

>
> That leaves the other possibility, that the curve author knows how to
> create curves that will be vulnerable to some class of attacks without
> a random search.  Here we can use curve selection criteria that involve
> parameter selections that no one person/entity can control --
> verifiably.
>
> Surely that was your point, no?  That curve25519 might be "special"
> (as in specially weak) in some way that you (and I) don't know.

My point was not about malicious curve selection, but its pre-requisite: 
existence of a weak class of curves.

>
> > Remember, Curve25519, though free from the potential of malicious
> > manipulation, is chosen, in part, for its special efficiency
> properties.
> >
> > These special properties may also given an attacker special
> > advantages.  DJB has already argued, based on the existing attacks  -
> - not random attacks --
> > that this is unlikely.   And I agreed.
> >
> > Consider the ECC history.  After resisting all generic attacks, we
> > have the following
> >
> > Miyaji proposed special trace 1 curves.  A few years later, these
> were
> > broken by the SASS attack.
> >
> > Various proposed supersingular curves.  Later, they were broken by
> the
> > MOVFR attacks.
> >
> > But ever since then, it has been fairly quiet on the prime-field side
> of ECC.
>
> We can look at things other than the constants in curve25519 (and curve
> 1174, and curve3617) -- the class(es) of curve(s) that it (they) fits..
> separately from the curve selection criteria.  How do we mitigate
> unknown weaknesses in each curve class?  The only thing I know is:
> algorithm agility.

In addition to algorithm agility, random curve selection mitigates unknown 
weaknesses, e.g. Brainpool or P256 (but only if you trust its creator).

Hmm, maybe, I am missing your point about "curve class".

I believe that, elsewhere in this thread, I said algorithm agility would be a 
very good reason for including Curve25519, in addition to Brainpool.

Algorithm agility, though, does not help much, in general, against untold 
attacks (mainly helping against newly announced attacks).

In particular, we don't want to TLS to become laissez-faire roll any algorithm 
you want, i.e. the ultimate in algorithm agility?  At some point, TLS 
considers the evidence and picks a few good algorithms, right?  The choice 
governing this selection of each algorithm is not primarily algorithm agility. 
For example, AES was chosen for inclusion in TLS, not because of algorithm 
agility but because of the extensive analysis it underwent.  TLS did not, and 
still does not, adopt every single newly proposed algorithm in the name of 
algorithm agility.  So, something other than algorithm agility seems to be 
protecting TLS.

Also, separately from but similary to algorithm agility, algorithm X is not 
usually adopted in TLS just on the grounds that we know of no attack, else 
each new proposal would be adopted.  So, it is inconsistent to consider only 
about known attacks.  TLS has to consider what evidence there is against 
unknown attacks.

I contend that it is on this basis, that is reasonable scrutinize crypto 
algorithms, be it P256 or Curve25519.


> As for selection criteria, I think I'd prefer a verifiably random
> selection process over the smallest freedom approach, but where there's
> doubt about the random selection process' verifiability I prefer the
> latter over the former.  The problem is that as time passes it becomes
> more difficult to verify that a long-ago random selection process was
> not manipulated -- we have to trust records of history in order to
> believe that it wasn't.
>
> >> 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.
> >
> > Furthermore, if we admit this possibility, i.e. to justify that the
> > ECDLP over P256, then we should not just ignore it, but consider
> alternatives to ECC.
>
> I didn't mean that we should flat out ignore that possibility.  I was
> very specific: "... so we must ignore this possibility WHEN COMPARING
> CURVES TO ONE ANOTHER".  I said nothing about comparing ECC to non-ECC.
> Once more, the only way I know of to mitigate against unknown attacks
> is algorithm agility.

Sorry for the confusion. In this thread, I've been arguing two INDEPENDENT 
points:

- random curves have slightly more assurance than special
- if the threat against P256 is serious, then we had better seriously consider 
non-ECC

The evidence set for the two points is similar, which may cause me to look 
like an arguing for one point, when I am trying to argue the other.

Put another way, what's the point in comparing curves to each other, if we 
believe there's a bigger problem of ECC being busted.

Put another way, it's as if we have something like C = max(A,B) + |A-B|, then 
C is always better than A or B, unless A and B are the same.


> For ephemeral DH algorithm agility is relatively simple: require to
> implement N different DH algorithms, make it easy to turn off any of
> them if they get broken.
>
> For other ECC uses algorithm agility is much harder: it involves re-
> keying.  We could require that principals have N public keys (in PKI
> cases, that all N certs have the same names and so on, issued by the
> same issuer), so that it's possible to drop any one that gets broken
> later.  But even this, I think, may be too much to ask for.
>
> So at some point we have to pick something.  At some point, in spite of
> uncertainty, we have to select some algorithm as the one we're going to
> rely on the most for authentication.  Which would you rather use?

Hmm, as an end user, I might go for the safest possible that can run on my 
device.

>
> >> 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.
> >
> > Of course, it's very hard to make such estimates.  Even so, there is
> > merit in making such estimates.  They have to been based on evidence.
> > There two types of evidence here:
> >
> > 1.  The lack of new attacks, despite efforts and incentives.
> >
> > 2.  The existing attacks, e.g. MOVFR and SASS.
> >
> > Intuition might entirely dismiss inferring estimates from this
> > evidence set, as wild speculation.  More formally, intuition would be
> > saying the inference drawn from the set have low confidence.
>
> So do nothing?  Ignore the whole field?  I'm not sure where you're
> going with this.  What specific advice are you giving us?
>

Oh, sorry, I was very unclear, hinging on the word "might" to express what 
others might intuit.  I was thinking about a totally different point.

My own intuition: I think ECC is safe, and that in the very unlikely case of 
any untold attacks, they will be at most similar in impact to MOVFR and SASS.

My advice: definitely don't worry about Brainpool.  Don't worry about P256, 
unless you view its creator as an adversary and you are somehow required to 
use ECC, almost against your will, instead of some alternative like RSA or 
integer DH.  Consider Curve25519 mainly if you really want efficiency, or 
don't trust the reliability of your implementation, and maybe also have dim 
view on the security of ECC alternatives.

TLS can safely adopt all these EC choices.

At some point, though, TLS may not want to allow too many choices.


---------------------------------------------------------------------
This transmission (including any attachments) may contain confidential information, privileged material (including material protected by the solicitor-client or other applicable privileges), or constitute non-public information. Any use of this information by anyone other than the intended recipient is prohibited. If you have received this transmission in error, please immediately reply to the sender and delete this information from your system. Use, dissemination, distribution, or reproduction of this transmission by unintended recipients is not authorized and may be unlawful.