Re: [Cfrg] Progress on curve recommendations for TLS WG

Dan Brown <dbrown@certicom.com> Fri, 15 August 2014 15:44 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 [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 97B791A03AB for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 08:44:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id n-IDbXoTW8DG for <cfrg@ietfa.amsl.com>; Fri, 15 Aug 2014 08:44:07 -0700 (PDT)
Received: from smtp-p01.blackberry.com (smtp-p01.blackberry.com [208.65.78.88]) by ietfa.amsl.com (Postfix) with ESMTP id 973151A6EEF for <cfrg@irtf.org>; Fri, 15 Aug 2014 08:44:06 -0700 (PDT)
Received: from xct102cnc.rim.net ([10.65.161.202]) by mhs211cnc.rim.net with ESMTP/TLS/AES128-SHA; 15 Aug 2014 11:44:05 -0400
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT102CNC.rim.net ([fe80::2066:5d4f:8c45:af55%17]) with mapi id 14.03.0174.001; Fri, 15 Aug 2014 11:44:05 -0400
From: Dan Brown <dbrown@certicom.com>
To: "'cfrg@irtf.org'" <cfrg@irtf.org>
Thread-Topic: [Cfrg] Progress on curve recommendations for TLS WG
Thread-Index: AQHPrSkVFDDUD0tW0keHIpwhcB27wpvR3EOAgAAXPgCAAB3vgP//zJRg
Date: Fri, 15 Aug 2014 15:44:04 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF5CCCF75@XMB116CNC.rim.net>
References: <20140801013659.11640.qmail@cr.yp.to> <53EDEB0D.9040304@secunet.com> <925e123f-d396-443f-9fc7-b1f6601bcd4c@email.android.com> <53EE17A9.7080408@secunet.com>
In-Reply-To: <53EE17A9.7080408@secunet.com>
Accept-Language: en-CA, en-US
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.249]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_00EC_01CFB87E.36E52250"
MIME-Version: 1.0
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/gtmMcjFvpO8P9LXO52F28zD_uIY
Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
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: Fri, 15 Aug 2014 15:44:10 -0000

> -----Original Message-----
> From: Cfrg [mailto:cfrg-bounces@irtf.org] On Behalf Of Johannes Merkle
> Sent: Friday, August 15, 2014 10:23 AM
> 
> are contra-productive. I am quite sure that one could also construct a
"one in a
> million curve" using a seed-less approach very similar to curve25519, but
this
> would only introduce more unjustified discredit and FUD.
> 

[DB] I thought I already did this, and more, in my email to this list with
subject "Bad and Rigid Curve".  I found a one-in-2^128 curve that is
seed-less.  Oh well, I suppose I cannot expect everybody to read everything
I write, or at least agree with it.

But maybe the point was that BARC seemed insufficiently similar to
Curve25519. 

Here's something more similar to Curve25519, but I need to count points and
factor, so I've use Sage, whose session I manually re-typed here (to save
myself from learning how to cutting-and-paste from the VM I'm using):

sage: E = EllipticCurve(GF(2^255-19),[0,1,0,1,0]); E
y^2 = x^3 + x^2 + x
sage: factor(E.order())
2^4 * 67 * 557233194274943 * 2014538529699005948261 *
4811068624484807686053494972215370277
sage: log(481106862448480768605349497215370277.0,2.0)
112

This curve is similar to Curve25519, same field, same equation shape, but
smaller x^2 coefficient, namely 1 instead of the value used in Curve25519,
which is about half a million, if I recall correctly.

If this curve had been proposed before the Pohlig--Hellman attack had been
made public, then it would be vulnerable to 2^56 step secret attack, yet the
best public attack would have been 2^128-step Pollard rho.