Re: [TLS] Curve25519 in TLS

Manuel Pégourié-Gonnard <mpg@elzevir.fr> Wed, 16 October 2013 19:56 UTC

Return-Path: <mpg@elzevir.fr>
X-Original-To: tls@ietfa.amsl.com
Delivered-To: tls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6F84B21F9AE3 for <tls@ietfa.amsl.com>; Wed, 16 Oct 2013 12:56:24 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.949
X-Spam-Level:
X-Spam-Status: No, score=-1.949 tagged_above=-999 required=5 tests=[AWL=-0.000, BAYES_00=-2.599, HELO_EQ_FR=0.35, MIME_8BIT_HEADER=0.3]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id MrNvLPjc+wFe for <tls@ietfa.amsl.com>; Wed, 16 Oct 2013 12:56:10 -0700 (PDT)
Received: from mordell.elzevir.fr (mordell.elzevir.fr [IPv6:2001:4b98:dc0:41:216:3eff:feeb:c406]) by ietfa.amsl.com (Postfix) with ESMTP id 36B9421F9926 for <tls@ietf.org>; Wed, 16 Oct 2013 12:56:04 -0700 (PDT)
Received: from thue.elzevir.fr (thue.elzevir.fr [88.165.216.11]) by mordell.elzevir.fr (Postfix) with ESMTPS id 66E5216153; Wed, 16 Oct 2013 21:55:58 +0200 (CEST)
Received: from [192.168.0.124] (unknown [192.168.0.254]) by thue.elzevir.fr (Postfix) with ESMTPSA id 7D2471F9DA; Wed, 16 Oct 2013 21:55:57 +0200 (CEST)
Message-ID: <525EEF4C.2070203@elzevir.fr>
Date: Wed, 16 Oct 2013 21:55:56 +0200
From: Manuel Pégourié-Gonnard <mpg@elzevir.fr>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Icedove/24.0
MIME-Version: 1.0
To: Watson Ladd <watsonbladd@gmail.com>
References: <a84d7bc61003011620i66fc7dfdre62b548fdd5ef7dd@mail.gmail.com> <522D25B9.7010506@funwithsoftware.org> <56C25B1D-C80F-495A-806C-5DD268731CD4@qut.edu.au> <87zjrl21wp.fsf_-_@latte.josefsson.org> <8738outeup.fsf@latte.josefsson.org> <525E3404.2090808@elzevir.fr> <CACsn0c=nGut9nFErUv9_B-kK+-9sF+FGcQ8kYVDT8jQ0B6_Fnw@mail.gmail.com>
In-Reply-To: <CACsn0c=nGut9nFErUv9_B-kK+-9sF+FGcQ8kYVDT8jQ0B6_Fnw@mail.gmail.com>
X-Enigmail-Version: 1.5.2
OpenPGP: id=98EED379; url=https://elzevir.fr/gpg/mpg.asc
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: 8bit
Cc: Simon Josefsson <simon@josefsson.org>, "tls@ietf.org" <tls@ietf.org>
Subject: Re: [TLS] Curve25519 in TLS
X-BeenThere: tls@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "This is the mailing list for the Transport Layer Security working group of the IETF." <tls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/tls>, <mailto:tls-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/tls>
List-Post: <mailto:tls@ietf.org>
List-Help: <mailto:tls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/tls>, <mailto:tls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 16 Oct 2013 19:56:24 -0000

On 16/10/2013 20:48, Watson Ladd wrote:
> On Tue, Oct 15, 2013 at 11:36 PM, Manuel Pégourié-Gonnard
> <mpg@elzevir.fr> wrote:
>> TLS ECDH:
>> 1. Private keys: random integer in the range [1, q-1] with q the order of G.
>> 2. Public keys: a point on the curve (defined over F_p).
>> 3. Public key encoding: either
>>     (a) the x and y coordinates of the point, or
>>     (b) the x coordinate and a bit for determination of the y coordinate,
>> with integers represented as big-endian bytes strings, preceded by a
>> first byte indicating which format was chosen (and holding the possible
>> additional bit).
>>
> I don't believe this is correct: RFC4492 permits curves with cofactor
> greater than one.  I don't have a copy of the IEEE standard in front
> of me, but I believe in this case one has to do a group membership
> check. So it depends on what the meaning of G is.
>
Yes, sure, when receiving the peer's public key, one must always check
it is actually a point on the expected curve (which is done
automatically in the process of computing y if the compressed format is
used) and, if the group generated by G has cofactor greater than one,
that the peer's public key belongs to this subgroup.

I don't really see how it contradicts my statements, but anyway.

>> 1. Concerning the private key, I think keeping the paper's definition
>> does not raise any issue. Implementors should just be careful to use a
>> special procedure for this curve.
>>
> What is actually happening is that exponentiation by the private key
> is annihilating the small order torsion subgroup on both the curve and
> the twist because the private key is divisible by 8, and the curve and
> twist have large prime-order subgroups with cofactor 8 and 4
> respectively.

100% agreed. I'm just not sure if this precision about the "why" is
essential in the I-D, or if we should just leave it in the paper, and
just mention in the I-D that implementers MUST be careful to generate
private keys in the mandated special way for Curve25519.

> This is a big difference from the usual method, in which one only
> sends members.

Well, to be really nitpicky, if the peer follows the procedure, she will
only send members, just as with the usual method. The difference is,
*if* the peer doesn't send members of the subgroup generated by G (ie by
9 in the Curve25519 case), with the usual method we must check and
reject invalid public keys, and with the Curve22519 we just don't care
since the choice of the private exponent takes care of that for us, as
you accurately described.

>> A. Just use the convention y = 0 and one of the existing formats.
>> Pros: simple, just works.
>> Cons: with the basic "uncompressed" format, wastes 32 bytes of bandwidth.
> Also, a dirty hack.

I don't deny it :)

>> B. Always use the "ansiX962_compressed_prime" format.
>> Pros: doesn't waste bandwidth.
>> Cons: forces applications to advertise support this format, which is a
>> problem if they can't support it for other prime curves, unless we
>> introduce an exception to the effect that support for this format with
>> this particular curve is implied as soon as support for the curve is
>> advertised. Does not seem very clean to me.
>>
> The other issue is that this isn't the ansiX962 format for deep
> technical reasons.  You would need to use a birational morphism to
> Weirstrauß form, which is a pointless PITA, or just tell pleasing
> lies, which annoys those of us trying to analyze things, and is a
> potential source of bugs.

Agreed. What I was suggested was indeed to abuse this format and give it
a different meaning just for this curve. Which may be qualified as a
dirty hack too, obviously.

>> C. Introduce a new point format "compressed_prime_montgomery".
>> Pros: doesn't waste bandwidth, doesn't look hacky.
>> Cons: a new point format only for one curve? OTOH, it is indeed a
>> particular class of curve, since the recommended formulas work only with
>> the x coordinate, and other curves in this class may be added later.
>>
> Probably the best idea, especially given that definition of addition
> is completely different.

It's certainly the less hackish way.

Thinking about it, I'm inclined to say we don't need to define a new
ECPointFormat entry, the I-D should just mandate that support for (resp.
use of) curve25519 implies support for (resp. use of) the associated
(unamed) point format. This avoids possible consistency issues like a
client advertising support for the curve but not for the associated
point format.

Similarly, the usual point formats have a leading byte indicating the
format used, that should IMO be dropped for curve25519.

So this would lead to the definition that, for this curve, instead of
containing "the byte string representation of a field element following
the conversion routine in Section 4.3.3 of ANSI X9.62", the point member
of the ECPoint structure contains an opaque[32] representing the
x-coordinate of the point.

Which would only leave the issue of the byte order of this string. Here
it has no security implications, and I'd be inclined to mandate
big-endian order (a divergence from the Curve25519 paper), with the
rationale that is it more consistent with other encodings and that
implementations already have routines for outpouting bignums in this
order. OTOH, this would mean that people using the existing/reference
implementations of the Curve25519 function would need to reverse its
output/inputs. Either way I don't have strong feelings about this.

Manuel.