Re: [TLS] Safe ECC usage
Dan Brown <dbrown@certicom.com> Tue, 01 October 2013 15:51 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 9548E11E8125 for <tls@ietfa.amsl.com>; Tue, 1 Oct 2013 08:51:24 -0700 (PDT)
X-Quarantine-ID: <s0vWBtrVjTLN>
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.865
X-Spam-Level:
X-Spam-Status: No, score=-2.865 tagged_above=-999 required=5 tests=[AWL=-0.266, BAYES_00=-2.599]
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 s0vWBtrVjTLN for <tls@ietfa.amsl.com>; Tue, 1 Oct 2013 08:51:19 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id 1AC2C11E8143 for <tls@ietf.org>; Tue, 1 Oct 2013 08:51:18 -0700 (PDT)
Content-Type: multipart/mixed; boundary="===============1931553311=="
MIME-Version: 1.0
Received: from xct106cnc.rim.net ([10.65.161.206]) by mhs212cnc.rim.net with ESMTP/TLS/AES128-SHA; 01 Oct 2013 11:51:09 -0400
Received: from XCT104CNC.rim.net (10.65.161.204) by XCT106CNC.rim.net (10.65.161.206) with Microsoft SMTP Server (TLS) id 14.3.123.3; Tue, 1 Oct 2013 11:51:08 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT104CNC.rim.net ([::1]) with mapi id 14.03.0123.003; Tue, 1 Oct 2013 11:51:08 -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: AQHOvrNuxn3XJXmgAkKRAg2ZE6kwf5nf7Ylw
Date: Tue, 01 Oct 2013 15:51:07 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5BDE21E@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>
In-Reply-To: <20131001143511.11010.qmail@cr.yp.to>
Accept-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.250]
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: Tue, 01 Oct 2013 15:51:25 -0000
> D. J. Bernstein writes > > Dan Brown writes: > > You noted that curve sizes p,p-1, and p+1 are weak. > > These might be called special curve sizes, since for a random curve, > > of order p+d, we expect |d| around p^(1/2), and for these d is much > > smaller. > > There is already overwhelming evidence that the size of d is not what > matters. For example, the next attack that you should learn is one that [DB] Thanks for the advice, but what I need to learn, or remember, is no justification for the security of Curve25519. > breaks group order p+6m+2 if p=12m^2-1; in this case the gap from p is [DB] In case, anybody gets scared here, standards already have the MOV test rule this class out. In my weak defense, negligible fraction of p are affected here. More strongly, please remember that we are talking about hypotheticals here: maybe there exists undiscovered attacks, e.g. against P256 or Curve25519. If the evidence is so overwhelming, then maybe we should worry much less about P256? That said, your argument is cogent, and I take new, so this discussion has proven fruitful for improving the justification Curve25519, at least to me. > more than 80% of its maximum possible value. > > What's actually going on is that the additive group F_p has order p; > the multiplicative group F_p^* has order p-1; the group F_{p^2}^* has > order p^2-1; the group F_{p^3}^* has order p^3-1; etc. For roughly the > first dozen groups in this list we have discrete-logarithm algorithms > fast enough to worry about. There are known methods to "transfer" ECDLP > over F_p into these discrete-logarithm problems---but only if the EC > group has order dividing p, p-1, p^2-1, p^3-1, etc. This is why p+1 is > a problem (it divides p^2-1); it's why p+6m+2 is a problem if p=12m^2-1 > (p+6m+2 divides p^3-1); etc. [DB] Excellent explanation, though not one I needed. > > > Of course, it's a logical leap to > > jump from small d to small curve coefficients, > > It's even worse than a logical leap: CM theory shows that each d that > isn't extremely close to +-2 sqrt(p) corresponds to a huge number of [DB] Good point, the case for Curve25519 is growing yet stronger. But how much is huge? I have much to learn, I know, but my understanding is that there are about p isomorphism classes of curves, and on the order of p^(1/2) of curve orders, so about p/^(1/2) curves per order. I could be wrong, but I think that a reasonable heuristic is for a random curve by isomorphism class, its corresponding coefficient (if its equation is pushed into a one-parameter family of equations) is approximately. Hmm, let's see, so what the smallest coefficient be, on average? This problem is probably a well known problem, but here is a crude approximation: p^(1/2). Consider the probability that all coefficients have size larger than p^(1/2). For each individual coefficient the chance is (p - p^(1/2))/p = 1 - p^(-1/2). Now (1-p^(-1/2))^(p^(1/2)) is the probability that they all are larger, and this e^(-1). > different curve coefficients. There's overwhelming evidence that the > correlation is negligible, making coefficient size useless as a > predictor of the size of d---never mind the question of what any of > this has to do with ECC security. > > > but if we are going to be prudent, then why not avoid small > > coefficients too? > > Calling this "prudent" has zero justification from the extensive > literature on ECC security analysis. You could, with exactly the same [DB] I know, from the current literature, which is why I said I feel Curve25519 is safe. Again, I am only talking about unanticipated hypothetical attacks. > amount of justification, claim that _large_ coefficients are more > likely to be weak and that choosing small coefficients is the safest > strategy. [DB] Agreed to an extent: coefficient size is just an arbitrary way to test pseudo-random uniformity. For example, what is the P-value of the coefficient size of Curve25519? (Compared to random curves of any size). You correctly argue that coefficient-size is not a concern based on current literature, and that it improves efficiency, so therefore, it seems economical to ignore a low P-value for this statistic. Also, taking your argument further, one could apply any other arbitrary statistic. One could then contrive some weird statistic with a low P-value to deliberate reject some given curve. The point of coefficient size as a statistic is just that it is a nothing-up-my-sleeve statistic. I thought all that was implicit in what I said. > > What actually matters is that taking large coefficients imposes an > extra cost, both in cryptographic performance and in the human effort > required to rule out back doors. These are resources taken away from [DB] Back doors in the case P256, and pseudo-random curves, require unpublished attacks, perhaps surprising ones. (Aside: even if back doors are inserted by adversary #1, it may be possible for adversary #2 to find the attack too, so the concern may extend beyond the back door.) I am concentrating on the issue of unpublished attacks of elliptic curves, because that is one of logical pre-requisite to a back door. (An alternative logical pre-requisite is an unpublished attack on SHA-1, or how it is used in the generation of P256, but that is an orthogonal issue to Curve25519.) Brainpool and RFC 5639 recommends pseudo-random parameters to avoid unanticipated attacks, and you are arguing against this recommendation by anticipating from known attacks.
--------------------------------------------------------------------- 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