Re: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Additional Curves in TLS

Andrey Jivsov <crypto@brainhub.org> Fri, 24 January 2014 01:04 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 74E541A0276 for <cfrg@ietfa.amsl.com>; Thu, 23 Jan 2014 17:04:32 -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, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 AoX2ngfy7K6q for <cfrg@ietfa.amsl.com>; Thu, 23 Jan 2014 17:04:28 -0800 (PST)
Received: from qmta10.emeryville.ca.mail.comcast.net (qmta10.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:17]) by ietfa.amsl.com (Postfix) with ESMTP id C40BB1A012B for <cfrg@irtf.org>; Thu, 23 Jan 2014 17:04:28 -0800 (PST)
Received: from omta03.emeryville.ca.mail.comcast.net ([76.96.30.27]) by qmta10.emeryville.ca.mail.comcast.net with comcast id HcjJ1n0020b6N64AAd4Tno; Fri, 24 Jan 2014 01:04:27 +0000
Received: from [127.0.0.1] ([71.202.164.227]) by omta03.emeryville.ca.mail.comcast.net with comcast id Hd4Q1n00p4uhcbK8Pd4SBM; Fri, 24 Jan 2014 01:04:27 +0000
Message-ID: <52E1BAE0.8060809@brainhub.org>
Date: Thu, 23 Jan 2014 16:59:12 -0800
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.1.0
MIME-Version: 1.0
To: cfrg@irtf.org
References: <87ob3456s1.fsf@latte.josefsson.org> <CABqy+spt7BYqjsqLAkZssGp3aY9M+iLqV+pmyr7ZN-TXmJJpVg@mail.gmail.com> <52E060D0.9030801@polarssl.org> <CABqy+spJoswrPovxf18QS1SGdk6K=mfny6joJm3X24Vh65oagQ@mail.gmail.com> <52E0E241.40406@polarssl.org> <CABqy+sqs31ATDWJSum55m1o5pRvw8Wq5GtB-mF-hgP2emB5eFQ@mail.gmail.com> <CABqy+sozYSOTh7pbUS2GXf=4kYV3zgztXZBa10Bx=s-N8zHHyA@mail.gmail.com> <CABqy+soSojSMfx=yU9eFhmAeuJaJ_r=4h=RDR6JtOchYZ9zsQA@mail.gmail.com>
In-Reply-To: <CABqy+soSojSMfx=yU9eFhmAeuJaJ_r=4h=RDR6JtOchYZ9zsQA@mail.gmail.com>
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=q20121106; t=1390525467; bh=PGQK/gX1ZF/facXwsOMlNabg9ABer1X3dSrU1X9a/70=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=muSqZ//ZYEYxhde7AqaNNRiVSQUG+ajO0e5wBvpVvtWvI+mfAIqi2n/p0LPt9QuES K9O5ULvjD3COQcfc0WdLk6AriCTaukgLT2F8pCZtRuC0J0TRQrKDFHPDe/vK+xjEvv A1RZCL1t/rSsgzLDVw1VZZommc7hfHf0xma9R2JGufQt5nbcIbVkncJA+Xvkz4ASCE HNZEPvvuAbTxLO5ch81gaFjfxKK5TzAWFL6FWymiK/384kNci4bGS8LDRO+GtwMYq6 SnYnfOqfhsk3YxoSUqiPsAzxNbgDV/dm89cGGrynr3+2v8q6KgGNcjTf3m4hSPKgck uZa4BxQFLyu4A==
Subject: Re: [Cfrg] Fwd: [TLS] Curve25519 in TLS and Additional Curves in TLS
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: Fri, 24 Jan 2014 01:04:32 -0000

On 01/23/2014 02:18 PM, Robert Ransom wrote:
> This is relevant to CFRG discussions as well, and I don't know whether
> everyone on the CFRG list is also subscribed to the TLS list.
>
> ---------- Forwarded message ----------
> From: Robert Ransom <rransom.8774@gmail.com>
> Date: Thu, 23 Jan 2014 13:37:18 -0800
> Subject: Re: [TLS] Curve25519 in TLS and Additional Curves in TLS
> To: Manuel Pégourié-Gonnard <mpg@polarssl.org>
> Cc: tls@ietf.org
>
> On 1/23/14, Robert Ransom <rransom.8774@gmail.com> wrote:
>> On 1/23/14, Manuel Pégourié-Gonnard <mpg@polarssl.org> wrote:
>>> On 23/01/2014 02:17, Robert Ransom wrote:
>>>> * If you do not add a leading point-format byte, there is no reason to
>>>> specify the meaning of the high bit in this document.  If you do add a
>>>> leading byte, you will have to choose in this document whether the
>>>> sign bit is for the Edwards-form x coordinate or the Montgomery-form y
>>>> coordinate.
>>>>
>>> Or we could add a leading byte now and say that the meaning of the msb is
>>> not
>>> defined yet an reserved for future use (which is what you suggest anyway,
>>> IIUC).
>>> Then a future document could update the meaning of this leading byte.
>> I think that's easiest (provided that current implementations also
>> accept 64-byte points and discard the second half; see below).
> On further thought, there is a major technical benefit to sending
> (either all of or a sign bit for) the Edwards-form x coordinate rather
> than the Montgomery-form y coordinate.  Denoting the Montgomery-form
> point as (u, v) and the Edwards-form point as (x, y), the isomorphism
> from Montgomery form to Edwards form computes x = 2 u/v, which is
> undefined for the point of order 2 (Montgomery (0, 0)).
>
> I think that issue, combined with the fact that implementations which
> use the sign bit will almost certainly use Edwards form internally,
> should rule out any use of a Montgomery-form y coordinate in any
> current or future protocol.
>
> Since Curve25519's coordinate field order is congruent to 5 mod 8,
> there is no notion of ‘principal square root’, and thus no plausible
> alternative to using the least significant bit of a coordinate as its
> sign bit.  So there is only one likely choice of sign bit for
> Curve25519 group elements, and that is the LSB of the Edwards-form x
> coordinate.

Wouldn't http://tools.ietf.org/html/draft-jivsov-ecc-compact be another 
method?

Traditionally the problem was solved by carrying 1 bit and then finding 
a place to fit it in and defining what it means, etc. There is another 
way. One can adjust the private key to make the coordinate that we drop, 
x in this case, be the smallest of the two possibilities.

The nice feature of my proposal is that you can still also encode the 
bit if you wish so, as you proposed.

>
> Now that I'm not worried about what will eventually be chosen as the
> sign bit, the only reason I can see to use a leading magic byte in the
> point format is to distinguish ‘the sender did not compute the sign
> bit of this point’ from ‘the sender computed the sign bit of this
> point, and it is 0’.  I have previously suggested that distinguishing
> those cases could be useful, but now I think mitigation of
> implementation fingerprinting is more important -- I see no reason to
> advertise whether an implementation computes the sign bit of its group
> elements or not, even if an attacker could infer that piece of
> information after a series of connections.

That's why I think that the party that generates the key needs to be 
nice to everybody and make the key "compliant". If you mandate a very 
fast adjustment Order-private_key (if you have to), there is no ambiguity.

In general, I think that whatever the encoding of the bit is, it needs 
to be fixed in the document.

( BTW, the proposal in the draft is in public domain since it was 
published on December 10, 2012. )