Re: [Cfrg] Outline -> was Re: normative references

Watson Ladd <watsonbladd@gmail.com> Thu, 16 January 2014 02:15 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 746AF1AE23E for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 18:15:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.8
X-Spam-Level:
X-Spam-Status: No, score=-0.8 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, J_CHICKENPOX_12=0.6, J_CHICKENPOX_34=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 Pkxldebl_61u for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 18:15:22 -0800 (PST)
Received: from mail-we0-x22c.google.com (mail-we0-x22c.google.com [IPv6:2a00:1450:400c:c03::22c]) by ietfa.amsl.com (Postfix) with ESMTP id F30991ADFD1 for <cfrg@irtf.org>; Wed, 15 Jan 2014 18:15:21 -0800 (PST)
Received: by mail-we0-f172.google.com with SMTP id q58so2630338wes.17 for <cfrg@irtf.org>; Wed, 15 Jan 2014 18:15:09 -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=uHI5DNgIILvIkPZEH0GiC31gbREGDAyPL3nfpBAEQjo=; b=OXOvPZ/htfab37otr/IW+YH1rbSInWjkdZ5UgnMbEKkSbYprhcr5OIH6fh5oC1/IKg Rfc/h0TzmfNOfDVkqAoxNu7B+hoYMJnRknvUxNyW3AnumVJTS3bpBg0nfnZN/lPHVABm Cj5qTlPQ8zULBVffAI2F1i2zVpnwqLNRsFkUENO6FRGX4KeMj6MqNVHBgRv5d/vCN8md 892jhh56GPxH78Tbw583Y7yWFi0G4F0elYMuZsjmu07JWnPlRscXvwbeBtdcGkNdeDPF 7lPhHxCBHmXYQF0mDNLfjfMuAg3GyKxwPEWptqxJJib/+tn0KzYelEWein3xGWPRJTme /sNg==
MIME-Version: 1.0
X-Received: by 10.195.13.130 with SMTP id ey2mr5625812wjd.7.1389838509143; Wed, 15 Jan 2014 18:15:09 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Wed, 15 Jan 2014 18:15:09 -0800 (PST)
In-Reply-To: <CEFC6B5C.2C6E8%paul@marvell.com>
References: <CEFC6B5C.2C6E8%paul@marvell.com>
Date: Wed, 15 Jan 2014 18:15:09 -0800
Message-ID: <CACsn0ckSMUbEJ4F3bQ5KVMbhdPQw1MTMCce6B8uhMfA_V0Nupw@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: Paul Lambert <paul@marvell.com>
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Cc: Yaron Sheffer <yaronf.ietf@gmail.com>, David McGrew <mcgrew@cisco.com>, "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] Outline -> was Re: normative references
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: Thu, 16 Jan 2014 02:15:24 -0000

On Wed, Jan 15, 2014 at 5:38 PM, Paul Lambert <paul@marvell.com> wrote:
> Watson,
>
>>> I’ve been trying to be helpful, but your arguments against well intended
>>> suggestions is frustrating.   It’s difficult to contribute if you’re
>>> arguing for a sloppy RFC because the code is the reference.
>>
>>I'm arguing for a precise statement of what needs to be calculated,
>>and nothing else.
>
> Likewise … but precision of math is not the same as precision of
> protocol interoperability.

If we merely needed to define the protocol to be interoperable, then
"big endian x coordinate of points on y^2=x^3+486662x^2+x over
GF(2^255-19) with Diffie-Hellman packed to 32 bytes with leading 0,
basepoint x coordinate 9" would
completely define the protocol.

What you are asking for is guidance on implementations, which I've
added significant amounts of. Let's not confuse
normative with informative.

>
> Many of the precise words in the latest draft are unnecessary
> from an implementation perspective. An implementor does not
> need to know anything about abelian groups - just that
> there are:
>  - algorithm parameters (curve type and domain parameters)
>  - x,y coordinate points used as input/output to
>    Algorithms using the defined parameters
>  - clear algorithm descriptions using just, input, output
>    And domain parameters to perform a specific operation
>    (point addition and point multiplication)

I think we have that in this draft: even a pseudocode outline of the
ladder/double and add method.

Are there specific aspects of the explicit formulas and the text
around them that you think need clarification?

>
>>That's not sloppy. And in fact I'm supplying
>>what has been requested in terms of implementation details, against my
>>preference for black-box standards. The next
>>version is almost done in fact.
>

> Box is still fuzzy - more suggestions:

Do you have specific comments about where there is ambiguity?

>  - make an outline to the following form:
i.e. the form of RFC 6090. I'll think about that for a few days and
see if it gets
advantages in comprehension that my current draft could never get.

>   - Elliptic Curve Crypto Background
>     (curve types and parameters)
>     - Trival intro Fp and points
>     Define p, order, generator, curve types
>     - background on notation and other necessary functions
>   - Montgomery curves
>     - short overview for reference
>       and pointer to other specs
>       (basically - beware new math ahead)
>   - Edwards curves
>     - point representation
>     - point addition
>       Just one clear set of equations
>     - point multiplication
>   - Twisted Edwards curves
>   - Montgomery Curves
>      - point representation
>      - point addition
>      - multiplication
>   - Cryptographic operations
>     - DH
>       - DH with Edwards Curve
>       - DH with Montgomery Curve
>     - Signature Alg(s)

Signatures are going separately.

>       - Signature Alg with Edwards Curve
>       - Montgomery Curve Signatures ...

If you have a method that will work on a Montgomery curve naturally I
would love to hear it.

Montgomery curves are here for their blazing speed in ECDH without large tables.
Edwards curves are here for their blazing speed in signatures where we
can't toss out
one coordinate. I'ld much rather use Montgomery for ECDH and Edwards
for signatures
than Edwards for everything.

>   - Curve Catalogue
>     (include curves def’s, origins, refs, strength, NUM+NUTS whatever)
>      - Overview
>      - Edwards
>      - Twisted Edwards
>      - Montgomery
>   - References
>  Annex
>    - int to string / string to int per ANSI
>      (could be up front also in intro )
>    - other stuff / recomendations / math options
>
>
>>
>>>
>>> I was pointing to specific examples that we could emulate in a perhaps
>>> more simple manner.  The next step would be get a summary of the
>>>relevant
>>> details required and emulate one or more of these documents.
>>>
>>>
>>>>>  ⨳|If we aren't specifying any twisted Edwards curves, why would we
>>>>>  ⨳|define the formulas?
>>>>>  ⨳|I suppose for use with Montgomery form, ala Ransom's suggestion.
>>>>> [ ⨳]
>>>>> Yes ... and why did you leave out Ed25519?       It's being used and
>>>>>should at least be discussed/reviewed/
>>>>
>>>>It's the same as Curve25519, and not in safecurves. Let's be real
>>>>clear: isogenies don't change anything substantial.
>>> Substantial???
>>> Curve22519 is not interoperable with Ed25519. What could be more
>>> substantial.  A point on one curve would have a different x and y value
>>> than a curve on the other.
>>
>>If I transmit to you a Curve25519 point, you can treat it as an
>>Ed25519 point (after appropriate transformations) and I
>>will never know the difference.
> But if you do not identify that it is a Curve25519 point versus a
> Ed25519 point you will not know when to do the ‘appropriate transformation’
>
> So .. both are needed - especially if we are restricting Montgomery
> Curves to DH operations … which you imply.

Well, there are Edwards curves of about the same size. I've put it in because I
take your point: we do need something that has a strongly unified
complete addition law
with that size that can be used for signatures.

The only way I know of to use Montgomery curves for signatures loses
the extreme speed.

As for the transformation, if I tell you that protocol x uses
Curve25519 ECDH, I hopefully
have told you enough to know exactly what will be sent, regardless of what
you chose to do to think about it. Anything in the draft that makes that
not the case is a major issue.

>
>>Again, implementations are different
>>from the results
>>they calculate.
>>
>>> This is one of my core issues with having mathematicians write
>>>protocols …
>>> the apparent mathematical precision make the implementations very fuzzy.
>>>
>>>
>>>>If you want to discuss it separately, go ahead: plenty of people have
>>>>been discussing alternatives on this list already.
>>> Discuss …  no, let me be clear and rephrase.  Please add Ed25519 to the
>>> RFC.
>>
>>By Ed25519 do you mean the twisted Edwards curve, or the Edwards curve?
>>Becuase
>>the Ed25519 paper uses the Edwards curve, which has a giant parameter,
>>and the twisted
>>Edwards curve is going to be a unique form in the RFC. Either way
>>there is a lot of revising to do, also
>>to the explanation of why the curves were chosen.
>
> Explaining why they were chosen should come after explain what we have.
> We should document both forms of Ed25519 and give them each unique new
> names.
> Once named, we can chose to ignore or recommend any named curve.

The argument for doing this can be extended to the twists of every
curve in the draft already....
I vote for putting in T25519, not the Ed25519 curve, because the small
parameters are much faster.
Yes, you can use an isomorphism to get the speed back, but I don't
like typing giant numbers any more
then you do, and if everyone is going to be using the isomorphism, why
stick with the original curve.

>
>>
>>Do you want to basepoint that corresponds to the choice of basepoint
>>9, or should I pick one?
>>
<snip>
>>>
>>> Ok … but introducing Weierstrass allows comparisons and clarity of
>>> specification.
>>> No eed to fully define Weierstrass … it’s just easier to have a complete
>>> view
>>> of all options.
>>
>>Unless I include operation counts and real timings from optimized code,
>>that
>>won't be a complete guide to the choice to make. Look at eBATS for
>>performance
>>info.
>
> My point above on Weierstrass was for clarity of implementation.  The
> parameters have names (like ‘a’).  NIST curves have an ‘a’ that is
> different
> from the usage in Montgomery curves.  You simply need to show both
> equations
> and define what an ‘a’ means in each context (text already provided to
> you).
>
> That was the point of an early discourse on these being ‘new’ curves.

I'm having trouble visualizing why putting in the short Weierstrass form here
helps an implementor understand what the document says about Montgomery and
Edwards curves.

<rest omitted>
Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin