Re: [TLS] Safe ECC usage

Dan Brown <dbrown@certicom.com> Thu, 03 October 2013 14:45 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 2DAE921E8054 for <tls@ietfa.amsl.com>; Thu, 3 Oct 2013 07:45:06 -0700 (PDT)
X-Quarantine-ID: <gnE+FtOWypQi>
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.299
X-Spam-Level:
X-Spam-Status: No, score=-2.299 tagged_above=-999 required=5 tests=[AWL=-0.300, BAYES_00=-2.599, J_CHICKENPOX_21=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 gnE+FtOWypQi for <tls@ietfa.amsl.com>; Thu, 3 Oct 2013 07:44:54 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id 9608C21E80A7 for <tls@ietf.org>; Thu, 3 Oct 2013 07:37:13 -0700 (PDT)
Content-Type: multipart/mixed; boundary="===============1490163058=="
MIME-Version: 1.0
Received: from xct105cnc.rim.net ([10.65.161.205]) by mhs212cnc.rim.net with ESMTP/TLS/AES128-SHA; 03 Oct 2013 10:37:07 -0400
Received: from XCT116CNC.rim.net (10.65.161.216) by XCT105CNC.rim.net (10.65.161.205) with Microsoft SMTP Server (TLS) id 14.3.123.3; Thu, 3 Oct 2013 10:37:07 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT116CNC.rim.net ([::1]) with mapi id 14.03.0123.003; Thu, 3 Oct 2013 10:37:06 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'djb@cr.yp.to'" <djb@cr.yp.to>, "'tls@ietf.org'" <tls@ietf.org>
Thread-Topic: [TLS] Safe ECC usage
Thread-Index: AQHOv9SSxn3XJXmgAkKRAg2ZE6kwf5ni98AQ
Date: Thu, 3 Oct 2013 14:37:06 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5BDECA6@XMB116CNC.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>
In-Reply-To: <20131003010455.17185.qmail@cr.yp.to>
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
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, 03 Oct 2013 14:45:06 -0000


D. J. Bernstein writes:
> 
> We're hypothesizing an attack A that isn't publicly known, and
> considering the following probabilities:
> 
>    Pr[A succeeds against a NIST P-256 user];
>    Pr[A succeeds against a brainpoolP256r1 user];
>    Pr[A succeeds against a Curve25519 user].
> 
> NSA had considerable power to manipulate the NIST P-256 curve choice
> and thus, at least potentially, the first probability. Under a wide
> range of reasonable assumptions on A this would allow NSA to create a
> very high first probability.
> 
> There's far less room for Brainpool manipulation, although still some
> (why SHA-1? why not right to left? why pi instead of e or sqrt(2)? and
> so on), maybe enough to exploit. There's essentially zero room for
> Curve25519 manipulation.

Agreed.  Good point.

Alternatively, it is also reasonable to assume that NSA knows of an attack A
but is unwilling to reveal it, and manipulated P256 to avoid A, by methods
that they do not wish to reveal.  The prudence principle, assume that worst,
means your pessimistic assumptions merits addressing more than this
alternative optimistic assumption.  

> 
> We have no basis for comparing the probabilities outside the case of
> manipulation. Perhaps
> 
>    Pr[A succeeds against a brainpoolP256r1 user]
>    < Pr[A succeeds against a Curve25519 user],
> 
> but there's zero justification for this guess. Perhaps
> 
>    Pr[A succeeds against a brainpoolP256r1 user]
>    > Pr[A succeeds against a Curve25519 user],
> 
> but there's also zero justification for this guess. This is wild
> speculation, completely divorced from rational risk management.

Agreed.  I don't think I said this.

> 
> Dan Brown writes:
> > a proof that Brainpool are invulnerable to the "missed attack" with
> > probability equal to the density of the vulnerable curves
> 
> There is no such proof, and there never will be any such proof. I hope
> you're not trying to bamboozle the innocent reader with bogus claims of
> provability!
>
> But that's not the big issue here. The big issue is that, even in a
> fantasy world of proving the (rather implausible) statement
> 
>    Pr[A succeeds against a brainpoolP256r1 user]
>    = Pr[A succeeds against a user of a random curve],

Well, I thought I prefaced my claim that you quoted above with an "if"
clause, something like we assume that we can trust verifiably pseudorandom
generation.  I had in mind something like random oracle model proof.  Since
you say there will never be such a proof, I am reconsidering what I thought,
and pondering why you say that.  

Hmm.  I don't think you are talking about posterior probabilities, which are
available to the parties who know A and to which I am not claiming any kind
of proof, argument or anything.  That is, I was thinking about prior
probabilities, given the fact that we don't know A, and that we are
specifically discussing unknown A.  

If you are saying that random oracle model proofs do not apply to that real
world, then you are right that I did not present anything like a standard
model proof.  I was wrong for implying such a thing.  But, you also said
there will never be such a proof, so I am rather puzzled.  

Maybe I am missing a factor in the equality, even in a random oracle proof,
because as you noted, even the Brainpool seeds are mildly subject to
manipulation. 

Anyway, you say it's not a big issue, and introduce a fantasy world or
proving that claim.

Anyway, I am still inclined to interpret the Brainpool phrase "verifiably
random" as claiming more that non-manipulability.  It seems to suggest some
form of justifiable indistinguishabilty to a random curve.  This may only be
a heuristic argument, but at least it some kind of argument.

> 
> we still wouldn't have any basis for comparing the Brainpool and
> Curve25519 probabilities. You claim that
> 
>    Pr[A succeeds against a user of a random curve]
>    < Pr[A succeeds against a Curve25519 user]
> 
> but you have zero justification for this claim. One could just as well
> claim the opposite, namely that
> 
>    Pr[A succeeds against a user of a random curve]
>    > Pr[A succeeds against a Curve25519 user],
> 
> which would also have zero justification. Maybe big coefficients are
> more secure than small coefficients, but maybe they're _less_ secure.
> 

Agreed.  Zero justification.  

Prudence principle: assume the worst, so choose the < inequality for
Curve25519.  I think we should continue to assume the worst, even if it is
wild speculation, and then address it as best as possible.

The Brainpool curves have some kind of justification, albeit maybe not a
full-fledged proof.  In other words, to me, the Brainpool approach presents
some kind of best-we-can-do-effort to resist attacks not yet known to us.  

I think P256 would do this too, except for the special field, and more
importantly, the unexplained seeds.  I would be quite surprised if the US
gov publicly recommended, via FIPS 186-2, that its agencies use EC curves
that could be affected an attack A.  I find it very hard to think how the US
gov could be sure that other skilled adversaries could not find the attack
A.  The only thing I can think of, is if a trapdoor key was embedded in
P256, but that seems to imply some kind of the weakness in sha1 or the
verifiable key generation process, because such a key would have require
sufficient entropy for third parties to guess, rendering the hash-generic
exhaustive search approach to manipulation infeasible.
 
Anyway, the advantage for Brainpool over Curve25519 is slight, and
hypothetical, and may be offset by Curve25519's many other benefits, e.g.
efficiency, simple and short implementation.


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