Re: [Cfrg] Progress on curve recommendations for TLS WG

Ilari Liusvaara <ilari.liusvaara@elisanet.fi> Fri, 08 August 2014 14:15 UTC

Return-Path: <ilari.liusvaara@elisanet.fi>
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 13FC41B2BB3 for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 07:15:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_NONE=-0.0001, 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 HtVQQvGNaQFj for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 07:15:11 -0700 (PDT)
Received: from emh03.mail.saunalahti.fi (emh03.mail.saunalahti.fi [62.142.5.109]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 018931B2BE3 for <cfrg@irtf.org>; Fri, 8 Aug 2014 07:15:10 -0700 (PDT)
Received: from LK-Perkele-VII (a88-112-44-140.elisa-laajakaista.fi [88.112.44.140]) by emh03.mail.saunalahti.fi (Postfix) with ESMTP id 232D1188791; Fri, 8 Aug 2014 17:15:06 +0300 (EEST)
Date: Fri, 8 Aug 2014 17:15:06 +0300
From: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
To: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
Message-ID: <20140808141506.GA24645@LK-Perkele-VII>
References: <CFFB1371.2916E%kenny.paterson@rhul.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
In-Reply-To: <CFFB1371.2916E%kenny.paterson@rhul.ac.uk>
User-Agent: Mutt/1.5.23 (2014-03-12)
Sender: Ilari Liusvaara <ilari.liusvaara@elisanet.fi>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/mqgZ1wZsnfeLE92YHBaitjoj3VY
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG
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: Fri, 08 Aug 2014 14:15:15 -0000

On Sun, Jul 27, 2014 at 08:04:45PM +0000, Paterson, Kenny wrote:

> - Do the current proposals (Curve25519 and friends, and the NUMS curves)
> provide an adequate degree of rigidity that is likely to satisfy the
> widest set of commentators? Or should we be thinking about generating
> fresh curves using a public process having verifiably random inputs? What
> would the likely impact be on performance?

I split the question to two parts: Prime and parameters

a) Prime

Picking prime randomly has _devastating_ impact on performance. Nobody will
seriously use the curve. This is THE reason why Brainpool is not used much
in the wild.

If one picks prime for performance (the prime is the dominant factor in
performance), there are very few primes that perform well[1].

This would force high degree of rigridity if performance is a major goal.

b) Parameters

While bad parameters aren't devastating for performance, badly picked ones
are still significantly slower (e.g. loses that ~0.75M advantage from small
parameter on addition or Montgomery step).

With parameters, random choice is not wise, given that there are very few
(I think 4 or 2 depending on bitlength[2][3]) rational choices for
deterministic curve per prime. It would be very hard to reach similar
rigidity via random process.


[1] The "contestants" all seem to be (pseudo) Mersennes with small c and
Solinas trinomials. I think some have tried to develop metrics to measure
the effectiveness of various primes.


[2] Complete Edwards (minimal |d|) vs. Complete Montgomery (minimal |a24|),
q < 2^n vs. q > 2^n.


[3] I think that shrinks to 2 on higher bitlengths, since using windowing
on Edwards curve becomes faster than using Montgomery ladder on Montgomery
curve.


-Ilari