Re: [GNUnet-developers] EcDSA signature scheme

[Christian Grothoff]

On 07/13/2018 12:33 AM, Bernd Fix wrote:
> The ECC crypto schemes (in ./src/util) have three different "mechanisms"
> (two for signatures and one for ECDHE key exchange): EdDSA, ECDSA and ECDHE.
> 
> I am fine with EdDSA (except for minor irritations), but would like to
> comment on the other two:
> 
> ECDHE:
> ------
> Good, but it is used with curve Ed25519. The problem is that ECDHE
> requires scalar multiplication of a point on the curve (that is not the
> base point!) - and that functionality is not available in many Ed25519
> implementations - they often only provide sign/verify operations.
> 
> A more natural choice for me would be ECDHE with Curve25519.
>
> Interestingly in ./src/include/gnunet_crypto_lib.h (line 248) I read:
> 
>> /**
>>  * Public ECC key (always for Curve25519) encoded in a format suitable
>>  * for network transmission and encryption (ECDH),
>>  * See http://cr.yp.to/ecdh.html
>>  */
>> struct GNUNET_CRYPTO_EcdhePublicKey
> 
> So it looks like that was the initial intention here too: Using ECDHE
> with Curve25519. Unfortunately this is not what is implemented (see
> ./src/util/crypto_ecc.c (line 563):
> 
>>  if (0 != (rc = gcry_sexp_build (&s_keyparam, NULL,
>>                                  "(genkey(ecc(curve \"" CURVE "\")"
>>                                  "(flags eddsa no-keytest)))")))
> 
> Does libgcrypt support Curve25519? If it does, a change here would be
> rather straight-forward. As only ephemeral keys are involved, no side
> effects on persistent information is to be expected.

EdDSA here does not refer to the actual EdDSA signature algorithm, but
to the point compression algorithm which should be used by libgcrypt
(see page 37, https://www.gnupg.org/documentation/manuals/gcrypt.pdf).
Now, I can see why you might argue that the resulting point should be in
X25519 format for Curve25519, that would seem to require the 0x40 byte
to explicitly request the algorithm's native compression method to be
used.  I don't mind changing the point format for the ECDHE case to
X25519 (at a point where we break compatibility).

> One last question: Is it correct that an ephemeral key for ECDHE has a
> lifetime of ~12h? Will all sessions between two peers use the same
> shared secret for the time the two 12h periods overlap (between 6h and 12h)?

Yes, we use the same ephemeral key for all peers for a fixed time
period, so we only need to do one EdDSA signature per 12h for CORE.

> 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.

> In ./src/include/gnunet_crypto_lib.h (line 248) I read:
> 
>> /**
>>  * Public ECC key (always for Curve25519) encoded in a format suitable
>>  * for network transmission and ECDSA signatures.
>>  */
>> struct GNUNET_CRYPTO_EcdsaPublicKey
> 
> Maybe this is just a copy&paste effect, but it seems that the original
> intention was to use Curve25519 - as for ECDHE. Because ECDSA would
> require not only scalar multiplication of a curve point but also point
> addition, implementors will run into the same problems as with ECDHE
> (libraries).

Well, libgcrypt does support ECDSA with Curve25519.

> 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'.

0xE29FC3CC.asc
Description: application/pgp-keys

signature.asc
Description: OpenPGP digital signature