Re: [TLS] Safe ECC usage

Dan Brown <dbrown@certicom.com> Fri, 18 October 2013 14:21 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 7AB1011E82B3 for <tls@ietfa.amsl.com>; Fri, 18 Oct 2013 07:21:58 -0700 (PDT)
X-Quarantine-ID: <TpiydFmrJS38>
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.479
X-Spam-Level:
X-Spam-Status: No, score=-2.479 tagged_above=-999 required=5 tests=[AWL=0.120, 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 TpiydFmrJS38 for <tls@ietfa.amsl.com>; Fri, 18 Oct 2013 07:21:53 -0700 (PDT)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) by ietfa.amsl.com (Postfix) with ESMTP id 8EB4B11E82AE for <tls@ietf.org>; Fri, 18 Oct 2013 07:21:50 -0700 (PDT)
Content-Type: multipart/mixed; boundary="===============1213953503=="
MIME-Version: 1.0
Received: from xct103cnc.rim.net ([10.65.161.203]) by mhs215cnc.rim.net with ESMTP/TLS/AES128-SHA; 18 Oct 2013 10:21:44 -0400
Received: from XCT111CNC.rim.net (10.65.161.211) by XCT103CNC.rim.net (10.65.161.203) with Microsoft SMTP Server (TLS) id 14.3.123.3; Fri, 18 Oct 2013 10:21:43 -0400
Received: from XMB117CNC.rim.net ([fe80::24f3:cc30:b596:7ca0]) by XCT111CNC.rim.net ([::1]) with mapi id 14.03.0123.003; Fri, 18 Oct 2013 10:21:43 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'nico@cryptonector.com'" <nico@cryptonector.com>
Thread-Topic: [TLS] Safe ECC usage
Thread-Index: AQHOxuJRxn3XJXmgAkKRAg2ZE6kwf5n3qq2ggAC0kACAAKQ6QIAAYI2AgAEXd7A=
Date: Fri, 18 Oct 2013 14:21:43 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5BEDA76@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> <810C31990B57ED40B2062BA10D43FBF5BEBAA5@XMB117CNC.rim.net> <CACsn0c=bSTMWwuHxD3eE3ABC_AxVRt-BOTybEr7umPQD5NB+cA@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF5BEC2EC@XMB117CNC.rim.net> <CAK3OfOhH8xORP9YbGaf5Ly59oJGddeqi4-bZt5TZcQWP=WAqng@mail.gmail.com>
In-Reply-To: <CAK3OfOhH8xORP9YbGaf5Ly59oJGddeqi4-bZt5TZcQWP=WAqng@mail.gmail.com>
Accept-Language: en-CA, en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
MIME-Version: 1.0
Cc: "'djb@cr.yp.to'" <djb@cr.yp.to>, "'tls@ietf.org'" <tls@ietf.org>
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: Fri, 18 Oct 2013 14:21:58 -0000

Nico Williams wrote:
> Dan Brown  wrote:
> > Why couldn't a new attack just work on one curve, namely Curve25519?
> > If I understand correctly, DJB has argued that the ECC theory and
> > experience would be evidence for a claim similar, but perhaps not as
> strong, as your claim.
>
> Let's say that there are single-curve attacks.  We don't know how many
> curves have such attacks, nor how hard it is to find such attacks for
> specific curves, or specific curves with such attacks.  Perhaps DJB
> does know, but either he got spectacularly lucky (if such attack/curve

Well, you've assumed here, just like others, that attacks are random.  If you 
assume that attacks are random, then you are right that manipulation is the 
main threat.

I've argued a few times that assuming random attacks is too optimistic, and 
also close to circular reasoning, and not supported by the evidence.

Remember, Curve25519, though free from the potential of malicious 
manipulation, is chosen, in part, for its special efficiency properties. 
These special properties may also given an attacker special advantages.  DJB 
has already argued, based on the existing attacks  -- not random attacks --  
that this is unlikely.   And I agreed.

Consider the ECC history.  After resisting all generic attacks, we have the 
following

Miyaji proposed special trace 1 curves.  A few years later, these were broken 
by the SASS attack.

Various proposed supersingular curves.  Later, they were broken by the MOVFR 
attacks.

But ever since then, it has been fairly quiet on the prime-field side of ECC.


> pairs are rare) or such attack/curve pairs are very common.  The latter
> would imply that all ECC is busted, in which case we needn't worry
> about whether Curve25519 is weak because we have bigger problems, so we
> must ignore this possibility when comparing curves to one another.

Furthermore, if we admit this possibility, i.e. to justify that the ECDLP over 
P256, then we should not just ignore it, but consider alternatives to ECC.

As I understand it, DJB has put forward his reasonable supposition of what the 
bigger problem is.  Maybe you should review it.

> That leaves the former, and now we need some estimate of frequency of
> such attack/curve pairs in order to decide if any one curve is weak.
>

Of course, it's very hard to make such estimates.  Even so, there is merit in 
making such estimates.  They have to been based on evidence.  There two types 
of evidence here:

1.  The lack of new attacks, despite efforts and incentives.

2.  The existing attacks, e.g. MOVFR and SASS.

Intuition might entirely dismiss inferring estimates from this evidence set, 
as wild speculation.  More formally, intuition would be saying the inference 
drawn from the set have low confidence.

---------------------------------------------------------------------
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.