[Cfrg] Curve25519 (and Safecurves more generally)

Watson Ladd <watsonbladd@gmail.com> Tue, 07 January 2014 01:37 UTC

Return-Path: <watsonbladd@gmail.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 D7AFA1AE3B8 for <cfrg@ietfa.amsl.com>; Mon, 6 Jan 2014 17:37:55 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.101
X-Spam-Status: No, score=-0.101 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id 8VcPZmF7ohD8 for <cfrg@ietfa.amsl.com>; Mon, 6 Jan 2014 17:37:54 -0800 (PST)
Received: from mail-wg0-x235.google.com (mail-wg0-x235.google.com [IPv6:2a00:1450:400c:c00::235]) by ietfa.amsl.com (Postfix) with ESMTP id F065A1AE3BA for <cfrg@irtf.org>; Mon, 6 Jan 2014 17:37:53 -0800 (PST)
Received: by mail-wg0-f53.google.com with SMTP id k14so16560387wgh.20 for <cfrg@irtf.org>; Mon, 06 Jan 2014 17:37:44 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=l5Pa/aupInhcYiVQrI7Lc1GTfD6GWfmxLNwqyo1gVxA=; b=wCdHY9fGxeLp5SInC+alUQCBdzZq3WHzRqgNqMH4BeSpN4BbvQ36nlLiHLxU9YGCO6 pv45k2mgS9kdOQyzYJ28ssx4GGrtPUeV4Izzml2esWABkawBFBNZh7fzEwwbnIB+5mWQ Y0zGdS4r62o56kKMc7acFDEaUnsQdrg7b5GxRbyBBv7zM++okkiuxjwpeOU4Hi+AIh/x kTJ+hh0mla6p5WgJQ3wQ3AmRrropVKQss/ZUjLDbw7Ri5+/CQKzXsqoil/qEE3cndgwh cRk0WHa+wlg6y+sb2MUZu1z4pXX1bXYPT1i++o6lrO2gU+HV9+9A+wzojq3dyHPQS5+P Fxlw==
MIME-Version: 1.0
X-Received: by with SMTP id dd4mr14748417wib.20.1389058664802; Mon, 06 Jan 2014 17:37:44 -0800 (PST)
Received: by with HTTP; Mon, 6 Jan 2014 17:37:44 -0800 (PST)
Date: Mon, 6 Jan 2014 17:37:44 -0800
Message-ID: <CACsn0c=NfuOhs33u-UhtLoeMG2PSOmF3tiWgE+bbkUqo5paQqQ@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset=UTF-8
Subject: [Cfrg] Curve25519 (and Safecurves more generally)
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: Tue, 07 Jan 2014 01:37:56 -0000

Paul Lambert has stated that industry doesn't have the guts to take
responsibility for using this in products and would like to blame us
if it goes bad, since they can't blame NIST. (In what other industry
does "we don't stand behind our products, because we don't have the
expertise to determine how good they are" count as acceptable?)

The question to be answered is as follows: is the curve
y^2=x^3+486662x^2+x over the prime field 2^{255}-19 an elliptic curve on
which the DDH is believed to be acceptably hard to provide 128-bit security?

My firm belief is that the answer is yes. There is no known reason why
this curve
could be weak and 486662 is the smallest integer for which this curve
shape is strong.
This curve shape is not particularly special. The only specialness is
the prime, but
that isn't known to do anything.

I would also like to ask this for each curve in Safecurves claimed to
be safe. Note that some numbers in the above question need to be
changed: I leave this as an exercise to the reader.

Is an RFC required to express this opinion? If so I'll write up the
shortest ID on record to define the model of each curve, and provide
the canonical basepoints on each. Would anything more be required for
these curves to count as appropriately blessed?

Lastly, there is a long tradition of providing challenges with
monetary rewards for cracking parameter choices. Bitcoin makes this a
bit redundant, so I will refrain from putting my own money as a prize
for ECC breaking.

Watson Ladd