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, 273 insertions, 0 deletions

diff --git a/src/lib/pubkey/xmss/xmss_publickey.h b/src/lib/pubkey/xmss/xmss_publickey.h
new file mode 100644
index 000000000..faa35d80a
--- /dev/null
+++ b/src/lib/pubkey/xmss/xmss_publickey.h
@@ -0,0 +1,273 @@
+/**
+ * XMSS Public Key
+ * (C) 2016 Matthias Gierlings
+ *
+ * Botan is released under the Simplified BSD License (see license.txt)
+ **/
+
+#ifndef BOTAN_XMSS_PUBLICKEY_H__
+#define BOTAN_XMSS_PUBLICKEY_H__
+
+#include <cstddef>
+#include <iterator>
+#include <limits>
+#include <memory>
+#include <string>
+#include <botan/alg_id.h>
+#include <botan/asn1_oid.h>
+#include <botan/der_enc.h>
+#include <botan/assert.h>
+#include <botan/exceptn.h>
+#include <botan/rng.h>
+#include <botan/types.h>
+#include <botan/pk_keys.h>
+#include <botan/xmss_parameters.h>
+#include <botan/xmss_wots_parameters.h>
+#include <botan/internal/pk_ops.h>
+
+namespace Botan {
+
+class XMSS_Verification_Operation;
+
+/**
+ * An XMSS: Extended Hash-Based Signature public key.
+ * The XMSS public key does not support the X509 standard. Instead the
+ * raw format described in [1] is used.
+ *
+ *   [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
+ **/
+class BOTAN_DLL XMSS_PublicKey : public virtual Public_Key
+   {
+   public:
+      /**
+       * Creates a new XMSS public key for the chosen XMSS signature method.
+       * New public and prf seeds are generated using rng. The appropriate WOTS
+       * signature method will be automatically set based on the chosen XMSS
+       * signature method.
+       *
+       * @param xmss_oid Identifier for the selected XMSS signature method.
+       * @param rng A random number generator to use for key generation.
+       **/
+      XMSS_PublicKey(XMSS_Parameters::xmss_algorithm_t xmss_oid,
+                     RandomNumberGenerator& rng)
+         : m_xmss_params(xmss_oid), m_wots_params(m_xmss_params.ots_oid()),
+           m_root(m_xmss_params.element_size()),
+           m_public_seed(rng.random_vec(m_xmss_params.element_size())) {}
+
+      /**
+       * Creates an XMSS public key from a byte sequence produced by
+       * raw_private_key().
+       **/
+      XMSS_PublicKey(const secure_vector<byte>& raw_key);
+
+      /**
+       * Creates a new XMSS public key for a chosen XMSS signature method as
+       * well as pre-computed root node and public_seed values.
+       *
+       * @param xmss_oid Identifier for the selected XMSS signature method.
+       * @param root Root node value.
+       * @param public_seed Public seed value.
+       **/
+      XMSS_PublicKey(XMSS_Parameters::xmss_algorithm_t xmss_oid,
+                     const secure_vector<byte>& root,
+                     const secure_vector<byte>& public_seed)
+         : m_xmss_params(xmss_oid), m_wots_params(m_xmss_params.ots_oid()),
+           m_root(root), m_public_seed(public_seed) {}
+
+      /**
+       * Creates a new XMSS public key for a chosen XMSS signature method as
+       * well as pre-computed root node and public_seed values.
+       *
+       * @param xmss_oid Identifier for the selected XMSS signature method.
+       * @param root Root node value.
+       * @param public_seed Public seed value.
+       **/
+      XMSS_PublicKey(XMSS_Parameters::xmss_algorithm_t xmss_oid,
+                     secure_vector<byte>&& root,
+                     secure_vector<byte>&& public_seed)
+         : m_xmss_params(xmss_oid), m_wots_params(m_xmss_params.ots_oid()),
+           m_root(std::move(root)), m_public_seed(std::move(public_seed)) {}
+
+      /**
+       * Retrieves the chosen XMSS signature method.
+       *
+       * @return XMSS signature method identifier.
+       **/
+      XMSS_Parameters::xmss_algorithm_t xmss_oid() const
+         {
+         return m_xmss_params.oid();
+         }
+
+      /**
+       * Sets the chosen XMSS signature method
+       *
+       * @return XMSS signature method identifier.
+       **/
+      void set_xmss_oid(XMSS_Parameters::xmss_algorithm_t xmss_oid)
+         {
+         m_xmss_params = XMSS_Parameters(xmss_oid);
+         m_wots_params = XMSS_WOTS_Parameters(m_xmss_params.ots_oid());
+         }
+
+      /**
+       * Retrieves the XMSS parameters determined by the chosen XMSS Signature
+       * method.
+       *
+       * @return XMSS parameters.
+       **/
+      const XMSS_Parameters& xmss_parameters() const
+         {
+         return m_xmss_params;
+         }
+
+      /**
+       * Retrieves the Winternitz One Time Signature (WOTS) method,
+       * corrseponding to the chosen XMSS signature method.
+       *
+       * @return XMSS WOTS signature method identifier.
+       **/
+      XMSS_WOTS_Parameters::ots_algorithm_t wots_oid() const
+         {
+         return m_wots_params.oid();
+         }
+
+      /**
+       * Retrieves the Winternitz One Time Signature (WOTS) parameters
+       * corrseponding to the chosen XMSS signature method.
+       *
+       * @return XMSS WOTS signature method parameters.
+       **/
+      const XMSS_WOTS_Parameters& wots_parameters() const
+         {
+         return m_wots_params;
+         }
+
+      secure_vector<byte>& root()
+         {
+         return m_root;
+         }
+
+      void set_root(const secure_vector<byte>& root)
+         {
+         m_root = root;
+         }
+
+      void set_root(secure_vector<byte>&& root)
+         {
+         m_root = std::move(root);
+         }
+
+      const secure_vector<byte>& root() const
+         {
+         return m_root;
+         }
+
+      virtual secure_vector<byte>& public_seed()
+         {
+         return m_public_seed;
+         }
+
+      virtual void set_public_seed(const secure_vector<byte>& public_seed)
+         {
+         m_public_seed = public_seed;
+         }
+
+      virtual void set_public_seed(secure_vector<byte>&& public_seed)
+         {
+         m_public_seed = std::move(public_seed);
+         }
+
+      virtual const secure_vector<byte>& public_seed() const
+         {
+         return m_public_seed;
+         }
+
+      std::string algo_name() const override
+         {
+         return "XMSS";
+         }
+
+      virtual AlgorithmIdentifier algorithm_identifier() const override
+         {
+         return AlgorithmIdentifier(get_oid(), AlgorithmIdentifier::USE_NULL_PARAM);
+         }
+
+      virtual bool check_key(RandomNumberGenerator&, bool) const override
+         {
+         BOTAN_ASSERT(false, "No key strength check implemented for XMSS.");
+         }
+
+      virtual std::unique_ptr<PK_Ops::Verification>
+         create_verification_op(const std::string&,
+                                const std::string& provider) const override;
+
+      virtual size_t estimated_strength() const override
+         {
+         return m_xmss_params.estimated_strength();
+         }
+
+      virtual size_t max_input_bits() const override
+         {
+         return std::numeric_limits<size_t>::infinity();
+         }
+
+      virtual size_t message_part_size() const override
+         {
+         return std::numeric_limits<size_t>::infinity();
+         }
+
+      virtual size_t message_parts() const override
+         {
+         return std::numeric_limits<size_t>::infinity();
+         }
+
+      /**
+       * Currently x509 is not suppoerted for XMSS. x509_subject_public_key()
+       * returns a raw byte sequence as defined in [1]. This method acts as
+       * alias for raw_public_key().
+       *
+       * @return raw non x509 compliant public key.
+       **/
+      virtual std::vector<byte> x509_subject_public_key() const override
+         {
+         return raw_public_key();
+         }
+
+      /**
+       * Size in bytes of the serialized XMSS public key produced by
+       * raw_public_key().
+       *
+       * @return size in bytes of serialized Public Key.
+       **/
+      virtual size_t size() const
+         {
+         return sizeof(uint32_t) + 2 * m_xmss_params.element_size();
+         }
+
+      /**
+       * Generates a non standartized byte sequence representing the XMSS
+       * public key, as defined in [1] (p. 23, "XMSS Public Key")
+       *
+       * @return 4-byte OID, followed by n-byte root node, followed by
+       *         public seed.
+       **/
+      virtual std::vector<byte> raw_public_key() const;
+
+   protected:
+      XMSS_Parameters m_xmss_params;
+      XMSS_WOTS_Parameters m_wots_params;
+      secure_vector<byte> m_root;
+      secure_vector<byte> m_public_seed;
+
+   private:
+      XMSS_Parameters::xmss_algorithm_t deserialize_xmss_oid(
+         const secure_vector<byte>& raw_key);
+   };
+
+}
+
+#endif