Edx25519 implemented

Edx25519 is a variant of EdDSA on curve25519 which allows for repeated
derivation of private and public keys, independently.  The private keys
in Edx25519 initially correspond to the data after expansion and
clamping in EdDSA.  However, this correspondence is lost after deriving
further keys from existing ones.  The public keys and signature
verification are compatible with EdDSA.

The ability to repeatedly derive key material is used for example in the
context of age restriction in GNU Taler.

The scheme that has been implemented is as follows:

/* Private keys in Edx25519 are pairs (a, b) of 32 byte each.
 * Initially they correspond to the result of the expansion
 * and clamping in EdDSA.
 */

Edx25519_generate_private(seed) {
  /* EdDSA expand and clamp */
  dh := SHA-512(seed)
  a := dh[0..31]
  b := dh[32..64]
  a[0]  &= 0b11111000
  a[31] &= 0b01111111
  a[31] |= 0b01000000

  return (a, b)
}

Edx25519_public_from_private(private) {
  /* Public keys are the same as in EdDSA */
  (a, _) := private
  return [a] * G
}

Edx25519_blinding_factor(P, seed) {
  /* This is a helper function used in the derivation of
   * private/public keys from existing ones.  */
  h1 := HKDF_32(P, seed)

  /* Ensure that h == h % L */
  h := h1 % L

  /* Optionally: Make sure that we don't create weak keys. */
  P' := [h] * P
  if !( (h!=1) && (h!=0) && (P'!=E) ) {
    return Edx25519_blinding_factor(P, seed+1)
  }

  return h
}

Edx25519_derive_private(private, seed) {
  /* This is based on the definition in
   * GNUNET_CRYPTO_eddsa_private_key_derive.  But it accepts
   * and returns a private pair (a, b) and allows for iteration.
   */
  (a, b) := private
  P := Edx25519_public_key_from_private(private)
  h := Edx25519_blinding_factor(P, seed)

  /* Carefully calculate the new value for a */
  a1 := a / 8;
  a2 := (h  * a1) % L
  a' := (a2 *  8) % L

  /* Update b as well, binding it to h.
     This is an additional step compared to GNS. */
  b' := SHA256(b ∥ h)

  return (a', b')
}

Edx25519_derive_public(P, seed) {
  h := Edx25519_blinding_factor(P, seed)
  return [h]*P
}

Edx25519_sign(private, message) {
  /* As in Ed25519, except for the origin of b */
  (d, b) := private
  P := Edx25519_public_from_private(private)
  r := SHA-512(b ∥ message)
  R := [r] * G
  s := r + SHA-512(R ∥ P ∥ message) * d % L

  return (R,s)
}

Edx25519_verify(P, message, signature) {
  /* Identical to Ed25519 */
  (R, s) := signature
  return [s] * G == R + [SHA-512(R ∥ P ∥ message)] * P
}

1 files changed, 233 insertions, 2 deletions

diff --git a/src/include/gnunet_crypto_lib.h b/src/include/gnunet_crypto_lib.h
index 77abab45d..582a58861 100644
--- a/src/include/gnunet_crypto_lib.h
+++ b/src/include/gnunet_crypto_lib.h
@@ -287,6 +287,59 @@ struct GNUNET_CRYPTO_EddsaPrivateScalar
   unsigned char s[512 / 8];
 };
 
+/**
+ * Private ECC key material encoded for transmission.  To be used only for
+ * Edx25519 signatures.  An inital key corresponds to data from the key
+ * expansion and clamping in the EdDSA key generation.
+ */
+struct GNUNET_CRYPTO_Edx25519PrivateKey
+{
+  /**
+   * a is a value mod n, where n has at most 256 bits.  It is the first half of
+   * the seed-expansion of EdDSA and will be clamped.
+   */
+  unsigned char a[256 / 8];
+
+  /**
+   * b consists of 32 bytes which where originally the lower 32bytes of the key
+   * expansion.  Subsequent calls to derive_private will change this value, too.
+   */
+  unsigned char b[256 / 8];
+};
+
+
+/**
+ * Public ECC key (always for curve Ed25519) encoded in a format suitable for
+ * network transmission and Edx25519 (same as EdDSA) signatures.  Refer to
+ * section 5.1.3 of rfc8032, for a thorough explanation of how this value maps
+ * to the x- and y-coordinates.
+ */
+struct GNUNET_CRYPTO_Edx25519PublicKey
+{
+  /**
+   * Point Q consists of a y-value mod p (256 bits); the x-value is
+   * always positive. The point is stored in Ed25519 standard
+   * compact format.
+   */
+  unsigned char q_y[256 / 8];
+};
+
+/**
+ * @brief an ECC signature using Edx25519 (same as in EdDSA).
+ */
+struct GNUNET_CRYPTO_Edx25519Signature
+{
+  /**
+   * R value.
+   */
+  unsigned char r[256 / 8];
+
+  /**
+   * S value.
+   */
+  unsigned char s[256 / 8];
+};
+
 
 /**
  * @brief type for session keys
@@ -1279,6 +1332,17 @@ GNUNET_CRYPTO_eddsa_key_get_public (
   const struct GNUNET_CRYPTO_EddsaPrivateKey *priv,
   struct GNUNET_CRYPTO_EddsaPublicKey *pub);
 
+/**
+ * @ingroup crypto
+ * Extract the public key for the given private key.
+ *
+ * @param priv the private key
+ * @param pub where to write the public key
+ */
+void
+GNUNET_CRYPTO_edx25519_key_get_public (
+  const struct GNUNET_CRYPTO_Edx25519PrivateKey *priv,
+  struct GNUNET_CRYPTO_Edx25519PublicKey *pub);
 
 /**
  * @ingroup crypto
@@ -1465,6 +1529,30 @@ GNUNET_CRYPTO_eddsa_key_create (struct GNUNET_CRYPTO_EddsaPrivateKey *pk);
 
 /**
  * @ingroup crypto
+ * Create a new private key.
+ *
+ * @param[out] pk private key to initialize
+ */
+void
+GNUNET_CRYPTO_edx25519_key_create (struct GNUNET_CRYPTO_Edx25519PrivateKey *pk);
+
+/**
+ * @ingroup crypto
+ * Create a new private key for Edx25519 from a given seed.  After expanding
+ * the seed, the first half of the key will be clamped according to EdDSA.
+ *
+ * @param seed seed input
+ * @param seedsize size of the seed in bytes
+ * @param[out] pk private key to initialize
+ */
+void
+GNUNET_CRYPTO_edx25519_key_create_from_seed (
+  const void *seed,
+  size_t seedsize,
+  struct GNUNET_CRYPTO_Edx25519PrivateKey *pk);
+
+/**
+ * @ingroup crypto
  * Create a new private key.  Clear with #GNUNET_CRYPTO_ecdhe_key_clear().
  *
  * @param[out] pk set to fresh private key;
@@ -1492,6 +1580,14 @@ GNUNET_CRYPTO_eddsa_key_clear (struct GNUNET_CRYPTO_EddsaPrivateKey *pk);
 void
 GNUNET_CRYPTO_ecdsa_key_clear (struct GNUNET_CRYPTO_EcdsaPrivateKey *pk);
 
+/**
+ * @ingroup crypto
+ * Clear memory that was used to store a private key.
+ *
+ * @param pk location of the key
+ */
+void
+GNUNET_CRYPTO_edx25519_key_clear (struct GNUNET_CRYPTO_Edx25519PrivateKey *pk);
 
 /**
  * @ingroup crypto
@@ -1874,6 +1970,53 @@ GNUNET_CRYPTO_ecdsa_sign_ (
                                               sig));               \
 } while (0)
 
+/**
+ * @ingroup crypto
+ * @brief Edx25519 sign a given block.
+ *
+ * The @a purpose data is the beginning of the data of which the signature is
+ * to be created. The `size` field in @a purpose must correctly indicate the
+ * number of bytes of the data structure, including its header.  If possible,
+ * use #GNUNET_CRYPTO_edx25519_sign() instead of this function (only if @a
+ * validate is not fixed-size, you must use this function directly).
+ *
+ * @param priv private key to use for the signing
+ * @param purpose what to sign (size, purpose)
+ * @param[out] sig where to write the signature
+ * @return #GNUNET_SYSERR on error, #GNUNET_OK on success
+ */
+enum GNUNET_GenericReturnValue
+GNUNET_CRYPTO_edx25519_sign_ (
+  const struct GNUNET_CRYPTO_Edx25519PrivateKey *priv,
+  const struct GNUNET_CRYPTO_EccSignaturePurpose *purpose,
+  struct GNUNET_CRYPTO_Edx25519Signature *sig);
+
+
+/**
+ * @ingroup crypto
+ * @brief Edx25519 sign a given block.  The resulting signature is compatible
+ * with EdDSA.
+ *
+ * The @a ps data must be a fixed-size struct for which the signature is to be
+ * created. The `size` field in @a ps->purpose must correctly indicate the
+ * number of bytes of the data structure, including its header.
+ *
+ * @param priv private key to use for the signing
+ * @param ps packed struct with what to sign, MUST begin with a purpose
+ * @param[out] sig where to write the signature
+ */
+#define GNUNET_CRYPTO_edx25519_sign(priv,ps,sig) do {              \
+    /* check size is set correctly */                              \
+    GNUNET_assert (ntohl ((ps)->purpose.size) == sizeof (*(ps)));  \
+    /* check 'ps' begins with the purpose */                       \
+    GNUNET_static_assert (((void*) (ps)) ==                        \
+                          ((void*) &(ps)->purpose));               \
+    GNUNET_assert (GNUNET_OK ==                                    \
+                   GNUNET_CRYPTO_edx25519_sign_ (priv,             \
+                                                 &(ps)->purpose,   \
+                                                 sig));            \
+} while (0)
+
 
 /**
  * @ingroup crypto
@@ -1917,7 +2060,7 @@ GNUNET_CRYPTO_eddsa_verify_ (
  */
 #define GNUNET_CRYPTO_eddsa_verify(purp,ps,sig,pub) ({             \
     /* check size is set correctly */                              \
-    GNUNET_assert (ntohl ((ps)->purpose.size) == sizeof (*(ps))); \
+    GNUNET_assert (ntohl ((ps)->purpose.size) == sizeof (*(ps)));  \
     /* check 'ps' begins with the purpose */                       \
     GNUNET_static_assert (((void*) (ps)) ==                        \
                           ((void*) &(ps)->purpose));               \
@@ -1927,7 +2070,6 @@ GNUNET_CRYPTO_eddsa_verify_ (
                                  pub);                             \
   })
 
-
 /**
  * @ingroup crypto
  * @brief Verify ECDSA signature.
@@ -1982,6 +2124,58 @@ GNUNET_CRYPTO_ecdsa_verify_ (
 
 /**
  * @ingroup crypto
+ * @brief Verify Edx25519 signature.
+ *
+ * The @a validate data is the beginning of the data of which the signature
+ * is to be verified. The `size` field in @a validate must correctly indicate
+ * the number of bytes of the data structure, including its header.  If @a
+ * purpose does not match the purpose given in @a validate (the latter must be
+ * in big endian), signature verification fails.  If possible, use
+ * #GNUNET_CRYPTO_edx25519_verify() instead of this function (only if @a
+ * validate is not fixed-size, you must use this function directly).
+ *
+ * @param purpose what is the purpose that the signature should have?
+ * @param validate block to validate (size, purpose, data)
+ * @param sig signature that is being validated
+ * @param pub public key of the signer
+ * @returns #GNUNET_OK if ok, #GNUNET_SYSERR if invalid
+ */
+enum GNUNET_GenericReturnValue
+GNUNET_CRYPTO_edx25519_verify_ (
+  uint32_t purpose,
+  const struct GNUNET_CRYPTO_EccSignaturePurpose *validate,
+  const struct GNUNET_CRYPTO_Edx25519Signature *sig,
+  const struct GNUNET_CRYPTO_Edx25519PublicKey *pub);
+
+
+/**
+ * @ingroup crypto
+ * @brief Verify Edx25519 signature.
+ *
+ * The @a ps data must be a fixed-size struct for which the signature is to be
+ * created. The `size` field in @a ps->purpose must correctly indicate the
+ * number of bytes of the data structure, including its header.
+ *
+ * @param purp purpose of the signature, must match 'ps->purpose.purpose'
+ *              (except in host byte order)
+ * @param priv private key to use for the signing
+ * @param ps packed struct with what to sign, MUST begin with a purpose
+ * @param sig where to write the signature
+ */
+#define GNUNET_CRYPTO_edx25519_verify(purp,ps,sig,pub) ({         \
+    /* check size is set correctly */                             \
+    GNUNET_assert (ntohl ((ps)->purpose.size) == sizeof (*(ps))); \
+    /* check 'ps' begins with the purpose */                      \
+    GNUNET_static_assert (((void*) (ps)) ==                       \
+                          ((void*) &(ps)->purpose));              \
+    GNUNET_CRYPTO_edx25519_verify_ (purp,                         \
+                                    &(ps)->purpose,               \
+                                    sig,                          \
+                                    pub);                         \
+  })
+
+/**
+ * @ingroup crypto
  * Derive a private key from a given private key and a label.
  * Essentially calculates a private key 'h = H(l,P) * d mod n'
  * where n is the size of the ECC group and P is the public
@@ -2115,6 +2309,43 @@ GNUNET_CRYPTO_eddsa_key_get_public_from_scalar (
   const struct GNUNET_CRYPTO_EddsaPrivateScalar *s,
   struct GNUNET_CRYPTO_EddsaPublicKey *pkey);
 
+/**
+ * @ingroup crypto
+ * Derive a private scalar from a given private key and a label.
+ * Essentially calculates a private key 'h = H(l,P) * d mod n'
+ * where n is the size of the ECC group and P is the public
+ * key associated with the private key 'd'.
+ *
+ * @param priv original private key
+ * @param seed input seed
+ * @param seedsize size of the seed
+ * @param result derived private key
+ */
+void
+GNUNET_CRYPTO_edx25519_private_key_derive (
+  const struct GNUNET_CRYPTO_Edx25519PrivateKey *priv,
+  const void *seed,
+  size_t seedsize,
+  struct GNUNET_CRYPTO_Edx25519PrivateKey *result);
+
+
+/**
+ * @ingroup crypto
+ * Derive a public key from a given public key and a label.
+ * Essentially calculates a public key 'V = H(l,P) * P'.
+ *
+ * @param pub original public key
+ * @param seed input seed
+ * @param seedsize size of the seed
+ * @param result where to write the derived public key
+ */
+void
+GNUNET_CRYPTO_edx25519_public_key_derive (
+  const struct GNUNET_CRYPTO_Edx25519PublicKey *pub,
+  const void *seed,
+  size_t seedsize,
+  struct GNUNET_CRYPTO_Edx25519PublicKey *result);
+
 
 /**
  * Output the given MPI value to the given buffer in network