Re: [Cfrg] draft-irtf-cfrg-eddsa - more implementation questions

[Mike Hamburg <[e-mail]>]

> On Jul 11, 2016, at 11:43 AM, Jim Schaad <[e-mail]> wrote:
> 
> 
> 
>> -----Original Message-----
>> From: Cfrg [mailto:[e-mail]] On Behalf Of Mike Hamburg
>> Sent: Monday, July 11, 2016 11:14 AM
>> To: Jim Schaad <[e-mail]>
>> Cc: [e-mail]; [e-mail]
>> Subject: Re: [Cfrg] draft-irtf-cfrg-eddsa - more implementation questions
>> 
>> 
>>> On Jul 11, 2016, at 6:53 AM, Jim Schaad <[e-mail]> wrote:
>>> 
>>> In step #3 of the verify function, I assume that I can reduce k mod p
>>> without any problems.   Can I reduce it mod L or not?  It would be useful to
>>> have the hint in the text since it is all over the Sign algorithm.
>> 
>> Good idea; we should add that hint to the spec.
>> 
>> You can’t reduce it mod p.  You can and should reduce it mod L (aka q), at least
>> for the non-strict verification formula.
>> 
>> For the strict verification formula, it may be better to reduce mod hL, where h=8
>> or 4 for ed25519 and ed448 respectively.  This doesn’t affect the usual notion of
>> security, but reducing mod hL will give you the same answer as not reducing,
>> and reducing mod L will sometimes change whether a maliciously-crafted
>> signature validates or not.
>> Since the spec doesn’t say you may reduce mod L, you probably shouldn’t.  But
>> the easier solution is not to use the strict formula.
>> 
>>> I have been using the python program to help debug my quick
>>> implementation of the signature algorithm.  This has worked up to the
>>> point of trying to decode points as the python code does not use the
>>> suggested formula in section 5.1.3 (use this trick) but instead just
>>> directly computes a square root on the base formula.
>>> 
>>> I am therefore unable to determine where my bug is:  In my code, in
>>> the formula, or in how I read the formula.  It might be worthwhile to
>>> actually implement this algorithm for computing square roots if that
>>> is what is suggested.
>> 
>> How are you implementing the division and square root?  The code for square
>> root looks almost the same as the trick anyway, so you could just switch it over.
> 
> Probably because the document implies that one should in order to avoid the double modular exponentiation.

I agree that the python code could stand some improvement.  It should probably also use pow() instead of implementing exponentiation itself.

I believe that the formula given for sqrt(u/v) is correct, but it really should be given as x = u * (uv)^((p-5)/8) and then the same adjustment stpes, because that’s simpler and also correct.  Also, it should be implemented in the Python code.

Likewise, the formula for ed448 in 5.2.3 is correct, but should be replaced by x = u * (uv)^((p-3)/4) with the same adjustment steps.

> 
>> 
>>> By the way, I finally found were the neutral point was defined.  You
>>> still might want to highlight it as part of the point addition sections.
>>> 
>>> Looking at the python code, I think I see the trick you are using to
>>> deal with step 1 in the decoding code for removing the x_0 bit but it
>>> could be highlighted that it is being done in the field parsing
>>> function rather than the decoding function.
>> 
>> It’s being done in decode_base, right?
> 
> No 
>        xs=s[(b-1)//8]>>((b-1)&7)
> 
> obtains the value of x_0, however it does not remove it from the array s, that is being done in frombytes (I think).
> 
> jim

Ah, OK.  Another place where the python should be simplified.

— Mike