Subject: [Cfrg] Citing specs in specs

From: Paul Hoffman <[email-masked]>
Date: Sat, 1 Mar 2014 17:21:39 +0000

[[ Subject line changed to be relevant to the discussion ]]

On Mar 1, 2014, at 4:16 AM, Robert Ransom <[email-masked]> wrote:

> On 2/28/14, David McGrew <[email-masked]> wrote:
>> I am wary of relying on the curve25519 paper as a normative reference.
>> Perhaps your goal here is to provide an informational document (the
>> draft that you mention above) that offers implementation guidance,
>> instead of a normative reference?
> 
> RFC 4492 (ECC ciphersuites for TLS) cites ANSI X9.62, IEEE 1363, and a
> few documents labeled as ‘standards’ by the corporations which
> authored them as normative references.  It cannot be implemented
> without the information in ANSI X9.62 and IEEE 1363.  ANSI X9.62 is
> available from ANSI for 100 USD; IEEE 1363 is available from ANSI for
> 168 USD.

I have been told by implementers that you can implement RFC 4492 just fine without those references, only with [SECG]. What information in the ANSI and IEEE spec do you feel is needed to implement 4492?

> It is true that the author of the Curve25519 paper is neither a large
> corporation nor an organization with “Standards” in its name, and did
> not label Curve25519 as a ‘standard’ in the paper's title.  However,
> the Curve25519 scalar multiplication function specified in the paper
> became a ‘standard’, in the sense which IETF claims to use the word,
> when software developers came to the rough consensus that it was a
> good cryptographic primitive to use, and wrote and deployed running
> code which implements it.  

That is not the sense which the IETF claims to use the word.

> The Curve25519 paper is available for free
> from the URL <http://cr.yp.to/ecdh/curve25519-20060209.pdf>.
> 
> What is your objection to using the Curve25519 paper as a normative
> reference for the standard Curve25519 scalar multiplication function?

The paper is at a URL; the contents of that URL can change any time. RFCs can sometimes make normative reference to URLs that seem very stable, and Dan's might or might not be. Dan has a history of poking at the IETF (sometimes for good reason), so it is quite believable that he might change the contents of that URL just to make a point. Having a more stable reference would clearly be better.

--Paul Hoffman

---

From: Watson Ladd <[email-masked]>
Date: Sat, 1 Mar 2014 09:39:39 -0800

> The paper is at a URL; the contents of that URL can change any time. RFCs can sometimes make normative reference to URLs that seem very stable, and Dan's might or might not be. Dan has a history of…

Bernstein, Daniel. "Curve25519:New Diffie-Hellman Speed Records".
Appears in Moti Yung, Yevgeniy Dodis, Aggelos Kiayias, Tal Malkin
Public Key Cryptography - PKC 2006, 9th International Conference on
Theory and Practice of Public-Key Cryptography, New York, NY, USA,
April 24-26, 2006, Proceedings. Springer 2006 Lecture Notes in
Computer Science ISBN 3-540-33851-9

This comes straight from Dan Bernstein's bibliography.

Alternatively one could put the paragraph that defines Curve25519 into
the draft.

I don't see a problem with either one of these alternatives.

Sincerely,
Watson Ladd

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

---

From: Paul Hoffman <[email-masked]>
Date: Sat, 1 Mar 2014 23:16:42 +0000

> I don't see a problem with either one of these alternatives.

Both look fine to me, the latter being better.

--Paul Hoffman

---

From: David McGrew <[email-masked]>
Date: Sat, 01 Mar 2014 19:39:26 -0500

> reference for the standard Curve25519 scalar multiplication function?

That it is not clear or precise enough.   Specifically, it is not 
written so that a hardware or software engineer would know how to 
implement it, and it describes multiple alternatives rather than a 
single specific algorithm.

Let me point out some examples from the end of Section 2 of 
http://cr.yp.to/ecdh/curve25519-20060209.pdf, where the document 
actually defines the curve function: "By Theorem 2.1, there is a unique 
integer s .... with the following property: s = X0(nQ) .... Note that 
Curve25519 is not surjective: in particular, its final output bit is 
always 0 and need not be transmitted."   Engineers will be confused by 
the lack of an imperative description of the function, and will not know 
whether to expect the last bit to be transmitted or not.

It would be a disservice to the community to not offer implementers a 
more usable description.   If the curve is worth using, it is worth a 
draft that specifies it.

Or perhaps there was another document about the curve that you had in mind?

David

---

From: Paul Lambert <[email-masked]>
Date: Sat, 1 Mar 2014 20:02:06 -0800

The curve25519 is NOT a good normative reference IETF protocols.
It¹s useful as an informative reference on the curve
Selection, but lacks clarity and completeness on
implementation details.

One of the main reasons 25519 is popular is that a nicely optimized
open source library is available for some of the more
Useful curve functions.

On 3/1/14, 9:21 AM, "Paul Hoffman" <[email-masked]> wrote:

>> few documents labeled as Œstandards¹ by the corporations which
>I have been told by implementers that you can implement RFC 4492 just
>fine without those references, only with [SECG]. What information in the
>ANSI and IEEE spec do you feel is needed to implement 4492?

We should be working here to document Edwards/Montgomery curves to
the same level of clarity as the SECG documents.  Perhaps we
could be even more concise and complete - SECG left out
details of most optimizations.

My favorite examples of clarity are:
http://www.nsa.gov/ia/_files/nist-routines.pdf

http://www.nsa.gov/ia/_files/SuiteB_Implementer_G-113808.pdf

Right now there is no equivalent documentation as the nist-routines.pdf
for Edwards/Montgomery curves.

Paul

>> corporation nor an organization with ³Standards² in its name, and did
>> not label Curve25519 as a Œstandard¹ in the paper's title.  However,
>> became a Œstandard¹, in the sense which IETF claims to use the word,
>The paper is at a URL; the contents of that URL can change any time. RFCs
>can sometimes make normative reference to URLs that seem very stable, and
>Dan's might or might not be. Dan has a history of poking at the IETF
>(sometimes for good reason), so it is quite believable that he might
>change the contents of that URL just to make a point. Having a more
>stable reference would clearly be better.
>
>--Paul Hoffman
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>http://www.irtf.org/mailman/listinfo/cfrg

---

From: Watson Ladd <[email-masked]>
Date: Sun, 2 Mar 2014 10:38:25 -0800

(Moving to TLS because that is where this draft is)

> Selection, but lacks clarity and completeness on

Since when does a normative reference contain implementation details?

IEEE 745 doesn't, RnRS doesn't, the ANSI C standard doesn't, POSIX
doesn't, etc. This doesn't affect being able to judge compliance which
is the normative function of a spec.

If you want RFCs, try writing a NTP protocol implementation (that is,
a client that keeps track of the current time accurately) without
understanding PLL control theory. This isn't in the spec at all, but
is completely necessary to get a functioning implementation.

Furthermore, the Curve25519 paper describes a very clever
implementation in great detail.

> for Edwards/Montgomery curves.

So your argument is that until such a document is written, the IETF
should not approve any RFC containing such a curve because absent such
a document, the specification is unclear? I disagree: the information
you demand to be placed into the spec can be figured out in a few days
of research in the library. There are numerous standard references on
bignum arithmetic, and given this with the paper of Montgomery, there
is nothing else that is needed to write an implementation that is
correct.

Sincerely,
Watson Ladd

---

From: Paul Lambert <[email-masked]>
Date: Sun, 2 Mar 2014 14:41:03 -0800

On 3/2/14, 10:38 AM, "Watson Ladd" <[email-masked]> wrote:

>a document, the specification is unclear?

No - I’m asking that an RFC be well written and contain enough information
to implement the RFC.

Paul

>I disagree: the information

---

From: Paul Lambert <[email-masked]>
Date: Sun, 2 Mar 2014 14:48:36 -0800

>No - I’m asking that an RFC be well written and contain enough information

Seeing now that this is cross posted to TLS… let me be clear.
The onus is onthe CRFG to produce a useable normative reference that can
be used
by TLS and other IETF protocols for using Edwards and Montogomery
elliptic curves.

Paul

---

From: Paul Lambert <[email-masked]>
Date: Sun, 2 Mar 2014 15:40:33 -0800

]-----Original Message-----
]From: Salz, Rich [mailto:[email-masked]]
]
]> No - I’m asking that an RFC be well written and contain enough
]information to implement the RFC.
]
]Okay, you don't think it's possible using, among other information, the
]25519 paper as an information source.  Others do think it possible, and
]have made the point that they think this is an unusually high
]requirement being imposed here.

Implementations are possible by using the readily available open source
implementation.  This is a good thing, but it is also desirable
to have a unambiguous description of the algorithms that is not 
a C code file.  This is why we write RFCs...

Paul 

]
]Have I summed up the angle brackets well enough?
]
]--
]Principal Security Engineer
]Akamai Technology
]Cambridge, MA

---

From: S Moonesamy <[email-masked]>
Date: Sun, 02 Mar 2014 18:14:58 -0800

Hi Paul,
>a C code file.  This is why we write RFCs...

A Proposed Standard is about interoperability.  It does not prescribe 
a method.  The test is to determine whether the standard actually 
works is see whether there are different implementations which have 
been deployed.

There is a Proposed Standard which contains the source code for a 
reference implementation.  That was unusual.

Please note that I currently have a draft referencing ED25519 [1].

Regards,
S. Moonesamy

1. http://tools.ietf.org/html/draft-moonesamy-sshfp-ed25519-00

---

From: Watson Ladd <[email-masked]>
Date: Sun, 2 Mar 2014 18:51:36 -0800

On Sun, Mar 2, 2014 at 6:14 PM, S Moonesamy <[email-masked]> wrote:
> A Proposed Standard is about interoperability.  It does not prescribe a
> method.  The test is to determine whether the standard actually works is see
> whether there are different implementations which have been deployed.

>From that perspective let me note that DJB's original assembly
language implementation, Matthew Dempsky's 32 bit C implementation,
and Adam Langley's 64 bit C implementations, were all independently
developed from the paper. Furthermore, I've been able to do the same
in a few hours, if not extremely concerned with speed.

Sincerely,
Watson Ladd

>
> There is a Proposed Standard which contains the source code for a reference
> implementation.  That was unusual.
>

---

From: Jon Callas <[email-masked]>
Date: Sun, 2 Mar 2014 22:52:28 -0800

> a C code file.  This is why we write RFCs...

It's hard to disagree with this, in a similar way that it's hard to disagree with the idea of peace on earth, living at one with nature, etc.

But in practice, code needs to be in a computer language rather than English and I've seen (and been involved with) a document that started with rough consensus and running code, translated that into English, and the English was (and is) devilishly hard to compile back into C.

Portably implemented algorithms are hard to do in any computer language. They're harder to do in words. I don't see how you're going to get an unambiguous description of the language in anything but a computer language. It doesn't have to be C, it could be Python, Ruby, or Algol-58 (which I mention because it was originally designed as an algorithmic description language). English is a suboptimal implementation language.

	Jon

---

From: David McGrew <[email-masked]>
Date: Mon, 03 Mar 2014 05:01:24 -0500

On 03/02/2014 06:55 PM, Tanja Lange wrote:
> Easy ways out:
> a) Refer to
> 	http://cr.yp.to/ecdh.html#curve25519-paper
>     which lists all (2) versions of the paper.
> b) Refer to the Springer version -- it's open access per contract
>     bewteen Springer and the IACR.
> 	http://link.springer.com/chapter/10.1007%2F11745853_14
>

Thanks, Tanja, the PKC2006 reference (including the link to the Springer 
PDF) would definitely be the best way to reference this work.

David

---

From: Paul Lambert <[email-masked]>
Date: Mon, 3 Mar 2014 21:32:52 -0800

On 3/3/14, 2:52 PM, "Jon Callas" <[email-masked]> wrote:

>It's hard to disagree with this, in a similar way that it's hard to
>disagree with the idea of peace on earth, living at one with nature, etc.
>
>But in practice, code needs to be in a computer language rather than
>English and I've seen (and been involved with) a document that started
>with rough consensus and running code, translated that into English, and
>the English was (and is) devilishly hard to compile back into C.
Yes - I¹e seen the same problem.  English is not a concise or clear way to
document an algorithm.

HAC is pretty clear and is a decent example of cryptographic algorithm
descriptions (http://cacr.uwaterloo.ca/hac/about/chap8.pdf), but still
uses a mix of math notation and english text.
>
>Portably implemented algorithms are hard to do in any computer language.
>They're harder to do in words. I don't see how you're going to get an
>unambiguous description of the language in anything but a computer
>language. It doesn't have to be C, it could be Python, Ruby, or Algol-58
>(which I mention because it was originally designed as an algorithmic
>description language). English is a suboptimal implementation language.

Yes, exactly!   'Readable code¹ would be a very good way to provide an
algorithm description.  Why bother with pseudo code when a executable
syntax could be used.   I submitted earlier on this list some Python code
fragments as examples of this approach.  Python allows operator
overloading, so it can provide some very readable ECC algorithm
descriptions.

Paul

---

From: Watson Ladd <[email-masked]>
Date: Mon, 3 Mar 2014 23:03:41 -0800

> Yes - I¹e seen the same problem.  English is not a concise or clear way to

Really? Because all the people doing algorithms I've seen use English
to describe their results because it is clearer then code.

For instance, consider the following short C code.

typedef struct{ member *p; int rank} member;

void init(member *a){a->p=a; rank=0;}

member * find(member *a){
   member *q=a;
   member *r=NULL;
   member *t;
   while(q !=q->p){
            t=q->p;
            q->p=r;
            r=q;
            q=t;
    }
 while (r !=NULL){
         t=r->p;
         r->p=q;
        r=t;
  }
return q;
}

void union(member *a, member *b){
   a=find(a);
   b=find(b);
   if(a->rank<b->rank){
          a->p=b->p;
          b->rank++;
    } else {
       b->p=a->p;
      a->rank++;
   }
}

The above code is of course union-find. However, I don't know what
looking at the above code tells you about the algorithm. By contrast
the following description gets the point across much more clearly.
"We consider a forest where the root node of each tree points to
itself, and pointers point up. The find operation takes the node it is
given, and follows the chain of pointers to the root, reversing each
pointer. It then descends the chain, setting each encountered pointer
to the root. The union operation links the root with lower rank to the
one with greater rank and increments the rank of the new root."

In particular the description makes clear the invariant that is
maintained: each set has a unique element that points to itself, the
rank of a node is an upper bound on the height of the tree rooted at
that node. The code makes none of this clear: it is concerned entirely
with bookkeeping that seems as important as the main idea.

For something like F5, or point counting, or inverse square root, or
direct sparse matrix factoring, or the Fast Fourier Transform, the gap
between what English is able to do and what an executable
representation can do in terms of ideas is only bigger. There is a
reason computer science produces books, not code.

> uses a mix of math notation and english text.

Your use of the word "still" implies that you think the two are in
some way opposed. They aren't: programming languages have nowhere near
the capacity of expressing ideas that the English language does.

> overloading, so it can provide some very readable ECC algorithm

Readable without a working Python implementation to see what happens?

Note that Python code implementing Curve25519 exists in "Cryptography
in NaCl", which also contains test vectors.
Does anyone have an objection to putting equivalent Python in the
draft/would this satisfy those calling for more documentation?
If I have the nroff source of the draft I can do it in a few hours.

Sincerely,
Watson Ladd

---

From: Paul Lambert <[email-masked]>
Date: Tue, 4 Mar 2014 02:57:58 -0800

>For instance, consider the following short C code.

No I will not.  Read my suggestion - C code sucks for readability.  Yes -
English is always needed, even in code for comments.

Pseudo code is just ‘psuedo’ and lacks defined syntax.  Higher level
languages like Python or Ruby provide an opportunity for clear and
syntactically well defined algorithm definitions.  Specifically where we
are describing equations for things like - iterating over a range,
recursive algorithms, etc.  Examples would look like:

def add_points(curve, p1, p2):
    """ Add two points on the curve """
    x1 = p1.x;  x2 = p2.x;  y1 = p1.y;  y2 = p2.y
    d = curve.d; a = curve.a; p = curve.p; inv = curve.inverse
        
    # Edwards curve addition
    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
    return curve.point(x3, y3)

#or

class Curve25519( MontgomeryCurveFp ):
    """ y**2 == x**3 + 486662*x**2 + x  mod 2**255-19 """
    curveId = 'curve25519'
    strength = 126
    oid = None
    p  = 2**255-19
    a  = 486662
    xG = 9
    yG =  
0x20ae19a1b8a086b4e01edd2c7748d14c923d4d7e6d7c61b229e9c5a27eced3d9
    n  = 2**252 + 27742317777372353535851937790883648493
    h  = 8

Your example below is irrelevant and I’m not sure why you are always
disagreeing with anything anyone posts on the list.

>the capacity of expressing ideas that the English language does.

Yes - both are required.
>in NaCl", which also contains test vectors.

Pieces of the code read well … the code by it’s self is not a
specification.
The ‘add’ code is a good example of something that could be used:

def add((xn,zn), (xm,zm), (xd,zd)):
    x = 4 * (xm * xn - zm * zn) ** 2 * zd
    z = 4 * (xm * zn - zm * xn) ** 2 * xd
    return (x % P, z % P)

>If I have the nroff source of the draft I can do it in a few hours.

‘readable' code written to closely map to the algorithm description
would be good - but this is not a raw nroff of the source file.
I’m suggesting that what is needed is a document using english text
in the style of:
 http://www.nsa.gov/ia/_files/nist-routines.pdf
Where the psuedo code is replaced with real Python functions.

That said … your flip and negative comments are very frustrating to deal
with and it’s not a good way to get any consensus.  The note was also not
directed to you and I do not expect you take any action from this
suggestion.  I’m hoping others will carry the flag for this documentation
exercise and that they will be easier to communicate with on the mailing
list.

Paul

---

From: Watson Ladd <[email-masked]>
Date: Tue, 4 Mar 2014 09:02:35 -0800

Dear all,
This is provisionally my last word on the matter.

Any consensus based process only works if people will block a largely
formed consensus for a good reason only. A document being unclear, or
having unanalyzed security properties, or major issues with regards to
alternatives not being discussed are good reasons. But the argument
that Paul I think is making, that until the CFRG produces a draft ala
RFC 6090 for Edwards curve we cannot use them, is fundamentally
unconvincing.

First off, let me note that black box implementations of Curve25519
using the paper are possible: I've written them, Adam Langley has
written them, as have lots of other people. So that leaves the
argument that the implementations require too much knowledge about
cryptography, and that such an issue is worth blocking specs.

The simplest argument for why it is unconvincing is the date of RFC
6090 vs. the dates of protocols that included Suite B and ECC. RFC
4869 includes Suite B a full 4 years before RFC 6090 was published.
Now, it is possible that Paul's argument was valid, but simply wasn't
raised at the time RFC 4869 was being published. But I don't see any
evidence that implementors of RFC 4869 were hamstrung by the
nonexistence of RFC 6090.

The second reason I am unconvinced is that I don't see why we
shouldn't assume the availability of standard references such as the
Handbook Of Elliptic and Hyperelliptic Curve Cryptography, or volume 2
of Knuth, to implementors. Such documents are available for far less
money than ISO standards, and in many regions of North America, Europe
and Asia, can be found for free in the library. The goal of a spec is
to explain to humans what is to be done: including excessive
information makes this much harder.

Finally, Mr. Lambert writes in terms of the "onus" being on CFRG to
produce such a document, which he calls a "usable normative
reference". Such a bare assertion is entirely unconvincing.
Furthermore, CFRG owes Paul nothing. While I would be happy to review
such a document for accuracy, I have no obligation to review or
produce such a document, and the same holds for all the members of the
CFRG. I can just as easily say that Mr. Lambert has the onus to
produce such a document.

I've changed my mind about the desirability of such a document as Mr.
Lambert wants. It would be nice if it existed, and it would be a nice
project to learn CWEB. However, I see no reason to consider the
absence of such a document a good reason to block
draft-josefsson-tls-curve25519-04.

Sincerely,
Watson Ladd

---

From: David McGrew <[email-masked]>
Date: Wed, 05 Mar 2014 06:11:26 -0500

> reference". Such a bare assertion is entirely unconvincing.

 From our charter: "The CFRG serves as a bridge between theory and 
practice, bringing new cryptographic techniques to the Internet 
community and promoting an understanding of the use and applicability of 
these mechanisms via Informational RFCs".     We have an opportunity to 
promote the understanding, use, and applicability of newer ECC 
mechanisms, and I hope that we do so.   I woud not say we have the 
"onus" to do so, but if CFRG does anything in this area, it should do 
what its charter says.

> draft-josefsson-tls-curve25519-04.

draft-josefsson-tls-curve25519-04 defines a way to use a variant of 
Curve25519 in TLS, by describing the differences between RFC4492 
(Weierstrass ECC in TLS) and Curve25519 processing, and some differences 
and clarifications relative to the Curve25519 processing described in 
the PKC2006 publication.   This is clear from the following quotes:

"Private keys MUST be selected as specified in [Curve25519].  That is, 
private keys are 255-bits numbers with the following properties: ..."

"ECPoint.point differs from the definition of public keys in 
[Curve25519] in two ways: ..."

"Again, in line with [RFC4492] and as a departure from the convention 
chosen in [Curve25519], the x coordinate is converted to a byte  string 
using big endian order. ..."

"The following subsections describe the differences between using 
Curve25519 and the curves defined by RFC 4492 for key exchange in TLS. ... "

Defining a new thing by its differences from two existing things is not 
the best way to get a clear and easy to implement specification.    The 
authors could improve clarity by brining in more of the description of 
Curve25519, or by referencing external work such as an informational 
draft/RFC that describes Curve25519 (preferably the same variant as in 
draft-josefsson-tls-curve25519).

One way that RFC6090 added clarity was by clearly separating normative 
references from informative ones, and relying only on a small sufficient 
set of normative references that were early (pre-1994).   It would be 
good to have this sort of clarity for IETF work on Curve25519.

It would be better to have a separate draft/RFC on Curve25519, as 
described above, because it will be clearer and more conducive to re-use 
of the mechanism across IETF protocols.   If no separate normative 
document is produced, then it will be important for 
draft-josefsson-tls-curve25519 to incorporated a more complete 
description of Curve25519.

Disclaimer: I have not tried to implement 
draft-josefsson-tls-curve25519, and I'm not claiming that it is 
ambiguous.   The authors deserve thanks for writing this document. Our 
aim should be to produce clear, well-understood specifications.   Not 
all RFC are clear or well-understood, but we don't need to emulate that 
precedent.

David

> TLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/tls
>

---

From: Paul Lambert <[email-masked]>
Date: Thu, 13 Mar 2014 22:56:08 -0700

>> cryptography, and that such an issue is worth blocking specs.

I was never advocating blocking these specifications.

The use of Edwards and Montgomery curves for Internet protocols are
relatively new.  There are gaps in the documentation of these new
mechanisms that should be filled at some point. I was trying to
constructively point to worked examples from twenty years of ECC
specifications.

Paul

---

From: Watson Ladd <[email-masked]>
Date: Thu, 13 Mar 2014 23:41:38 -0700

> I was never advocating blocking these specifications.

I have to apologise: I misread your initial email as saying that the
Curve25519 was an insufficient normative reference as meaning that it
didn't define things clearly enough, and therefore you thought the
spec was ambiguous. I realise now you meant that, independent of the
citation issue, you wanted more documentation.

> constructively point to worked examples from twenty years of ECC

And that is currently being worked on by Robert Ransom, who seems to
have taken over right now from myself. I'll probably jump in this
weekend and write up the algorithms that are required to compute point
multiples, together with the precautions to avoid side channels.

The big problem with Edwards is we don't have a good point format yet.
Robert Ransom has a good idea, but I haven't seen explicit formulas
for encoding and decoding yet.

Sincerely,
Watson Ladd