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

Andrey Jivsov <crypto@brainhub.org> Tue, 02 September 2014 23:52 UTC

Return-Path: <crypto@brainhub.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 763491A0B7D for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 16:52:51 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, 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 WJxe9F1IOLJS for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 16:52:49 -0700 (PDT)
Received: from qmta02.emeryville.ca.mail.comcast.net (qmta02.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:24]) by ietfa.amsl.com (Postfix) with ESMTP id 0D5991A0390 for <cfrg@irtf.org>; Tue, 2 Sep 2014 16:52:48 -0700 (PDT)
Received: from omta08.emeryville.ca.mail.comcast.net ([76.96.30.12]) by qmta02.emeryville.ca.mail.comcast.net with comcast id mPlX1o0030FhH24A2Psocn; Tue, 02 Sep 2014 23:52:48 +0000
Received: from [IPv6:::1] ([71.202.164.227]) by omta08.emeryville.ca.mail.comcast.net with comcast id mPsn1o0014uhcbK8UPsnMG; Tue, 02 Sep 2014 23:52:48 +0000
Message-ID: <5406584E.3060000@brainhub.org>
Date: Tue, 02 Sep 2014 16:52:46 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0
MIME-Version: 1.0
To: Nico Williams <nico@cryptonector.com>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com> <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com> <CACsn0cktxTyPpeaqKU-oL+DiP4Fu0risHB1Wx8-by+94s30h=g@mail.gmail.com> <CA+Vbu7yMvyPzRAGrtVH38mzaYy3XQ1wswEUQisqbwpT10JfQVg@mail.gmail.com> <54058021.9040801@cs.tcd.ie> <CACsn0c=XV4bQSa7Oh3=s+JvFpJdT3Lm16wQHRG2ACEjxuU-dvg@mail.gmail.com> <5405E343.7010302@cs.tcd.ie> <5406387E.4060507@brainhub.org> <54063AEA.7060903@cs.tcd.ie> <54063D8B.7020302@brainhub.org> <CAK3OfOgJWkYS5NkO2ffJQshE8sO1hFu0UJGZ-akSs93PxSbTBw@mail.gmail.com>
In-Reply-To: <CAK3OfOgJWkYS5NkO2ffJQshE8sO1hFu0UJGZ-akSs93PxSbTBw@mail.gmail.com>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1409701968; bh=nCnawU/Ds83HoBOuKrFwrE133YDSKSIAeJ0vgxyCeLQ=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=acP+RHJl5uTXEBTmzNxd73c3veSHaf3M7tZ08NlD/0LT756eYP6R+xlq0aUS7R8Tg Fu4PKfgqf4cYUkE2/MbqJONr14sCWYTs28VbZhkEMMIdIeVZOpbjJvYGxkuLhpCGjB 8u6mgZN9fWuGftaDamOPnuCvC1cSWX6T7PsOP+WtV2SHfJk9gDSzIEU21Q6rkxTe/a 317GVkiZZwSDKCO63nMJ3ymSaXE7NRjw1Oc93FSiVLpaSKWY6egAR5OiRFE+/72r3G N09eQQpb4tarbW0DG4RfmFLk/3s1NiGZTREhJgW+efy4BWKmNdWhYZCpgEZfWGRX1g gzFmxAsSpCOdQ==
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/n4Ik28PPpXblC_c2HatW9lh7DVc
Cc: cfrg@irtf.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 23:52:51 -0000

On 09/02/2014 03:59 PM, Nico Williams wrote:
> On Tue, Sep 2, 2014 at 4:58 PM, Andrey Jivsov <crypto@brainhub.org>; wrote:
>> On 09/02/2014 02:47 PM, Stephen Farrell wrote:
>>> Can you give me an example of such an IETF protocol? Without
>>> having thought much about it, I think there are always different
>>> codepoints allocated for DH and signatures, and I doubt we'd
>>> want the same private values shared anyway, so I'm not sure
>>> if that's a real or a theoretical issue.
> +1.  We generally strive for key hygiene.  We'd not use a key for
> different purposes.
>
> What is the use of using the same key for DH and signatures in the
> same protocol?  I can only think of a round-trip optimization, but
> what I have in mind is very handwavy and not likely to be a win
> (partly because it means losing PFS).
>
>> A few examples of dual-key use and a bit braader question of whether would
>> want to add points as oppose to only do scalar multiplication.
>>
>> Some TLS server side fixed-base optimization will benefit from point
>> addition.
> Can you give some more details of what this would mean protocol-wise?
The format on the wire is not affected, but if there is a penalty for 
point addition, this is a property that didn't exist for, say P-256.

Consider the following example of an optimization a server might have to 
produce a fresh ephemeral key (proof omitted but I think is possible):

Generate n keypairs {ki, kiG}. There are about n^2/2 of the unique 
pairs. The ephemeral key is {ki+kj}G, which is done with a single point 
addition. Thus, sqrt(n) keygens provide n ephemeral keys.

This can be viewed as a special case of fixed-point optimization.


>> While OpenPGP RFC 4880 has a concept of a "bundle of keys" things are easier
>> when the top key can have both encryption and signing capability. There are
>> products that add X.509 certs to PGP keys.
> Yes, I could see this.  Though key bundles have been around for long
> enough (and in widespread enough use) that it doesn't seem likely to
> matter much.

Signatures in OpenPGP "live" on the top key. It's more challenging to 
add X.509 certs to subkeys. X.509 certs on subkeys might go into 
notation packets, but notations are a part of self-signatures are 
therefore signed by the top key, which poses challenges if one wants to 
do management like removal of certificates (by untrusted entity like a 
key server)

>
>> Signing a certificate request for a DH key to prove key possession.
> A self-signed DH cert.  OK, this one makes some sense, but if the
> price is losing PFS or paying extra CPU cycles if you want PFS, then
> it seems not worthwhile.
>
> On the other hand, if using the same key for DH and signatures is
> worthwhile, then it seems likely that point form conversion won't be a
> big deal.  No?

Also CSRs for DH keys, if you want to do ECDSA-like signature with a DH key.

Keys with 10% penalty should be viewed as "optimized" for particular use 
based on the choice of coordinate system.

Compare this with conversion between Montgomery coordinates and Short 
Weierstrass coordinates 
(http://www.ietf.org/mail-archive/web/cfrg/current/msg04996.html): there 
is no such penalty for such a pair.

>> Protocols for applications with space-saving requirements : keys on URLs or
>> e-mail aliases, pre-generate keys "for everybody" to represent identities.
>> Keys that are handled by humans (e.g. typed in base32 encoding), etc
> Yes, this is a clear win.  But again, any point conversion penalty
> seems minor for such a protocol.

Depends on the case. If you think something like SMIME/CMS on outgoing 
e-mails, they will likely get signed+encrypted (to self, when placed 
into the Sent folder) . Not an issue for TLS clients, though.
...