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

Michael Hamburg <mike@shiftleft.org> Wed, 03 September 2014 00:20 UTC

Return-Path: <mike@shiftleft.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 ED4AD1A6EF9 for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 17:20:27 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 1.556
X-Spam-Level: *
X-Spam-Status: No, score=1.556 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FH_HOST_EQ_D_D_D_D=0.765, FH_HOST_EQ_D_D_D_DB=0.888, HELO_MISMATCH_ORG=0.611, HOST_MISMATCH_NET=0.311, HTML_MESSAGE=0.001, RDNS_DYNAMIC=0.982, SPF_HELO_PASS=-0.001, 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 lMJPXzoGVkq9 for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 17:20:25 -0700 (PDT)
Received: from aspartame.shiftleft.org (199-116-74-168-v301.PUBLIC.monkeybrains.net [199.116.74.168]) (using TLSv1.1 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A8FF71A8914 for <cfrg@irtf.org>; Tue, 2 Sep 2014 17:20:23 -0700 (PDT)
Received: from [192.168.1.135] (unknown [192.168.1.1]) by aspartame.shiftleft.org (Postfix) with ESMTPSA id 892053AA12; Tue, 2 Sep 2014 17:17:49 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=shiftleft.org; s=sldo; t=1409703469; bh=7qkSHYW+Udm9gsnJ1RYVjvTNf0D4MMvYsbBaKnzhdI0=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=QjXbDE2j5RuqH5xJpY/UX/kW05oLni/Q3/jYLll0Lt8UvS59UzH7hwyJssocz52mw QaJRvop1A/m1rTXrxVhMFOHqYoUNVKud9ejTQT9iBJxGkxT61aXLgZAbiieToK2oJh bg8+kJoRNeT8kBHW+W2d4brQzOJp0SsUaVgSYv8k=
Content-Type: multipart/alternative; boundary="Apple-Mail=_6D251047-4C45-4031-8577-7F3BE7FA8F5C"
Mime-Version: 1.0 (Mac OS X Mail 8.0 \(1973.6\))
From: Michael Hamburg <mike@shiftleft.org>
In-Reply-To: <5406584E.3060000@brainhub.org>
Date: Tue, 2 Sep 2014 17:20:21 -0700
Message-Id: <7B0EC922-D82E-441A-AC3C-B62C6A22ABC1@shiftleft.org>
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> <5406584E.3060000@brainhub.org>
To: Andrey Jivsov <crypto@brainhub.org>
X-Mailer: Apple Mail (2.1973.6)
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/A3H6J3KgJVz31npv7zlas27Q8_Q
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: Wed, 03 Sep 2014 00:20:28 -0000

There isn’t actually a 10% penalty for switching forms unless you are translating between two different wire formats.  If one side or the other is internal to the application, it will be projective, which makes translation free unless the format is compressed.

There’s a 10% penalty for decompressing points, if they’re compressed going down the wire.  This is true almost no matter how you compress them, except that you can do the Montgomery ladder without decompressing if you have a suitable coordinate.  So for example:

Montgomery x only: Can’t add points at all.  Technically can check signatures, but don’t do it this way.  Ladderable.

Montgomery (x,y): No 10% penalty for decompression.  Ladderable (you can recover y at the end for cheap).

Montgomery (x,bit): Needs decompression before you can add, costing 10%.  Ladderable, but the recovery may be complicated depending on how the bit is computed.

Montgomery 1/sqrt(x): Needs decompression before you can add, costing 10%.  Ladderable.  Uses p==3 mod 4.

Edwards (x,y): No 10% penalty for decompression.  Not ladderable (there’s an Edwards ladder but it isn’t as efficient).

Edwards (bit,y): Needs decompression before you can add, costing 10%.  Not ladderable.

Edwards x/y: Needs decompression before you can add, costing 20% (unless someone can improve?).  Ladderable.

By “ladderable”, I mean that you can do a nearly-unmodified 5M+4S Montgomery ladder without decompression, then recompress at the cost of about one exponentiation in the base field.

Because I believe point compression to be commonly desirable, and ladderability to be “nice to have”, I’m currently using 1/sqrt(x) as a wire format for all points in my software.

Also, before someone says the Montgomery ladder isn’t actually faster: in my experience it is faster even at 512 bits if it lets you skip decompression, but at that size it only beats Edwards by 5-10%, so not a big deal.

Cheers,
— Mike

> On Sep 2, 2014, at 4:52 PM, Andrey Jivsov <crypto@brainhub.org>; wrote:
> 
> 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 <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.
> ...
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org <mailto:Cfrg@irtf.org>
> http://www.irtf.org/mailman/listinfo/cfrg <http://www.irtf.org/mailman/listinfo/cfrg>