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

Andrey Jivsov <crypto@brainhub.org> Tue, 28 January 2014 17:20 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 4D65F1A0158 for <cfrg@ietfa.amsl.com>; Tue, 28 Jan 2014 09:20:35 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, LOTS_OF_MONEY=0.001, 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 hSnYTAVL7c6c for <cfrg@ietfa.amsl.com>; Tue, 28 Jan 2014 09:20:32 -0800 (PST)
Received: from qmta09.emeryville.ca.mail.comcast.net (qmta09.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:96]) by ietfa.amsl.com (Postfix) with ESMTP id D9AA01A0187 for <cfrg@irtf.org>; Tue, 28 Jan 2014 09:20:32 -0800 (PST)
Received: from omta11.emeryville.ca.mail.comcast.net ([76.96.30.36]) by qmta09.emeryville.ca.mail.comcast.net with comcast id KSHh1n0050mlR8UA9VLW15; Tue, 28 Jan 2014 17:20:30 +0000
Received: from [192.168.1.8] ([71.202.164.227]) by omta11.emeryville.ca.mail.comcast.net with comcast id KVLV1n0044uhcbK8XVLVgG; Tue, 28 Jan 2014 17:20:30 +0000
Message-ID: <52E7E6DD.9090800@brainhub.org>
Date: Tue, 28 Jan 2014 09:20:29 -0800
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
MIME-Version: 1.0
To: Robert Ransom <rransom.8774@gmail.com>
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> <CABqy+sqpJr8Vki7-hP4nvwz0VP6+-1RnZ8taz6MZsxkWXfm8FA@mail.gmail.com> <52E76999.5030809@brainhub.org> <CABqy+sp92+=YAmvfTFLnvFhR_FAZYD9aoYSo=gbkUVybZW5uDQ@mail.gmail.com>
In-Reply-To: <CABqy+sp92+=YAmvfTFLnvFhR_FAZYD9aoYSo=gbkUVybZW5uDQ@mail.gmail.com>
Content-Type: text/plain; charset="UTF-8"; format="flowed"
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20121106; t=1390929630; bh=r6REO+dPn6ArijMqywrRTOyssQkUzfjJ5xsdEN4LlBI=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=E+sljGH2ikLNUv5rhNZ73SOvAFoLQsaJqGv8WIBds9biZQFMsZcplhqg9XT0DiHAs aqWqYYYoNfLnGA5PhrHT6KEo7WVQS0NYca/Yw5sR7oge/WUZS0HMKN69/7LfYcaFYj ZIhUnHyTNd0I9o9RXlFhSWohTrfePgD7oAbEmm8MC3onsM9j8+i63DHi7MGXRNrD8x 47QvYlL+3AUcEwb7/94wvSK0/ENatFhM8trEzXkKGwnFk8om5uGGK7UTOxoy7if8LX LM+DEY/53dT8kHha9n3sxHYjrLszhJ2beNt4yI07w7LKqqb/cFcHdIgZeHyBjpar8i jO2MYuWTzNoGw==
Cc: cfrg@irtf.org
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: Tue, 28 Jan 2014 17:20:35 -0000

On 01/28/2014 06:47 AM, Robert Ransom wrote:
> On 1/28/14, Andrey Jivsov <crypto@brainhub.org> wrote:
>> On 01/23/2014 06:58 PM, Robert Ransom wrote:
>>> On 1/23/14, Andrey Jivsov <crypto@brainhub.org> wrote:
>>>
>>>> Wouldn't http://tools.ietf.org/html/draft-jivsov-ecc-compact be another
>>>> method?
>>>
>>>> ( BTW, the proposal in the draft is in public domain since it was
>>>> published on December 10, 2012. )
>>>
>>> Are you claiming that the point format that I suggested is patented?
>>
>> I was making a statement about my contribution, in case this issue comes
>> up.
>>
>> The IP for the use of 1 bit to compress a point is a common knowledge,
>> but I've heard that some of them are expiring.
>
> If you are referring to the patent addressed in
> <http://cr.yp.to/patents/us/6141420.html>, claim 29 of the same patent
> covers point decompression with your proposal.

I am basing the method on the the CRYPTO '85 paper, which tells:

> Finally, it should be remarked, that even though we have phrased
> everything in terms of points on an elliptic curve, that, for the key
> exchange protocol (and other uses as one-way functions), that only the
> x-coordinate needs to be transmitted. The formulas for multiples of a
> point cited in the first section make it clear that the x-coordinate of
> a multiple depends only on the x-coordinate of the original point.


>> However, I am concerned about the cofactor issue. These curves have the
>> cofactor greater than 1. Unlike "unsafe" NIST curves, this needs to be
>> handled. The draft suggest methods that, as I understand them, may run
>> into IP issues. Besides, there may be protocols that want to do classic
>> DH. One solution to these issues is to enumerate the points in the small
>> subgroup, explicitly in the document, or by providing the method to
>> identify them.
>
> U.S. patent 6,226,383 (Jablon) claims 31 and 32 cover the use of your
> suggestion in ECDH.

I try not to read patents, one never knows what can be found there...

Because any modp group will have a cofactor of at least 2, all modp 
operations are effected by these claims. These claims would cover, for 
example, http://tools.ietf.org/html/rfc6989 sec 2.2 that excludes 0 and p-1.

I was assuming that such a general method of comparing one element to 
another, or a concept of a subgroup, were known before 1990s.

>
>
> Dr. Bernstein's paper which specifies Curve25519 for use in ECDH
> addresses its groups' cofactors by (a) generating Diffie-Hellman
> keypairs such that the secret exponent is divisible by the cofactor
> (as is common in multiplicative-group Diffie-Hellman, where the
> cofactor is at least 2), and (b) requiring that the shared-secret
> group element be used only as input to a hash function or hash-based
> KDF (as is required for all Diffie-Hellman systems).
>
> Are you aware of any specific patent claims which cover these
> techniques, or are you merely trying to spread patent FUD?

The quick search reveals this one: US6563928. Yes, I did notice that the 
paper specifies that the key generation must clear the lower bits, which 
is equivalent to multiplying by a (power of 2) cofactor. Such a method 
hardwires the cofactor multiplication into the field operation. This was 
not necessarily needed, but I understand that this was important to be 
"safe". I personally would prefer the cofactor not to be a part of the 
raw ECC operations.