Re: [Cfrg] On the use of Montgomery form curves for key agreement
"D. J. Bernstein" <djb@cr.yp.to> Tue, 02 September 2014 16:53 UTC
Return-Path: <djb-dsn2-1406711340.7506@cr.yp.to>
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 3FFF91A01F3 for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 09:53:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.701
X-Spam-Level:
X-Spam-Status: No, score=0.701 tagged_above=-999 required=5 tests=[BAYES_50=0.8, J_CHICKENPOX_210=0.6, RCVD_IN_DNSWL_LOW=-0.7, UNPARSEABLE_RELAY=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 0iQ2wJP4KNjI for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 09:53:48 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id 769771A0022 for <cfrg@irtf.org>; Tue, 2 Sep 2014 09:53:48 -0700 (PDT)
Received: (qmail 15007 invoked by uid 1011); 2 Sep 2014 16:53:48 -0000
Received: from unknown (unknown) by unknown with QMTP; 2 Sep 2014 16:53:48 -0000
Received: (qmail 17288 invoked by uid 1001); 2 Sep 2014 16:53:40 -0000
Date: Tue, 02 Sep 2014 16:53:40 -0000
Message-ID: <20140902165340.17284.qmail@cr.yp.to>
From: "D. J. Bernstein" <djb@cr.yp.to>
To: cfrg@irtf.org
Mail-Followup-To: cfrg@irtf.org
In-Reply-To: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/_J-RSYumWmUqviR1UdSJb847waM
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:53:51 -0000
Brian LaMacchia writes: > 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 Several reports have indicated that Microsoft's standard TLS library (SChannel) reuses ephemeral DH keys (specifically TLS ECDHE keys) for two hours. Are those reports not accurate? Even if keygen were implemented as variable-base scalarmult without the complication of a separate fixed-base scalarmult function, wouldn't you agree that this key reuse makes the cost of key generation irrelevant? Wouldn't you expect other implementors to reuse keys for this reason? Obviously two hours is not the right choice: repressive police states can certainly seize equipment within that time interval. In my message dated 1 Aug 2014 01:36:59 -0000, I suggested 10 seconds as an upper limit. However, this doesn't change the DH performance picture! Variable-base scalarmult is dominant for DH, including ephemeral DH. I concluded that CFRG should consider the performance of variable-base scalarmult (for DH), fixed-base scalarmult (for signing), and double-base scalarmult (for signature verification). But I don't expect this to produce different curve choices from considering solely variable-base scalarmult---which is also the most fundamental operation and the usual focus of DH performance analyses in the literature. > allowing X25519 implementations to amortize > the cost of operations which are particularly expensive for X25519 > over multiple uses of the same key. The "expensive for X25519" claim here is completely wrong. X25519 allows all the usual speed benefits from all the usual fixed-base speedups. As Mike Hamburg put it in his mail message dated 7 Aug 2014 11:57:45 -0700, optimized fixed-base scalarmult "will pretty much always cost about a third of what the variable-base scalar multiply costs." Concretely, https://github.com/floodyberry/ed25519-donna https://github.com/agl/curve25519-donna support all Curve25519/X25519/Ed25519 operations under discussion: DH keygen (curved25519_scalarmult_basepoint is the fast version), DH shared-secret computation, signature keygen, signing, and verification. These are faster than the speeds announced by Microsoft for each of these operations (and of course also for combinations of operations in ECDHE etc.) on the CPU that Microsoft has selected for benchmarks. Also, unlike Microsoft's library, these actually do the work of signing etc. There are many X25519 implementations, reflecting the wide use of X25519 in many real-world protocols. It's of course true that reusing DH keys practically eliminates keygen cost, which is exactly why typical users don't care about DH keygen time, which is exactly why typical DH implementations prioritize simplicity over DH keygen optimizations. This has given you the flexibility to cherry-pick X25519 implementations that don't bother speeding up keygen, and to misrepresent the performance of those implementations as the keygen performance of X25519, even though faster X25519 keygen code has been available for longer than Microsoft's library has. Your position is not defensible. > There has been no legitimate argument put forward for > repeated use of ephemeral keys in ECDHE. If a server notices keygen time, it can gain far more performance by reusing a key 100 times than by switching to fixed-base scalarmult. Reusing keys also costs less code in many settings than implementing fixed-base scalarmult, but even without this simplicity argument you have to admit that there's a legitimate performance argument. Out of curiosity: If it wasn't for performance, why did Microsoft's TLS library ever reuse ephemeral DH keys in the first place? Would you say that the Microsoft reason was illegitimate? Even if you're sure that it was illegitimate, wouldn't you agree that taking this reuse off of the CFRG radar screen would require a blanket prohibition on this reuse in all IETF protocols, and that no such prohibition exists? > 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. No. All Edwards (and twisted Edwards) curves, at all security levels, are compatible with choosing Montgomery coordinates for ECDHE. See my message dated 25 Aug 2014 23:43:05 -0000 for the relevant formulas. When Tanja Lange and I introduced Edwards-curve cryptography, we correctly and publicly predicted that Edwards coordinates would be close in performance to Montgomery coordinates. However, nothing has ever matched the amazing _simplicity_ of the Montgomery X-coordinate for DH. This simplicity is more than just a time-saver; it also removes many opportunities for DH implementors to screw up security. > clear drawback to requiring different curve forms for key agreement > and digital signature at the same security level. The Montgomery approach to DH is exceptionally simple---costing very few lines of code for a unified DH+signatures implementation (as TweetNaCl demonstrates), and at the same time saving many more lines of code for a pure DH implementation. If the picture looks like * complexity 300: DH using Montgomery * complexity 500: DH using Edwards * complexity 600: DH using Edwards + signatures using Edwards * complexity 610: DH using Montgomery + signatures using Edwards you can't claim that there is a "clear drawback" to DH using Montgomery. ---Dan
- [Cfrg] On the use of Montgomery form curves for k… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… D. J. Bernstein
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Tony Arcieri
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Robert Ransom
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Robert Ransom
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Watson Ladd
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Tanja Lange
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Benjamin Black
- Re: [Cfrg] On the use of Montgomery form curves f… Stephen Farrell
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov
- Re: [Cfrg] On the use of Montgomery form curves f… Michael Hamburg
- Re: [Cfrg] On the use of Montgomery form curves f… Brian LaMacchia
- Re: [Cfrg] On the use of Montgomery form curves f… Tanja Lange
- Re: [Cfrg] On the use of Montgomery form curves f… Paterson, Kenny
- Re: [Cfrg] On the use of Montgomery form curves f… Jim Schaad
- Re: [Cfrg] On the use of Montgomery form curves f… Markulf Kohlweiss
- Re: [Cfrg] On the use of Montgomery form curves f… Paterson, Kenny
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… Manuel Pégourié-Gonnard
- Re: [Cfrg] On the use of Montgomery form curves f… Andy Lutomirski
- Re: [Cfrg] On the use of Montgomery form curves f… Nico Williams
- Re: [Cfrg] On the use of Montgomery form curves f… Andrey Jivsov