Re: [TLS] Safe ECC usage
Dan Brown <dbrown@certicom.com> Wed, 16 October 2013 19:37 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 DDC5911E8260 for <tls@ietfa.amsl.com>; Wed, 16 Oct 2013 12:37:25 -0700 (PDT)
X-Quarantine-ID: <sxKbiTrHfRZR>
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.499
X-Spam-Level:
X-Spam-Status: No, score=-2.499 tagged_above=-999 required=5 tests=[AWL=0.100, 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 sxKbiTrHfRZR for <tls@ietfa.amsl.com>; Wed, 16 Oct 2013 12:37:20 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id 16C5511E8181 for <tls@ietf.org>; Wed, 16 Oct 2013 12:36:53 -0700 (PDT)
Content-Type: multipart/mixed; boundary="===============1319045333=="
MIME-Version: 1.0
Received: from xct103cnc.rim.net ([10.65.161.203]) by mhs213cnc.rim.net with ESMTP/TLS/AES128-SHA; 16 Oct 2013 15:36:50 -0400
Received: from XCT104CNC.rim.net (10.65.161.204) by XCT103CNC.rim.net (10.65.161.203) with Microsoft SMTP Server (TLS) id 14.3.123.3; Wed, 16 Oct 2013 15:36:49 -0400
Received: from XMB117CNC.rim.net ([fe80::24f3:cc30:b596:7ca0]) by XCT104CNC.rim.net ([::1]) with mapi id 14.03.0123.003; Wed, 16 Oct 2013 15:36:49 -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: AQHOxuJRxn3XJXmgAkKRAg2ZE6kwf5n3qq2g
Date: Wed, 16 Oct 2013 19:36:48 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5BEBAA5@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>
In-Reply-To: <20131012003058.669.qmail@cr.yp.to>
Accept-Language: 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: Wed, 16 Oct 2013 19:37:26 -0000
D. J. Bernstein writes: > Dan Brown writes: > > if an attack affects all random curves, excluding Curve25519, then > > basically ECC would be no more, > > Here are six examples of attacks that already affect the security level > of the vast majority of elliptic curves: > > * Shanks's baby-step-giant-step attack. Drastic reduction in the > number of arithmetic operations required to break ECDLP. There's > no > defense against this attack. > > * The Pohlig--Hellman attack. Further drastic reduction in the > number > of arithmetic operations required for _most_ curves---but not all; > there are occasional special curves that resist the attack. > > * Twist attacks. Again applicable to _most_ curves---but, again, not > all; again there are occasional special curves that resist the > attack. > > * Negating rho. Okay, it's just a 1.4x attack speedup, but I can't > see any justification for you to ignore it. There's no defense > against this attack. > > * Pollard's rho attack. Drastic reduction in _memory_ consumption, > making elliptic curves much easier to break (in reality, and in > sensible cost metrics). There's no defense against this attack. > > * The van Oorschot--Wiener parallel rho attack. Drastic reduction in > _communication_, allowing efficient parallelization, again making > elliptic curves much easier to break. There's no defense against > this attack. > > So you're wrong in implying that there haven't already been attacks > that affect "random curves". Do we respond by discarding ECC, as you Yes, those are pretty good examples favouring special over random, but they are not pertinent to my analysis. The S, PH, P, and vOW attacks above affect any group over which one does DH/DL crypto. They are not ECC-specific. Resisting these attacks and doing DH/DL crypto requires ensuring the parameters resist the attacks. So, any DH/DL system needs to use a group whose order has a prime factor of bit size at least twice the desired security level. If I was an opponent of DH/DL, let's say RSA or NTRU, I might use these to argue against DH/DL. One reason, despite such arguments, to still use DH/DL is forward secrecy. I don't know if NTRU provides forwards secrecy as efficiently as DH/DL. I made a mistake in my previous email about the class of curves to which I restricted: I forgot to specify that I meant random EC curves that meet these generic conditions. When I say "curve" in the context of ECC, I assume this condition. Maybe you have a more mathematically correct perspective, and read random curve to include these vulnerable to PH. The twist attack is just as easily addressed by checking the point before applying one's private key to it. (Unless I misunderstand.) Yes, implementation fault resistance is important, but it is secondary to algorithm security, because an insecure algorithm cannot be fixed any kind of implementation technique. In this case, my personal opinion is that the most reasonable guesses at the difference in algorithm security here are so slight, then implementation fault resistance benefits of Curve25519 have much merit. In other words, I wouldn't object to that argument. The negation attack is considerably weaker than the MOV and SASS attacks, and in any case it seems to be the price to pay for any form of ECC. So, it cannot be used to choose between curves. To summarize, once one sets up the basic DH/DL requirements, and tries to make a choice of ECC for this purpose, then the attack count is still 0 random, and 2 special (or 1 if you prefer to merge MOVFR and SASS into a transfer attack). Based on this score, if I had to guess what the next attack would be, then I would guess special. An attack on random would be a breakthrough. Therefore, trying to choose a random curve is a best guess approach. > suggest? > Of course not. We respond by choosing parameters to resist the attacks: > > * Choose _extremely_ special curves (we're talking about one curve > in > a thousand here!) that defend against twist attacks and the > Pohlig--Hellman attack. > > * Choose primes far above 200 bits to defend against the other four > attacks. > > Of course, we also take time to further investigate and build > confidence that the security story is stable. All of these attacks have > been known for more than ten years (three of them even before ECC was > published), as have the two attacks that you mentioned for extremely > rare curves. > People working on attacks have found interesting improvements for > extension fields, higher genus, etc., but seem to have run out of ideas > for attacking prime-field ECC. > > > So far, there no are 0 (*) attacks against random curves, and 2 > > against special curves: the MOV and SASS attacks. I view this as > > quite good evidence in favour of random curves, over special curves. > > That's because you're simply ignoring all the contrary evidence. For > example, if you insist on using random curves then Pohlig--Hellman will > damage your security, probably quite severely. That's why everyone is > actually using rare curves that resist the Pohlig--Hellman attack. I already answered this above, but in brief: PH must resisted by all forms of DH/DL crypto, so is not a basis to choose between EC curves. And yes again, I did forgot to mention in my definition of random curves the condition that the group order be divisible by a large prime. This is a fact that I take for granted. > > In other words, rather than taking the uniform distribution over all > elliptic curves of whatever size, ECC users are massively biasing the > distribution of elliptic curves. The biased distribution discards the > vast majority of elliptic curves: at least the curves vulnerable to > Pohlig--Hellman, and nowadays also the curves that aren't twist-secure. > Every sane risk analysis will conclude that this bias is a good idea. Not that it matters, but my psychiatrist let me go home. > > I say that it's a good idea to narrow the distribution even more, in > fact down to a single curve, by taking the _smallest_ curve coefficient > within the usual massively biased distribution. That's what Curve25519 > does. This isn't just a performance win; it also prevents the sort of > manipulation that's clearly possible for someone who claims to be > "randomly" choosing curves from the wider distribution. > > Now imagine that there's no manipulation. How does this single-curve > distribution compare in security to the larger (massively biased) > distribution against some unknown attack? The correct answer is that we > have no idea---maybe it's more secure, maybe it's less secure, maybe > it's the same. Uncertainty, "no idea", about unknown attacks is a given, but we should still try to resist them, even if that means making assumptions and guessing. Provably secure algorithm try to do this. Previously unknown attacks are known pop up, occasionally. But, we also give weight to the effort that people have exerted in trying to find attacks, to infer the unlikelihood of new attacks being discovered. > > You keep trying to trivialize this question by promoting the myth that > more uniformity is safer. You present this as some sort of ill-defined > dichotomy between "random" and "special", with "random" clearly being > better. You take every break of a small curve class as support for your > position, retroactively declaring the curves in the class to be > "special", while you ignore the glaring counterexamples such as Pohlig- > -Hellman. As I said above, I take PH resistance for granted in any DH/DL, and a built into the ECC. > > > You gave an example that, under reasonable assumptions, with 2^(-30) > > probability the ECDLP in Curve25519 could be solved in 2^64 > > computations. > > No. What I actually wrote was "Suppose NSA knows---and knew in the late > 1990s---a cost-2^64 attack that breaks one P1363-compliant 256-bit > curve in a billion". I gave examples to illustrate that this "wouldn't > be out of line with the spectrum of known ECC attacks". I then > explained how this attack would have allowed NSA to _guarantee_ > weakness of the NIST > P-256 curve, while for an honestly generated curve the situation is > obviously quite different. Why was I wrong? Is it because Curve25519 is not P1363-compliant? > > By misstating my assumptions as being specific to Curve25519, you're > omitting the critical security impact on NIST P-256, and you're also > promoting a misconception that ECC security analysis is curve-specific. > Yes, your supposition applies to any fixed curve, including Brainpool and Curve25519. Yes, it is not curve-specific. > > I do not see how those assumptions are reasonable, but even so, if > > 2^30 people use Curve25519, then is that a good risk? > > I have no idea what you think you mean by "a good risk" (and I also Good meaning sufficiently small compared to the benefit. > have no idea why you're talking about the number of people---the > discussion is about weak curves, not weak keys). In the situation that If an algorithm is weak, then all its users lose. My heuristic is that the ensuing loss is proportional to the number of (human) users. Such heuristics might be useful to define what a good risk is. Granted for most risks we have make a lot of guessing, but it still has merit to try. > I actually described, there's no reason to think that the risk is > different for > Curve25519 and for an _honestly_ generated NIST P-256. The problem is See all my arguments above. > that we don't know whether NIST P-256 was honestly generated. Agreed that is a problem. I am still surprised that you think it so reasonable a supposition. I forgot now, what attacks you quoted to support that position. Was it PH? > > > Do you feel that the system-wide risk for RSA, or integer DH is > comparable? > > There are improvements in index calculus all the time. Those have been > continually dragging down the security level of RSA, which in turn has > been dragging down the performance of RSA, which is exactly why modern > RSA is so much slower than ECC. > Yes, that's well-known, but is it reasonable to suppose that, with probability 2^(-30) some lurking adversary knows an attack a 2^64 cost attack against each possible RSA key? I don't see any evidence to support that reasonability of the weakness in the whole RSA algorithm. (Weak low-density classes of RSA keys, maybe but that's different.)
--------------------------------------------------------------------- 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