Re: [GNUnet-developers] EcDSA signature scheme

[Christian Grothoff]

On 07/13/2018 06:39 PM, Bernd Fix wrote:
>> Well, there is one tricky bit with that I forgot to point out in my 
>> previous message: we do use (rarely) the same point/key for both 
>> ECDHE and EdDSA (specifically, in Taler).  Hence, here it is
>> relevant to have the same public key representation across both
>> schemes.
> 
> This constraint of course make things trickier, because that means we
> are stuck in using Ed25519 for ECDHE. A possible solution (again: not
> for GNUnet itself, but for implementators in general) for using Ed25519
> points with ECDHE is to use the bijective mapping between Ed25519 and
> Curve25519 and to do the ECDHE on Curve25519. Not nice probably, but
> that could work.

Well, there is another possibility: simply have *two* versions of
ECDHE/X25519: one for Taler where we mix it with EdDSA, and another one
for GNUnet core/cadet KX where we do not rely on this property.

>>> ECDSA: ------ I also have some problems with this one - and it is 
>>> used everywhere in GNUnet for (user) identities (although not by 
>>> the crypto used for secure message exchange in sessions).
>>>
>>> AFAIK is the choice of curve for ECDSA limited (NIST curves 
>>> basically). I think that is one of the reason we have EdDSA in the 
>>> first place. But maybe I am wrong here...
>>
>> You are. You can use Curve25519 with ECDSA, and that is what we do in
>> GNUnet. No NIST curves to be found.
> 
> Well, ECDSA in GNUnet is used with Ed25519 (and not Curve25519). Even
> the gcrypt manual
> (https://www.gnupg.org/documentation/manuals/gcrypt/General-public_002dkey-related-Functions.html)
> states:
> 
> "Here is an example on how to create a key using curve Ed25519 with the
> ECDSA signature algorithm. Note that the use of ECDSA with that curve is
> in general not recommended."

Right, I would totally underwrite that one, emphasis on "generally" ;-).
That's why when we can avoid it, we do use EdDSA ;-).

> Yes, you *can* use ECDSA with Ed25519 (gcrypt implements it) or
> Curve25519, but to my knowledge both curve types (Montgomery/twisted
> Edwards) are not *recommended* for ECDSA, which was designed with
> Weierstrass curves in mind (but I am not so deep into ECC that I can
> recall the exact security considerations leading to that statement - or
> do you consider that statement incorrect?)

Well, I don't think the type of curve is so much what has people
worried, but the issue with nonce generation inherent in DSA and ECDSA.
So if there is a better scheme that is applicable (like EdDSA), one
should use the less brittle one. But I'm not aware of a specific risk
arising from the Edwards/Montgomery curves for ECDSA. Just ECDSA in
general is inferior to EdDSA. That's like using BLS for no reason. But
here we do have a reason.

>>> Changing the code to really use Curve25519 would ease the pain 
>>> significantly. But if someone asks me, I would replace ECDSA with 
>>> EdDSA completely...
>>
>> Please note that this is not so easy: we use ECDSA specifically 
>> because the following holds (needed for GNS):
>>
>> Suppose A := aG.  Let b := xa for some random x.  Then B := xaG.
>> Now, suppose I give you my public key A and x. Now I can sign
>> something with xa as the private key, and you can verify the
>> signature using xA.
>>
>> EdDSA applies h(ax) to the private key, and this hashing destroys the
>> (otherwise) linear relationship as with
>>
>> A := h(a)G, b := xa and B := h(xa)G
>>
>> no longer allows for xA = B (and also not h(x)A = B).
>>
>> Doing GNS-crypto (which is what we do with identities) thus would 
>> require you to re-implement parts of EdDSA to get past the 'h' 
>> application. Doable, but messy. So please make sure that if you do
>> try to change this, that the GNS crypto is still 'happy'.
> Let's assume ECDSA is used with Curve25519 (ignoring my previous
> arguments against this). For me it then looks like all requirements for
> GNS-crypto are also satisfied. So are there any other arguments to at
> least switch ECDSA from Ed25519 to Curve25519?

Right now, none come to mind. There was a reason for ECDH(E) to be
EdDSA-compatible, so I just used EdDSA everywhere for uniformity, but
for the ECDSA-case I don't immediately see a technical reason why we
could not use Curve25519.

Naturally, we should do this in the context of a larger
compatibility-break *and* make sure to test things carefully. As we've
seen with the Taler use-case, I sometimes forget about some corner case
that does ultimately matter ;-).

signature.asc
Description: OpenPGP digital signature