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

Robert Ransom <rransom.8774@gmail.com> Fri, 24 January 2014 03:17 UTC

Return-Path: <rransom.8774@gmail.com>
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 699BB1A012A for <cfrg@ietfa.amsl.com>; Thu, 23 Jan 2014 19:17:15 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.75
X-Spam-Level:
X-Spam-Status: No, score=-1.75 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, SPF_PASS=-0.001] autolearn=no
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 nTpne7qNzF67 for <cfrg@ietfa.amsl.com>; Thu, 23 Jan 2014 19:17:14 -0800 (PST)
Received: from mail-qa0-x233.google.com (mail-qa0-x233.google.com [IPv6:2607:f8b0:400d:c00::233]) by ietfa.amsl.com (Postfix) with ESMTP id DD9F11A0141 for <cfrg@irtf.org>; Thu, 23 Jan 2014 19:17:13 -0800 (PST)
Received: by mail-qa0-f51.google.com with SMTP id f11so3253827qae.24 for <cfrg@irtf.org>; Thu, 23 Jan 2014 19:17:12 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=fYLiJm/Yv5dJAOe6JPEUkRRz3k0/ZHJCns2bn4BapX0=; b=q5kbDuQ2Txb+xPWVhVBj+p+qbqvIMIZYhiHZwRyKiYWNmPlcEtKF9Bs913Uq8pbZp7 fSZ0sKSdO72mDc+MPMuGljmvLz2eXjGZCEKKUojtgWQLn8Yv1hCY1UktvcZ7tnm4eoza 7SZ2xNeJ2V+hb95vxbAhzrWfEwVYqY4ODdFedIfLCrbs8BvI7sqEUq1fDEQN6EDoxtQ8 JDggFhZoDNtzz6laLhsr7Oa14a3Ud/wA057QJe6l63xN1srTn4evViItKV+uyr+JHy1V tuI56Q1nYkGyKvC4XB4nWk3r7w7cRoX8XGbTO0wusUtNZN1TKFzeOlbiOfIqBzSthfgM 1zQg==
MIME-Version: 1.0
X-Received: by 10.140.47.212 with SMTP id m78mr15972582qga.21.1390533432694; Thu, 23 Jan 2014 19:17:12 -0800 (PST)
Received: by 10.229.181.132 with HTTP; Thu, 23 Jan 2014 19:17:12 -0800 (PST)
In-Reply-To: <2311ADE0-B85D-4EEA-A675-03ED3735DE1D@shiftleft.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> <52E1BAE0.8060809@brainhub.org> <2311ADE0-B85D-4EEA-A675-03ED3735DE1D@shiftleft.org>
Date: Thu, 23 Jan 2014 19:17:12 -0800
Message-ID: <CABqy+souWU30JvfzE61GY11gZLevL+Ru50GHkxJDfCkLMuRYqg@mail.gmail.com>
From: Robert Ransom <rransom.8774@gmail.com>
To: Michael Hamburg <mike@shiftleft.org>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] [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 03:17:15 -0000

On 1/23/14, Michael Hamburg <mike@shiftleft.org> wrote:
> On Jan 23, 2014, at 4:59 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
>>
>> 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.
>
> This is interesting, but I think it works better with the Edwards
> x-coordinate instead of the Montgomery y-coordinate.  That is, it applies
> well to Watson’s (Montgomery x, Edwards x) representation.  This is because
> not every point you might want to transmit is a public key; it might be the
> product of something which does not support an easy negation, such as PAKE.
> In this case, with your proposal, implementers have to send the sign bit,
> and we have two wire formats again.  But if the Edwards x-coordinate is
> used, you can also fast-adjust by adding the point of order 2, which maps
> EdX to -EdX.  (It maps EdY to -EdY and MontX to 1/MontX.)  If the protocol
> wipes out the cofactor (almost every protocol does for security reasons),
> then this is more likely to be acceptable than negating the point.

This makes point encoding to Montgomery-form x slightly less efficient
and more complex -- instead of computing (for the main coordinate)
Zinv=1/Z, then x=X*Zinv, this requires XZinv=1/(X*Z), then either
x=X^2*XZinv or xinv=Z^2*XZinv (conditional on the sign bit of the
Edwards-form x coordinate).  (I'm omitting the part where Zinv or
XZinv must be batched with the inversion to compute the Edwards-form x
coordinate and its sign bit.)

(It may still be worthwhile; I'm just pointing out exactly what effect
this would have on implementations.  I should also point out that the
Montgomery-form x coordinate can't distinguish the identity element
from the point of order 2.)


Robert Ransom