[Cfrg] Preserving Implementation Optimizations

Russ Housley <housley@vigilsec.com> Mon, 01 September 2014 01:57 UTC

Return-Path: <housley@vigilsec.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 A089D1A90BD for <cfrg@ietfa.amsl.com>; Sun, 31 Aug 2014 18:57:33 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -99.2
X-Spam-Status: No, score=-99.2 tagged_above=-999 required=5 tests=[BAYES_50=0.8, USER_IN_WHITELIST=-100] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id NxJC38ED_6Ki for <cfrg@ietfa.amsl.com>; Sun, 31 Aug 2014 18:57:32 -0700 (PDT)
Received: from odin.smetech.net (mail.smetech.net []) by ietfa.amsl.com (Postfix) with ESMTP id 193211A90BA for <cfrg@irtf.org>; Sun, 31 Aug 2014 18:57:32 -0700 (PDT)
Received: from localhost (unknown []) by odin.smetech.net (Postfix) with ESMTP id A7C87F9C00F for <cfrg@irtf.org>; Sun, 31 Aug 2014 21:57:21 -0400 (EDT)
X-Virus-Scanned: amavisd-new at smetech.net
Received: from odin.smetech.net ([]) by localhost (ronin.smeinc.net []) (amavisd-new, port 10024) with ESMTP id AovogLkfNi6c for <cfrg@irtf.org>; Sun, 31 Aug 2014 21:57:00 -0400 (EDT)
Received: from v150.vpn.iad.rg.net (v150.vpn.iad.rg.net []) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by odin.smetech.net (Postfix) with ESMTP id 99C989A4426 for <cfrg@irtf.org>; Sun, 31 Aug 2014 21:57:00 -0400 (EDT)
From: Russ Housley <housley@vigilsec.com>
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Date: Sun, 31 Aug 2014 21:56:46 -0400
Message-Id: <01DE592A-008C-4CD7-BD00-07FD25B4B463@vigilsec.com>
To: IRTF CFRG <cfrg@irtf.org>
Mime-Version: 1.0 (Apple Message framework v1085)
X-Mailer: Apple Mail (2.1085)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/aSFQkVhiz1sWb4bvyzBC6z4OhNc
Subject: [Cfrg] Preserving Implementation Optimizations
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, 01 Sep 2014 01:57:33 -0000

I am not a cryptographer, but I have been involved in security protocols that make use of cryptography since 1986.  This experience tells me that we should preserve the hard work that has gone into existing ECC implementations if possible.  I have four thoughts in this direction...

First, the use of the same curve for digital signature and key agreement is highly desirable.  This provides obvious modularity.

Second, a lot of effort has gone into optimization of modular reduction for the NIST primes.  If a curve is selected that uses those primes, this optimization effort would carry forward to the new curves.  I have only heard one person question whether those values are actually prime, so I assume that this is not a widely held concern.

Third, many implementations have taken advantage of the "a term" chosen for the NIST curves to optimize point addition. In Weierstrass form, y^2 = x^3 + ax + b, the NIST curves use a = -3 mod p.

Fourth, recent discussion makes it clear that the Edwards form, x^2 + y^2 = 1 + dx^2y^2, offers some significant advantages, especially when the "d term" is chosen to be small.  We can make our curve selection in this form, and then transform it to Weierstrass form to determine the "b term".  The order of the curve needs to be 4 times a prime.  This allows new implementations to take advantage of the Edwards form, and it allows existing implementations to make minimal modifications to support the new curve.

If I have been following this discussion, we need to consider whether we want a Bernstien-Lange SafeCurve.  If we do, then the order of the Edwards twist needs to have a large prime factor.  As best I can tell, this requirement does not conflict with finding a curve that meets the above criteria.

I realize that this is quite different than selecting one of the choices that were presented in Toronto.  However, I think that we should preserve the implementation investment if it does not otherwise hinder security or efficiency.

Thanks for your consideration,