[curves] Climbing the elliptic learning curve (was: Re: Finalizing XEdDSA)

[Ron Garret]

OK, that makes sense.  Thanks!  (And thanks to Trevor for giving me the answer off-list.)

So let me hard-fork this thread and ask a followup meta-question:  The fact that 8 was the cofactor of the curve is apparently something most (if not all) people on this list already knew.  But how?  Neither the Ed25519 paper nor the Curve25519 paper mentions it (AFAICT).

In trying to back-solve the answer to this question myself I was led to RFC7748 Appendix A, which was very enlightening, but contained this (to me) cryptic comment:

"For primes congruent to 1 mod 4, the minimal cofactors of the curve and its twist are either {4, 8} or {8, 4}.”

Where the heck did *that* come from?  Digging through the references, I happened to stumble upon this:

http://www.hpl.hp.com/techreports/97/HPL-97-128.pdf

which seems like it’s the answer to that particular question.  But even this (apparently) elementary fact seems to be almost deliberately obscured in the literature.  Even https://safecurves.cr.yp.to doesn’t mention it, which is another indication that all this is just taken to be common knowledge.

Another data point: I asked a similar question to this once before and was pointed to the Handbook of Elliptic and Hyperelliptic Curve Cryptography by Cohen & Fry et al.  The word “cofactor” appears in that 800-page tome on 22 pages.  The first appearance of the word is this passage on page 218:

"If the cofactor N/p is sufficiently small, the computations can be done modulo N without any addi- tional cost since multiplications are usually performed at a word level.”

i.e. the word is introduced in an offhand way and defined only in passing, as if the reader is expected to already know what a cofactor is and why it’s important.

BTW: Smart’s result came as a complete shock to me.  Every intro to ECC on the web says something isomorphic to “ECC is secure because DLP over elliptic curves is hard.”  But if I’m understanding this correctly, that statement is actually not true at all.  The correct statement is (AFAICT) something more like, “DLP over elliptic curves with cofactor >1 is hard, otherwise it’s easy.”

Bottom line: there seems to be a huge disconnect between the importance of cofactors on the one hand and the information available about them on the other.  On the one hand, cofactors seem to be so important that all this stuff that I just learned about seems to be common knowledge, and on the other hand, even now that I know it I *still* can’t figure out how I could have learned it other than asking this apparently stupid question.

So my meta-question is: *was* this a stupid question?  Did everyone really already know this except me?  And if so, how?

On Nov 1, 2016, at 10:30 AM, Mike Hamburg <mike at shiftleft.org> wrote:

> The 8s are the cofactor of Ed25519.  The idea is that you may check the equation's projection on the order-q subgroup, instead of in the whole group.  Depending on implementation, this may make things easier. For example, libdecaf projects everything into the order-q subgroup.
> 
> This is not supposed to make a difference because everything is supposed to live in the order-q subgroup.  But if someone generates their key or nonce wrong, then it makes a difference.
> 
> The problem with giving implementers the option is that it could allow fingerprinting or forking attacks. I'd rather see a hard requirement one way or the other. 
> 
> Sent from my phone.  Please excuse brevity and typos.
> 
>> On Nov 1, 2016, at 09:04, Ron Garret <ron at flownet.com> wrote:
>> 
>> 
>>> On Nov 1, 2016, at 7:14 AM, Peter Schwabe <peter at cryptojedi.org> wrote:
>>> 
>>> Trevor Perrin <trevp at trevp.net> wrote:
>>> 
>>> Dear Trevor,
>>> 
>>>> One last tweak to consider is clearing the cofactor in verification.
>>>> Currently XEdDSA does "cofactorless verification", i.e. it takes a
>>>> signature (R, s) and checks R == sB - hA.  We could change it to cR ==
>>>> c(sB - hA).  VXEdDSA would be unchanged.
>>>> 
>>>> This has no effect on valid signatures, but adding the cofactor
>>>> multiplication means signers could create signatures with a few
>>>> different values of R for the same s (which has no security relevance,
>>>> I think, and does not cause "malleability" because the signer's choice
>>>> of R is included in the hash).
>>>> 
>>>> Advantages to current "cofactorless" approach:
>>>> - matches existing code like (ref10, libsodium)
>>>> - less code, doesn't need a "point comparison" function (can encode,
>>>> then compare)
>>>> - less computation (by tiny amount, 1% or something)
>>>> 
>>>> Advantages to changing to "cofactor" approach:
>>>> - Allows batch verification of signatures (I'm told), that can give ~2x speedup
>>>> - Preferred approach in Ed25519 paper, "EdDSA for more curves" paper,
>>>> and CFRG draft
>>> 
>>> The Ed25519 paper says 
>>> 
>>> "The verifier is /permitted/ to check this stronger equation and
>>> to reject alleged signatures where the stronger equation does not
>>> hold. However, this is not /required/; checking that
>>> 8SB=8R+8H(\encode{R},\encode{A},M)A is enough for security."
>>> 
>>> 
>>> You could decide to do the same; allowing both for verification in the
>>> specification and leaving the choice to the implementation. If I
>>> understand correctly, this gives you the advantages of both approaches,
>>> right?
>> 
>> Possibly naive question: What is “this stronger equation” that the paper refers to?  Because the immediately preceding equation is:
>> 
>> SB = rB + H(\encode{R},\encode{A},M)aB = R + H(\encode{R},\encode{A},M)A
>> 
>> which is actually two equations.  The first:
>> 
>> SB = rB + H(\encode{R},\encode{A},M)aB
>> 
>> relies on the secret key a, so that does not seem particularly useful.  But the second equation:
>> 
>> SB = R + H(\encode{R},\encode{A},M)A
>> 
>> Is (AFAICT) identical to the earlier “weaker” equation:
>> 
>> 8SB = 8R+8H(\encode{R},\encode{A},M)A
>> 
>> except for factoring out the 8’s.  (Where did those 8’s come from anyway?  They seem completely unmotivated.)
>> 
>> What am I missing?
>> 
>> rg
>> 
>> _______________________________________________
>> Curves mailing list
>> Curves at moderncrypto.org
>> https://moderncrypto.org/mailman/listinfo/curves