Re: [Cfrg] draft-agl-cfrgcurve-00 point format (was: options)

Alyssa Rowan <akr@akr.io> Sat, 10 January 2015 12:35 UTC

Return-Path: <akr@akr.io>
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 86E9A1A875B for <cfrg@ietfa.amsl.com>; Sat, 10 Jan 2015 04:35:00 -0800 (PST)
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, LOTS_OF_MONEY=0.001, SPF_HELO_PASS=-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 evJGMsKmJtck for <cfrg@ietfa.amsl.com>; Sat, 10 Jan 2015 04:34:57 -0800 (PST)
Received: from entima.net (entima.net [78.129.143.175]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 954131A1EED for <cfrg@irtf.org>; Sat, 10 Jan 2015 04:34:57 -0800 (PST)
Message-ID: <54B11C8E.8070001@akr.io>
Date: Sat, 10 Jan 2015 12:35:26 +0000
From: Alyssa Rowan <akr@akr.io>
MIME-Version: 1.0
To: "cfrg@irtf.org" <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>
In-Reply-To: <54B03F3E.3020108@brainhub.org>
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/v2vEiq0KTfzAiM526-B_FQEdlVg>
Subject: Re: [Cfrg] draft-agl-cfrgcurve-00 point format (was: options)
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: Sat, 10 Jan 2015 12:35:00 -0000

-----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.

> (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).

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;
• seems to have clearer IPR, because that check may have patent claims;
• 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.

> 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.

___

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
-----BEGIN PGP SIGNATURE-----

iQIcBAEBCgAGBQJUsRyOAAoJEOyEjtkWi2t6FfAQAL5R20rwtVXLQMhUfAXLp0TQ
TJjTMig2LkQyyhYCEXO9meeVKLINuWT9EVaXy9fdSP6mAQPB8zOfWosqQiwF5StF
3ER4B20BXc1qNDOfl28lpx8MBdDCoBDyfhtoyiRswsXijBhqZhIEXyqKraIjLlCU
+G2+FUXPhGf66Uzjk95+kbZrTonL/ZDK7kDPxYQqsXSzQoOW/Yduj6bk7aOBnLM+
7VW1XWwOQhcgMESFOuDDtR+nEaGkhSdFRaP18txAUPNdOs99Ju/2LDXTiz5zi10S
2Ou/dY6CkX/pXii6zxl+t34rzEAMOnCtfBr/wu76pZLkxoZ2IJmEXdEFD6o9CBRV
PgOdTdvCT4erKba8xca0Im5x4UaWRgj9br6zowNKmBhsYdS45MKe4+aBouoTaUVl
ShQpYCLKn3jnvteQd3IgM7mtFDHSype3lIbyIdV9S6B7KQYgBBD9I5DtaH9NKbce
OyswkQOkI9weJnIIEqSNe1Det+XKEDKx+186WaKcT2n1SBgOjIyvaGU8ZxINvG31
jW+8LTKDbPqARcLmToUrdoBXwKuEIrjI0IWjtuKkYy/1RCajA7Lbwt6fHopWceIx
/NicdUBVY7wO4RWygqL7HecfXFDY5nG03Xm4LPRqJsTNqqSraJ6AgtlLsrMT0zYw
B8EEe2uCAW9CfDmQ5VIX
=i8dO
-----END PGP SIGNATURE-----