Re: [TLS] Safe ECC usage
Dan Brown <dbrown@certicom.com> Mon, 04 November 2013 20:21 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 3AB3F21E808D for <tls@ietfa.amsl.com>; Mon, 4 Nov 2013 12:21:35 -0800 (PST)
X-Quarantine-ID: <AoemJk4hVLjA>
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.32
X-Spam-Level:
X-Spam-Status: No, score=-2.32 tagged_above=-999 required=5 tests=[AWL=-0.021, BAYES_00=-2.599, SARE_WEOFFER=0.3]
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 AoemJk4hVLjA for <tls@ietfa.amsl.com>; Mon, 4 Nov 2013 12:21:30 -0800 (PST)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id BEE6C11E82CA for <tls@ietf.org>; Mon, 4 Nov 2013 12:21:28 -0800 (PST)
Content-Type: multipart/mixed; boundary="===============0766314385=="
MIME-Version: 1.0
Received: from xct101cnc.rim.net ([10.65.161.201]) by mhs211cnc.rim.net with ESMTP/TLS/AES128-SHA; 04 Nov 2013 15:21:21 -0500
Received: from XCT110CNC.rim.net (10.65.161.210) by XCT101CNC.rim.net (10.65.161.201) with Microsoft SMTP Server (TLS) id 14.3.123.3; Mon, 4 Nov 2013 15:21:21 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT110CNC.rim.net ([::1]) with mapi id 14.03.0123.003; Mon, 4 Nov 2013 15:21:21 -0500
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: AQHOxuJRxn3XJXmgAkKRAg2ZE6kwf5n3qq2ggAC0kACAAKQ6QIAB8gaAgAcmnxGAE3vA8A==
Date: Mon, 04 Nov 2013 20:21:19 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5BFA5CB@XMB116CNC.rim.net>
References: <523E176F.3050304@gmail.com> <52616365.1080108@nthpermutation.com> <20131023094710.32763.qmail@cr.yp.to>
In-Reply-To: <20131023094710.32763.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: Mon, 04 Nov 2013 20:21:35 -0000
Hi again ECC in TLS enthusiasts, Sorry to raise this very theoretical issue yet again, but I realized a stronger argument for one of my claims in this thread. Claim: The Brainpool 256-bit curve, as a remedy to a hypothetically manipulated P256, provides more security assurance than Curve25519, assuming faultless implementations. Mildly formal argument for the claim above: P256: Let us call the curve weakness, which we are hypothesizing here that the P256 seed has been exhaustively searched, i.e. manipulated, to have: the spectral weakness (a term inspired by spectre and prism). For simplicity, let us initially assume that the best available process to manipulate P256 was exhaustive search of seed, and this had an a priori expected running time of 2^w trial seeds. (A more complex analysis might go further and postulate a weakness in the P256 curve generation algorithm, perhaps even in the SHA1 hash function used, but in this case I will still use 2^w for the number of seeds that must be tried under this more complicated situation.) Brainpool: Under the fairly reasonable heuristic assumptions below, one can argue that the probability the Brainpool 256-bit curve is affected by the spectral weakness with probability about 2^(-w). The heuristic assumptions here are the independence of spectral weakness from the curve generation algorithm and from the digits of pi and e, or any similar fundamental constants (with the wiggle contributing the about). These assumptions are fairly mild assumption about the spectral weakness, in my opinion. Curve25519: It can also be argued (and, as I understand it, has already been argued on the list) that Curve25519 is affected by the spectral weakness with probability about 2^(-w), under the either of the following assumptions: (1) the spectral weakness affects curves uniformly, or (2) the spectral attack would be very similar to known attacks, e.g. PH, MOV and SASS, and that the non-random features that Curve25519 displays, such as small coefficients, have no bearing whatsoever on those attacks, thereby rendering Curve25519 as safe as any random curve. Brainpool vs Curve25519: Both of the assumptions above made for Curve25519 on the spectral attack are formally, and intuitively, stronger than the mild assumption made for Brainpool curve, therefore the assurance that Curve25519 provides is weaker than that of Brainpool. Much more informal asides: As I, and others, have noted already in this thread, Curve25519 has very good resistance to 1st person attacks, i.e. it has rigidity, perhaps even more than Brainpool. Unfortunately, that does not sufficient to rule out the spectral weakness affecting Curve25519, at least under the arguments above, except under quite strong assumptions. Besides, I find it unreasonable to suspect a 1st person attack from Curve25519 because even in the very unlikely event that DJB knew what the spectral weakness, or even some other weakness, was, I feel certain he would reveal it, not exploit it. At one point in this thread, I mistakenly tried to apply something like the semiformal argument above for future attacks, rather than for the spectral weakness. Indeed, under the spectral attack hypothesis, it is unnecessary to argue, or even further speculate, about the nature of a future attack, e.g. whether they are more likely to affect random or special curves. Rather, under the spectral attack hypothesis, we presume that an attack already affects P256, and we may attempt to avoid it when choosing alternative curves, and must avoid it as best as possible if we offer those curves as being safe against the spectral attack. In other words, when I argued that it was more prudent to use random curves, e.g. Brainpool than to use special curves, e.g. Curve25519, merely because one has to be pessimistic as possible in one's assumptions, I was right about spectral attack, but wrong about future attacks. Just to be clear, this is not to say that I think it likely, or that the evidence points to it being likely, for the spectral weakeness to affect Curve25519. What I am saying is that Brainpool seems to be designed, whether intentionally or not, in such a way to offer better assurance of avoiding the spectral weakness. The Brainpool curve is a fixed curve, but seems to be nearly as pseudorandom as a fixed curve could be. Nonetheless, using a random curve for every exchange, or pair of users, ought to be even safer than Brainpool, but would be too inefficient, for example, due to the cost of point counting. But that issue seems to independent of the arguments for the claim above. I alluded above to a more complicated situation in which the curve generation algorithm is weak. This seems unlikely for many reasons, but this issue is independent of the main claim that Curve25519 relies on a strong assumption about the spectral attack. Also, this issue starts to become a different one from pure manipulation. Further, if this hypothesis goes so far as to postulate invertibility of SHA1, then we may need further consider other criteria on elliptic curves, such as resisting Cheon-type attacks. Of course, many reasons remain to doubt the existence of a spectral attack, including: the extensive research efforts into ECC, the risk of standardizing curves one knows to be weak, many other curves and algorithms from the same sources not known to be weak or subject to manipulation. It may be worthwhile for TLS to offer its users more guidance than just "here are some safe algorithms you can use". Some TLS users may have a reasonable expectation of security from the available TLS algorithms, and perhaps even security levels, which is reasonable if only because of the S in TLS. Some users may want to make their own decisions about security. Yet others may seek guidance for specific security goals, hoping to find it the TLS specs. Naturally, nobody has a very strong incentive to commit to too strong security claims. If TLS is to offer various curves as providing 128-bit security, then it might point to what the provisos behind each to guide users in their choice. Suggestions for further discussion: Perhaps, I am missing or misunderstanding an argument for Curve25519 avoiding the hypothesized spectral weakeness. Please correct me as needed. Perhaps, my security analysis for Brainpool is unconvincing or too vague. Maybe we can discuss further. I suspect one could formalize it better, i.e. random oracle model, pseudorandom functions, etc. Certainly, there is a logical leap from pseudorandom fixed to random, but this independent of the arguments above. Perhaps, one really can quantify the amount of wiggle room in the curves for Brainpool and Curve25519 to get slightly different probabilities from 2^(-w), with Curve25519 having a lower probability. That does not override the stronger assumptions being necessary, but may be an argument that the relative security between the two is incomparable. Best regards, Dan
--------------------------------------------------------------------- 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