Re: [TLS] Safe ECC usage

"D. J. Bernstein" <djb@cr.yp.to> Wed, 02 October 2013 16:21 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 A51A021F9D12 for <tls@ietfa.amsl.com>; Wed, 2 Oct 2013 09:21:19 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.598
X-Spam-Level:
X-Spam-Status: No, score=-2.598 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, 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 F9M7IauoJQtW for <tls@ietfa.amsl.com>; Wed, 2 Oct 2013 09:21:08 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id 4468621F8B04 for <tls@ietf.org>; Wed, 2 Oct 2013 09:19:49 -0700 (PDT)
Received: (qmail 7417 invoked by uid 1011); 2 Oct 2013 16:19:48 -0000
Received: from unknown (unknown) by unknown with QMTP; 2 Oct 2013 16:19:48 -0000
Received: (qmail 8126 invoked by uid 1001); 2 Oct 2013 16:19:44 -0000
Date: 2 Oct 2013 16:19:44 -0000
Message-ID: <20131002161944.8125.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>
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, 02 Oct 2013 16:21:23 -0000

Dan Brown writes:
> Brainpool and RFC 5639 recommends pseudo-random parameters to avoid
> unanticipated attacks, and you are arguing against this recommendation
> by anticipating from known attacks.

No, and no.

The Brainpool standard (from which RFC 5639 is derived) says that the
unexplained NIST seeds leave "an essential part of the security analysis
open" and that this is a "major issue." I completely agree with this.

There are two reasonable ways to address this problem. One way, which
Brainpool uses, is to generate curves "in a pseudo-random manner using
seeds that are generated in a systematic and comprehensive way," subject
of course to other requirements. Another way, which I use, is to take
the smallest possible curves meeting the other requirements.

Both of these approaches are clear improvements over what NIST/NSA did.
As Brainpool puts it, choosing fully explained seeds will "enhance trust
in the recommended curves." Choosing smallest curves has the same
effect. There's no contradiction between these statements.

There is zero reason to believe that either of these approaches is more
secure than the other. There is, in particular, zero reason to believe
that either approach is safer against "unanticipated attacks." You are
wrong to attribute any such belief to the Brainpool standard; the
document says no such thing. All available evidence is that both
approaches are fine; if we've missed an attack then we have no way to
guess whether the attack is more likely to apply to one curve or to the
other.

My reason for not taking the Brainpool approach is that it has a rather
heavy cost. We have enough problems deploying secure crypto without
incurring unnecessary costs; if we can afford extra costs then I'd
rather put those into taking steps that actually matter for security,
such as adding defenses against quantum computers. So I prefer the
second approach. Conversely, Brainpool does not discuss the second
approach, and does not state any reason to avoid the approach. 

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