Re: [TLS] Safe ECC usage

"D. J. Bernstein" <djb@cr.yp.to> Thu, 03 October 2013 01:05 UTC

Return-Path: <57756671618275-ietf-tls@sublist.cr.yp.to>
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 C2D2721F8C0C for <tls@ietfa.amsl.com>; Wed, 2 Oct 2013 18:05:41 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.298
X-Spam-Level:
X-Spam-Status: No, score=-2.298 tagged_above=-999 required=5 tests=[AWL=-0.300, BAYES_00=-2.599, J_CHICKENPOX_21=0.6, UNPARSEABLE_RELAY=0.001]
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 VDu7Ivlyi07g for <tls@ietfa.amsl.com>; Wed, 2 Oct 2013 18:05:30 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id 44B5921F9EE1 for <tls@ietf.org>; Wed, 2 Oct 2013 18:05:08 -0700 (PDT)
Received: (qmail 8310 invoked by uid 1011); 3 Oct 2013 01:05:06 -0000
Received: from unknown (unknown) by unknown with QMTP; 3 Oct 2013 01:05:06 -0000
Received: (qmail 17186 invoked by uid 1001); 3 Oct 2013 01:04:55 -0000
Date: 3 Oct 2013 01:04:55 -0000
Message-ID: <20131003010455.17185.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: tls@ietf.org
Mail-Followup-To: tls@ietf.org
Automatic-Legal-Notices: See http://cr.yp.to/mailcopyright.html.
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>
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 01:05:41 -0000

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.

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.

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],

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.

---D. J. Bernstein
   Research Professor, Computer Science, University of Illinois at Chicago