Re: [TLS] Safe ECC usage

"D. J. Bernstein" <djb@cr.yp.to> Tue, 01 October 2013 14:35 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 7B94211E8129 for <tls@ietfa.amsl.com>; Tue, 1 Oct 2013 07:35:35 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.114
X-Spam-Level:
X-Spam-Status: No, score=0.114 tagged_above=-999 required=5 tests=[AWL=0.112, BAYES_50=0.001, 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 2k-GfkXCP0kE for <tls@ietfa.amsl.com>; Tue, 1 Oct 2013 07:35: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 5980F11E8153 for <tls@ietf.org>; Tue, 1 Oct 2013 07:35:26 -0700 (PDT)
Received: (qmail 5094 invoked by uid 1011); 1 Oct 2013 14:35:20 -0000
Received: from unknown (unknown) by unknown with QMTP; 1 Oct 2013 14:35:20 -0000
Received: (qmail 11011 invoked by uid 1001); 1 Oct 2013 14:35:11 -0000
Date: 1 Oct 2013 14:35:11 -0000
Message-ID: <20131001143511.11010.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>
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: Tue, 01 Oct 2013 14:35:35 -0000

Dan Brown writes:
> You noted that curve sizes p,p-1, and p+1 are weak.
> These might be called special curve sizes, since for a random curve,
> of order p+d, we expect |d| around p^(1/2), and for these d is much
> smaller.

There is already overwhelming evidence that the size of d is not what
matters. For example, the next attack that you should learn is one that
breaks group order p+6m+2 if p=12m^2-1; in this case the gap from p is
more than 80% of its maximum possible value.

What's actually going on is that the additive group F_p has order p; the
multiplicative group F_p^* has order p-1; the group F_{p^2}^* has order
p^2-1; the group F_{p^3}^* has order p^3-1; etc. For roughly the first
dozen groups in this list we have discrete-logarithm algorithms fast
enough to worry about. There are known methods to "transfer" ECDLP over
F_p into these discrete-logarithm problems---but only if the EC group
has order dividing p, p-1, p^2-1, p^3-1, etc. This is why p+1 is a
problem (it divides p^2-1); it's why p+6m+2 is a problem if p=12m^2-1
(p+6m+2 divides p^3-1); etc.

> Of course, it's a logical leap to
> jump from small d to small curve coefficients,

It's even worse than a logical leap: CM theory shows that each d that
isn't extremely close to +-2 sqrt(p) corresponds to a huge number of
different curve coefficients. There's overwhelming evidence that the
correlation is negligible, making coefficient size useless as a
predictor of the size of d---never mind the question of what any of this
has to do with ECC security.

> but if we are going to be prudent, then why not avoid small
> coefficients too?

Calling this "prudent" has zero justification from the extensive
literature on ECC security analysis. You could, with exactly the same
amount of justification, claim that _large_ coefficients are more likely
to be weak and that choosing small coefficients is the safest strategy.

What actually matters is that taking large coefficients imposes an extra
cost, both in cryptographic performance and in the human effort required
to rule out back doors. These are resources taken away from things that
actually matter for security. If this were the only bad cryptographic
decision then it wouldn't be a huge problem, but unfortunately it's just
one of many things that people screw up.

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