Added Extended Hash-Based Signatures (XMSS)

[1] XMSS: Extended Hash-Based Signatures,
    draft-itrf-cfrg-xmss-hash-based-signatures-06
    Release: July 2016.
    https://datatracker.ietf.org/doc/
    draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1

Provides XMSS_PublicKey and XMSS_PrivateKey classes as well as implementations
for the Botan interfaces PK_Ops::Signature and PK_Ops::Verification. XMSS has
been integrated into the Botan test bench, signature generation and verification
can be tested independently by invoking "botan-test xmss_sign" and
"botan-test xmss_verify"

- Some headers that are not required to be exposed to users of the library have
  to be declared as public in `info.txt`. Declaring those headers private will
  cause the amalgamation build to fail. The following headers have been
  declared public inside `info.txt`, even though they are only intended for
  internal use:
    * atomic.h
    * xmss_hash.h
    * xmss_index_registry.h
    * xmss_address.h
    * xmss_common_ops.h
    * xmss_tools.h
    * xmss_wots_parameters.h
    * xmss_wots_privatekey.h
    * xmss_wots_publickey.h

- XMSS_Verification_Operation Requires the "randomness" parameter out of the
  XMSS signature. "Randomness" is part of the prefix that is hashed *before*
  the message. Since the signature is unknown till sign() is called, all
  message content has to be buffered. For large messages this can be
  inconvenient or impossible.

  **Possible solution**: Change PK_Ops::Verification interface to take
  the signature as constructor argument, and provide a setter method to be able
  to update reuse the instance on multiple signatures. Make sign a parameterless
  member call. This solution requires interface changes in botan.

  **Suggested workaround** for signing large messages is to not sign the message
  itself, but to precompute the message hash manually using Botan::HashFunctio
  and sign the message hash instead of the message itself.

- Some of the available test vectors for the XMSS signature verification have
  been commented out in order to reduce testbench runtime.

1 files changed, 337 insertions, 0 deletions

diff --git a/src/lib/pubkey/xmss/xmss_wots_publickey.h b/src/lib/pubkey/xmss/xmss_wots_publickey.h
new file mode 100644
index 000000000..e024c486f
--- /dev/null
+++ b/src/lib/pubkey/xmss/xmss_wots_publickey.h
@@ -0,0 +1,337 @@
+/**
+ * XMSS WOTS Public Key
+ * (C) 2016 Matthias Gierlings
+ *
+ * Botan is released under the Simplified BSD License (see license.txt)
+ **/
+
+#ifndef BOTAN_XMSS_WOTS_PUBLICKEY_H__
+#define BOTAN_XMSS_WOTS_PUBLICKEY_H__
+
+#include <cstddef>
+#include <string>
+#include <vector>
+#include <botan/auto_rng.h>
+#include <botan/alg_id.h>
+#include <botan/asn1_oid.h>
+#include <botan/assert.h>
+#include <botan/pk_keys.h>
+#include <botan/types.h>
+#include <botan/xmss_wots_parameters.h>
+#include <botan/xmss_address.h>
+#include <botan/xmss_hash.h>
+
+namespace Botan {
+
+typedef std::vector<secure_vector<byte>> wots_keysig_t;
+
+/**
+ * A Winternitz One Time Signature public key for use with Extended Hash-Based
+ * Signatures.
+ **/
+class BOTAN_DLL XMSS_WOTS_PublicKey : virtual public Public_Key
+   {
+   public:
+      class TreeSignature
+         {
+         public:
+            TreeSignature()
+               : m_ots_sig(), m_auth_path() {}
+
+            TreeSignature(const wots_keysig_t& ots_sig,
+                          const wots_keysig_t& auth_path)
+               : m_ots_sig(ots_sig), m_auth_path(auth_path)
+               {}
+
+            TreeSignature(wots_keysig_t&& ots_sig,
+                          wots_keysig_t&& auth_path)
+               : m_ots_sig(std::move(ots_sig)),
+                 m_auth_path(std::move(auth_path))
+               {}
+
+            const wots_keysig_t& ots_signature() const
+               {
+               return m_ots_sig;
+               }
+
+            wots_keysig_t& ots_signature()
+               {
+               return m_ots_sig;
+               }
+
+            const wots_keysig_t& authentication_path() const
+               {
+               return m_auth_path;
+               }
+
+            wots_keysig_t& authentication_path()
+               {
+               return m_auth_path;
+               }
+
+         private:
+            wots_keysig_t m_ots_sig;
+            wots_keysig_t m_auth_path;
+         };
+
+      /**
+       * Creates a XMSS_WOTS_PublicKey for the signature method identified by
+       * oid. The public seed for this key will be initialized with a
+       * uniformly random n-byte value, where "n" is the element size of the
+       * selected signature method.
+       *
+       * @param oid Identifier for the selected signature method.
+       **/
+      XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid)
+         : m_wots_params(oid),
+           m_hash(m_wots_params.hash_function_name()) {}
+
+      /**
+       * Creates a XMSS_WOTS_PublicKey for the signature method identified by
+       * oid. The public seed for this key will be initialized with a
+       * uniformly random n-byte value, where "n" is the element size of the
+       * selected signature method.
+       *
+       * @param oid Identifier for the selected signature method.
+       * @param rng A random number generate used to generate the public seed.
+       **/
+      XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid,
+                          RandomNumberGenerator& rng)
+         : m_wots_params(oid),
+           m_hash(m_wots_params.hash_function_name()),
+           m_public_seed(rng.random_vec(m_wots_params.element_size())) {}
+
+      /**
+       * Creates a XMSS_WOTS_PrivateKey for the signature method identified by
+       * oid, with a precomputed public seed.
+       *
+       * @param oid Identifier for the selected signature method.
+       * @param public_seed A precomputed public seed of n-bytes length.
+       **/
+      XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid,
+                          secure_vector<byte> public_seed)
+         : m_wots_params(oid),
+           m_hash(m_wots_params.hash_function_name()),
+           m_public_seed(public_seed) {}
+
+      /**
+       * Creates a XMSS_WOTS_PublicKey for the signature method identified by
+       * oid. The public seed will be initialized with a precomputed seed and
+       * and precomputed key data which should be derived from a
+       * XMSS_WOTS_PrivateKey.
+       *
+       * @param oid Ident:s/ifier for the selected signature methods.
+       * @param public_seed A precomputed public seed of n-bytes length.
+       * @param key Precomputed raw key data of the XMSS_WOTS_PublicKey.
+       **/
+      XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid,
+                          secure_vector<byte>&& public_seed,
+                          wots_keysig_t&& key)
+         : m_wots_params(oid),
+           m_hash(m_wots_params.hash_function_name()),
+           m_key(std::move(key)),
+           m_public_seed(std::move(public_seed))
+         {}
+
+      /**
+       * Creates a XMSS_WOTS_PublicKey for the signature method identified by
+       * oid. The public seed will be initialized with a precomputed seed and
+       * and precomputed key data which should be derived from a
+       * XMSS_WOTS_PrivateKey.
+       *
+       * @param oid Identifier for the selected signature methods.
+       * @param public_seed A precomputed public seed of n-bytes length.
+       * @param key Precomputed raw key data of the XMSS_WOTS_PublicKey.
+       **/
+      XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid,
+                          const secure_vector<byte>& public_seed,
+                          const wots_keysig_t& key)
+         : m_wots_params(oid),
+           m_hash(m_wots_params.hash_function_name()),
+           m_key(key),
+           m_public_seed(public_seed)
+         {}
+
+      /**
+       * Creates a XMSS_WOTS_PublicKey form a message and signature using
+       * Algorithm 6 WOTS_pkFromSig defined in the XMSS standard. This
+       * overload is used to verify a message using a public key.
+       *
+       * @param oid WOTSP algorithm identifier.
+       * @param msg A message.
+       * @param sig A WOTS signature for msg.
+       * @param adrs An XMSS_Address.
+       * @param public_seed The public public_seed.
+       **/
+      XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid,
+                          const secure_vector<byte>& msg,
+                          const wots_keysig_t& sig,
+                          XMSS_Address& adrs,
+                          const secure_vector<byte>& public_seed)
+         : m_wots_params(oid),
+           m_hash(m_wots_params.hash_function_name()),
+           m_key(pub_key_from_signature(msg,
+                                        sig,
+                                        adrs,
+                                        public_seed)),
+           m_public_seed(public_seed)
+         {}
+
+      /**
+       * Retrieves the i-th element out of the length len chain of
+       * n-byte elements contained in the public key.
+       *
+       * @param i index of the element.
+       * @returns n-byte element addressed by i.
+       **/
+      const secure_vector<byte>& operator[](size_t i) const { return m_key[i]; }
+      secure_vector<byte>& operator[](size_t i) { return m_key[i]; }
+
+      /**
+       * Convert the key into the raw key data. The key becomes a length
+       * len vector of n-byte elements.
+       **/
+      operator const wots_keysig_t& () const { return m_key; };
+
+      /**
+       * Convert the key into the raw key data. The key becomes a length
+       * len vector of n-byte elements.
+       **/
+      operator wots_keysig_t& () { return m_key; }
+
+      const secure_vector<byte>& public_seed() const { return m_public_seed; }
+      secure_vector<byte>& public_seed() { return m_public_seed; }
+      void set_public_seed(const secure_vector<byte>& public_seed)
+         {
+         m_public_seed = public_seed;
+         }
+      void set_public_seed(secure_vector<byte>&& public_seed)
+         {
+         m_public_seed = std::move(public_seed);
+         }
+
+      const wots_keysig_t& key_data() const { return m_key; }
+      wots_keysig_t& key_data() { return m_key; }
+      void set_key_data(const wots_keysig_t& key_data)
+         {
+         m_key = key_data;
+         }
+      void set_key_data(wots_keysig_t&& key_data)
+         {
+         m_key = std::move(key_data);
+         }
+
+      const XMSS_WOTS_Parameters& wots_parameters() const
+         {
+         return m_wots_params;
+         }
+
+      virtual std::string algo_name() const override
+         {
+         return m_wots_params.name();
+         }
+
+      virtual AlgorithmIdentifier algorithm_identifier() const override
+         {
+         BOTAN_ASSERT(false, "No AlgorithmIdentifier available for XMSS-WOTS.");
+         }
+
+      virtual bool check_key(RandomNumberGenerator&, bool) const override
+         {
+         BOTAN_ASSERT(false, "No key strength check implemented for XMSS-WOTS.");
+         }
+
+      virtual std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string&,
+                                const std::string& provider) const override
+         {
+         BOTAN_ASSERT(false, "XMSS_WOTS_Verification_Operation not available.");
+         }
+
+      virtual size_t estimated_strength() const override
+         {
+         return m_wots_params.estimated_strength();
+         }
+
+      virtual size_t max_input_bits() const override
+         {
+         return message_part_size() * 8;
+         }
+
+      virtual size_t message_part_size() const override
+         {
+         return m_wots_params.element_size();
+         }
+
+      virtual size_t message_parts() const override
+         {
+         return 1;
+         }
+
+      virtual std::vector<byte> x509_subject_public_key() const override
+         {
+         BOTAN_ASSERT(false, "No x509 key format defined for XMSS-WOTS.");
+         }
+
+      bool operator==(const XMSS_WOTS_PublicKey& key)
+         {
+         return m_key == key.m_key;
+         }
+
+      bool operator!=(const XMSS_WOTS_PublicKey& key)
+         {
+         return !(*this == key);
+         }
+
+   protected:
+      /**
+       * Algorithm 2: Chaining Function.
+       *
+       * Takes an n-byte input string and transforms it into a the function
+       * result iterating the cryptographic hash function "F" steps times on
+       * the input x using the outputs of the PRNG "G".
+       *
+       *
+       * @param[out] x An n-byte input string, that will be transformed into
+       *               the chaining function result.
+       * @param start_idx The start index.
+       * @param steps A number of steps.
+       * @param adrs An OTS Hash Address.
+       * @param public_seed A public seed.
+       *
+       **/
+      void chain(secure_vector<byte>& x,
+                 size_t start_idx,
+                 size_t steps,
+                 XMSS_Address& adrs,
+                 const secure_vector<byte>& public_seed);
+
+      XMSS_WOTS_Parameters m_wots_params;
+      XMSS_Hash m_hash;
+
+      wots_keysig_t m_key;
+      secure_vector<byte> m_public_seed;
+
+   private:
+      /**
+       * Algorithm 6: "WOTS_pkFromSig"
+       * Computes a Winternitz One Time Signature+ public key from a message and
+       * its signature.
+       *
+       * @param msg A message.
+       * @param sig The signature for msg.
+       * @param adrs An address.
+       * @param public_seed A public_seed.
+       *
+       * @return Temporary WOTS+ public key.
+       **/
+      wots_keysig_t pub_key_from_signature(
+         const secure_vector<byte>& msg,
+         const wots_keysig_t& sig,
+         XMSS_Address& adrs,
+         const secure_vector<byte>& public_seed);
+   };
+
+}
+
+#endif