Re: [Cfrg] normative references

Paul Lambert <> Wed, 15 January 2014 18:02 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id E295E1AE125 for <>; Wed, 15 Jan 2014 10:02:19 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.567
X-Spam-Status: No, score=-1.567 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, IP_NOT_FRIENDLY=0.334, SPF_PASS=-0.001] autolearn=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id wnZeETGI-YNm for <>; Wed, 15 Jan 2014 10:02:18 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id 842C61AE0DC for <>; Wed, 15 Jan 2014 10:02:18 -0800 (PST)
Received: from pps.filterd ( []) by (8.14.5/8.14.5) with SMTP id s0FI1pmc028559; Wed, 15 Jan 2014 10:02:04 -0800
Received: from ([]) by with ESMTP id 1hd9d34qkt-1 (version=TLSv1/SSLv3 cipher=RC4-MD5 bits=128 verify=NOT); Wed, 15 Jan 2014 10:02:03 -0800
Received: from ([]) by ([]) with mapi; Wed, 15 Jan 2014 10:02:03 -0800
From: Paul Lambert <>
To: David McGrew <>, Yaron Sheffer <>
Date: Wed, 15 Jan 2014 10:02:01 -0800
Thread-Topic: [Cfrg] normative references
Thread-Index: Ac8SG+S8o3C/CsDhQny6deFVrtuLVQ==
Message-ID: <>
References: <> <> <>
In-Reply-To: <>
Accept-Language: en-US
Content-Language: en-US
user-agent: Microsoft-MacOutlook/
acceptlanguage: en-US
Content-Type: text/plain; charset="Windows-1252"
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10432:5.11.87, 1.0.14, 0.0.0000 definitions=2014-01-15_06:2014-01-15, 2014-01-15, 1970-01-01 signatures=0
X-Proofpoint-Spam-Details: rule=outbound_notspam policy=outbound score=0 spamscore=0 suspectscore=0 phishscore=0 adultscore=0 bulkscore=0 classifier=spam adjust=0 reason=mlx scancount=1 engine=7.0.1-1305240000 definitions=main-1401150116
Cc: "" <>
Subject: Re: [Cfrg] normative references
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 15 Jan 2014 18:02:20 -0000

On 1/15/14, 4:54 AM, "David McGrew" <> 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.

I¹ve just been through the web sites and many/most references and find it
extremely frustrating to find any clear and consistent implementation

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

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

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

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

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

 - 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

 - no test vectors or example calculations readily available
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.

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

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

        curveId = 'curve25519'
        strength = 127
        oid = None
        p  = 2**255-19
        a  = 486662
        xG = 9
        yG = 
        n  = 2**252 + 27742317777372353535851937790883648493
        h  = 8
    Also Š long numbers should be consistently represented hex versus
    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

  3) Use math representation in RFCs that maps directly to a computer
     language notation - Python would be a good choice for
     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

   4) curve names need consolidation and should clearly indicate curve type


>> Thanks,
>>     Yaron
>> _______________________________________________
>> Cfrg mailing list
>Cfrg mailing list