triple DH

[Christian Grothoff]

Hi!

Bart just prompted me to look over libgcrypt's key generation for EdDSA
vs. ECDHE (again).
I noticed a two odd things.  First, in 'ecc.c::nist_generate_key' you do
(for EdDSA):

      rndbuf = _gcry_random_bytes_secure (32, random_level);
      rndbuf[0] &= 0x7f;  /* Clear bit 255. */
      rndbuf[0] |= 0x40;  /* Set bit 254.   */
      rndbuf[31] &= 0xf8; /* Clear bits 2..0 so that d mod 8 == 0  */
      _gcry_mpi_set_buffer (sk->d, rndbuf, 32, 0);
 
The bit operations may seem to be to follow the EdDSA spec, but that's
actually false. Those
bit operations must be done AFTER the hashing, and you do those there as
well, in ecc-edsa.c::508:

 reverse_buffer (hash_d, 32);  /* Only the first half of the hash.  */
  hash_d[0] = (hash_d[0] & 0x7f) | 0x40;
  hash_d[31] &= 0xf8;
  _gcry_mpi_set_buffer (a, hash_d, 32, 0);

So in ecc:c::nist_generate_key() they seem to be misplaced and just
draining a bit of
entropy from the key generation process (effectively reducing key size
from 256 bits
of entropy to 251).


Now, what I was actually tring to do was establish why ECDHE key
generation is 3x
slower than EdDSA key generation (both on Ed25519).  We use the
following code:


// Slow 'ECDHE' version:
  if (0 != (rc = gcry_sexp_build (&s_keyparam, NULL,
                                  "(genkey(ecc(curve Ed25519)"
                                  "(flags)))")))
  {
    LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_sexp_build", rc);
    return NULL;
  }
  if (0 != (rc = gcry_pk_genkey (&priv_sexp, s_keyparam)))
  {
    LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_pk_genkey", rc);
    gcry_sexp_release (s_keyparam);
    return NULL;
  }


// Fast 'EdDSA' version:
  if (0 != (rc = gcry_sexp_build (&s_keyparam, NULL,
                                  "(genkey(ecc(curve Ed25519)"
                                  "(flags eddsa)))")))
  {
    LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_sexp_build", rc);
    return NULL;
  }
  if (0 != (rc = gcry_pk_genkey (&priv_sexp, s_keyparam)))
  {
    LOG_GCRY (GNUNET_ERROR_TYPE_ERROR, "gcry_pk_genkey", rc);
    gcry_sexp_release (s_keyparam);
    return NULL;
  }

The benchmarking results are rather dramatic:
On 05/19/2015 01:22 PM, Bart Polot wrote:
> Still happens in svn head:
>
> [bart at voyager ~/g/src/util] (master *% u+1)$ ./perf_crypto_asymmetric
>                   Init:     54 µs
>  EdDSA      create key:   3502 µs <---
>  EdDSA      get pubilc:   3395 µs
>  EdDSA   sign HashCode:   7924 µs
>  EdDSA verify HashCode:   6731 µs
>   ECDH      create key:  11054 µs <---
>   ECDH      get public:   2353 µs
>   ECDH           do DH:   2684 µs
> [bart at voyager ~/g/src/util] (master *% u+1)$ pacman -Q libgcrypt
> libgcrypt 1.6.3-2
> [bart at voyager ~/g/src/util] (master *% u+1)$
>
>

Why is this? In ecc.c:158, we see that

 if (E->dialect == ECC_DIALECT_ED25519)
    point_set (&sk->Q, &Q);
  else
    {
    // ... lots of code
    }

the key generation logic diverges here.  The reason is that for NIST
curves (and other non-Curve25519)
some logic is needed to ensure that the Q has the right sign.  So I
understand why this code is there,
but why is it needed on Curve25519? AFAIK for ECDHE on Curve25519 we
still don't need this.

If I set the 'eddsa' flag when generating the ECDHE key, everything
still works fine (done so in GNUnet
SVN 35742), so that's an easy workaround. Still, feels 'wrong' to use
such a hack.

Happy hacking!

Christian


-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20150519/19919ab9/attachment.sig>