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.