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

diff --git a/src/lib/pubkey/xmss/xmss_signature_operation.cpp b/src/lib/pubkey/xmss/xmss_signature_operation.cpp
new file mode 100644
index 000000000..d223ddef0
--- /dev/null
+++ b/src/lib/pubkey/xmss/xmss_signature_operation.cpp
@@ -0,0 +1,112 @@
+/**
+ * XMSS Signature Operation
+ * Signature generation operation for Extended Hash-Based Signatures (XMSS) as
+ * defined in:
+ *
+ * [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
+ *
+ * (C) 2016 Matthias Gierlings
+ *
+ * Botan is released under the Simplified BSD License (see license.txt)
+ **/
+
+#include <botan/internal/xmss_signature_operation.h>
+
+namespace Botan {
+
+XMSS_Signature_Operation::XMSS_Signature_Operation(
+   const XMSS_PrivateKey& private_key)
+   : XMSS_Common_Ops(private_key.xmss_oid()),
+     m_priv_key(private_key),
+     m_randomness(0),
+     m_leaf_idx(0),
+     m_is_initialized(false)
+   {}
+
+XMSS_WOTS_PublicKey::TreeSignature
+XMSS_Signature_Operation::generate_tree_signature(const secure_vector<byte>& msg,
+      XMSS_PrivateKey& xmss_priv_key,
+      XMSS_Address& adrs)
+   {
+
+   wots_keysig_t auth_path = build_auth_path(xmss_priv_key, adrs);
+   adrs.set_type(XMSS_Address::Type::OTS_Hash_Address);
+   adrs.set_ots_address(m_leaf_idx);
+
+   wots_keysig_t sig_ots = xmss_priv_key.wots_private_key().sign(msg, adrs);
+   return XMSS_WOTS_PublicKey::TreeSignature(sig_ots, auth_path);
+   }
+
+XMSS_Signature
+XMSS_Signature_Operation::sign(const secure_vector<byte>& msg_hash,
+                               XMSS_PrivateKey& xmss_priv_key)
+   {
+   XMSS_Address adrs;
+   XMSS_Signature sig(m_leaf_idx,
+                      m_randomness,
+                      generate_tree_signature(msg_hash, xmss_priv_key,adrs));
+   return sig;
+   }
+
+wots_keysig_t
+XMSS_Signature_Operation::build_auth_path(XMSS_PrivateKey& priv_key,
+      XMSS_Address& adrs)
+   {
+   wots_keysig_t auth_path(m_xmss_params.tree_height());
+   adrs.set_type(XMSS_Address::Type::Hash_Tree_Address);
+
+   for(size_t j = 0; j < m_xmss_params.tree_height(); j++)
+      {
+      size_t k = (m_leaf_idx / (1 << j)) ^ 0x01;
+      auth_path[j] = priv_key.tree_hash(k * (1 << j), j, adrs);
+      }
+
+   return auth_path;
+   }
+
+void XMSS_Signature_Operation::update(const byte msg[], size_t msg_len)
+   {
+   initialize();
+   m_hash.h_msg_update(msg, msg_len);
+   }
+
+
+secure_vector<byte>
+XMSS_Signature_Operation::sign(RandomNumberGenerator&)
+   {
+   initialize();
+   secure_vector<byte> signature(sign(m_hash.h_msg_final(),
+                                      m_priv_key).bytes());
+   m_is_initialized = false;
+   return signature;
+   }
+
+void XMSS_Signature_Operation::initialize()
+   {
+   // return if we already initialized and reserved a leaf index for signing.
+   if(m_is_initialized)
+      return;
+
+   secure_vector<byte> index_bytes;
+   // reserve leaf index so it can not be reused in by another signature
+   // operation using the same private key.
+   m_leaf_idx = m_priv_key.reserve_unused_leaf_index();
+
+   // write prefix for message hashing into buffer.
+   XMSS_Tools::get().concat(index_bytes, m_leaf_idx, 32);
+   m_randomness = m_hash.prf(m_priv_key.prf(), index_bytes);
+   index_bytes.clear();
+   XMSS_Tools::get().concat(index_bytes, m_leaf_idx,
+                            m_priv_key.xmss_parameters().element_size());
+   m_hash.h_msg_init(m_randomness,
+                     m_priv_key.root(),
+                     index_bytes);
+   m_is_initialized = true;
+   }
+
+}
+