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, 03 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.
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yoav Nir
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Stephen Farrell
- [TLS] draft-sheffer-tls-bcp: DH recommendations Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Michael D'Errico
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Patrick Pelletier
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Xuelei Fan
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Martin Rex
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yoav Nir
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Martin Rex
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Blumenthal, Uri - 0558 - MITLL
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Blumenthal, Uri - 0558 - MITLL
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Peter Gutmann
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Peter Gutmann
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Michael Ströder
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Blumenthal, Uri - 0558 - MITLL
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… james hughes
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… james hughes
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Blumenthal, Uri - 0558 - MITLL
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Michael Ströder
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Michael Ströder
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… james hughes
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Blumenthal, Uri - 0558 - MITLL
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yoav Nir
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Bill Frantz
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Ralph Holz
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Martin Rex
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Martin Rex
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Martin Rex
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… james hughes
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Peter Gutmann
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Peter Gutmann
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Michael Ströder
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… james hughes
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Peter Gutmann
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Michael Ströder
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Michael D'Errico
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yoav Nir
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Stephen Farrell
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Patrick Pelletier
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yoav Nir
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Michael D'Errico
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Ralph Holz
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… james hughes
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Ralph Holz
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Nikos Mavrogiannopoulos
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Patrick Pelletier
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Patrick Pelletier
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Patrick Pelletier
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yoav Nir
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Peter Gutmann
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Patrick Pelletier
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Martin Rex
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Peter Gutmann
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Yaron Sheffer
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Alex Elsayed
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Michael D'Errico
- Re: [TLS] draft-sheffer-tls-bcp: DH recommendatio… Peter Gutmann
- [TLS] Safe ECC usage D. J. Bernstein
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage D. J. Bernstein
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage Kyle Hamilton
- Re: [TLS] Safe ECC usage Johannes Merkle
- Re: [TLS] Safe ECC usage Adam Langley
- Re: [TLS] Safe ECC usage Santosh Chokhani
- Re: [TLS] Safe ECC usage Martin Rex
- Re: [TLS] Safe ECC usage Kyle Hamilton
- Re: [TLS] Safe ECC usage Yoav Nir
- Re: [TLS] Safe ECC usage Martin Rex
- Re: [TLS] Safe ECC usage D. J. Bernstein
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage Johannes Merkle
- Re: [TLS] Safe ECC usage Manuel Pégourié-Gonnard
- Re: [TLS] Safe ECC usage Yoav Nir
- Re: [TLS] Safe ECC usage D. J. Bernstein
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage D. J. Bernstein
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage Johannes Merkle
- [TLS] (offline note) Re: Safe ECC usage Rene Struik
- Re: [TLS] Safe ECC usage D. J. Bernstein
- [TLS] (EC)DSA potential problems (ECC "brittlenes… Martin Rex
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage D. J. Bernstein
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage Watson Ladd
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage Johannes Merkle
- Re: [TLS] Safe ECC usage Nico Williams
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage Nico Williams
- Re: [TLS] Safe ECC usage Michael StJohns
- Re: [TLS] Safe ECC usage Dan Brown
- Re: [TLS] Safe ECC usage Nico Williams
- Re: [TLS] Safe ECC usage Bill Frantz
- Re: [TLS] Safe ECC usage D. J. Bernstein
- Re: [TLS] Safe ECC usage Dan Brown
- [TLS] DH group negotiation extension [was: Re: dr… Daniel Kahn Gillmor
- Re: [TLS] DH group negotiation extension [was: Re… Dang, Quynh
- Re: [TLS] DH group negotiation extension [was: Re… Patrick Pelletier
- Re: [TLS] DH group negotiation extension [was: Re… Watson Ladd