Re: [TLS] [Cfrg] Citing specs in specs

[Paul Lambert <[e-mail]>]

On 3/4/14, 3:03 PM, "Watson Ladd" <[e-mail]> wrote:

>On Mon, Mar 3, 2014 at 9:32 PM, Paul Lambert <[e-mail]> wrote:
>>
>>
>> On 3/3/14, 2:52 PM, "Jon Callas" <[e-mail]> wrote:
>>
>>>On Mar 2, 2014, at 3:40 PM, Paul Lambert <[e-mail]> wrote:
>>>
>>>> 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...
>>>
>>>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.
>
>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.


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.




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

Yes - both are required.
>
>>>
>>>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.
>
>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.

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)



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

‘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




>
>Sincerely,
>Watson Ladd
>>
>> Paul
>>
>>
>>
>>
>>>
>>>       Jon
>>>
>>
>
>
>
>-- 
>"Those who would give up Essential Liberty to purchase a little
>Temporary Safety deserve neither  Liberty nor Safety."
>-- Benjamin Franklin