Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

Andrey Jivsov <crypto@brainhub.org> Mon, 21 July 2014 02:32 UTC

Return-Path: <crypto@brainhub.org>
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 6D9D91B2AC8 for <cfrg@ietfa.amsl.com>; Sun, 20 Jul 2014 19:32:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.831
X-Spam-Level:
X-Spam-Status: No, score=-1.831 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_SORBS_WEB=0.77, SPF_PASS=-0.001] 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 4-lk0lyHIXmP for <cfrg@ietfa.amsl.com>; Sun, 20 Jul 2014 19:32:27 -0700 (PDT)
Received: from mail-ie0-f172.google.com (mail-ie0-f172.google.com [209.85.223.172]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 157141B2ACE for <cfrg@irtf.org>; Sun, 20 Jul 2014 19:32:26 -0700 (PDT)
Received: by mail-ie0-f172.google.com with SMTP id lx4so6369808iec.31 for <cfrg@irtf.org>; Sun, 20 Jul 2014 19:32:26 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:sender:message-id:date:from:user-agent :mime-version:to:subject:references:in-reply-to:content-type :content-transfer-encoding; bh=idmLUjBxSlly5khfdSHXE8yp7QvYkkR2Izq3PMAK85c=; b=Uewpy0KJYktdkYB6CEdInfuc6H0OWr/w+t4fxtQQZ/Jc8e98eoNSd3UNCGwVKz/ccm OcjIuWG0JYLdlRjboK9fQ/xLYBc+mHp7Cp1LDYe0zJeoYKbh0w7AHf6ETImdZNj3bN/c T6h+1MM6CJCObAtERezACJBMd4z0Vdxhr4r0+H1gLE4nnTif3lmLinSRAZe8q68Oz3bp uVvTZmCiYMIfw6kXOs/wJjJqwZ8QN7tUUPDTYRm/N4R8jkf91HugZazB+3AbEJ6EZnMd ir+hItpplAukkq0241xOqEhtdsgvkj6ljj3S3EAmg3DINa/fip44HjS6hVKdOXPG2aQP mong==
X-Gm-Message-State: ALoCoQlFs9nGL7YF7TmtWjGE5lqM84Zwxf2OfuadC6p6TTOFmjjC2hxRsbsR8evE6nHZ5OJSWb4I
X-Received: by 10.50.79.232 with SMTP id m8mr4611034igx.39.1405909946343; Sun, 20 Jul 2014 19:32:26 -0700 (PDT)
Received: from [10.255.234.94] ([207.236.147.203]) by mx.google.com with ESMTPSA id lo3sm34103907igb.22.2014.07.20.19.32.25 for <cfrg@irtf.org> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 20 Jul 2014 19:32:25 -0700 (PDT)
Sender: Andrey <andrey@brainhub.org>
Message-ID: <53CC7BB8.8050604@brainhub.org>
Date: Sun, 20 Jul 2014 22:32:24 -0400
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <c37f9974d2be4614b9a03392572dd29c@BL2PR03MB242.namprd03.prod.outlook.com>
In-Reply-To: <c37f9974d2be4614b9a03392572dd29c@BL2PR03MB242.namprd03.prod.outlook.com>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/w5JToNNLcA3WtjOGdnoazUReYek
Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves
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, 21 Jul 2014 02:32:28 -0000

>  s: Denotes the bit length, here s in {256,384,512}.
>  p: Denotes the prime number defining the base field.
>  c: A positive integer used in the representation of the prime
>          p = 2^s - c.

In light of the recent discussion, would an attempt to reach a consensus 
on the value of p first has a higher chance for success at this point?

Assuming we want a new p, some arguments for a fixed F(p) are:

* the specs like Curve25519 are "stacks of layers", which prescribe a 
Curve, co-factor multiplication, F(p) operations, and an integer format 
(fixing p seems as one of the the least controversial tasks among these 
"layers")
* the performance advantage are mostly attributed to the F(p) operations 
(factor of n improvement in F(p) results in ~ n^2 curve performance)
* F(p) operations are platform-specific  (if there is assembler code 
used in the "stack", it will likely be restricted to the F(p))
* F(p) clarity will let hardware vendors focus on optimizations (and not 
worry about the entire stack)
* same F(p) doesn't prohibit multiple curves over it; ( fixing F(p) 
first and the curve or curves later will allow implementations to 
proceed sooner and enables a compromise )
* fixed F(p) allows greater flexibility to upgrade the curves (future 
curves will likely have hardware support available, sensitive code resused).
* fixed F(p) reduces the code size, increases interoperability 
(currently NUMS and Curve25519 are at odds here)

This narrow focus leads to these questions regarding the F(p):
* is a pseudo-Mersenne p an appropriate p for the new curves (the only 
cons to this so far is that such a p fixes the Curve's order to be close 
to 2^s; besides the trivial one that this makes the Pollard-rho faster)
* Curve25519 uses 255 instead of 256; however, CFRG can choose s=255 for 
128 bit security as well (citing "historic" reasons).

Should CFRG seek consensus on the above two questions first?