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

Andrey Jivsov <crypto@brainhub.org> Fri, 24 January 2014 20:07 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 62D431A0047 for <cfrg@ietfa.amsl.com>; Fri, 24 Jan 2014 12:07:53 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.301
X-Spam-Level:
X-Spam-Status: No, score=-1.301 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, J_CHICKENPOX_12=0.6, 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 IEgK6i4g6nOM for <cfrg@ietfa.amsl.com>; Fri, 24 Jan 2014 12:07:51 -0800 (PST)
Received: from qmta14.emeryville.ca.mail.comcast.net (qmta14.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:44:76:96:27:212]) by ietfa.amsl.com (Postfix) with ESMTP id 990001A001A for <cfrg@irtf.org>; Fri, 24 Jan 2014 12:07:51 -0800 (PST)
Received: from omta02.emeryville.ca.mail.comcast.net ([76.96.30.19]) by qmta14.emeryville.ca.mail.comcast.net with comcast id Hrft1n0030QkzPwAEw7q3S; Fri, 24 Jan 2014 20:07:50 +0000
Received: from [127.0.0.1] ([71.202.164.227]) by omta02.emeryville.ca.mail.comcast.net with comcast id Hw6r1n00i4uhcbK8Nw6sye; Fri, 24 Jan 2014 20:07:50 +0000
Message-ID: <52E2C6A2.1010403@brainhub.org>
Date: Fri, 24 Jan 2014 12:01:38 -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: Michael Hamburg <mike@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> <52E208AD.2020100@brainhub.org> <0F98B193-910E-430B-A5DF-4F72A3D9C6EC@shiftleft.org>
In-Reply-To: <0F98B193-910E-430B-A5DF-4F72A3D9C6EC@shiftleft.org>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1390594070; bh=mO/9YyO+RqvPrT4lke/+x7ZqIuAuizoYYwtBW9QxOVw=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=pJJTabez6naw+mcXrOYoNUrXo0Dfr4nr+QndlUIy4HU66YxCCwjgjrPcV4s6hPLuu +MOhAV3IhMcEDcZy7Oajtuzu5Z0rCZWrzH2JeZHMPGzNzJ0pU4ryWRqL/E/p0Iy8kK MS4QqkIE+mzEkIsP1CPqOSsU+aBkoRtxu50v5TRcN0FnN3MCY+cSFI1kayAm8tYe8T fl4FnFg6aKOWHjm3M3twcSF8SUiFVyxYJqWSJTmPklkNmssdQBTWOFwsEPPprFA/3F yuJDhjm7K4OSZaTceb9l7/tSP0uvtRJj2eNBmbd/HXcZlwEktiZHQHX/ZsLes+XJIY cCHa1MXaiIg/g==
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 20:07:53 -0000

On 01/24/2014 10:44 AM, Michael Hamburg wrote:
> On Jan 23, 2014, at 10:31 PM, Andrey Jivsov <crypto@brainhub.org> wrote:
>
>> On 01/23/2014 06:08 PM, Michael Hamburg 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.
>>>
>>> Then again, any discussion like this is fraught with issues about alternative encodings for non-wire formats, implementation compatibility, uniqueness, covert channels, etc.  Might take some hashing out.
>>>
>>> Cheers,
>>> — Mike
>>>
>> It seems to me that it will be possible to find an option to tweak the private scalar in more complex protocols, while making this an internal adjustment.
>>
>> For example, in
>> http://tools.ietf.org/search/draft-irtf-cfrg-dragonfly-02#page-10
>>
>> the PE is never sent out, so its generation doesn't change.
>>
>> The Element is a point, which is very similar to a public key for our purpose. The Element is sent to the other peer and it needs to be "compliant". The element is generated from a random mask and PE; thus the mask can be adjusted appropriately so that the Element is "compliant" (then the 'scalar' is calculated with the appropriately adjusted mask).
>
> Dragonfly, SPEKE and ECDH don’t use addition, and don’t need y-coordinates at all.  They could use a Montgomery ladder and never compute or transmit those coordinates.
>
> Some systems, such as signatures, use addition but don’t send the results out on the wire.  Your technique works well for those.  You still need a point encoding before hashing, but compression has no value there anyway.
>
> But I can’t think of an obvious way to extend your approach to a protocol like SPAKE2 which requires sending a point out after addition.
I looked at this description of SPAKE2 
http://www.ietf.org/mail-archive/web/cfrg/current/msg03840.html

I will use the additive notation. Assuming M=m*G, the SPAKE2 client 
sends the point (x+h(pass)m) G

It must be a compliant point. Let's say that the client must adjust (1) 
to (2)

    (x+h(pass)m)  (1)
    Ord - x - h(pass)m   (2)

Doing just that will not work because the server will be subtracting (in 
effect) h(pass)m and the server will not arrive at either x or Ord-x.

Here is what the client does instead.

The client adjusts the randomly generated x as

    x' = Ord - x - 2h(pass)m

and assumes x' and x'*G as the ephemeral keypair (corresponding to the 
g^x in the above email reference)

Now, with that private x' plugged into the equation (1), (1) is exactly 
(2), which we said is a compliant point. Then the value in (2) times G 
is sent out.

Performance-wise, the delta = Ord - 2h(pass)m by which the x may need to 
be adjusted is fixed for the user (provided that the M is fixed).



Hopefully, I can always get away with this technique, as long as a peer 
generates a random private-key-like scalar that I can adjust (by Ord in 
trivial cases, but potentially by other quantities as in SPAKE2).

This should work for your suggestions to use the Elligator map, assuming 
that I get the corresponding scalar.

I will need access to the private m for M=mG. I assumed it is sort of a 
user static public key.

The server side adjustments are similar.
> — Mike