[Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom

Dan Brown <dbrown@certicom.com> Mon, 13 January 2014 16:55 UTC

Return-Path: <dbrown@certicom.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com []) by ietfa.amsl.com (Postfix) with ESMTP id A1DEE1AE192 for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 08:55:47 -0800 (PST)
X-Quarantine-ID: <jYKHVi6taqvq>
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: -1.899
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id jYKHVi6taqvq for <cfrg@ietfa.amsl.com>; Mon, 13 Jan 2014 08:55:44 -0800 (PST)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com []) by ietfa.amsl.com (Postfix) with ESMTP id 2FFBF1AE16E for <cfrg@irtf.org>; Mon, 13 Jan 2014 08:55:43 -0800 (PST)
Content-Type: multipart/mixed; boundary="===============0182478644=="
MIME-Version: 1.0
Received: from xct108cnc.rim.net ([]) by mhs213cnc.rim.net with ESMTP/TLS/AES128-SHA; 13 Jan 2014 11:55:23 -0500
Received: from XCT112CNC.rim.net ( by XCT108CNC.rim.net ( with Microsoft SMTP Server (TLS) id; Mon, 13 Jan 2014 11:55:22 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT112CNC.rim.net ([::1]) with mapi id 14.03.0158.001; Mon, 13 Jan 2014 11:55:22 -0500
From: Dan Brown <dbrown@certicom.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Thread-Topic: [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
Thread-Index: Ac8Qflj1a4qQ887tT6aHk4eH+te9FQ==
Date: Mon, 13 Jan 2014 16:55:21 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5C1EA1B@XMB116CNC.rim.net>
Accept-Language: en-CA, en-US
X-MS-Has-Attach: yes
x-originating-ip: []
MIME-Version: 1.0
Subject: [Cfrg] [CFRG] Safecurves v Brainpool / Rigid v Pseudorandom
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 13 Jan 2014 16:55:47 -0000

Last week I wrote that I would soon write up my disagreements with the safe
curves site.  


My first disagreement is written up below, but first two editorial issues:


-        My last email was in the context of Watson's draft spec for the
Chicago (Bernstein?) curves, but I would like to detach the issue from the
I-D.  My comment about the reference in Watson's I-D to a website was just
an editorial comment.    


-        These technical issues that I hope CFRG discusses just might be
resolved and written into a CFRG I-D cataloging of elliptic curves and their
relative merits and so on, which should be independent of Watson's spec for
the Chicago curves.  For now, I opted to discuss via email list, rather than
placing these arguments into my own one-sided individual I-D.  Please advise
me if such an I-D is preferred to email.


Today, I checked that




characterizes Curve25519 as "fully rigid", and brainpoolP256t1 as "somewhat
rigid", and more critically, implies the latter to be at greater risk to a
secret attack on the ECLDP.  (Am I misinterpreting?)


On November 4, 2013, I wrote the following email to the TLS list




which claims that BrainpoolP256t1 has a lower risk than Curve25519 of resist
a hypothetical secret attack on a maliciously generated NIST P256.  These
seems to an opposite conclusion from that implied by the safecurves.  Hence
my disagreement.


The gist of my argument was that pseudorandomness can avoid a class of
unknown weak curves, with a certain probability related to the density of
the weak class from the pool of curves which it is drawn.  


Yes, rigidity helps more to prevent malicious generation of the curve.  I am
not disagreeing with the safecurves site on that point.  


I am saying that for an honest generator of a new curve, who is thoroughly
worried about some secret attack that could affect a maliciously-generated
P256, using a random curve is her best recourse, followed by pseudorandom
curve (as in brainpool). Rigidity is on par with arbitrary regeneration for
convincing oneself that one's chosen curve resists this secret attack, but
rigidity is better for convincing other parties.


In the terms of the safecurves site, I'd say that, first, it omits this
important argument, that is okay in the sense that the site serves to put
the best foot forward. Second it implies wrong conclusions, which is a
slight mistake and ought to be corrected. Anyway, I hope that CFRG and IETF
will consider a more balanced argument, and the users of Curve25519 are
adequately informed.  That is, I hope that CFRG can provide peer review.


Is it fair to say that the possibility of P256 being malicious is one of the
main reasons for the recent rise in popularity of Curve25519?  Or is the
pattern between recent news and standards adoption just a coincidence?  If
this is the main reason, then we should look into it carefully.


Not to lose focus: I hope to start other emails threads on other less
important issues, e.g. how much risk is there that P256 is weak and the
impact on the rest of ECC, random v special, how special are safecurves,
relative importance of side-channel resistance v DLP, risks of parameters v
keys, do attacks target curves, random v pseudorandom, and so on.  So, I
hope that that this thread can be kept focussed on this one issue.  


To summarize my position, and divide into candidate pieces for discusssion: 


1.      Pseudorandomness protects effectively (as possible for ECC) against
the spectral weakness necessary to hypothesize a malicious NIST P256.

2.      Rigidity protects against the spectral weakness only by invoking
assumptions about spectral weakness (*).

3.      Protecting against attacks, such as the hypothetical spectral
weakness, is more important than (subsumes?) protecting against malicious


Regarding (*), the assumptions about the spectral weakness, I may wish to
start a separate thread to discuss.  It seems that the safecurves site does
not say too much about it, but there was some pertinent email discussion on
the TLS list, that I think merits some consideration for the CFRG.


Best regards,


Daniel Brown

Research In Motion Limited 






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.