Subject: [Cfrg] Review of draft-irtf-cfrg-eddsa-05

From: Jim Schaad <[email-masked]>
Date: Mon, 1 Aug 2016 10:39:56 -0700

I am reviewing the current draft because it is what is published.  I know
that some very significant changes have been made by the author's to their
editors draft which have not yet been published.  These changes must be
considered to be blocking as they are errors in the algorithm.

I will now comment on the draft as a whole and on specific issues that I
have with the draft.

1.  I find the different capabilities between the two signature algorithms
to be frustrating.  I understand the value of context structures, however
the reasoning for it not being in the Curve 25519 side of the world is not
motivated.  While they are useful, I believe they should be removed from the
Curve 448 algorithms for consistency between the two.  I do not believe that
it is sufficient to say, don't worry and use an empty context when doing
drop in replacements if they are really that significant.  Either put them
in both or remove them from both.

2.  Although it does appear that the point addition code can be used for
doubling, the fact that the python code does not use would imply that it is
far more efficient to use a doubling function that is different.  The
Doubling code should be part of the provided document for people to use if
they desire.  This is true for both curves.  - Suggest highlighting the fact
in section 3 where it says that the formulas are complete that they can be
used for point doubling.

3.  It would be reasonable to provide a list of differences between the two
curve functions.  This would include things like the use of dom for one and
not the other with a list of reasons for the differences and expected
security differences.  One of which I assume is that 448 is more resistant
to abuse of pre-hash vs non pre-hash swaps since that is part of the dom
function.  There may be other things that should be highlighted up front as
well.

4.  It might be clearer in section 3.1 to describe ENC(x, y) = ENC(y) ||
SIGN(x)  and then defined SIGN(x) as "1 if x is negative and 0 if x is not
negative".  This builds on the previous paragraph.   I don't know what
happens to the ENC(x, y) function if b is not a multiple of 8.  This should
probably be defined.  The ENC(x) function I assume is never padded out to a
multiple of 8, but that might not be the case.  It might also be different
depending on the context in which case life will get fun really fast.
Simplest answer might be to go from recommended to required in the
definition of b

5.  In section 3.1, I don't understand where the last paragraph is going.
It might be useful to motivate it.

6.  In section 3.3, the function dom is not used in the computation of S.
This should be included in the generic algorithm and defined as being the
empty function for Ed25519.  This means that introducing it later is no
longer a surprise.

7.  In section 3.4 suggest s/A in E/A/  I found the additional in E to be
confusing and it is not used elsewhere.

8.  In section 5.1.7 there needs to be a discussion of the trade-offs of
using the second verification formula rather than the first.  What is the
difference if any?

9.  In section 5.2, I just got a surprise that was unexpected.  I did not
expect that the pre-hash function would include the use of function dom.
This is going to be a surprise for a lot of code as it will assume that they
can just compute the hash of the message x and then pass that into the
signing function without any additional work being done on their part.  I
can understand dom being used in the signature computation but why is it
done here as well.  Also this is very different from Ed25519ph.

10.  A citation in section 10.2 on multiple signature verification needing
randomness is requested.

11. I found the driver function to be frustrating in the process of using it
to debug my code for a number of reasons.

a)  It was missing the following line " assert sys.version_info >= (3,3)"
which would have saved me time since I have multiple versions of python.
b) The driver is only setup to deal with the one function of Ed25519.  That
meant I had to munge it in various ways to deal with the other functions.
c) The format is of the file at sign.input is not documented either here or
in the file itself.
d) It is not clear what the file format should be for the pre-hash functions
or for the addition of the context field for Ed448.
e) The python code occasionally pulls tricks that are not self-evident in
order to perform some of the checks required in the document making checking
of this more difficult.  "Do I need to do that check really?"
f) The python code uses point doubling, but of course the document doesn't.

jim

---

From: Ilari Liusvaara <[email-masked]>
Date: Tue, 2 Aug 2016 10:50:55 +0300

> in both or remove them from both.

Yeah, that _seriously_ annoys me. Because if you need contexts, you _need_
contexts.

The issues with "LURK SKI" ekr pointed out are a good warning on how
things can go wrong (abusing TLS server signing key to sign some
completely different things).

> in section 3 where it says that the formulas are complete that they can be

One of the changes to Editor's Copy should fix this (doubling formulas
are given after respective addition formulas). In one case, there is
substantial difference.

> function.  There may be other things that should be highlighted up front as

Oh yeah, the Ed25519 vs. Ed25519ph footgun...

> Simplest answer might be to go from recommended to required in the

If b is not multiple of 8, some outputs will not be octet strings! That's
the reason for using b=456 and not b=449 with Ed448, as the latter would
cause nasty special cases.

> It might be useful to motivate it.

Essentially, the idea is to defer divisions to as late as possible by
representing numbers in form x/z.

This is because divisions are _seriously_ slow. It is much faster to
do lots of extra multiplies to handle "numerators" and "denominators"
separatedly.

> empty function for Ed25519.  This means that introducing it later is no

Hmm...
 
> confusing and it is not used elsewhere.

E means the elliptic curve (and it is defined earlier).

The whole section 3 is pretty confusing...

> using the second verification formula rather than the first.  What is the

The second formula rejects some signatures (that aren't constructed by
the signing algorithm presented) the first accepts.

Specifically, the first one ignores multiples of point of order 8 added
to R and A (however, A is hashed into k), whereas with the second formula,
such multiples have to match up too.

And in certain applications, it is a problem if two implementations don't
agree on what are acceptable signatures (even if computing acceptable
signatures for both without private key is infeasible).

> done here as well.  Also this is very different from Ed25519ph.

Yeah, that's unnecressary. Also, the prehash used is kinda weird anyway
(SHAKE256@512, which is not actual hash function).

> 10.  A citation in section 10.2 on multiple signature verification needing

Essentially, the idea is to verify a random linear combination of
signatures, and the role of randomness is to prevent attacker from
constructing signatures that meet the fixed relation.

> f) The python code uses point doubling, but of course the document doesn't.

I actually have alternate driver that is focused to protocol development
(I don't remember if it does contexts, but it definitely does Ed448).
Can take keys stuff as hex/base64/UTF-8 from command line or as binary
from file, and output hex/base64 to screen or binary to file.

-Ilari

---

From: Jim Schaad <[email-masked]>
Date: Tue, 2 Aug 2016 09:21:18 -0700

> -----Original Message-----
> From: Cfrg [mailto:[email-masked]] On Behalf Of Ilari Liusvaara
> Sent: Tuesday, August 02, 2016 12:51 AM
> To: Jim Schaad <[email-masked]>
> Cc: [email-masked]; [email-masked]
> Subject: Re: [Cfrg] Review of draft-irtf-cfrg-eddsa-05
> 
> > I am reviewing the current draft because it is what is published.  I
> > know that some very significant changes have been made by the author's
> > to their editors draft which have not yet been published.  These
> > changes must be considered to be blocking as they are errors in the
algorithm.
> >
> > I will now comment on the draft as a whole and on specific issues that
> > I have with the draft.
> >
> > 1.  I find the different capabilities between the two signature
> > algorithms to be frustrating.  I understand the value of context
> > structures, however the reasoning for it not being in the Curve 25519
> > side of the world is not motivated.  While they are useful, I believe
> > they should be removed from the Curve 448 algorithms for consistency
> > between the two.  I do not believe that it is sufficient to say, don't
> > worry and use an empty context when doing drop in replacements if they
> > are really that significant.  Either put them in both or remove them
from both.
> The issues with "LURK SKI" ekr pointed out are a good warning on how
things
> can go wrong (abusing TLS server signing key to sign some completely
different
> things).
> 
> > 2.  Although it does appear that the point addition code can be used
> > for doubling, the fact that the python code does not use would imply
> > that it is far more efficient to use a doubling function that is
> > different.  The Doubling code should be part of the provided document
> > for people to use if they desire.  This is true for both curves.  -
> > Suggest highlighting the fact in section 3 where it says that the
> > formulas are complete that they can be used for point doubling.
> 
> One of the changes to Editor's Copy should fix this (doubling formulas are
given
> after respective addition formulas). In one case, there is substantial
difference.
> 
> > 3.  It would be reasonable to provide a list of differences between
> > the two curve functions.  This would include things like the use of
> > dom for one and not the other with a list of reasons for the
> > differences and expected security differences.  One of which I assume
> > is that 448 is more resistant to abuse of pre-hash vs non pre-hash
> > swaps since that is part of the dom function.  There may be other
> > things that should be highlighted up front as well.
> 
> > happens to the ENC(x, y) function if b is not a multiple of 8.  This
> > should probably be defined.  The ENC(x) function I assume is never
> > padded out to a multiple of 8, but that might not be the case.  It
> > might also be different depending on the context in which case life will
get fun
> really fast.
the reason
> for using b=456 and not b=449 with Ed448, as the latter would cause nasty
> special cases.
> 
representing
> numbers in form x/z.
> 
> This is because divisions are _seriously_ slow. It is much faster to do
lots of extra
> multiplies to handle "numerators" and "denominators"
> separatedly.

I think you hit the wrong section.

The encoding of GF(p) is used to define "negative" elements of GF(p):
   specifically, x is negative if the (b-1)-bit encoding of x is
   lexicographically larger than the (b-1)-bit encoding of -x.

> > This should be included in the generic algorithm and defined as being
> > the empty function for Ed25519.  This means that introducing it later
> > is no longer a surprise.
> 
> Hmm...
> 
> > 7.  In section 3.4 suggest s/A in E/A/  I found the additional in E to
> > be confusing and it is not used elsewhere.
> 
> > 8.  In section 5.1.7 there needs to be a discussion of the trade-offs
> > of using the second verification formula rather than the first.  What
> > is the difference if any?
> 
> The second formula rejects some signatures (that aren't constructed by the
> signing algorithm presented) the first accepts.
> 
> Specifically, the first one ignores multiples of point of order 8 added to
R and A
> (however, A is hashed into k), whereas with the second formula, such
multiples
> have to match up too.
agree
> on what are acceptable signatures (even if computing acceptable signatures
for
> both without private key is infeasible).
> 
> > 9.  In section 5.2, I just got a surprise that was unexpected.  I did
> > not expect that the pre-hash function would include the use of function
dom.
> > This is going to be a surprise for a lot of code as it will assume
> > that they can just compute the hash of the message x and then pass
> > that into the signing function without any additional work being done
> > on their part.  I can understand dom being used in the signature
> > computation but why is it done here as well.  Also this is very
different from
> Ed25519ph.
> > 10.  A citation in section 10.2 on multiple signature verification
> > needing randomness is requested.
> 
signatures, and
> the role of randomness is to prevent attacker from constructing signatures
that
> meet the fixed relation.

Hmmmmm....   Yeah that doesn't help any.

Jim

> 
> > 11. I found the driver function to be frustrating in the process of
> > using it to debug my code for a number of reasons.
> >
> > b) The driver is only setup to deal with the one function of Ed25519.
> > That meant I had to munge it in various ways to deal with the other
functions.
> > c) The format is of the file at sign.input is not documented either
> > here or in the file itself.
> > d) It is not clear what the file format should be for the pre-hash
> > functions or for the addition of the context field for Ed448.
> > e) The python code occasionally pulls tricks that are not self-evident
> > in order to perform some of the checks required in the document making
> > checking of this more difficult.  "Do I need to do that check really?"
(I don't
> remember if it does contexts, but it definitely does Ed448).
from
> file, and output hex/base64 to screen or binary to file.
> 
> 
> -Ilari
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 2 Aug 2016 13:59:28 -0700

> On Aug 2, 2016, at 12:50 AM, Ilari Liusvaara <[email-masked]> wrote:
> 

Perhaps we could fix the context to the empty string, and then put the actual context code in the appendix?

There’s been a lot of criticism for contexts, since of course they are redundant with prefixing the message.  I still kind of like them, because in some legacy protocol you can specify the signature algorithm as Ed448(context=“my legacy protocol”) and it will be separated from other uses of Ed448 with the same key.  But I agree that the split is confusing as it is now.

> signatures for both without private key is infeasible).

I agree that this needs to be discussed in the document.

> (SHAKE256@512, which is not actual hash function).

I’d be happy to see a change to the prehash.  It should still probably be SHAKE or SHA3 though, to match the signature; or else we would have to extend the context to describe what the hash is, which would be annoying.

Cheers,
— Mike

---

From: Taylor R Campbell <[email-masked]>
Date: Tue, 2 Aug 2016 22:28:41 +0000

Date: Tue, 2 Aug 2016 13:59:28 -0700
   From: Mike Hamburg <[email-masked]>

   There's been a lot of criticism for contexts, since of course they
   are redundant with prefixing the message.  I still kind of like
   them, because in some legacy protocol you can specify the signature
   algorithm as Ed448(context=`my legacy protocol') and it will be
   separated from other uses of Ed448 with the same key.  But I agree
   that the split is confusing as it is now.

In what legacy protocol can you specify a new signature scheme over a
new curve with a new special-purpose context parameter for existing
keys, yet you can't control anything else about how the existing keys
are used for other inputs?

---

From: Jim Schaad <[email-masked]>
Date: Tue, 2 Aug 2016 17:12:01 -0700

I would have to go through the mailing list again to be sure, however I
believe that the argument was the Ed25519 is currently being used in
protocols today.  For some reason I seem to remember that SSH was one such
but I don't have anything but a vague memory to back that up. If so, the
version being used in SSH does not have the context structure built into it.
The desire was to not deliberately have an incompatible signature scheme
defined here that would not match what is being done in these protocols.

Jim

> From: Taylor R Campbell [mailto:[email-masked]] On Behalf Of Taylor R
> Campbell
> Sent: Tuesday, August 02, 2016 3:29 PM
> To: Mike Hamburg <[email-masked]>
> Cc: Ilari Liusvaara <[email-masked]>; Jim Schaad
> <[email-masked]>; [email-masked];
[email-masked]
> Subject: legacy protocols and contexts [was Re: [Cfrg] Review of
draft-irtf-cfrg-
> eddsa-05]
> In what legacy protocol can you specify a new signature scheme over a new
> curve with a new special-purpose context parameter for existing keys, yet
you
> can't control anything else about how the existing keys are used for other
> inputs?

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 2 Aug 2016 18:43:37 -0700

> On Aug 2, 2016, at 3:28 PM, Taylor R Campbell <[email-masked]> wrote:
> 

Legacy protocols get extended all the time.  Especially TLS.  They get new cryptosystems and new ways of using those cryptosystems.  They have many extension specs written by many different people, some of which may be rather unlikely to change and would therefore need to be superseded, compounding the legacy headache.

Contexts are there so that you can domain-separate two extensions or other uses of a key, without changing the specs to both of them — or, conceivably, to either of them, if you define a way to determine the context for a given extension.

I understand that this doesn’t protect people who use older signature schemes that don’t have contexts.  It is merely a defense in depth, but this seems appropriate for what is already a paranoid-level curve.

If you don’t use the contexts, they cost a couple paragraphs in the spec, one extra byte passed to a hash function, and (if the library supports with and without) one extra function in the library API.  I hope that this is still little enough complexity that the potential gains outweigh the risks.  If not, I don’t have a huge problem with removing them, but I still think it’s important to distinguish prehashed and non-prehashed modes.

— Mike

---

From: Jim Schaad <[email-masked]>
Date: Tue, 2 Aug 2016 21:53:07 -0700

It dawns on me that I should probably state that while my main worry is that
the two algorithms be consistent of either having or not having the context
structure.  My preference would be to have the context structure as it
strengthens the resistance to the pre-hash/pure misuse even if it means that
there are two different things called Ed25519 in the wild.

Jim

> From: Cfrg [mailto:[email-masked]] On Behalf Of Jim Schaad
> Sent: Tuesday, August 02, 2016 5:12 PM
> To: 'Taylor R Campbell' <[email-masked]>; 'Mike Hamburg'
> <[email-masked]>
> Subject: Re: [Cfrg] legacy protocols and contexts [was Re: Review of
draft-irtf-
> cfrg-eddsa-05]
believe
> that the argument was the Ed25519 is currently being used in protocols
today.
> For some reason I seem to remember that SSH was one such but I don't have
> anything but a vague memory to back that up. If so, the version being used
in
> SSH does not have the context structure built into it.
> > From: Taylor R Campbell [mailto:[email-masked]] On Behalf Of
> > Taylor R Campbell
> > keys, yet
> > can't control anything else about how the existing keys are used for
> > other inputs?
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Wed, 3 Aug 2016 11:39:12 +0300

> there are two different things called Ed25519 in the wild.

I really don't think Ed25519 should be any different from what is in the
wild. Ed25519ph is not in the wild much.

The Chacha20-Poly1305 mess was bad enough, and that function was MUCH
less out there than Ed25519.

Also, I came up with the following cute hack:

- Split Ed448 into Ed448 and Ed448ctx according to context present/not.
- Define Ed25519ctx with hash prefix of
  "SigEd25519 no Ed25519 collisions"|byte(phflag)|byte(len(ctx))|ctx
- Define Ed25519ph in terms of Ed25519ctx.

Leaves Ed448(key,message) unchanged, leaves Ed25519 unchanged, that
prefix prevents any trivial hash collisions with Ed25519[1], prevents
Ed25519 vs. Ed25519ph key mixups (that seems like a major footcannon,
considering some of the use proposals I have seen).

One couldn't then compute Ed25519ph with standard Ed25519 software,
but I don't consider that that major problem.

[1] If one tries to use that value as R in Ed25519, which is necressary
for trivial collision, verification tries to calculate square root of
QNR, which obviously fails.

-Ilari

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 3 Aug 2016 11:55:41 -0700

I like this hack, though it is certainly a hack.  Does 
> - Split Ed448 into Ed448 and Ed448ctx according to context present/not.
mean that Ed448 is equivalent to Ed448ctx(context=“”)?  I’m guessing so?

— Mike

> On Aug 3, 2016, at 1:39 AM, Ilari Liusvaara <[email-masked]> wrote:
>

---

From: Jim Schaad <[email-masked]>
Date: Wed, 3 Aug 2016 12:08:32 -0700

It is a hack, but as hacks go this is relatively clean and looks like it addresses the problems.  There would be a question in the Curdle group about which of the 25519 functions to support - with or w/o the context but other than that things look good.

Jim

> From: Mike Hamburg [mailto:[email-masked]]
> Sent: Wednesday, August 03, 2016 11:56 AM
> To: Ilari Liusvaara <[email-masked]>
> Cc: Jim Schaad <[email-masked]>; [email-masked]; draft-irtf-cfrg-
> [email-masked]
> Subject: Re: [Cfrg] legacy protocols and contexts [was Re: Review of draft-irtf-
> cfrg-eddsa-05]
> 
> >> It dawns on me that I should probably state that while my main worry
> >> is that the two algorithms be consistent of either having or not
> >> having the context structure.  My preference would be to have the
> >> context structure as it strengthens the resistance to the
> >> pre-hash/pure misuse even if it means that there are two different things
> called Ed25519 in the wild.
> >
> > I really don't think Ed25519 should be any different from what is in
> > the wild. Ed25519ph is not in the wild much.
> >
> > [1] If one tries to use that value as R in Ed25519, which is
> > necressary for trivial collision, verification tries to calculate
> > square root of QNR, which obviously fails.
> >
> >
> > -Ilari
> >

---

From: Jim Schaad <[email-masked]>
Date: Wed, 10 Aug 2016 23:12:53 -0700

What if we do the following for dealing with things:

Ed25519:

r = SHA-512(dom(F, c) || prefix || PH(M))
k = SHA-512(dom(F, c) || A || PH(M))

where
dom(F, c) = empty string for PureEdDSA
dom(F, c) = "SigEd25519" || octet(x) || octet(OLEN(y)) || y    for Prehash-EdDSA

Ed448:
Keep the fomulas as they are today.

This would allow for a later definition of a 25519 context pure EdDSA in a new document.  While I would prefer to make this the one that is used in the IETF going forward, these changes will make things cleaner today and still allow for a forward path in the future if needed.

Jim

> From: [email-masked] [mailto:[email-masked]]
> Sent: Wednesday, August 03, 2016 1:39 AM
> I really don't think Ed25519 should be any different from what is in the wild.
> Ed25519ph is not in the wild much.
> 
> Leaves Ed448(key,message) unchanged, leaves Ed25519 unchanged, that prefix
> prevents any trivial hash collisions with Ed25519[1], prevents
> One couldn't then compute Ed25519ph with standard Ed25519 software, but I
> don't consider that that major problem.
> 
> 
> [1] If one tries to use that value as R in Ed25519, which is necressary for trivial
> collision, verification tries to calculate square root of QNR, which obviously
> fails.
> 
> 
> -Ilari

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 11 Aug 2016 09:51:21 +0300

On Wed, Aug 10, 2016 at 11:12:53PM -0700, Jim Schaad wrote:
> This would allow for a later definition of a 25519 context pure EdDSA
> in a new document.  While I would prefer to make this the one that is
> used in the IETF going forward, these changes will make things cleaner
> today and still allow for a forward path in the future if needed.

I would use some 32-byte prefix that does not decode as valid point.
Even if I don't know any attacks if prefix can decode as a valid point,
I'd rather not risk anything.

Also, If one wanted to do contexts in another document, one could
just fix the OLEN octet to 0 (so it is compatible).

-Ilari

---

From: Jim Schaad <[email-masked]>
Date: Thu, 11 Aug 2016 13:33:54 -0700

> Sent: Wednesday, August 10, 2016 11:51 PM
draft-irtf-
> > r = SHA-512(dom(F, c) || prefix || PH(M)) k = SHA-512(dom(F, c) || A
> > || PH(M))
> >
> > where
> > dom(F, c) = "SigEd25519" || octet(x) || octet(OLEN(y)) || y    for
Prehash-
> EdDSA
I'd rather
> not risk anything.

I agree that this would make a better prefix that what I suggested above.  I
do not think that it would be sufficient to just provide a value which is
invalid because it is greater than P, I think that a non-square root is
better.  If the first is fine, then just extending the string with 0xff
would be fine.  If the latter is better then somebody would need to find a
value.

> 
> 
> Also, If one wanted to do contexts in another document, one could just fix
the
> OLEN octet to 0 (so it is compatible).

I would find that to be reasonable.

Jim