Re: [Cfrg] On the use of Montgomery form curves for key agreement

Tanja Lange <tanja@hyperelliptic.org> Tue, 02 September 2014 16:30 UTC

Return-Path: <tanja@hyperelliptic.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 888481A045C for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 09:30:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.6
X-Spam-Level:
X-Spam-Status: No, score=-2.6 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7] 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 S1SRYFsaMjiJ for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 09:30:01 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id 422851A045B for <cfrg@ietf.org>; Tue, 2 Sep 2014 09:30:01 -0700 (PDT)
Received: (qmail 14815 invoked from network); 2 Sep 2014 16:29:59 -0000
Received: from pcdhz005.win.tue.nl (HELO hyperelliptic.org) (131.155.71.33) by mace.cs.uic.edu with SMTP; 2 Sep 2014 16:29:59 -0000
Received: (qmail 27304 invoked by uid 1000); 2 Sep 2014 16:29:59 -0000
Date: Tue, 2 Sep 2014 18:29:59 +0200
From: Tanja Lange <tanja@hyperelliptic.org>
To: Brian LaMacchia <bal@microsoft.com>
Message-ID: <20140902162959.GH8540@cph.win.tue.nl>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com>
User-Agent: Mutt/1.5.11
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/qDJAo5kvGv-BkCWDCHr-9e4Vzgg
Cc: "cfrg@ietf.org" <cfrg@ietf.org>
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
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: Tue, 02 Sep 2014 16:30:04 -0000

Dear Brian,
 
Most of this is going in circles; the points you raise were discussed 
on the mailing list before and during the Toronto meeting. I would 
appreciate it if instead of starting a new round of this you could 
reply to some earlier emails.

>    1.       Requiring a Montgomery form curve for key agreement and for a
>    particular security level means that implementations of protocols with
>    both key agreement and digital signatures must implement both Montgomery
>    curve arithmetic and additionally curve arithmetic for another curve
>    form.  From an engineering perspective there is thus a clear drawback to
>    requiring different curve forms for key agreement and digital signature at
>    the same security level.
> 
As several people pointed out now and in previous discussions, this
is conflating wire format, implementation, and curve form.

For security and ease of correct implementation I prefer Montgomery-x
for the wire format for DH and a compressed (but uniquely decompressible)
wire format for signatures.

>    2.       Assuming that implementations will implement more than one
>    security level, choosing X25519 for ECDHE at the 128 bit security level
>    will require implementations to use different curve arithmetic for the 128
>    bit security level than other security levels.  Again from an engineering
>    standpoint this is a negative.
> 
This is arguing about one particular suggestion and, again, mixes
wire format, implementation, and curve form.

>    3.       Despite repeated claims to the contrary, there is little evidence
>    that there is a consistent and significant performance benefit to
>    X25519. Indeed, as both the performance numbers in
>    http://eprint.iacr.org/2014/130.pdf as well as the more recent performance
>    numbers posted by Andrey Jivsov demonstrate, the performance of X25519
>    does not significantly differ from that of (twisted) Edwards curves for
>    (non-ephemeral) ECDH at the same size.  For the case of ECDHE,
>    Dan Bernstein has argued for a definition of "ephemeral" that would allow
>    keys to be re-used for some amount of time allowing X25519 implementations
>    to amortize the cost of operations which are particularly expensive for
>    X25519 over multiple uses of the same key.* Such arguments are intended to
>    wrap requirements around specific curves, which is inappropriate for this
>    process. There has been no legitimate argument put forward for repeated
>    use of ephemeral keys in ECDHE.  As a consequence, the adoption of a
>    definition of "ephemeral" that does not allow key re-use (as previously
>    recommended) means that implementations of X25519 would require
>    conversions between curve forms to avoid a significant loss in
>    performance. These conversions are a negative from an engineering
>    perspective.
> 

This is mostly about curve choices, not requirements. As far as the 
requirement of 'ephemeral = once' is concerned we've been through 
this discussion. For a speed comparison one can choose to go for
"KG+DH" or for "KG+nDH" for some value of n or look at several data 
points. However, for the security of the implementation, the system
must not break if the DH key is reused. I already said that after my
talk in Toronto. 

To say it simpler:
Requirement: security MUST not decrease if DH keyis reused
Selection criterion: speed of KG+nDH (incl., maybe exclusively, n=1)

There has been enough ripping into items a0-e) already, 
so I skip that apart from pointing out that you're arguing 
against one particular curve and mixing that with the requirements.
How about my up and coming T255.5? (just kidding).

Regards
	Tanja