Re: [Cfrg] On the use of Montgomery form curves for key agreement

Watson Ladd <watsonbladd@gmail.com> Tue, 02 September 2014 02:05 UTC

Return-Path: <watsonbladd@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 6B3191A6F6B for <cfrg@ietfa.amsl.com>; Mon, 1 Sep 2014 19:05:45 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=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 rDB7hLsQINY5 for <cfrg@ietfa.amsl.com>; Mon, 1 Sep 2014 19:05:44 -0700 (PDT)
Received: from mail-yk0-x232.google.com (mail-yk0-x232.google.com [IPv6:2607:f8b0:4002:c07::232]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id F1FF81A6F66 for <cfrg@ietf.org>; Mon, 1 Sep 2014 19:05:43 -0700 (PDT)
Received: by mail-yk0-f178.google.com with SMTP id q200so3755875ykb.9 for <cfrg@ietf.org>; Mon, 01 Sep 2014 19:05:43 -0700 (PDT)
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; bh=4faFKXfRkERIPFbebL1Ya0FVICVZpxeiY2KieYg6x7Y=; b=Ejsa45QCQmd3QyNBPtufRhGehFPW0BEvVZf8QFNN+QaabmAOnjQbcaIfLxhJjR93I4 1MJlg3NifYYixNjlHWEurn+R96vQegdFYCyt3ipjwesMO5pH7cRontIcRs6zLnoS9UMT r9V0E8rrcSuLNsGSj6DpxAuH9+3HCteloHxX6sIlNN2OONeI0slFmUs0HWRmrAHSUZ61 //xq2vvVWFgMIb6PHja3UWdh0xTGeaFj1uX6WAIkqQDETmP+nEeTqIYvcOmSu14t08LC kwIwAX9rdmhRVVjB/z7/rMjeU3D3qVVGp+T4d6fmhlfUdmuW28C+1eYbIxXadCW4OJpI uKUA==
MIME-Version: 1.0
X-Received: by 10.236.101.138 with SMTP id b10mr19299625yhg.91.1409623543296; Mon, 01 Sep 2014 19:05:43 -0700 (PDT)
Received: by 10.170.202.2 with HTTP; Mon, 1 Sep 2014 19:05:43 -0700 (PDT)
In-Reply-To: <CA+Vbu7yMvyPzRAGrtVH38mzaYy3XQ1wswEUQisqbwpT10JfQVg@mail.gmail.com>
References: <e16ac4926a934565a65456058e50b68e@BL2PR03MB242.namprd03.prod.outlook.com> <CALCETrUby2o5O3=tMkv20JTVkahSo5Wan4oSCPOspRnXhFCg+g@mail.gmail.com> <b53e2c5417d247199f4496e0c0d5c29c@BL2PR03MB242.namprd03.prod.outlook.com> <CACsn0cktxTyPpeaqKU-oL+DiP4Fu0risHB1Wx8-by+94s30h=g@mail.gmail.com> <CA+Vbu7yMvyPzRAGrtVH38mzaYy3XQ1wswEUQisqbwpT10JfQVg@mail.gmail.com>
Date: Mon, 1 Sep 2014 19:05:43 -0700
Message-ID: <CACsn0cnQ-WEkL0kJS5F-TZb5YJ_4RrL9JgsAmC95qQayQFQGuQ@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Benjamin Black <b@b3k.us>
Content-Type: text/plain; charset=UTF-8
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/w48JBJdEGAamY_dflP6Vyxntwow
Cc: "cfrg@ietf.org" <cfrg@ietf.org>
Subject: Re: [Cfrg] On the use of Montgomery form curves for key agreement
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, 02 Sep 2014 02:05:45 -0000

On Mon, Sep 1, 2014 at 6:50 PM, Benjamin Black <b@b3k.us>; wrote:
> On Mon, Sep 1, 2014 at 6:06 PM, Watson Ladd <watsonbladd@gmail.com>; wrote:
>>
>>
>> >
>> > Alternatively and for the record, it seems to me that it would be
>> > perfectly reasonable for CFRG to decide to specify only Edwards curves
>> > (*not* twisted, just plain Edwards curves) as Mike Hamburg and others have
>> > suggested, and leave *all* of the optimizations as implementation choices.
>> > So whether someone wants to use twisted Edwards curves, the Montgomery
>> > ladder, some other improvement, etc., would be completely up to them.
>>
>> Which is the case anyway: your code could implement Weierstrass
>> coordinates and interop with X25519. But leaving the choice of
>> coordinates open isn't a possibility.
>>
>> The question we need to answer is what goes on the wire? That needs to
>> have an answer. And how the computations take place is largely
>> irrelevant, although we do need to address security considerations,
>> some of which our choice of coordinates and curve influence. What's
>> the difference between specifying twisted Edwards and Edwards from
>> this perspective?
>>
>
> The various working groups and standards bodies have already answered the
> question of what goes on the wire. The TLS request was for new curves. As we
> all seem to agree implementers are and should be free to use whatever form
> they wish internally as long as the external representation is fixed, there
> is general support for specifying curves in Edwards form, and existing
> protocols all define X/Y coordinates on the wire, then I see an opportunity
> for broad consensus here.

The standards define short Weierstrass coordinates as what goes on the
wire, not arbitrary pairs X,Y. Furthermore, things like the
representability of the identity, small order points, etc. introduce
enough differences from existing practice that one has to check
carefully how well the specs deal with them.

Sincerely,
Watson Ladd