[curves] Finalizing XEdDSA

[Mike Hamburg]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2517 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161101/e2391651/attachment.bin>