[Cfrg] Curve25519 meets NUMS rigidity definition

Watson Ladd <watsonbladd@gmail.com> Sat, 03 January 2015 18:07 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 64CF31A912C for <cfrg@ietfa.amsl.com>; Sat, 3 Jan 2015 10:07:10 -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_40=-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 B-onz30t9Upk for <cfrg@ietfa.amsl.com>; Sat, 3 Jan 2015 10:07:08 -0800 (PST)
Received: from mail-yk0-x229.google.com (mail-yk0-x229.google.com [IPv6:2607:f8b0:4002:c07::229]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 8FA401A912A for <cfrg@irtf.org>; Sat, 3 Jan 2015 10:07:08 -0800 (PST)
Received: by mail-yk0-f169.google.com with SMTP id 79so9468042ykr.28 for <cfrg@irtf.org>; Sat, 03 Jan 2015 10:07:07 -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=uT8tHgIWT++Ex9oLgYU9SMTKG+iMae4YBqqEADPRz1o=; b=Qi2wNAbXl1PxoPEd+MxYO0CWmyapV25m8uoMIMbPkdYEUNtp3F3Dhn6RceX4xwRlgg rm2Yqy455XO2g5DKHnRuKEHtmcUZ+efjMdsoEGW9nrf6hhbirBI/2SOt2wpsG/lS4ewZ XfsLsF2lCpVpBQyZpwdgjb1gyBG4lN0RINtsIY0zpgbe94urDWFFO+24YQveMPFdFgEe K5EJWBkYySmD2ad83Ed4pHRB4zI0yP2T2vRWXOGW4o9x8KFO7Bl75zMMesEANl5q9vyn ONDRTuXaMOiuqfbYVYHBhMHTZ6qtz9O6Z6a/2AGMb/iokFo65OBqtglmCCxqsBHvNhRn 1liw==
MIME-Version: 1.0
X-Received: by with SMTP id c69mr4244111yha.49.1420308427560; Sat, 03 Jan 2015 10:07:07 -0800 (PST)
Received: by with HTTP; Sat, 3 Jan 2015 10:07:07 -0800 (PST)
Date: Sat, 3 Jan 2015 13:07:07 -0500
Message-ID: <CACsn0cmeGX5aAXJfJMo7UxOanDLPW_y+dOLf=Ue6izTQXkn2TA@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/Ye7_fqy7GUxTPqeyb1J_4d6J3_o
Subject: [Cfrg] Curve25519 meets NUMS rigidity definition
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: Sat, 03 Jan 2015 18:07:10 -0000

Dear all,

In  draft-black-numscurves-02 we see the following sentence: "The
domain parameters SHALL be generated in a simple,  deterministic
manner, without any secret or random inputs."

If we actually take this sentence as written, it would seem the
Brainpool curves work. After all, there were no secret or random
inputs to the algorithm that output the Brainpool curves. Same with
the BADA55 curves: there were no secret or random inputs. I doubt that
these were what was meant to be rigid.

So it's clear to me that this was scrivener's error: something else
was meant. But what?

Given the details of the various processes that have all be claimed to
be rigid by the NUMS group, it seems to be that one takes a
parametrization of a certain set of elliptic curves, and searches for
the minimal parameter achieving certain properties forced by security
considerations, then takes the generator with one coordinate minimal,
and this is the only kind of method allowed.

So I'll take p=2^255-19, y^2=x^3+ux^2+x, and search for the minimal
positive u that makes the order of the curve 8 times prime, order of
the twist 4 times other prime, and minimal x coordinate on the curve
with prime order for the generator, with u congruent to 2 mod 4. I can
even throw in restrictions on endomorphism ring and supersingularity,
and it won't change the result.

Of course, this gives Curve25519 on the nose. So what's actually being
claimed is something much weirder: only certain curve shapes lead to
good results. Weierstrass does, and Edwards does, and twisted Edwards
does, but Montgomery doesn't. Either that, or Curve25519 does fall
within the set of curves that are generated by NUMS, and with the
original generators too.

This appears in the original paper presenting Curve25519, and seems to
be the core objection to Curve25519. I'd like to know if the chairs
propose to move for consensus on Curve25519 in the Turner draft form,
or if they still want to drag this out longer, or consider drafts
containing generation methods. If they do want to drag this out
longer, I'd like to know if the Powers That Be have any plan to deal
with this farcical situation.

Watson Ladd