Re: [Cfrg] Preserving Implementation Optimizations

Mike Hamburg <mike@shiftleft.org> Mon, 01 September 2014 03:06 UTC

Return-Path: <mike@shiftleft.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 E45261A90F4 for <cfrg@ietfa.amsl.com>; Sun, 31 Aug 2014 20:06:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.555
X-Spam-Level: *
X-Spam-Status: No, score=1.555 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=no
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 Ghrhgm5ffGsH for <cfrg@ietfa.amsl.com>; Sun, 31 Aug 2014 20:06:06 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 3A0201A90F1 for <cfrg@irtf.org>; Sun, 31 Aug 2014 20:06:06 -0700 (PDT)
Received: from [192.168.1.140] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id EC3323AA12; Sun, 31 Aug 2014 20:03:39 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1409540619; bh=ltVrdjmMGbMIgK2q82Vqrh5NTAdY8B+xSl+68GDy9Bc=; h=Date:From:To:Subject:References:In-Reply-To:From; b=McHsXCUx4mlzEJQOqrbWOcgTqOemWObFzhzNKWS3GT6plK0lyFExpGutZ3wt1Bw5e ZGgCRPVsFzlhLBzziqLEcuC53TplMkONFCaQK35GoRnna0AHyHjsA3cUd6W8waVl65 c1ONkUeryjZFHE1U7It4S2LKWZ0LPgeDpwEDTCRk=
Message-ID: <5403E295.3070209@shiftleft.org>
Date: Sun, 31 Aug 2014 20:05:57 -0700
From: Mike Hamburg <mike@shiftleft.org>
User-Agent: Mozilla/5.0 (Windows NT 6.3; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
To: Russ Housley <housley@vigilsec.com>, IRTF CFRG <cfrg@irtf.org>
References: <01DE592A-008C-4CD7-BD00-07FD25B4B463@vigilsec.com>
In-Reply-To: <01DE592A-008C-4CD7-BD00-07FD25B4B463@vigilsec.com>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/DGZZeIJ8lmw8tlm0nc1VfeBmS6g
Subject: Re: [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 03:06:08 -0000

On 8/31/2014 6:56 PM, Russ Housley wrote:
> 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.
A lot of effort may have gone into optimizing for the NIST primes, but 
nonetheless most implementations mod these primes are not actually very 
fast.  The most widely-used primes (P-256 and P-384) have the worst 
performance of the lot, especially on 64-bit machines.  Furthermore, the 
newer primes are usually easier to implement than the NIST primes.

The exception may be in dedicated hardware, where the many coefficients 
of primes like P-256 don't make as big an obstacle, and any change is 
very expensive.

Note that P-521 := 2^521-1 is fast, and should definitely be an option.
> 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.
The question of curve specification and point encodings has been 
discussed at length here.  On the one hand, this sort of encoding might 
be good for compatibility; but on the other hand, it may enable new 
attacks on recycled implementations while increasing complexity of the 
new implementations.

Personally I don't think we should put new wine in old wineskins, but I 
suppose it is an option.

Cheers,
-- Mike

> 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,
>    Russ
>
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg