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

[Andrey Jivsov <[e-mail]>]

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