Re: [Cfrg] normative references

Watson Ladd <watsonbladd@gmail.com> Wed, 15 January 2014 20: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 D03271AE1E6 for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 12:05:35 -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 Ym7JLz2QZeVq for <cfrg@ietfa.amsl.com>; Wed, 15 Jan 2014 12:05:33 -0800 (PST)
Received: from mail-wi0-x235.google.com (mail-wi0-x235.google.com [IPv6:2a00:1450:400c:c05::235]) by ietfa.amsl.com (Postfix) with ESMTP id EBA5E1AE1A6 for <cfrg@irtf.org>; Wed, 15 Jan 2014 12:05:32 -0800 (PST)
Received: by mail-wi0-f181.google.com with SMTP id hi8so1234986wib.2 for <cfrg@irtf.org>; Wed, 15 Jan 2014 12:05:20 -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=xozZhChN+9t2S5foTiIgNN4vw/cx2cyzq11evC2HutI=; b=TmuihpEa0+FHwLo2kUW6ySzDlBswHjBDQpAt8RpY4Z0f26x16NOAwecCg3eyB+pfem 0JgQabgkYxQIjzHP2uq1BvgabLAOXiwSwP44Rx+Br2hPOabdZPq67WXG31Ac7MUg4fVf I9jSz8co9vewBj4PDs1L8kLz0hUfCgH3iGI5f5g3a4bxYPoAl3wYEnnWtBhZ4GoeWi4j 6A88q00YKb2m1HTW5D4X93TrmnkTWU5zWrTsXwApToIn/Bed/c22HUrB39DBVDUbQnD2 YW7UGF8h95JMvnR3AjlRsVTfLywCCTUP6ZbeLHiR7dx7eT+K+zkoNUcPCwfRxqKcND9b toUg==
MIME-Version: 1.0
X-Received: by 10.194.187.101 with SMTP id fr5mr4014981wjc.76.1389816320637; Wed, 15 Jan 2014 12:05:20 -0800 (PST)
Received: by 10.194.242.131 with HTTP; Wed, 15 Jan 2014 12:05:20 -0800 (PST)
In-Reply-To: <CEFBFBE5.2C52B%paul@marvell.com>
References: <mailman.4685.1389738617.2658.cfrg@irtf.org> <52D645EC.4000408@gmail.com> <52D684EE.9050304@cisco.com> <CEFBFBE5.2C52B%paul@marvell.com>
Date: Wed, 15 Jan 2014 12:05:20 -0800
Message-ID: <CACsn0cmegQ8_CjCFx7VN30yQ=P=Neb8kLr-i+wgj680E16V1rQ@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 20:05:36 -0000

On Jan 15, 2014 10:02 AM, "Paul Lambert" <paul@marvell.com> wrote:
>
>
>
> On 1/15/14, 4:54 AM, "David McGrew" <mcgrew@cisco.com> wrote:
>
> >On 01/15/2014 03:25 AM, Yaron Sheffer wrote:
> >> Hi David,
> >>
> >> Somewhere down the Safe Curves thread you mention that you expect a
> >> CFRG draft to contain "stable normative references" to definitions of
> >> crypto mechanisms. I share this wish in part, in particular I would
> >> appreciate "stable" references (e.g., to academic papers). However
> >> many/most crypto publications are not aimed at implementors. Often
> >> they are not well-specified enough to implement. And we don't want to
> >> wait a few years for NIST to create normative versions. So I would
> >> actually expect the new CFRG document to become the "normative"
> >> reference.
> >
> >This is a good point, Yaron.
> Yes!!!
>
> I¹ve just been through the web sites and many/most references and find it
> extremely frustrating to find any clear and consistent implementation
> details.

(sidenote: I got mojobake in this email. Check your encodings are set
correctly. And please, can we ban rich text from this list?)

I think it is important to remember that normative references specify
what, not how. How would be informative,
as it doesn't affect compliance.

>
> Example issues include:
>  - changes in notation and terminology
>    E.g. For Edwards point addition , is it:
>         y3 = (y1*y2   +    x1*x2) * inv(1-d*x1*x2*y1*y2)
>       or is it:
>         y3 = (y1*y2   -    x1*x2) * inv(1-d*x1*x2*y1*y2)
>    Š It depends on the way the curve class is named, it¹s actually
>         y3 = (y1*y2  +  a*x1*x2) * inv(1-d*x1*x2*y1*y2)
>         and usually a=1

>
>  - unclear guidelines on important security topics
>     E.g.
>       ed25519 has restrictions on the secret key structure for ECDH
>       Does this extend to other curves?
>
>  - references describe the poofs, but hand wave the actual way
>    you would send and receive and process as data
>    E.g.  Hand waving of when and if to use projective coordinates

Affine of course: the same is true for Weierstrass form. One uses
projective form for intermediate calculations.
I'll make this clear in the draft if it isn't already. The security
issues cofactors present I will be sure to discuss: I thought
they were well known because over F_p^{\times} you always have a cofactor.

>
>  - Lack of clarity on edge conditions (small subgroups, special points)

This is important and I will definitely try to address it.

>
>  - Unclear algorithm selection guidelines
>    E.g. Scalar multiplication and point addition
>      - fastest algorithms no longer have all the Œsafe¹ properties
>
>  - unclear implications of use of the cofactor (since it is not =1)

I'll explain the group structure and the necessary changes to DH.
For algorithms, you can get away with the fast ones
if you are careful to show that the problems won't matter. For
instance if I have a point that
isn't of small order, I can multiply using the 2008 algorithms if I
take care never to add two points that
might be the same in my multiplication algorithm.

The safe method is still pretty fast. If you use an unsafe method,
it's your responsibility to check that it
will work, and not mine.

>
>  - no guidelines on use of different EC algorithms with the curve types
>    E.g.  ECDSA with Montgomery curve using just x-coordinate math ???
>     Do we use cofactor DH since  cofactor >1?

I'm not sure what you mean by cofactor DH, but yes, the implication of
the cofactor is you need to represent your
private keys as coercive, forcing points into the large subgroup, or
you leak a few bits. (Basically the same from a security standpoint).

>
>  - Terms in the references are used in papers in an inconsistent manner
>    With respect to an implementation
>    E.g. ³Twist²

I'm going to avoid discussing math on the quadratic or cubic twist of
a curve, because it isn't necessary for implementions.
Just plug in the formulas and the algorithms, and it will all work.

>
>  - math is represented inconsistently and imprecisely for an implementation
>     E.g.  + versus * for   ECDH
>           ^  versus **  on curve equationss
>           Œmod¹  imply all math is in field versus as an operation at a
> specific operation

The notation issue won't get fixed anytime soon. I'll be consistent in
the draft, but that means
being inconsistent with half of everyone else. The operations issue is
the sort of thing where a little bit
of reading comprehension goes a long way: spelling out what exactly +
means at any given time is annoying,
especially when it is always obvious.

>
>  - no test vectors or example calculations readily available

This cannot be said about Curve25519: "Cryptography in NaCL" contains a Python
test program together with an example DH exchange, but in little-endian.

For the other curves I agree this is an issue. I'll do a black-box
interop test with you and other
interested people before we publish.

>
> It appears that much of the interest and ability to use some of these
> curves comes from their availability in a few specific C libraries.  These
> might be used as a reference, but are curve specific and it¹s unclear how
> to extract generic guidelines for more than the implemented curve.

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

>
> So Š. lot¹s of issues, but they could be solved by a clear specification.
>
> Initial Recommendations:
>  1) Always use the most general form of any of the representations
>      Replace any algorithms for Edwards with Twisted Edwards (more general)
>      E.g.  Curve as:
>           (a*y**2+x**2) % p == (1 + d*x**2*y**2) % p
>            and
>             y3 = (y1**2  +  a*x1**2) * inv(1-d*x1*x2*y1*y2)
>
>      One question here Š I also see alternate form with Œc'
>             (y**2+x**2) % p == c*(1 + d*x**2*y**2) % p
>
>                 or
>             (y**2+x**2) % p == c**4*(1 + d*x**2*y**2) % p
>
>          Not sure if any advantages versus Œa¹ or both Œa¹ and Œc'
>             (a*y**2+x**2) % p == c*(1 + d*x**2*y**2) % p

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.

>
>   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 =
> 147816194475895447910205935684099868872646061346164752889648818377555862374
> 01
>         n  = 2**252 + 27742317777372353535851937790883648493
>         h  = 8

Strength is the base 2 log of the operations to break, right?
Also, different things should be written differently.

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

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

>
>
>   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
systems. Anyway, at some point I will be done with
the major revision, and kick it around for comments.

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

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