From jon@callas.org Sat Feb 1 13:05:40 2014 Return-Path: X-Original-To: openpgp@ietfa.amsl.com Delivered-To: openpgp@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 898401A1F7A for ; Sat, 1 Feb 2014 13:05:40 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -0.358 X-Spam-Level: X-Spam-Status: No, score=-0.358 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DATE_IN_PAST_06_12=1.543, SPF_PASS=-0.001] autolearn=no 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 qbxb5mBLIln2 for ; Sat, 1 Feb 2014 13:05:39 -0800 (PST) Received: from mail.merrymeet.com (merrymeet.com [173.164.244.100]) by ietfa.amsl.com (Postfix) with ESMTP id F18F81A1F76 for ; Sat, 1 Feb 2014 13:05:38 -0800 (PST) Received: from localhost (localhost [127.0.0.1]) by mail.merrymeet.com (Postfix) with ESMTP id B32FA4C53C22; Sat, 1 Feb 2014 13:05:34 -0800 (PST) X-Virus-Scanned: amavisd-new at merrymeet.com Received: from mail.merrymeet.com ([127.0.0.1]) by localhost (merrymeet.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id GBASkhkHalMo; Sat, 1 Feb 2014 13:05:33 -0800 (PST) Received: from keys.merrymeet.com (keys.merrymeet.com [173.164.244.97]) by mail.merrymeet.com (Postfix) with ESMTPSA id 57EC04C53BFF; Sat, 1 Feb 2014 13:05:31 -0800 (PST) Received: from [192.168.10.248] ([64.134.147.132]) by keys.merrymeet.com (PGP Universal service); Sat, 01 Feb 2014 13:05:33 -0800 X-PGP-Universal: processed; by keys.merrymeet.com on Sat, 01 Feb 2014 13:05:33 -0800 Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\)) From: Jon Callas In-Reply-To: <874n4kxqop.fsf@vigenere.g10code.de> Date: Sat, 1 Feb 2014 04:57:29 -0800 Message-Id: References: <87iot0y1su.fsf@vigenere.g10code.de> <874n4kxqop.fsf@vigenere.g10code.de> To: Werner Koch X-Mailer: Apple Mail (2.1827) Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: quoted-printable Cc: "openpgp@ietf.org OpenPGP" , Jon Callas Subject: Re: [openpgp] Catch 22 in ECC support of OpenPGP? X-BeenThere: openpgp@ietf.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: "Ongoing discussion of OpenPGP issues." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 01 Feb 2014 21:05:40 -0000 On Jan 31, 2014, at 4:48 AM, Werner Koch wrote: > Sure. We already use one from the GNU arc in Libgcrypt: >=20 > 1.3.6.1.4.1.11591.15 ellipticCurve > 1.3.6.1.4.1.11591.15.1 Ed25519 >=20 > This is a different OID than Peter Gutman's for Curve25519. Who cares? It's just a bitstring that is added into the hash to make it = unique for the signature algorithm. Think of it as a form of salted hash = where that is for the algorithm. The only thing that matters is = uniqueness, and even if there's an OID collision, it's not the end of = the world. Do it! >=20 >> As you've noted, in RFC 6637, Andrey codes an EC point into an MPI, >> which I think is clever, and works fine. Why not just do it? >=20 > I explained it below. RFC-6637 requires the use of SEC encoding which > is nice because you will never have the problems with leading zeroes. > However, EdDSA uses a different compression format without any > identifier (which makes up nice 32 bytes). A leading zero may however > happen. RFC-4880 does not allow that and thus one would need to check > whether to left pad a read MPI before using it with Ed25519 code. As = I > said, not a real problem but it would be possible to save 2 lines of > code if we could use a raw octet string. I can think of two ways to deal with it: 1) Ignore it. It's not *really* an MPI. It's a point in MPI format, and = just throw it in there. The reason for the rule is so that a given integer doesn't have subtle = problems from different encodings with leading zeroes. But these aren't integers, they're points of a known length. Just use = the length and don't worry. 2) Consider this a primitive form of compression and roll with it. Of those two, I vote for (1). There's no real value in the compression, = it's an observation. And the reason there's little value in compression = is the same reason that there's little harm in just putting the point = there and don't worry about leading zeroes. Let me take the case of the curve 414-19, and let's imagine that there's = two leading zeroes in a point and thus the debate is whether we code it = as a 412 or 414 bit field. Either of those is kinda meh. It would be *better* even to make the = field be 416, as that's an even multiple of 32. That gives you fast = unpacking. If you're not going to do 416, it seems not worth worrying = about the MPI rules, as you already have to have in your library a way = to slosh zero high bits around anyway. For a curve like one of the 255-bit ones, it's easy to stress over that = extra bit, and why *not* just pack it into 256 bits for efficiency? = Don't stress.=20 =20 > I have not yet seen the specs for Curve41417 and thus I do not know > whether it also defines EdDSA for signatures. EdDSA according to the > paper requires the use of SHA512 but it also tells that other hash > algorithms are possible. Hopefully Watson Ladd's I-D can eventually = be > used as a reference. Well, 414-19 is an Edwards curve so you can do EdDSA on it. It's 30 bits = larger than 384, so you could use a 384-bit hash, or a variable-length = hash function like Skein or SHA-512/z. Jon From openpgp@brainhub.org Mon Feb 3 22:53:49 2014 Return-Path: X-Original-To: openpgp@ietfa.amsl.com Delivered-To: openpgp@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 9EEE81A037D for ; Mon, 3 Feb 2014 22:53:49 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -0.002 X-Spam-Level: X-Spam-Status: No, score=-0.002 tagged_above=-999 required=5 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 Xe2m3BCcP2Ax for ; Mon, 3 Feb 2014 22:53:48 -0800 (PST) Received: from qmta11.emeryville.ca.mail.comcast.net (qmta11.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:44:76:96:27:211]) by ietfa.amsl.com (Postfix) with ESMTP id 19EA51A0360 for ; Mon, 3 Feb 2014 22:53:47 -0800 (PST) Received: from omta06.emeryville.ca.mail.comcast.net ([76.96.30.51]) by qmta11.emeryville.ca.mail.comcast.net with comcast id N6tn1n00216AWCUAB6tn0U; Tue, 04 Feb 2014 06:53:47 +0000 Received: from [192.168.1.8] ([71.202.164.227]) by omta06.emeryville.ca.mail.comcast.net with comcast id N6tm1n00G4uhcbK8S6tn7A; Tue, 04 Feb 2014 06:53:47 +0000 Message-ID: <52F08E7A.9000002@brainhub.org> Date: Mon, 03 Feb 2014 22:53:46 -0800 From: Andrey Jivsov User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0 MIME-Version: 1.0 To: openpgp@ietf.org References: <87iot0y1su.fsf@vigenere.g10code.de> <874n4kxqop.fsf@vigenere.g10code.de> In-Reply-To: Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1391496827; bh=bbWlhRrN4TsQCfZ71GvcwusfQ23ZeoH7B9t+jEDRXXg=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=UDWOdHyJsU+IKyC1s5QHlI/WfDjkOtKlqG6MsAi3jhFRr8v3tmWIfB9Wcv0EDTT+3 aC1BTIRbXhtTjd7n2Ki2oKl6Q/EwkywWo+qcvegKuU9xnonbewekgZBrEyMqCbKBrn q0/y7NjBayhSVcKcMYTN+3L1t20ZqoUcUlNQ+keTZqmfKlvvO+b+z6ynTpu9DX6fnN b07EANFx+w77YvClv23b/8V89KOg+qbiZF8Mf3g6grehT0QmFDPESaYlTlM14dlJIC WH3m48/D3sDOcZUYChWiloghN5IuSJZEUGdi8RSryuQ6Eq64fq2IebwkTDlcxqUYtO wcjM0CY5Rqzdg== Subject: Re: [openpgp] Catch 22 in ECC support of OpenPGP? X-BeenThere: openpgp@ietf.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: "Ongoing discussion of OpenPGP issues." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 04 Feb 2014 06:53:49 -0000 On 02/01/2014 04:57 AM, Jon Callas wrote: > Of those two, I vote for (1). There's no real value in the compression, it's an observation. And the reason there's little value in compression is the same reason that there's little harm in just putting the point there and don't worry about leading zeroes. One positive side effect of using compression is that de-compression implies a validated point. In some uses of OpenPGP protocol it may be necessary to validate that the ephemeral public key of ECDH lies on the curve and not on some specially selected curve with points of low order. See "Validation of Elliptic Curve Public Keys" sec 4.2 Invalid-Curve Attack on ECIES (that applies to ECDH as well). From gniibe@fsij.org Wed Feb 5 22:52:59 2014 Return-Path: X-Original-To: openpgp@ietfa.amsl.com Delivered-To: openpgp@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E05FC1A0380 for ; Wed, 5 Feb 2014 22:52:59 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.435 X-Spam-Level: X-Spam-Status: No, score=-2.435 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.535] 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 cwJwnQE96y5j for ; Wed, 5 Feb 2014 22:52:57 -0800 (PST) Received: from atom.fsij.org (atom.fsij.org [211.14.6.125]) by ietfa.amsl.com (Postfix) with ESMTP id E77261A037F for ; Wed, 5 Feb 2014 22:52:56 -0800 (PST) Received: from 241.137.55.36.ap.dti.ne.jp ([36.55.137.241] helo=[192.168.2.105]) by atom.fsij.org with esmtpsa (TLS1.0:DHE_RSA_AES_256_CBC_SHA1:256) (Exim 4.80) (envelope-from ) id 1WBIpL-00022v-5m; Thu, 06 Feb 2014 15:52:48 +0900 Message-ID: <1391669565.1566.5.camel@cfw2.gniibe.org> From: NIIBE Yutaka To: Werner Koch Date: Thu, 06 Feb 2014 15:52:45 +0900 In-Reply-To: <87mwicy20d.fsf@vigenere.g10code.de> References: <1391140017.2806.7.camel@cfw2.gniibe.org> <52EB3FEE.9070205@brainhub.org> <1391154601.2806.10.camel@cfw2.gniibe.org> <87mwicy20d.fsf@vigenere.g10code.de> Organization: Free Software Initiative of Japan Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.8.5-2+b1 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-SA-Exim-Connect-IP: 36.55.137.241 X-SA-Exim-Mail-From: gniibe@fsij.org X-SA-Exim-Version: 4.2.1 (built Mon, 26 Dec 2011 16:24:06 +0000) X-SA-Exim-Scanned: Yes (on atom.fsij.org) Cc: Andrey Jivsov , openpgp@ietf.org Subject: [openpgp] ECDH with Curve25519 (was: Catch 22 in ECC support of OpenPGP?) X-BeenThere: openpgp@ietf.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: "Ongoing discussion of OpenPGP issues." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 06 Feb 2014 06:53:00 -0000 Hello, [ It was me to start this discussion at the gnupg-devel list. As it's better to continue here, I redirect my reply. ] On 2014-01-31 at 09:44 +0100, Werner Koch wrote: > On Fri, 31 Jan 2014 08:50, gniibe@fsij.org said: > > > When Curve25519 will be supported in GnuPG, I think that it's only for > > ECDH (since people use EdDSA with Ed25519, instead of ECDSA with > > I think it makes more sense to use an Ed25519 based ECDH in OpenPGP than > to require the implementation of its Montgomery variant Curve25519. > This would benefit small OpenPGP implementation which won't do the > current MUST algorithms but anyway provide compatibility with general > purpose OpenPGP tools. There might be a small performance drawback but > can be justified by a more compact implementation. The current ECDH > algo ID can still be used for this if we go without point compression. ECDH with Ed25519 would be better for some implementations. For a specification, I think that it is straightforward to define ECDH with Curve25519 (where curve point is represented by Montgomery curve). By the way, I realized that Curve25519 has cofactor 8. It seems for me that many other curves these days have cofactor > 1. RFC 6637 assumes that cofactor is 1. Here is another place to consider. --