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

Brian LaMacchia <bal@microsoft.com> Mon, 01 September 2014 18:46 UTC

Return-Path: <bal@microsoft.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 3E0C21A04DC for <cfrg@ietfa.amsl.com>; Mon, 1 Sep 2014 11:46:40 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id FCmHAIyzt7tY for <cfrg@ietfa.amsl.com>; Mon, 1 Sep 2014 11:46:37 -0700 (PDT)
Received: from na01-bn1-obe.outbound.protection.outlook.com (mail-bn1lp0140.outbound.protection.outlook.com []) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 832A91A04AA for <cfrg@ietf.org>; Mon, 1 Sep 2014 11:46:37 -0700 (PDT)
Received: from BL2PR03MB242.namprd03.prod.outlook.com ( by BL2PR03MB241.namprd03.prod.outlook.com ( with Microsoft SMTP Server (TLS) id 15.0.1015.19; Mon, 1 Sep 2014 18:46:34 +0000
Received: from BL2PR03MB242.namprd03.prod.outlook.com ([]) by BL2PR03MB242.namprd03.prod.outlook.com ([]) with mapi id 15.00.1015.018; Mon, 1 Sep 2014 18:46:35 +0000
From: Brian LaMacchia <bal@microsoft.com>
To: "cfrg@ietf.org" <cfrg@ietf.org>
Thread-Topic: On the use of Montgomery form curves for key agreement
Thread-Index: Ac/GFKdVASv0pPTeROyHvj6EvV57FQ==
Date: Mon, 01 Sep 2014 18:46:34 +0000
Message-ID: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: []
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;UriScan:;
x-forefront-prvs: 03218BFD9F
x-forefront-antispam-report: SFV:NSPM; SFS:(243025005)(199003)(189002)(79102001)(46102001)(19580395003)(19300405004)(105586002)(2656002)(54356999)(110136001)(229853001)(19617315012)(15975445006)(64706001)(20776003)(16236675004)(99286002)(92566001)(2351001)(107046002)(95666004)(50986999)(83072002)(85852003)(87936001)(33646002)(15202345003)(81342001)(81542001)(107886001)(21056001)(101416001)(66066001)(108616004)(19625215002)(80022001)(85306004)(4396001)(77982001)(86362001)(74502001)(31966008)(74662001)(90102001)(76482001)(106356001)(99396002)(76576001)(83322001)(77096002)(74316001)(2501002)(24736002)(42262002); DIR:OUT; SFP:; SCL:1; SRVR:BL2PR03MB241; H:BL2PR03MB242.namprd03.prod.outlook.com; FPR:; MLV:sfv; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
Content-Type: multipart/alternative; boundary="_000_e16ac4926a934565a65456058e50b68eBL2PR03MB242namprd03pro_"
MIME-Version: 1.0
X-OriginatorOrg: microsoft.onmicrosoft.com
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/JuFwHITh-YgHMebtN7ZpUzDDbpU
Subject: [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: Mon, 01 Sep 2014 18:46:40 -0000


Here are the points that must be considered regarding the potential selection of a Montgomery form curve (and its realization using the Montgomery ladder):

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.

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.

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.

Those arguing for adoption of X25519 are requesting that CFRG (a) treat the 128 bit security level different from other security levels, (b) force implementations of multiple security levels of key agreement to implement different curve arithmetic for different security levels, (c) force implementations of protocols with both key agreement and digital signatures to implement different curve arithmetic for those two operations, even at the same security level, (d) force point conversions between curve forms to avoid efficiency loss in ECDHE, and (e) to do (a)-(d) for no clear gain in performance. These points overwhelmingly contradict arguments in favor of forcing the use of the Montgomery form for key agreement, especially for only a single security level.