Re: [Cfrg] Proposed requirements for curve candidate evaluation
"D. J. Bernstein" <djb@cr.yp.to> Fri, 08 August 2014 18:06 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 4EFBE1A0019 for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 11:06:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.599
X-Spam-Level:
X-Spam-Status: No, score=-2.599 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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 uR-SAMqiiWcV for <cfrg@ietfa.amsl.com>; Fri, 8 Aug 2014 11:06:39 -0700 (PDT)
Received: from mace.cs.uic.edu (mace.cs.uic.edu [131.193.32.224]) by ietfa.amsl.com (Postfix) with SMTP id 593841B2CB4 for <cfrg@irtf.org>; Fri, 8 Aug 2014 11:06:32 -0700 (PDT)
Received: (qmail 16669 invoked by uid 1011); 8 Aug 2014 18:06:30 -0000
Received: from unknown (unknown) by unknown with QMTP; 8 Aug 2014 18:06:30 -0000
Received: (qmail 24426 invoked by uid 1001); 8 Aug 2014 18:06:23 -0000
Date: Fri, 08 Aug 2014 18:06:23 -0000
Message-ID: <20140808180623.24424.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: <f9d9c886d08e4a4eb09c4a57584f950b@BL2PR03MB242.namprd03.prod.outlook.com>
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/ql5Mdl-Sa2G7nIfCo6r_GX-TLH0
Subject: Re: [Cfrg] Proposed requirements for curve candidate evaluation
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 18:06:45 -0000
Brian LaMacchia writes: > 1. CFRG-recommended curves should be generated by as rigid and > deterministic a procedure as possible. If one "procedure" allows 26 different curves, and another "procedure" allows only 23 different curves, then requiring the maximum rigidity would prohibit the first procedure. Is this really what you meant? If this isn't what you meant, then what exactly _did_ you mean? Also, do you expect CFRG to evaluate "as rigid as possible" on the basis of advertisements, or on the basis of actual analyses of wiggle room? For example, if Brainpool were a proposal rather than an existing RFC, would you expect CFRG to start from Brainpool's advertisement of being "generated in a systematic and comprehensive way", or to start from analyses showing that this "way" actually allows >1 million curves? > As I stated at the beginning of my talk, our most important goal is to > recommend new elliptic curves for the IETF that will restore trust and > transparency in our protocols' use of elliptic curve cryptography. So you're saying that using a "procedure" that allows 26 different curves wouldn't restore "trust and transparency" if there's another "procedure" that allows only 23 different curves? > 2. At each security level, the CFRG-recommended curve must be > specified in a single curve model that is used for both digital > signatures and key exchange algorithms (in particular ECDSA and > ECDHE), without transformation to other models. The ECDSA standard uses short-Weierstrass coordinates to specify the transmission format for public keys, so you're saying that all curves must be specified in short-Weierstrass coordinates, and that CFRG can't consider other coordinates for digital signatures and key-exchange algorithms. (If this isn't what you meant, please clarify!) For choosing _curves_ this requirement is content-free. For example, Curve25519 is Y^2 = X^3-(236839902241/3)X+(230521961007359098/27) in short-Weierstrass form---simply shift the x-coordinate by 486662/3. For choosing _coordinates_ this requirement has content---and that content is contrary to the fundamental goals of security, simplicity, and speed. See my "curves, coordinates, and computations" message for much more detail. > 3. The CFRG-recommended curves must be specified using the same > curve model for all security levels. This is a superficial presentation requirement, of no help in choosing curves. Also, the previous requirement forced short Weierstrass in all cases, so this requirement is redundant. > 4. When evaluating candidate curves for use in ECDHE, "ephemeral" > should be defined as "use exactly once in a key exchange" (or for TLS > "use in exactly one handshake"). https://www.imperialviolet.org/2013/06/27/botchingpfs.html explains how keys can be kept around for months---despite meeting your definition of "ephemeral". These keys are clearly _not_ ephemeral and do _not_ provide perfect forward secrecy. As I explained in a previous message, "use for exactly one session" is the wrong policy; "use for exactly one connection" is the wrong policy; and Microsoft's current reuse-for-two-hours is also the wrong policy. These all fail to accomplish what the user wants, namely for keys to be erased very soon---I suggested 10 seconds as an upper limit. An implementation that reuses keys for just 1 second will have negligible keygen time on typical CPUs, even if the implementor uses a simple Montgomery ladder rather than a more complicated keygen method. Concretely, http://bench.cr.yp.to/results-dh.html shows one of the curves under discussion taking 145907 cycles for Montgomery-ladder variable-base-point scalar multiplication on a 3.5GHz Intel Haswell CPU. That's just 0.000042 seconds on a single core, completely unnoticeable even if it's repeated every second. This implementation strategy is simpler _and_ faster than the strategy you're talking about, and there's no security problem with it, so it's a perfectly valid benchmark target. I don't mean to suggest that it's the only valid benchmark target; I'm just saying that there's no basis for insisting that this target be ignored. As a side note, cryptographers for years have known a better protocol design in which "use a long-term signing key to sign a short-term DH key" is replaced by "use a long-term DH key to authenticate a short-term DH key". This makes variable-base-point scalar multiplication much more frequent while reducing overall costs. My understanding is that the dns-privacy group is already evaluating some protocols that use this better design, and I wouldn't be surprised to see TLS eventually moving in this direction. But I also think that the current TLS situation, in which key reuse is widespread and has obvious performance benefits, is already ample justification for carrying out relevant benchmarks. ---Dan
- [Cfrg] Proposed requirements for curve candidate … Brian LaMacchia
- Re: [Cfrg] Proposed requirements for curve candid… Michael Hamburg
- Re: [Cfrg] Proposed requirements for curve candid… Benjamin Black
- Re: [Cfrg] Proposed requirements for curve candid… Salz, Rich
- Re: [Cfrg] Proposed requirements for curve candid… Michael Hamburg
- Re: [Cfrg] Proposed requirements for curve candid… Salz, Rich
- Re: [Cfrg] Proposed requirements for curve candid… Watson Ladd
- Re: [Cfrg] Proposed requirements for curve candid… Michael Hamburg
- Re: [Cfrg] Proposed requirements for curve candid… Andrey Jivsov
- Re: [Cfrg] Proposed requirements for curve candid… D. J. Bernstein
- Re: [Cfrg] Proposed requirements for curve candid… Tanja Lange
- Re: [Cfrg] Proposed requirements for curve candid… David Jacobson
- Re: [Cfrg] Proposed requirements for curve candid… Craig Costello
- Re: [Cfrg] Proposed requirements for curve candid… Michael Hamburg