Re: [TLS] Safe ECC usage

"D. J. Bernstein" <djb@cr.yp.to> Sat, 05 October 2013 19:30 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 B23B221F90CF for <tls@ietfa.amsl.com>; Sat, 5 Oct 2013 12:30:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.518
X-Spam-Level:
X-Spam-Status: No, score=-1.518 tagged_above=-999 required=5 tests=[AWL=-0.780, BAYES_20=-0.74, 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 nLt5rU5l9V6e for <tls@ietfa.amsl.com>; Sat, 5 Oct 2013 12:30:15 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id 2BB0721F90AC for <tls@ietf.org>; Sat, 5 Oct 2013 12:30:11 -0700 (PDT)
Received: (qmail 12698 invoked by uid 1011); 5 Oct 2013 19:30:09 -0000
Received: from unknown (unknown) by unknown with QMTP; 5 Oct 2013 19:30:09 -0000
Received: (qmail 27062 invoked by uid 1001); 5 Oct 2013 19:29:50 -0000
Date: Sat, 05 Oct 2013 19:29:50 -0000
Message-ID: <20131005192950.27059.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> <20131003010455.17185.qmail@cr.yp.to> <810C31990B57ED40B2062BA10D43FBF5BDECA6@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: Sat, 05 Oct 2013 19:30:19 -0000

Dan Brown writes:
> it is also reasonable to assume that NSA knows of an attack A
> but is unwilling to reveal it, and manipulated P256 to avoid A

Sure. In BigBrotherLand, the eavesdropper Eve is actually a big fan of
the innocent users Alice and Bob, and is helping protect them against
hidden weaknesses in their communication system.

However, our job as _cryptographers_ is to tell Alice and Bob how to
protect themselves against the possibility of _bad_ behavior by Eve.
That's why all these ECC standards are advertising the "verifiable"
randomness of the NIST curves---they're claiming that the curves are
protected against bad behavior by NSA's Jerry Solinas. That's also why
people are unhappy to learn that the advertising is false.

When we see a protocol that turns out to have Eve as a trusted third
party with the power to compromise security, we fix the protocol. We
don't say "Well, gee, maybe Eve is actually helping our security."

> The Brainpool curves have some kind of justification, albeit maybe not
> a full-fledged proof.  In other words, to me, the Brainpool approach
> presents some kind of best-we-can-do-effort to resist attacks not yet
> known to us.

No, it doesn't. Maybe an unknown attack is _more_ likely to break
brainpoolP256r1 than to break Curve25519. You keep using words like
"best" and "prudence" and "advantage"; but you have zero justification
for any of this. You keep

   * misrepresenting brainpoolP256r1 as a random curve and
   * stating the "random is safer" myth in several different ways;

do you not realize that this myth was solidly debunked several years
ago? Section 11 of http://eprint.iacr.org/2008/390.pdf presents several
clear counterexamples; do you dispute those counterexamples?

If you think there's some reason that brainpoolP256r1 is more like the
examples where randomness helps security, rather than the examples where
randomness hurts security, then you should say what that reason is. You
can't simply pretend that the counterexamples don't exist.

By the way, I also don't see anything in the Brainpool document along
the lines that you're claiming. For example, the document never claims
that its primes are more secure than "special" primes; it clearly states
that it avoids "special" primes "to avoid patented fast arithmetic."

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