Add Ed25519 key type and tests

This work was sponsored by Ribose Inc

4 files changed, 380 insertions, 24 deletions

diff --git a/src/lib/pubkey/ed25519/ed25519.cpp b/src/lib/pubkey/ed25519/ed25519.cpp
index 334badfa8..13f75ac3b 100644
--- a/src/lib/pubkey/ed25519/ed25519.cpp
+++ b/src/lib/pubkey/ed25519/ed25519.cpp
@@ -14,7 +14,7 @@
 
 namespace Botan {
 
-int ed25519_gen_keypair(uint8_t* pk, uint8_t* sk, const uint8_t seed[32])
+void ed25519_gen_keypair(uint8_t* pk, uint8_t* sk, const uint8_t seed[32])
    {
    uint8_t az[64];
 
@@ -30,12 +30,11 @@ int ed25519_gen_keypair(uint8_t* pk, uint8_t* sk, const uint8_t seed[32])
    // todo copy_mem
    memmove(sk, seed, 32);
    memmove(sk + 32, pk, 32);
-   return 0;
    }
 
-int ed25519_sign(uint8_t sig[64],
-                 const uint8_t* m, size_t mlen,
-                 const uint8_t* sk)
+void ed25519_sign(uint8_t sig[64],
+                  const uint8_t* m, size_t mlen,
+                  const uint8_t* sk)
    {
    uint8_t az[64];
    uint8_t nonce[64];
@@ -63,13 +62,11 @@ int ed25519_sign(uint8_t sig[64],
 
    sc_reduce(hram);
    sc_muladd(sig + 32, hram, az, nonce);
-
-   return 0;
    }
 
-int ed25519_verify(const uint8_t* m, size_t mlen,
-                   const uint8_t sig[64],
-                   const uint8_t* pk)
+bool ed25519_verify(const uint8_t* m, size_t mlen,
+                    const uint8_t sig[64],
+                    const uint8_t* pk)
    {
    uint8_t h[64];
    uint8_t rcheck[32];
@@ -78,11 +75,11 @@ int ed25519_verify(const uint8_t* m, size_t mlen,
 
    if(sig[63] & 224)
       {
-      return -1;
+      return false;
       }
    if(ge_frombytes_negate_vartime(&A, pk) != 0)
       {
-      return -1;
+      return false;
       }
 
    sha.update(sig, 32);
@@ -93,8 +90,7 @@ int ed25519_verify(const uint8_t* m, size_t mlen,
 
    ge_double_scalarmult_vartime(rcheck, h, &A, sig + 32);
 
-   // TODO const time compare
-   return (memcmp(rcheck, sig, 32) == 0);
+   return same_mem(rcheck, sig, 32);
    }
 
 }
diff --git a/src/lib/pubkey/ed25519/ed25519.h b/src/lib/pubkey/ed25519/ed25519.h
index 86740b4f4..f098517a0 100644
--- a/src/lib/pubkey/ed25519/ed25519.h
+++ b/src/lib/pubkey/ed25519/ed25519.h
@@ -11,21 +11,107 @@
 #ifndef BOTAN_ED25519_H__
 #define BOTAN_ED25519_H__
 
-#include <botan/types.h>
+#include <botan/pk_keys.h>
 
 namespace Botan {
 
-int ed25519_gen_keypair(uint8_t pk[32], uint8_t sk[64], const uint8_t seed[32]);
+class BOTAN_DLL Ed25519_PublicKey : public virtual Public_Key
+   {
+   public:
+      std::string algo_name() const override { return "Ed25519"; }
 
-int ed25519_sign(uint8_t sig[64],
-                 const uint8_t msg[],
-                 size_t msg_len,
-                 const uint8_t sk[64]);
+      size_t estimated_strength() const override { return 128; }
 
-int ed25519_verify(const uint8_t msg[],
-                   size_t msg_len,
-                   const uint8_t sig[64],
-                   const uint8_t pk[32]);
+      size_t key_length() const override { return 255; }
+
+      bool check_key(RandomNumberGenerator& rng, bool strong) const override;
+
+      AlgorithmIdentifier algorithm_identifier() const override;
+
+      std::vector<uint8_t> public_key_bits() const override;
+
+      /**
+      * Create a Ed25519 Public Key.
+      * @param alg_id the X.509 algorithm identifier
+      * @param key_bits DER encoded public key bits
+      */
+      Ed25519_PublicKey(const AlgorithmIdentifier& alg_id,
+                        const std::vector<uint8_t>& key_bits);
+
+      /**
+      * Create a Ed25519 Public Key.
+      * @param pub 32-byte raw public key
+      */
+      explicit Ed25519_PublicKey(const std::vector<uint8_t>& pub) : m_public(pub) {}
+
+      /**
+      * Create a Ed25519 Public Key.
+      * @param pub 32-byte raw public key
+      */
+      explicit Ed25519_PublicKey(const secure_vector<uint8_t>& pub) :
+         m_public(pub.begin(), pub.end()) {}
+
+      std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string& params,
+                                const std::string& provider) const override;
+
+      const std::vector<uint8_t>& get_public_key() const { return m_public; }
+
+   protected:
+      Ed25519_PublicKey() = default;
+      std::vector<uint8_t> m_public;
+   };
+
+class BOTAN_DLL Ed25519_PrivateKey : public Ed25519_PublicKey,
+                                     public virtual Private_Key
+   {
+   public:
+      /**
+      * Construct a private key from the specified parameters.
+      * @param alg_id the X.509 algorithm identifier
+      * @param key_bits PKCS #8 structure
+      */
+      Ed25519_PrivateKey(const AlgorithmIdentifier& alg_id,
+                         const secure_vector<uint8_t>& key_bits);
+
+      /**
+      * Generate a private key.
+      * @param rng the RNG to use
+      */
+      explicit Ed25519_PrivateKey(RandomNumberGenerator& rng);
+
+      /**
+      * Construct a private key from the specified parameters.
+      * @param secret_key DER encoded private key bits
+      */
+      explicit Ed25519_PrivateKey(const secure_vector<uint8_t>& secret_key);
+
+      const secure_vector<uint8_t>& get_private_key() const { return m_private; }
+
+      secure_vector<uint8_t> private_key_bits() const override;
+
+      bool check_key(RandomNumberGenerator& rng, bool strong) const override;
+
+      std::unique_ptr<PK_Ops::Signature>
+         create_signature_op(RandomNumberGenerator& rng,
+                             const std::string& params,
+                             const std::string& provider) const override;
+
+   private:
+      secure_vector<uint8_t> m_private;
+   };
+
+void ed25519_gen_keypair(uint8_t pk[32], uint8_t sk[64], const uint8_t seed[32]);
+
+void ed25519_sign(uint8_t sig[64],
+                  const uint8_t msg[],
+                  size_t msg_len,
+                  const uint8_t sk[64]);
+
+bool ed25519_verify(const uint8_t msg[],
+                    size_t msg_len,
+                    const uint8_t sig[64],
+                    const uint8_t pk[32]);
 
 }
 
diff --git a/src/lib/pubkey/ed25519/ed25519_key.cpp b/src/lib/pubkey/ed25519/ed25519_key.cpp
new file mode 100644
index 000000000..5a7ca5f13
--- /dev/null
+++ b/src/lib/pubkey/ed25519/ed25519_key.cpp
@@ -0,0 +1,253 @@
+/*
+* Ed25519
+* (C) 2017 Ribose Inc
+*
+* Based on the public domain code from SUPERCOP ref10 by
+* Peter Schwabe, Daniel J. Bernstein, Niels Duif, Tanja Lange, Bo-Yin Yang
+*
+* Botan is released under the Simplified BSD License (see license.txt)
+*/
+
+#include <botan/ed25519.h>
+#include <botan/internal/pk_ops_impl.h>
+#include <botan/hash.h>
+#include <botan/ber_dec.h>
+#include <botan/der_enc.h>
+
+namespace Botan {
+
+AlgorithmIdentifier Ed25519_PublicKey::algorithm_identifier() const
+   {
+   return AlgorithmIdentifier(get_oid(), AlgorithmIdentifier::USE_NULL_PARAM);
+   }
+
+bool Ed25519_PublicKey::check_key(RandomNumberGenerator&, bool) const
+   {
+   return true; // no tests possible?
+   // TODO could check cofactor
+   }
+
+Ed25519_PublicKey::Ed25519_PublicKey(const AlgorithmIdentifier&,
+                                           const std::vector<uint8_t>& key_bits)
+   {
+   BER_Decoder(key_bits)
+      .start_cons(SEQUENCE)
+      .decode(m_public, OCTET_STRING)
+   .end_cons();
+
+   if(m_public.size() != 32)
+      throw Decoding_Error("Invalid size for Ed25519 public key");
+   }
+
+std::vector<uint8_t> Ed25519_PublicKey::public_key_bits() const
+   {
+   return DER_Encoder()
+      .start_cons(SEQUENCE)
+        .encode(m_public, OCTET_STRING)
+      .end_cons()
+      .get_contents_unlocked();
+   }
+
+Ed25519_PrivateKey::Ed25519_PrivateKey(const secure_vector<uint8_t>& secret_key)
+   {
+   if(secret_key.size() == 64)
+      {
+      m_private = secret_key;
+      m_public.assign(&m_private[32], &m_private[64]);
+      }
+   else if(secret_key.size() == 32)
+      {
+      m_public.resize(32);
+      m_private.resize(64);
+      ed25519_gen_keypair(m_public.data(), m_private.data(), secret_key.data());
+      }
+   else
+      throw Decoding_Error("Invalid size for Ed25519 private key");
+   }
+
+Ed25519_PrivateKey::Ed25519_PrivateKey(RandomNumberGenerator& rng)
+   {
+   const secure_vector<uint8_t> seed = rng.random_vec(32);
+   m_public.resize(32);
+   m_private.resize(64);
+   ed25519_gen_keypair(m_public.data(), m_private.data(), seed.data());
+   }
+
+Ed25519_PrivateKey::Ed25519_PrivateKey(const AlgorithmIdentifier&,
+                                       const secure_vector<uint8_t>& key_bits)
+   {
+   BER_Decoder(key_bits)
+      .start_cons(SEQUENCE)
+      .decode(m_private, OCTET_STRING)
+   .end_cons();
+
+   if(m_private.size() != 64)
+      throw Decoding_Error("Invalid size for Ed25519 private key");
+   m_public.assign(&m_private[32], &m_private[64]);
+   }
+
+secure_vector<uint8_t> Ed25519_PrivateKey::private_key_bits() const
+   {
+   return DER_Encoder()
+      .start_cons(SEQUENCE)
+        .encode(m_private, OCTET_STRING)
+      .end_cons()
+      .get_contents();
+   }
+
+bool Ed25519_PrivateKey::check_key(RandomNumberGenerator&, bool) const
+   {
+   return true; // ???
+   }
+
+namespace {
+
+/**
+* Ed25519 verifying operation
+*/
+class Ed25519_Pure_Verify_Operation : public PK_Ops::Verification
+   {
+   public:
+      Ed25519_Pure_Verify_Operation(const Ed25519_PublicKey& key) : m_key(key)
+         {
+         }
+
+      void update(const uint8_t msg[], size_t msg_len) override
+         {
+         m_msg.insert(m_msg.end(), msg, msg + msg_len);
+         }
+
+      bool is_valid_signature(const uint8_t sig[], size_t sig_len)
+         {
+         if(sig_len != 64)
+            return false;
+         const bool ok = ed25519_verify(m_msg.data(), m_msg.size(), sig, m_key.get_public_key().data());
+         m_msg.clear();
+         return ok;
+         }
+
+   private:
+      std::vector<uint8_t> m_msg;
+      const Ed25519_PublicKey& m_key;
+   };
+
+/**
+* Ed25519 verifying operation with pre-hash
+*/
+class Ed25519_Hashed_Verify_Operation : public PK_Ops::Verification
+   {
+   public:
+      Ed25519_Hashed_Verify_Operation(const Ed25519_PublicKey& key, const std::string& hash) : m_key(key)
+         {
+         m_hash = HashFunction::create_or_throw(hash);
+         }
+
+      void update(const uint8_t msg[], size_t msg_len) override
+         {
+         m_hash->update(msg, msg_len);
+         }
+
+      bool is_valid_signature(const uint8_t sig[], size_t sig_len)
+         {
+         if(sig_len != 64)
+            return false;
+         std::vector<uint8_t> msg_hash(m_hash->output_length());
+         m_hash->final(msg_hash.data());
+         return ed25519_verify(msg_hash.data(), msg_hash.size(), sig, m_key.get_public_key().data());
+         }
+
+   private:
+      std::unique_ptr<HashFunction> m_hash;
+      const Ed25519_PublicKey& m_key;
+   };
+
+/**
+* Ed25519 signing operation ('pure' - signs message directly)
+*/
+class Ed25519_Pure_Sign_Operation : public PK_Ops::Signature
+   {
+   public:
+      Ed25519_Pure_Sign_Operation(const Ed25519_PrivateKey& key) : m_key(key)
+         {
+         }
+
+      void update(const uint8_t msg[], size_t msg_len) override
+         {
+         m_msg.insert(m_msg.end(), msg, msg + msg_len);
+         }
+
+      secure_vector<uint8_t> sign(RandomNumberGenerator&) override
+         {
+         secure_vector<uint8_t> sig(64);
+         ed25519_sign(sig.data(), m_msg.data(), m_msg.size(), m_key.get_private_key().data());
+         m_msg.clear();
+         return sig;
+         }
+
+   private:
+      std::vector<uint8_t> m_msg;
+      const Ed25519_PrivateKey& m_key;
+   };
+
+/**
+* Ed25519 signing operation with pre-hash
+*/
+class Ed25519_Hashed_Sign_Operation : public PK_Ops::Signature
+   {
+   public:
+      Ed25519_Hashed_Sign_Operation(const Ed25519_PrivateKey& key, const std::string& hash) : m_key(key)
+         {
+         m_hash = HashFunction::create_or_throw(hash);
+         }
+
+      void update(const uint8_t msg[], size_t msg_len) override
+         {
+         m_hash->update(msg, msg_len);
+         }
+
+      secure_vector<uint8_t> sign(RandomNumberGenerator&) override
+         {
+         secure_vector<uint8_t> sig(64);
+         std::vector<uint8_t> msg_hash(m_hash->output_length());
+         m_hash->final(msg_hash.data());
+         ed25519_sign(sig.data(), msg_hash.data(), msg_hash.size(), m_key.get_private_key().data());
+         return sig;
+         }
+
+   private:
+      std::unique_ptr<HashFunction> m_hash;
+      const Ed25519_PrivateKey& m_key;
+   };
+
+}
+
+std::unique_ptr<PK_Ops::Verification>
+Ed25519_PublicKey::create_verification_op(const std::string& params,
+                                          const std::string& provider) const
+   {
+   if(provider == "base" || provider.empty())
+      {
+      if(params == "" || params == "Identity" || params == "Pure")
+         return std::unique_ptr<PK_Ops::Verification>(new Ed25519_Pure_Verify_Operation(*this));
+      else
+         return std::unique_ptr<PK_Ops::Verification>(new Ed25519_Hashed_Verify_Operation(*this, params));
+      }
+   throw Provider_Not_Found(algo_name(), provider);
+   }
+
+std::unique_ptr<PK_Ops::Signature>
+Ed25519_PrivateKey::create_signature_op(RandomNumberGenerator&,
+                                        const std::string& params,
+                                        const std::string& provider) const
+   {
+   if(provider == "base" || provider.empty())
+      {
+      if(params == "" || params == "Identity" || params == "Pure")
+         return std::unique_ptr<PK_Ops::Signature>(new Ed25519_Pure_Sign_Operation(*this));
+      else
+         return std::unique_ptr<PK_Ops::Signature>(new Ed25519_Hashed_Sign_Operation(*this, params));
+      }
+   throw Provider_Not_Found(algo_name(), provider);
+   }
+
+}
diff --git a/src/lib/pubkey/pk_algs.cpp b/src/lib/pubkey/pk_algs.cpp
index 52e2e3be9..45e88f2a3 100644
--- a/src/lib/pubkey/pk_algs.cpp
+++ b/src/lib/pubkey/pk_algs.cpp
@@ -32,6 +32,10 @@
   #include <botan/eckcdsa.h>
 #endif
 
+#if defined(BOTAN_HAS_ED25519)
+  #include <botan/ed25519.h>
+#endif
+
 #if defined(BOTAN_HAS_GOST_34_10_2001)
   #include <botan/gost_3410.h>
 #endif
@@ -120,6 +124,11 @@ load_public_key(const AlgorithmIdentifier& alg_id,
       return std::unique_ptr<Public_Key>(new ECKCDSA_PublicKey(alg_id, key_bits));
 #endif
 
+#if defined(BOTAN_HAS_ED25519)
+   if(alg_name == "Ed25519")
+      return std::unique_ptr<Public_Key>(new Ed25519_PublicKey(alg_id, key_bits));
+#endif
+
 #if defined(BOTAN_HAS_GOST_34_10_2001)
    if(alg_name == "GOST-34.10")
       return std::unique_ptr<Public_Key>(new GOST_3410_PublicKey(alg_id, key_bits));
@@ -186,6 +195,11 @@ load_private_key(const AlgorithmIdentifier& alg_id,
       return std::unique_ptr<Private_Key>(new ECKCDSA_PrivateKey(alg_id, key_bits));
 #endif
 
+#if defined(BOTAN_HAS_ED25519)
+   if(alg_name == "Ed25519")
+      return std::unique_ptr<Private_Key>(new Ed25519_PrivateKey(alg_id, key_bits));
+#endif
+
 #if defined(BOTAN_HAS_GOST_34_10_2001)
    if(alg_name == "GOST-34.10")
       return std::unique_ptr<Private_Key>(new GOST_3410_PrivateKey(alg_id, key_bits));
@@ -262,6 +276,13 @@ create_private_key(const std::string& alg_name,
       }
 #endif
 
+#if defined(BOTAN_HAS_ED25519)
+   if(alg_name == "Ed25519")
+      {
+      return std::unique_ptr<Private_Key>(new Ed25519_PrivateKey(rng));
+      }
+#endif
+
    // ECC crypto
 #if defined(BOTAN_HAS_ECC_PUBLIC_KEY_CRYPTO)