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

From: Jim Schaad <[email-masked]>
Date: Mon, 11 Jul 2016 06:53:54 -0700

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.

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.  

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.

Jim

---

From: Mike Hamburg <[email-masked]>
Date: Mon, 11 Jul 2016 11:14:19 -0700

> On Jul 11, 2016, at 6:53 AM, Jim Schaad <[email-masked]> wrote:
> 

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.

> implement this algorithm for computing square roots if that is what is

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.

> highlighted that it is being done in the field parsing function rather than

It’s being done in decode_base, right?

> Jim

Cheers,
— Mike

---

From: Jim Schaad <[email-masked]>
Date: Mon, 11 Jul 2016 11:43:37 -0700

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Mike Hamburg
> Sent: Monday, July 11, 2016 11:14 AM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]; [email-masked]
> Subject: Re: [Cfrg] draft-irtf-cfrg-eddsa - more implementation questions
> 
> 
> 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.
> 

Probably because the document implies that one should in order to avoid the double modular exponentiation.

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

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

> 
> > Jim
> 
> Cheers,
> — Mike
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Mike Hamburg <[email-masked]>
Date: Mon, 11 Jul 2016 12:25:43 -0700

> On Jul 11, 2016, at 11:43 AM, Jim Schaad <[email-masked]> wrote:
> 
> 
> 

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.

> obtains the value of x_0, however it does not remove it from the array s, that is being done in frombytes (I think).

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

— Mike