Subject: [Cfrg] Open Issue List for draft-irtf-cfrg-eddsa-06

From: Jim Schaad <[email-masked]>
Date: Thu, 11 Aug 2016 16:47:53 -0700

The following is what I would consider to be on my open issue list for this
draft to get to approval.  I have tried to triage the list according to my
priorities.

High Priority:

1.  Fix the known security issue with EdDSA25519 and EdDSA25119ph:  I have
provided what I consider to be an elegant solution for this with the
modification from Ilari
(https://mailarchive.ietf.org/arch/msg/cfrg/VkBtpUwNIJ1JFAka1NljgBXgwVo)
And I was not the first, but my presentation is slightly different.

Moderate Priority:

1.  Remove the dom function from Ed448ph

Low Priority:

1.  In section 5.1.7, explain the trade-off between the two formulas and why
one is better than the other.

2.  Increase the size of the output of the Ed448ph if the security is not
consistent between the 448 bit curve and the 512 bit hash.  It just looks
odd because Ed25519 also uses a 512 bit pre-hash function.   My guess is
that nothing needs to be done, but an explanation might be useful.

3.  Define the ctx version of EdDSA25519.   It would be nice, esp if we
think that the context version is better even with null contexts, but if we
solve the first issue this can be done later if we decide it is preferable.

I don't care anymore:

1. Change the Ed448ph function to be a hash function rather than an XOR.  It
appears as long as the length is a known constant the two are equivalent for
all intents and purposes.
2. Previous issues that I raised with the python code.  My code is working
it no longer bothers me anymore.

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 12 Aug 2016 22:12:53 +0300

> And I was not the first, but my presentation is slightly different.

For reference, the idea is to add Ed448/Ed448ph-style prefix to
Ed25519ph, with first 32-bytes being fixed to be invalid point (so
hash can't trivially collide with any Ed25519 signature hash).

> 1.  Remove the dom function from Ed448ph

This is from the inner hash right?
 
> one is better than the other.

The second formula is stricter. However many existing implementations use
the first, and in some cases, not agreeing on exact set of acceptable
inputs is a problem (e.g. fingerprinting).

Well, the matematical explanation of the issue:

There is point T on Edwards25519, which has property [8]T = 0.

Arbitrary point P on Edwards25519 can be written in form:

P = [x]B + [y]T

For some 0<=x<L and 0<=y<8.

Now, the verification formula without multiplication becomes:

[s]B = R + [h]A  =>
[s]B = ([r_x]B+[r_y]T) + [h]([a_x]B+[a_y]T)  =>
[s]B = [r_x]B+[h][a_x]B + [r_y]T+[h][a_y]T  =>
[s]B = [r_x+h*a_x]B + [r_y+h*a_y]T

Which is satified iff:
s = r_x+h*a_x (mod L)
0 = r_y+h*a_y (mod 8).

Whereas with multiplication it becomes:
[8][s]B = [8]R + [8][h]A  =>
[8][s]B = [8]([r_x]B+[r_y]T) + [8][h]([a_x]B+[a_y]T)  =>
[8][s]B = [8][r_x]B+[8][h][a_x]B + [8][r_y]T+[h][a_y]T  =>
[8][s]B = [8r_x+8h*a_x]B + [r_y+h*a_y][8]T  =>
[8][s]B = [8r_x+8h*a_x]B + [r_y+h*a_y]0  =>
[8][s]B = [8r_x+8h*a_x]B  =>
[s]B = [r_x+h*a_x]B

Which is satified iff:
s = r_x+h*a_x (mod L)

So the second condition has dropped out. Now normally signatures have r_y=0
and a_y=0. But specially generated signatures may have nonzero values for
those parameters. So the exact set of signatures accepted differs.

(One can't use this for malleability, because h depends on R and A, so
any tweaks there after generation make signature fail).

And in some situations, it is issue if implmentations don't agree on exact
set of accepted inputs.
 
> that nothing needs to be done, but an explanation might be useful.

No action needed: Ed448ph uses SHAKE256, which caps off as 256-bit collision
resistance at 512 bit output.

> all intents and purposes.

Actually, they aren't (SHAKE256@512 is much weaker against preimages than
what 512-bit hash would be), but the differences don't matter here, since
we want collision resistance (which should be equivalent to 512-bit hash).

-Ilari

---

From: Jim Schaad <[email-masked]>
Date: Fri, 12 Aug 2016 12:46:29 -0700

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]]
> Sent: Friday, August 12, 2016 12:13 PM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]
> Subject: Re: [Cfrg] Open Issue List for draft-irtf-cfrg-eddsa-06
> 
> > The following is what I would consider to be on my open issue list for
> > this draft to get to approval.  I have tried to triage the list
> > according to my priorities.
> >
> >
> > High Priority:
> >
> > 1.  Fix the known security issue with EdDSA25519 and EdDSA25119ph:  I
> > have provided what I consider to be an elegant solution for this with
> > the modification from Ilari
> > (https://mailarchive.ietf.org/arch/msg/cfrg/VkBtpUwNIJ1JFAka1NljgBXgwV
> > o) And I was not the first, but my presentation is slightly different.
> 
> For reference, the idea is to add Ed448/Ed448ph-style prefix to Ed25519ph, with
> first 32-bytes being fixed to be invalid point (so hash can't trivially collide with
> any Ed25519 signature hash).
> 
> 
> > Moderate Priority:
> >

Not sure what you mean by inner hash - I was a little bit lax - I am talking about the PH function for Ed448ph.  

> 
> > Low Priority:
> >
> > 1.  In section 5.1.7, explain the trade-off between the two formulas
> > and why one is better than the other.
> 
> The second formula is stricter. However many existing implementations use the
> first, and in some cases, not agreeing on exact set of acceptable inputs is a
> problem (e.g. fingerprinting).
> 
> 
> [s]B = ([r_x]B+[r_y]T) + [h]([a_x]B+[a_y]T)  => [s]B = [r_x]B+[h][a_x]B +
> [r_y]T+[h][a_y]T  => [s]B = [r_x+h*a_x]B + [r_y+h*a_y]T
> 
> Which is satified iff:
> s = r_x+h*a_x (mod L)
> 0 = r_y+h*a_y (mod 8).
> 
> [8][s]B = [8]([r_x]B+[r_y]T) + [8][h]([a_x]B+[a_y]T)  => [8][s]B =
> [8][r_x]B+[8][h][a_x]B + [8][r_y]T+[h][a_y]T  => [8][s]B = [8r_x+8h*a_x]B +
> [r_y+h*a_y][8]T  => [8][s]B = [8r_x+8h*a_x]B + [r_y+h*a_y]0  => [8][s]B =
> [8r_x+8h*a_x]B  => [s]B = [r_x+h*a_x]B
> 
> Which is satified iff:
> s = r_x+h*a_x (mod L)
> 
> (One can't use this for malleability, because h depends on R and A, so any
> tweaks there after generation make signature fail).
> 
> And in some situations, it is issue if implmentations don't agree on exact set of
> accepted inputs.

Right and it would be useful to put some of that in as a security consideration or as part of the text that lists the formulas.  

> 
> > 2.  Increase the size of the output of the Ed448ph if the security is
> > not consistent between the 448 bit curve and the 512 bit hash.  It just looks
> > think that the context version is better even with null contexts, but
> > if we solve the first issue this can be done later if we decide it is preferable.
> 
> > I don't care anymore:
> >
> > 1. Change the Ed448ph function to be a hash function rather than an
> > XOR.  It appears as long as the length is a known constant the two are
> > equivalent for all intents and purposes.
> 
> what 512-bit hash would be), but the differences don't matter here, since we
> want collision resistance (which should be equivalent to 512-bit hash).

Yes, but that is because of the parameters chosen and not because there is something inherently bad about using SHAKE (the XOR) function rather than SHA1 (a hash function).  There is nothing about being an XOR construct that makes it bad unless the length can be changed in some arbitrary fashion by and attacker which is less true with hash functions.  That is doing something along the lines making the length of the SHAKE output a parameter might not be a good idea.  But having an OID with a fixed length might be reasonable.

In the LAMPS group there is a question of using SHAKE rather than SHA2 for computing the digest of the message.  This is more problematic if the length of the resulting digest is not fixed but is allowed to very.

Jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 15 Aug 2016 11:41:48 +0300

> And I was not the first, but my presentation is slightly different.

Did a WIP about algorithm modifications. Basically everything except
Ed25519 and Ed448 got modified.

I crosschecked the changes to the Python reference implementation
by modifying C implementation I have (turns out one has to only modify
tables that specify how schemes behave).

> 1.  Remove the dom function from Ed448ph

Done in the WIP.

> one is better than the other.

Added some text about this into Editor's Copy.
 
> that nothing needs to be done, but an explanation might be useful.

Added some text about this into Editor's Copy.

> solve the first issue this can be done later if we decide it is preferable.

Since that is easy to do once one has fix for the prehash issue, I did that
too (named the result "Ed25519ctx", just to avoid confusion).

-Ilari