Re: [Cfrg] draft-agl-cfrgcurve-00 point format

Andrey Jivsov <crypto@brainhub.org> Mon, 12 January 2015 09:02 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 4BA2B1A1B3E for <cfrg@ietfa.amsl.com>; Mon, 12 Jan 2015 01:02:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, LOTS_OF_MONEY=0.001, 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 mz3QhA-iAcC3 for <cfrg@ietfa.amsl.com>; Mon, 12 Jan 2015 01:02:21 -0800 (PST)
Received: from resqmta-ch2-04v.sys.comcast.net (resqmta-ch2-04v.sys.comcast.net [IPv6:2001:558:fe21:29:69:252:207:36]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D5EDB1A1B42 for <cfrg@irtf.org>; Mon, 12 Jan 2015 01:02:20 -0800 (PST)
Received: from resomta-ch2-16v.sys.comcast.net ([69.252.207.112]) by resqmta-ch2-04v.sys.comcast.net with comcast id ex2L1p0012S2Q5R01x2LJV; Mon, 12 Jan 2015 09:02:20 +0000
Received: from [172.18.75.35] ([76.247.118.9]) by resomta-ch2-16v.sys.comcast.net with comcast id ex0B1p00B0CF8l001x0EVj; Mon, 12 Jan 2015 09:00:18 +0000
Message-ID: <54B38D1B.9020501@brainhub.org>
Date: Mon, 12 Jan 2015 01:00:11 -0800
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <54AAE2CA.1080701@isode.com> <54AEF855.4090100@brainhub.org> <CACsn0cm01o4vhwwzs_WNpLq6vnA_cBchvLNS+Eyg5YZH_hQyMg@mail.gmail.com> <54AF1C99.5070308@brainhub.org> <54AFA179.4010403@cs.tcd.ie> <54B03F3E.3020108@brainhub.org> <54B11C8E.8070001@akr.io>
In-Reply-To: <54B11C8E.8070001@akr.io>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1421053340; bh=3Skw8Rm3RolYcKLtUwRMgfILa71aKDS0eGsgb7mkGgk=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=GbcQVmhi62Fh/c2laVwqyKljvkHbeNODkQDfMgwv3/Tk+kPyX6TApYzSd2WzCLyKL JXdVzrSrjQzxgHFqF2u5C2q4UTBmkcT77xUeVs0OBq58wG8B2ecClrQHPuNhwUPh9N dYGMyznvuPvKGrnOXv1iNR7fLOV1Be9DEO+EDv4KUcCie2OYg3X3069rhhp54zP5yt F36worBVO5BtQ4+8m0mT3k3jINpFGsYu4TmyfUbTHCjUhmBqnBVjeZzN8nDPSLjwN0 irchVzf9ZiMZkD777c6FNfG1f8VMIVB+MhgP4YTKV8ru6yhPDsPVVj+DHlGRpqCYfv u1cmyJco2U0YQ==
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/h_qcZVZu7jkrGijBYTrNz3S8XQ0>
Subject: Re: [Cfrg] draft-agl-cfrgcurve-00 point format
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: Mon, 12 Jan 2015 09:02:24 -0000

On 01/10/2015 04:35 AM, Alyssa Rowan wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> On 09/01/2015 20:51, Andrey Jivsov wrote:
>
>> Hello Stephen. I agree in general that fewer options is a good
>> thing.
>
> Agreed there too.
>
>> A single format across security strengths and algorithm types means
>> fewer options.
>
> Now, the upstream WG asking for these curves has actually already
> covered this point (if you'll excuse the pun!).
>
> The TLS WG discussed point compression specifically¹ and thought there
> was value for TLS 1.3.
>
> In Hawaii² they decided to use uncompressed points for existing NIST &
> Brainpool curves (due to the inertia you noted, and the now-expired
> patent, essentially nobody used compressed points with the NIST &
> Brainpool curves) - but to allow new curves (i.e. us) to define their
> own wire format individually, which is what is done in the draft, and
> that this could be compressed. (X25519, as Curve25519, was in fact
> specifically raised within that discussion³.) So…
>
>> …the point representation negotiation defined in TLS…
>
> …is being removed from TLS 1.3. And we can do pretty much what we want.

It looks reasonable to remove compression negotiation packets from TLS.

To allow other implementations besides the Montgomery ladder y is 
probably need to be a part of point format on the wire to avoid the ~10% 
penalty to recover it.

>
>> (If you like Montgomery ladder, just ignore the other 32 bytes
>> representing the y; one shouldn't care about 32 bytes in a ~4Kb TLS
>> handshake).
>
> "Ignore it if you like" is just an option (to ignore it) in a fancy hat.
> Drawback: fingerprinting. An attacker can tell which ignore y and which
> don't (and therefore which might have omitted or screwed up a vital
> validation step).

One would likely need (x,y) to allow the choice of (internal, invisible 
to a peer) implementations. It's almost certain that sending only x 
significantly benefits the Montgomery ladder implementation, because 
there will unlikely be a faster implementation that uses only x (or 
doesn't benefit from the input point being in affine form, so that z!=1 
can be used without cost).

When both (x,y) are used in the scalar multiplication formula, 
re-computing y from x has ~10% cost.

>
> I also note patent US6563928 appears (to me, and others) to claim on
> point validation to avoid small-subgroup attacks⁴ in some contexts. Dan
> Brown disclosed this patent previously on the list, querying whether it
> may impact twist security⁵. It expires (I believe) mid-May 2015 - and I
> (again) do not specifically address its applicability or validity here,
> merely note the concerns.
>
> djb, in Curve25519, specifically used the point format from Miller
> [1986], and deliberately doesn't compute y. So…

>
>> …the de-facto standard on the Internet is to use uncompressed
>> point.
>
> …the de-facto standard for _this curve_ is to use _compressed_ point, as
> in the draft. It:

>
> • is simpler as it doesn't need a (critical) point validation check;

I think 'critical' is arguable for twist-secure curves and TLS ECDH, 
however, please note that the Montgomery ladder is an implementation 
choice when one doesn't wants these checks.

> • seems to have clearer IPR, because that check may have patent claims;

The abstract of the patent telling to multiply by a cofactor (8) to 
avoid a small subgroup is also an issue.

> • is slightly smaller; and,
> • is already supported by all the widely-deployed code for this curve.
>
> No sale on a change there, as far as I'm concerned: I don't see the
> significant benefit.

Thank you for the feedback, Alyssa.

>
>> I would say that I care about 10% because Curve25519 Montgomery
>> ladder is ~60% faster than P-256 on modern x86.
>
> Um, perhaps I just haven't had enough tea this morning to follow what
> you mean here?
>
> I'm also not sure the performance gap is that wide anymore, see Intel's
> nistz256 contribution to OpenSSL.

The ratio is from 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05251.html . It's 
about the same 60% on Haswell.

>
> ___
>
> Footnotes (for easy reference):
>
> [1] <https://www.ietf.org/mail-archive/web/tls/current/msg14087.html>
>
> [2]
> <https://www.ietf.org/proceedings/interim/2014/11/09/tls/minutes/minutes-interim-2014-tls-4>
>
> [3] <https://www.ietf.org/mail-archive/web/tls/current/msg14088.html>
>
> [4] US6563928, Menezes-Qu-Vanstone, Certicom
> <https://www.google.com/patents/US6563928>
>
> [5] <https://www.ietf.org/mail-archive/web/cfrg/current/msg05588.html>
> although you may find it easier to read
> <https://www.ietf.org/mail-archive/web/cfrg/current/msg05589.html> and
> down. Short answer: no.
>
> [6] <https://www.ietf.org/mail-archive/web/cfrg/current/msg04766.html>
>
> - --
> /akr
...