Re: [Cfrg] normative references

Watson Ladd <watsonbladd@gmail.com> Wed, 15 January 2014 23:34 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 630011AE246 for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 15:34:12 -0800 (PST)
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 ZR8R_qrqhXy0 for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 15:34:09 -0800 (PST)
Received: from mail-wi0-x229.google.com (mail-wi0-x229.google.com [IPv6:2a00:1450:400c:c05::229]) by ietfa.amsl.com (Postfix) with ESMTP id 3B19F1AE0D0 for <cfrg@irtf.org>; Wed, 15 Jan 2014 15:34:09 -0800 (PST)
Received: by mail-wi0-f169.google.com with SMTP id e4so4616923wiv.0 for <cfrg@irtf.org>; Wed, 15 Jan 2014 15:33:56 -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=aRLRetluqWd7wrUwpINZnfLSSTwEOS4nlvZUqq+vp2o=; b=PF0L9yBG8VXum1tYS4TlIV57z5c52t/0iqV+0ATvMX0pGMlIc5nMleXlXPFcA39WjK 2VJJi4Zr64PYBK9NZjyAtO7XYiNLNSGeT+T4X1Z2EIbW+3gxQLdlVdgntH9M6AxK+1Wm P41gUltxuWNh2Dr2oQqkHJ7AwDomfnrHWT+itMgy2lQlXN9NnwJ7vC9lyn7/U0pb2P0Z JZLix3QH7jsavn80sknQ5QYtC85fE0IYq9BX6S41UyhhT5M9gKOv7O16AFglWtLt6XNN pxm417Jj8ScAt9NznSj/uFBgzSCsT/S+k4ABh6N9YSo2MTFhhB9cjwfyi/+faCCUgBbu /reg==
MIME-Version: 1.0
X-Received: by 10.180.86.9 with SMTP id l9mr4933142wiz.20.1389828836907; Wed, 15 Jan 2014 15:33:56 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Wed, 15 Jan 2014 15:33:56 -0800 (PST)
In-Reply-To: <CEFC467B.2C628%paul@marvell.com>
References: <mailman.4685.1389738617.2658.cfrg@irtf.org> <52D645EC.4000408@gmail.com> <52D684EE.9050304@cisco.com> <CEFBFBE5.2C52B%paul@marvell.com> <CACsn0cmegQ8_CjCFx7VN30yQ=P=Neb8kLr-i+wgj680E16V1rQ@mail.gmail.com> <7BAC95F5A7E67643AAFB2C31BEE662D018B7FB9B37@SC-VEXCH2.marvell.com> <CACsn0cnw8MydqSxL0fEjM+jzB+UUfqwMoMVqG2Df99pU30Tr5A@mail.gmail.com> <CEFC467B.2C628%paul@marvell.com>
Date: Wed, 15 Jan 2014 15:33:56 -0800
Message-ID: <CACsn0c=e-u097UMadqsYNr7c=sS2wVjp=XaLvy_H2NS27d4UKQ@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] 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: Wed, 15 Jan 2014 23:34:12 -0000

On Wed, Jan 15, 2014 at 3:05 PM, Paul Lambert <paul@marvell.com> wrote:
>
> Watson,
>
>>>  ⨳|> There is a significant body of work on implementing Weierstrass
>>>  ⨳|curves
>>>  ⨳|> (ANSI, IEEE, NIST, NSA, etc.).  Edwards, Twisted Edwards and
>>>  ⨳|> Montgomery need the same level of documentation to progress.
>>>  ⨳|
>>>  ⨳|Or the same level of C library support. I'd much rather have everyone
>>>  ⨳|copy a well-made library then write their own bugs we have to deal
>>>  ⨳|with down the line/that the SIGINT people exploit. But yes, better
>>>  ⨳|documentation about how to implement is necessary.
>>> We're in the documentation business here - not code libraries. Plus
>>>we're
>>> supposed to have multiple interoperable different implementations.
>>
>>Do you really think everyone implementing P256 does it themselves? Or do
>>they
>>take example code from the Internet?
> I have seen a large number of P256 implementations … few if any from the
> public domain.
>
> Existence of an open source library is not an excuse for a sloppy RFC.  If
> this is the direction you are going, we would just need to write a
> one-line pointer to the source code.
>
> Real products implement in hardware, on multiple processor types … etc.
>
> 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. 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.

>
> 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. 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.

Do you want to basepoint that corresponds to the choice of basepoint
9, or should I pick one?

>>
>>I'm also going to explain the Montgomery ladder and double-and-add on
>>Edwards and that's it. RFC 6090 doesn't talk about
>>radix-k either, nor does it explain Shamir's trick, or fun with the
>>Brier-Joyce ladder, or w-NAF, etc.
>>>
>>>
>>>  ⨳|
>>>  ⨳|>
>>>  ⨳|>   2) reuse where possible terminology and variables from
>>>Weierstrass
>>>  ⨳|ECC
>>>  ⨳|>      E.g.  P for prime defining Fp,  n for order, h for cofactor
>>>  ⨳|>          This would allow all classes of curves to viewed equally
>>>in
>>>  ⨳|>          an implementation catalog
>>>  ⨳|>           E.g.
>>>  ⨳|>
>>>  ⨳|>         curveId = 'curve25519'
>>>  ⨳|>         strength = 127
>>>  ⨳|>         oid = None
>>>  ⨳|>         p  = 2**255-19
>>>  ⨳|>         a  = 486662
>>>  ⨳|>         xG = 9
>>>  ⨳|>         yG =
>>>...
>
> ...
>>
>>I still don't see why this form is much better than a paragraph
>>listing these things.
>>
>>>  ⨳|Also, different things should be written differently.
>>> [ ⨳]
>>>
>>> On the Edwards curves with cofactors >1 I believe the strength estimate
>>>may be a little less
>>> than simply taking the bit length of the size / 2
>>>
>>> Advice on this small adjustment would be appreciated.
>>
>>Size of the group generated by g, not the size of the curve.
> Oh … of course, thanks.
>
>>
>>>
>>>
>>>  ⨳|
>>>  ⨳|>     Also Š long numbers should be consistently represented hex
>>>  ⨳|versus
>>>  ⨳|> decimal
>>>  ⨳|
>>>  ⨳|Why hex? Most math papers use decimal, and more importantly GP/PARI
>>>  ⨳|doesn't accept hex.
>>>  ⨳|MAGMA, PARI and Sage are going to be used for test vector validation.
>>> [ ⨳]
>>> By you maybe ...
>>>
>>> Hex fits better in an RFC ...  decimal would be fine also.
>>
>>Six of one, half-dozen of the other.
>>
>>>
>>>  ⨳|
>>>  ⨳|>     Note also - Weierstrass Œa¹ is not the same as Edwards Œa¹, but
>>>  ⨳|>     can be written around Š and we should keep Edwards equations
>>>  ⨳|consistent
>>>  ⨳|>     where possible with literature.
>>>  ⨳|
>>>  ⨳|When we define DH exchange on a group yes. With setting the
>>>parameters
>>>  ⨳|like you did we're tempting fate.
>>> Not really ... just another area for clear specification, eg:
>>>
>>> Suggested RFC text:
>>>
>>>     The ECC definitions include three classes of curves defined over
>>>the field
>>>     of integers modulo a prime p (Fp).  Each class of curve has an
>>>equation and
>>>     assoicated parameters unique to the class type.  Three classes of
>>>curves
>>>     are described:
>>>
>>>       SmallWeierstrassCurveFp       y**2 = x**3 + a*x + b  mod p
>>>       EdwardsCurveFp         x**2 + y**2 = c*(1 + d*x**2 * y**2)  mod p
>>>       MontgomeryCurveFp             y**2 = x**3 + a*x**2 + x  mod p
>>>
>>>     The defintions include for each curve type:
>>>
>>>       curveId - An ASCII string used to identify the curve parameters
>>>       strength - an integer providing the estimated cryptographic
>>>strength
>>>                  of the curve as a power of 2
>>>       oid - a list of integers that correspond to the associated ASN.1
>>>object
>>>             identifier. The oid is listed as 'None' if there is no
>>>assigned oid
>>>       p - The prime modulus of the group (Fp). Often p is a Mersenne
>>>prime
>>>           to facilitate more efficient modular inversion
>>>       xG - the x-coordinate of a generator point G for the curve
>>>       yG - the y-coordinate of a generator point G for the curve
>>>       n  - the order of the generator point G
>>>       seed - included for reference when available
>>>       h - the cofactor of the curve
>>>
>>>     Each curve type has the following unique parameters
>>>
>>>       Small Wierstrass      y**2 = x**3 + a*x + b  mod p
>>>         a - often set to p-3 for efficiency
>>>         b - elected for the security properties of the curve shape
>>>         z - used by 'twisted' Brainpool curves for isogenous transform
>>>             of untwisted curve to a curve with a = p-3
>>>
>>>       Montgomery            y**2 = x**3 + c*x**2 + x  mod p
>>>         a - selected for the security properties of the curve shape
>>>
>>>       Edwards               x**2 + y**2 = c*(1 + d*x**2 * y**2) mod p
>>>         c - typically set to 1 so the equation is reduced to:
>>>                             x**2 + y**2 = 1 + d*x**2 * y**2  mod p
>>>         d - selected for the security properties of the curve shape
>>>
>>> Hummm .. could add Twisted Edwards to the above
>>
>>But none of the curves in safecurves are presented in twisted Edwards
>>form,
>>I'm not going to rehash short Weierstrass here, (RFC 6090 already exists).
>
> 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.

RFC's are standards, not how to guides for the terminally lazy.
>
> Paul
>
>
>>
>>Anyway, I think this conversation would be far more productive when I
>>finish the revisions and put it before
>>the group again. You can follow on github in between.
>>
>>>
>>>  ⨳|
>>>  ⨳|>
>>>  ⨳|>
>>>  ⨳|>   3) Use math representation in RFCs that maps directly to a
>>>  ⨳|computer
>>>  ⨳|>      language notation - Python would be a good choice for
>>>  ⨳|>      readability.
>>>  ⨳|>      E.g. Twisted Edwards point addition definition
>>>  ⨳|>
>>>  ⨳|>        x3 = ((x1*y2+x2*y1) * inv(1+d*x1*x2*y1*y2)) % p
>>>  ⨳|>        y3 = ((y1*y2-a*x1*x2) * inv(1-d*x1*x2*y1*y2)) % p
>>>  ⨳|
>>>  ⨳|The math notation I am using maps directly to that of most CAS
>>> [ ⨳]
>>> No - for example:
>>> " On Montgomery curves, curves of the form y^2=x^3+Ax^2+x, the typical"
>>> is Ax a variable 'Ax' or A*x ... this is sloppy non-parseable notation
>>
>>>  ⨳|systems. Anyway, at some point I will be done with the major
>>>revision,
>>>  ⨳|and kick it around for comments.
>>> [ ⨳]
>>> CAS???
>>> I prefer running code useable for a protocol implementation.
>>
>>So I can just copy the relevant parts of tweetnacl.c and be done with it?
>>
>>>
>>> Paul
>>>
>>>  ⨳|
>>>  ⨳|>
>>>  ⨳|>    4) curve names need consolidation and should clearly indicate
>>>  ⨳|curve
>>>  ⨳|> type
>>>  ⨳|
>>>  ⨳|Blame Tanja. I really do not like the idea of changing existing names
>>>  ⨳|especially when referring people to papers with them. SEC/NIST has
>>>  ⨳|already caused enough confusing as it is.
>>> [ ⨳]
>>> No need to blame, just make the change but  include reference to
>>>original author and curve name.
>>> NIST did not add confusion ... just branded the results.
>>> CFRG branding would be valuable.  More curves will happen and  a
>>>consistent notation is a good thing.
>>
>>What do you propose for the name scheme? E,M with prime in the expc
>>format is my best proposal, but this might not be unique all the time.
>>>
>>> Paul
>>>
>>>  ⨳|
>>>  ⨳|>
>>>  ⨳|>
>>>  ⨳|>
>>>  ⨳|>
>>>  ⨳|> Paul
>>>  ⨳|>
>>>  ⨳|>
>>>  ⨳|>
>>>  ⨳|> >
>>>  ⨳|> >David
>>>  ⨳|> >
>>>  ⨳|> >>
>>>  ⨳|> >> Thanks,
>>>  ⨳|> >>     Yaron
>>>  ⨳|> >>
>>>  ⨳|> >> _______________________________________________
>>>  ⨳|> >> Cfrg mailing list
>>>  ⨳|> >> Cfrg@irtf.org
>>>  ⨳|> >> http://www.irtf.org/mailman/listinfo/cfrg
>>>  ⨳|> >>
>>>  ⨳|> >
>>>  ⨳|> >_______________________________________________
>>>  ⨳|> >Cfrg mailing list
>>>  ⨳|> >Cfrg@irtf.org
>>>  ⨳|> >http://www.irtf.org/mailman/listinfo/cfrg
>>>  ⨳|>
>>>  ⨳|> _______________________________________________
>>>  ⨳|> Cfrg mailing list
>>>  ⨳|> Cfrg@irtf.org
>>>  ⨳|> http://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>>
>>--
>>"Those who would give up Essential Liberty to purchase a little
>>Temporary Safety deserve neither  Liberty nor Safety."
>>-- Benjamin Franklin
>



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