From 6bf0a5cb5034a7e684dcc3500e841785237ce2dd Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 19:32:43 +0200 Subject: Adding upstream version 1:115.7.0. Signed-off-by: Daniel Baumann --- .../third_party/botan/src/lib/pubkey/xmss/atomic.h | 55 ++ .../third_party/botan/src/lib/pubkey/xmss/info.txt | 40 ++ comm/third_party/botan/src/lib/pubkey/xmss/xmss.h | 459 +++++++++++++ .../botan/src/lib/pubkey/xmss/xmss_address.h | 405 +++++++++++ .../botan/src/lib/pubkey/xmss/xmss_common_ops.cpp | 74 ++ .../botan/src/lib/pubkey/xmss/xmss_common_ops.h | 83 +++ .../botan/src/lib/pubkey/xmss/xmss_hash.cpp | 80 +++ .../botan/src/lib/pubkey/xmss/xmss_hash.h | 156 +++++ .../src/lib/pubkey/xmss/xmss_index_registry.cpp | 84 +++ .../src/lib/pubkey/xmss/xmss_index_registry.h | 105 +++ .../botan/src/lib/pubkey/xmss/xmss_key_pair.h | 49 ++ .../botan/src/lib/pubkey/xmss/xmss_parameters.cpp | 184 +++++ .../botan/src/lib/pubkey/xmss/xmss_parameters.h | 119 ++++ .../botan/src/lib/pubkey/xmss/xmss_privatekey.cpp | 405 +++++++++++ .../botan/src/lib/pubkey/xmss/xmss_privatekey.h | 13 + .../botan/src/lib/pubkey/xmss/xmss_publickey.cpp | 129 ++++ .../botan/src/lib/pubkey/xmss/xmss_publickey.h | 14 + .../botan/src/lib/pubkey/xmss/xmss_signature.cpp | 92 +++ .../botan/src/lib/pubkey/xmss/xmss_signature.h | 127 ++++ .../lib/pubkey/xmss/xmss_signature_operation.cpp | 120 ++++ .../src/lib/pubkey/xmss/xmss_signature_operation.h | 89 +++ .../botan/src/lib/pubkey/xmss/xmss_tools.h | 108 +++ .../pubkey/xmss/xmss_verification_operation.cpp | 138 ++++ .../lib/pubkey/xmss/xmss_verification_operation.h | 71 ++ .../botan/src/lib/pubkey/xmss/xmss_wots.h | 752 +++++++++++++++++++++ .../pubkey/xmss/xmss_wots_addressed_privatekey.h | 68 ++ .../pubkey/xmss/xmss_wots_addressed_publickey.h | 96 +++ .../src/lib/pubkey/xmss/xmss_wots_parameters.cpp | 137 ++++ .../src/lib/pubkey/xmss/xmss_wots_parameters.h | 14 + .../src/lib/pubkey/xmss/xmss_wots_privatekey.cpp | 99 +++ .../src/lib/pubkey/xmss/xmss_wots_privatekey.h | 15 + .../src/lib/pubkey/xmss/xmss_wots_publickey.cpp | 72 ++ .../src/lib/pubkey/xmss/xmss_wots_publickey.h | 14 + 33 files changed, 4466 insertions(+) create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/atomic.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/info.txt create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_address.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_common_ops.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_common_ops.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_hash.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_hash.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_index_registry.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_index_registry.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_key_pair.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_parameters.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_parameters.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_privatekey.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_privatekey.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_publickey.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_publickey.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature_operation.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature_operation.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_tools.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_verification_operation.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_verification_operation.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_addressed_privatekey.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_addressed_publickey.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_parameters.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_parameters.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_privatekey.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_privatekey.h create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_publickey.cpp create mode 100644 comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_publickey.h (limited to 'comm/third_party/botan/src/lib/pubkey/xmss') diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/atomic.h b/comm/third_party/botan/src/lib/pubkey/xmss/atomic.h new file mode 100644 index 0000000000..a542d4c005 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/atomic.h @@ -0,0 +1,55 @@ +/* + * Atomic + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_ATOMIC_H_ +#define BOTAN_ATOMIC_H_ + +#include +#include +#include + +//BOTAN_FUTURE_INTERNAL_HEADER(atomic.h) + +namespace Botan { + +template +/** + * Simple helper class to expand std::atomic with copy constructor and copy + * assignment operator, i.e. for use as element in a container like + * std::vector. The construction of instances of this wrapper is NOT atomic + * and needs to be properly guarded. + **/ +class Atomic final + { + public: + Atomic() = default; + Atomic(const Atomic& data) : m_data(data.m_data.load()) {} + Atomic(const std::atomic& data) : m_data(data.load()) {} + ~Atomic() = default; + + Atomic& operator=(const Atomic& a) + { + m_data.store(a.m_data.load()); + return *this; + } + + Atomic& operator=(const std::atomic& a) + { + m_data.store(a.load()); + return *this; + } + + operator std::atomic& () { return m_data; } + operator T() { return m_data.load(); } + + private: + std::atomic m_data; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/info.txt b/comm/third_party/botan/src/lib/pubkey/xmss/info.txt new file mode 100644 index 0000000000..ae290f5fc9 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/info.txt @@ -0,0 +1,40 @@ + +XMSS_RFC8391 -> 20201101 + + + +xmss.h +xmss_hash.h +xmss_wots.h +xmss_parameters.h +xmss_key_pair.h +xmss_privatekey.h +xmss_publickey.h +xmss_wots_parameters.h +xmss_wots_privatekey.h +xmss_wots_publickey.h + + + +atomic.h +xmss_address.h +xmss_common_ops.h +xmss_index_registry.h +xmss_signature.h +xmss_signature_operation.h +xmss_tools.h +xmss_verification_operation.h +xmss_wots_addressed_privatekey.h +xmss_wots_addressed_publickey.h + + + +asn1 +rng +hash +sha2_32 + + + +atomics + diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss.h new file mode 100644 index 0000000000..af8e8a41e8 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss.h @@ -0,0 +1,459 @@ +/* + * XMSS Keys + * (C) 2016,2017 Matthias Gierlings + * (C) 2019 René Korthaus, Rohde & Schwarz Cybersecurity + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_H_ +#define BOTAN_XMSS_H_ + +#include +#include +#include +#include + +namespace Botan { + +class RandomNumberGenerator; +class XMSS_Verification_Operation; + +/** + * An XMSS: Extended Hash-Based Signature public key. + * + * [1] XMSS: Extended Hash-Based Signatures, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + **/ +class BOTAN_PUBLIC_API(2,0) 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); + + /** + * Loads a public key. + * + * Public key must be encoded as in RFC + * draft-vangeest-x509-hash-sigs-03. + * + * @param key_bits DER encoded public key bits + */ + XMSS_PublicKey(const std::vector& key_bits); + + /** + * 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& root, + const secure_vector& 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&& root, + secure_vector&& 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 + **/ + 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 XMSS parameters determined by the chosen XMSS Signature + * method. + * + * @return XMSS parameters. + **/ + std::string xmss_hash_function() const + { + return m_xmss_params.hash_function_name(); + } + + /** + * Retrieves the Winternitz One Time Signature (WOTS) method, + * corresponding 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 + * corresponding 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& root() + { + return m_root; + } + + void set_root(const secure_vector& root) + { + m_root = root; + } + + void set_root(secure_vector&& root) + { + m_root = std::move(root); + } + + const secure_vector& root() const + { + return m_root; + } + + virtual secure_vector& public_seed() + { + return m_public_seed; + } + + virtual void set_public_seed(const secure_vector& public_seed) + { + m_public_seed = public_seed; + } + + virtual void set_public_seed(secure_vector&& public_seed) + { + m_public_seed = std::move(public_seed); + } + + virtual const secure_vector& public_seed() const + { + return m_public_seed; + } + + std::string algo_name() const override + { + return "XMSS"; + } + + AlgorithmIdentifier algorithm_identifier() const override + { + return AlgorithmIdentifier(get_oid(), AlgorithmIdentifier::USE_EMPTY_PARAM); + } + + bool check_key(RandomNumberGenerator&, bool) const override + { + return true; + } + + std::unique_ptr + create_verification_op(const std::string&, + const std::string& provider) const override; + + size_t estimated_strength() const override + { + return m_xmss_params.estimated_strength(); + } + + size_t key_length() const override + { + return m_xmss_params.estimated_strength(); + } + + /** + * Returns the encoded public key as defined in RFC + * draft-vangeest-x509-hash-sigs-03. + * + * @return encoded public key bits + **/ + std::vector public_key_bits() const override; + + /** + * 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 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 raw_public_key() const; + + protected: + std::vector m_raw_key; + XMSS_Parameters m_xmss_params; + XMSS_WOTS_Parameters m_wots_params; + secure_vector m_root; + secure_vector m_public_seed; + + private: + XMSS_Parameters::xmss_algorithm_t deserialize_xmss_oid( + const std::vector& raw_key); + }; + +template class Atomic; + +class XMSS_Index_Registry; + +/** + * An XMSS: Extended Hash-Based Signature private key. + * The XMSS private key does not support the X509 and PKCS7 standard. Instead + * the raw format described in [1] is used. + * + * [1] XMSS: Extended Hash-Based Signatures, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + **/ +class BOTAN_PUBLIC_API(2,0) XMSS_PrivateKey final : public virtual XMSS_PublicKey, + public virtual Private_Key + { + public: + /** + * Creates a new XMSS private key for the chosen XMSS signature method. + * New seeds for public/private key and pseudo random function input are + * generated using the provided RNG. The appropriate WOTS signature method + * will be automatically set based on the chosen XMSS signature method. + * + * @param xmss_algo_id Identifier for the selected XMSS signature method. + * @param rng A random number generator to use for key generation. + **/ + XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id, + RandomNumberGenerator& rng); + + /** + * Creates an XMSS_PrivateKey from a byte sequence produced by + * raw_private_key(). + * + * @param raw_key An XMSS private key serialized using raw_private_key(). + **/ + XMSS_PrivateKey(const secure_vector& raw_key); + + /** + * Creates a new XMSS private key for the chosen XMSS signature method + * using precomputed seeds for public/private keys and pseudo random + * function input. The appropriate WOTS signature method will be + * automatically set, based on the chosen XMSS signature method. + * + * @param xmss_algo_id Identifier for the selected XMSS signature method. + * @param idx_leaf Index of the next unused leaf. + * @param wots_priv_seed A seed to generate a Winternitz-One-Time- + * Signature private key from. + * @param prf a secret n-byte key sourced from a secure source + * of uniformly random data. + * @param root Root node of the binary hash tree. + * @param public_seed The public seed. + **/ + XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id, + size_t idx_leaf, + const secure_vector& wots_priv_seed, + const secure_vector& prf, + const secure_vector& root, + const secure_vector& public_seed); + + bool stateful_operation() const override { return true; } + + /** + * Retrieves the last unused leaf index of the private key. Reusing a leaf + * by utilizing leaf indices lower than the last unused leaf index will + * compromise security. + * + * @return Index of the last unused leaf. + **/ + size_t unused_leaf_index() const; + + /** + * Sets the last unused leaf index of the private key. The leaf index + * will be updated automatically during every signing operation, and + * should not be set manually. + * + * @param idx Index of the last unused leaf. + **/ + void set_unused_leaf_index(size_t idx); + + size_t reserve_unused_leaf_index(); + + /** + * Winternitz One Time Signature Scheme key utilized for signing + * operations. + * + * @return WOTS+ private key. + **/ + const XMSS_WOTS_PrivateKey& wots_private_key() const + { + return m_wots_priv_key; + } + + /** + * Winternitz One Time Signature Scheme key utilized for signing + * operations. + * + * @return WOTS+ private key. + **/ + XMSS_WOTS_PrivateKey& wots_private_key() + { + return m_wots_priv_key; + } + + const secure_vector& prf() const + { + return m_prf; + } + + secure_vector& prf() + { + return m_prf; + } + + void set_public_seed( + const secure_vector& public_seed) override + { + m_public_seed = public_seed; + m_wots_priv_key.set_public_seed(public_seed); + } + + void set_public_seed(secure_vector&& public_seed) override + { + m_public_seed = std::move(public_seed); + m_wots_priv_key.set_public_seed(m_public_seed); + } + + const secure_vector& public_seed() const override + { + return m_public_seed; + } + + std::unique_ptr + create_signature_op(RandomNumberGenerator&, + const std::string&, + const std::string& provider) const override; + + secure_vector private_key_bits() const override; + + size_t size() const override + { + return XMSS_PublicKey::size() + + sizeof(uint32_t) + + 2 * XMSS_PublicKey::m_xmss_params.element_size(); + } + + /** + * Generates a non standartized byte sequence representing the XMSS + * private key. + * + * @return byte sequence consisting of the following elements in order: + * 4-byte OID, n-byte root node, n-byte public seed, + * 8-byte unused leaf index, n-byte prf seed, n-byte private seed. + **/ + secure_vector raw_private_key() const; + /** + * Algorithm 9: "treeHash" + * Computes the internal n-byte nodes of a Merkle tree. + * + * @param start_idx The start index. + * @param target_node_height Height of the target node. + * @param adrs Address of the tree containing the target node. + * + * @return The root node of a tree of height target_node height with the + * leftmost leaf being the hash of the WOTS+ pk with index + * start_idx. + **/ + secure_vector tree_hash( + size_t start_idx, + size_t target_node_height, + XMSS_Address& adrs); + + private: + /** + * Fetches shared unused leaf index from the index registry + **/ + std::shared_ptr> recover_global_leaf_index() const; + + inline void tree_hash_subtree(secure_vector& result, + size_t start_idx, + size_t target_node_height, + XMSS_Address& adrs) + { + return tree_hash_subtree(result, start_idx, target_node_height, adrs, m_hash); + } + + + /** + * Helper for multithreaded tree hashing. + */ + void tree_hash_subtree(secure_vector& result, + size_t start_idx, + size_t target_node_height, + XMSS_Address& adrs, + XMSS_Hash& hash); + + XMSS_WOTS_PrivateKey m_wots_priv_key; + XMSS_Hash m_hash; + secure_vector m_prf; + XMSS_Index_Registry& m_index_reg; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_address.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_address.h new file mode 100644 index 0000000000..05a78f3b88 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_address.h @@ -0,0 +1,405 @@ +/* + * XMSS Address + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_ADDRESS_H_ +#define BOTAN_XMSS_ADDRESS_H_ + +#include + +namespace Botan { + +/** + * Generic XMSS Address type holding 256 Bits of data. Properties + * of all three address formats L-Tree-Address, Hash-Tree-Address, + * OTS-Hash-Address can be called depending on the type currently + * assigned to the XMSS address using set_type(). + **/ +class XMSS_Address final + { + public: + /** + * Distinct types an XMSS_Address can represent. The available types + * are specified in [1] - 2.5 Hash Function Address Scheme. + **/ + enum class Type : uint8_t + { + None = 255, + OTS_Hash_Address = 0, + LTree_Address = 1, + Hash_Tree_Address = 2 + }; + + /** + * The available modes for an XMSS Address: + * - Key_Mode: Used to generate the key. + * - Mask_Mode: Sets the n-byte bitmask (OTS-Hash-Address) + * - Mask_MSB_Mode: Used to generate the b most significant bytes of + * the 2n-byte bitmask (LTree Address and Hash Tree Address). + * - Mask_LSB_Mode: Used to generated the b least significant bytes + * of the 2n-byte bitmask. (LTree Address and Hash Tree Address). + **/ + enum class Key_Mask : uint8_t + { + Key_Mode = 0, + Mask_Mode = 1, + Mask_MSB_Mode = 1, + Mask_LSB_Mode = 2 + }; + + /** + * Layer Address for XMSS is constantly zero and can not be changed this + * property is only of relevance to XMSS_MT. + * + * @return Layer address, which is constant 0 for XMSS. + **/ + uint8_t get_layer_addr() const { return 0; } + + /** + * Layer Address for XMSS is constantly zero and can not be changed this + * property is only of relevance to XMSS_MT. Calling this method for + * XMSS will result in an error. + **/ + void set_layer_addr() + { + BOTAN_ASSERT(false, "Only available in XMSS_MT."); + } + + /** + * Tree Address for XMSS is constantly zero and can not be changed this + * property is only of relevance to XMSS_MT. + * + * @return Tree address, which is constant 0 for XMSS. + **/ + uint64_t get_tree_addr() const { return 0; } + + /** + * Tree Address for XMSS is constantly zero and can not be changed this + * property is only of relevance to XMSS_MT. Calling this method for + * XMSS will result in an error. + **/ + void set_tree_addr() + { + BOTAN_ASSERT(false, "Only available in XMSS_MT."); + } + + /** + * retrieves the logical type currently assigned to the XMSS Address + * instance. + * + * @return Type of the address (OTS_Hash_Address, LTree_Address or + * Hash_Tree_Address) + **/ + Type get_type() const + { + return static_cast(m_data[15]); + } + + /** + * Changes the logical type currently assigned to the XMSS Address + * instance. Please note that changing the type will automatically + * reset the 128 LSBs of the Address to zero. This affects the + * key_mask_mode property as well as all properties identified by + * XMSS_Address::Property. + * + * @param type Type that shall be assigned to the address + * (OTS_Hash_Address, LTree_Address or Hash_Tree_Address) + **/ + void set_type(Type type) + { + m_data[15] = static_cast(type); + std::fill(m_data.begin() + 16, m_data.end(), static_cast(0)); + } + + /** + * Retrieves the mode the address os currently set to. (See + * XMSS_Address::Key_Mask for details.) + * + * @return currently active mode + **/ + Key_Mask get_key_mask_mode() const + { + return Key_Mask(m_data[31]); + } + + /** + * Changes the mode the address currently used address mode. + * (XMSS_Address::Key_Mask for details.) + * + * @param value Target mode. + **/ + void set_key_mask_mode(Key_Mask value) + { + BOTAN_ASSERT(value != Key_Mask::Mask_LSB_Mode || + get_type() != Type::OTS_Hash_Address, + "Invalid Key_Mask for current XMSS_Address::Type."); + m_data[31] = static_cast(value); + } + + /** + * Retrieve the index of the OTS key pair within the tree. A call to + * this method is only valid, if the address type is set to + * Type::OTS_Hash_Address. + * + * @return index of OTS key pair. + **/ + uint32_t get_ots_address() const + { + BOTAN_ASSERT(get_type() == Type::OTS_Hash_Address, + "get_ots_address() requires XMSS_Address::Type::" + "OTS_Hash_Address."); + return get_hi32(2); + } + + /** + * Sets the index of the OTS key pair within the tree. A call to this + * method is only valid, if the address type is set to + * Type::OTS_Hash_Address. + * + * @param value index of OTS key pair. + **/ + void set_ots_address(uint32_t value) + { + BOTAN_ASSERT(get_type() == Type::OTS_Hash_Address, + "set_ots_address() requires XMSS_Address::Type::" + "OTS_Hash_Address."); + set_hi32(2, value); + } + + /** + * Retrieves the index of the leaf computed with this LTree. A call to + * this method is only valid, if the address type is set to + * Type::LTree_Address. + * + * @return index of the leaf. + **/ + uint32_t get_ltree_address() const + { + BOTAN_ASSERT(get_type() == Type::LTree_Address, + "set_ltree_address() requires XMSS_Address::Type::" + "LTree_Address."); + return get_hi32(2); + } + + /** + * Sets the index of the leaf computed with this LTree. A call to this + * method is only valid, if the address type is set to + * Type::LTree_Address. + * + * @param value index of the leaf. + **/ + void set_ltree_address(uint32_t value) + { + BOTAN_ASSERT(get_type() == Type::LTree_Address, + "set_ltree_address() requires XMSS_Address::Type::" + "LTree_Address."); + set_hi32(2, value); + } + + /** + * Retrieve the chain address. A call to this method is only valid, if + * the address type is set to Type::OTS_Hash_Address. + * + * @return chain address. + **/ + uint32_t get_chain_address() const + { + BOTAN_ASSERT(get_type() == Type::OTS_Hash_Address, + "get_chain_address() requires XMSS_Address::Type::" + "OTS_Hash_Address."); + return get_lo32(2); + } + + /** + * Set the chain address. A call to this method is only valid, if + * the address type is set to Type::OTS_Hash_Address. + **/ + void set_chain_address(uint32_t value) + { + BOTAN_ASSERT(get_type() == Type::OTS_Hash_Address, + "set_chain_address() requires XMSS_Address::Type::" + "OTS_Hash_Address."); + set_lo32(2, value); + } + + /** + * Retrieves the height of the tree node to be computed within the + * tree. A call to this method is only valid, if the address type is + * set to Type::LTree_Address or Type::Hash_Tree_Address. + * + * @return height of the tree node. + **/ + uint32_t get_tree_height() const + { + BOTAN_ASSERT(get_type() == Type::LTree_Address || + get_type() == Type::Hash_Tree_Address, + "get_tree_height() requires XMSS_Address::Type::" + "LTree_Address or XMSS_Address::Type::Hash_Tree_Address."); + return get_lo32(2); + } + + /** + * Sets the height of the tree node to be computed within the + * tree. A call to this method is only valid, if the address type is + * set to Type::LTree_Address or Type::Hash_Tree_Address. + * + * @param value height of the tree node. + **/ + void set_tree_height(uint32_t value) + { + BOTAN_ASSERT(get_type() == Type::LTree_Address || + get_type() == Type::Hash_Tree_Address, + "set_tree_height() requires XMSS_Address::Type::" + "LTree_Address or XMSS_Address::Type::Hash_Tree_Address."); + set_lo32(2, value); + } + + /** + * Retrieves the address of the hash function call within the chain. + * A call to this method is only valid, if the address type is + * set to Type::OTS_Hash_Address. + * + * @return address of the hash function call within chain. + **/ + uint32_t get_hash_address() const + { + BOTAN_ASSERT(get_type() == Type::OTS_Hash_Address, + "get_hash_address() requires XMSS_Address::Type::" + "OTS_Hash_Address."); + return get_hi32(3); + } + + /** + * Sets the address of the hash function call within the chain. + * A call to this method is only valid, if the address type is + * set to Type::OTS_Hash_Address. + * + * @param value address of the hash function call within chain. + **/ + void set_hash_address(uint32_t value) + { + BOTAN_ASSERT(get_type() == Type::OTS_Hash_Address, + "set_hash_address() requires XMSS_Address::Type::" + "OTS_Hash_Address."); + set_hi32(3, value); + } + + /** + * Retrieves the index of the tree node at current tree height in the + * tree. A call to this method is only valid, if the address type is + * set to Type::LTree_Address or Type::Hash_Tree_Address. + * + * @return index of the tree node at current height. + **/ + uint32_t get_tree_index() const + { + BOTAN_ASSERT(get_type() == Type::LTree_Address || + get_type() == Type::Hash_Tree_Address, + "get_tree_index() requires XMSS_Address::Type::" + "LTree_Address or XMSS_Address::Type::Hash_Tree_Address."); + return get_hi32(3); + } + + /** + * Sets the index of the tree node at current tree height in the + * tree. A call to this method is only valid, if the address type is + * set to Type::LTree_Address or Type::Hash_Tree_Address. + * + * @param value index of the tree node at current height. + **/ + void set_tree_index(uint32_t value) + { + BOTAN_ASSERT(get_type() == Type::LTree_Address || + get_type() == Type::Hash_Tree_Address, + "set_tree_index() requires XMSS_Address::Type::" + "LTree_Address or XMSS_Address::Type::Hash_Tree_Address."); + set_hi32(3, value); + } + + const secure_vector& bytes() const + { + return m_data; + } + + secure_vector& bytes() + { + return m_data; + } + + /** + * @return the size of an XMSS_Address + **/ + size_t size() const + { + return m_data.size(); + } + + XMSS_Address() + : m_data(m_address_size) + { + set_type(Type::None); + } + + XMSS_Address(Type type) + : m_data(m_address_size) + { + set_type(type); + } + + XMSS_Address(const secure_vector& data) : m_data(data) + { + BOTAN_ASSERT(m_data.size() == m_address_size, + "XMSS_Address must be of 256 bits size."); + } + + XMSS_Address(secure_vector&& data) : m_data(std::move(data)) + { + BOTAN_ASSERT(m_data.size() == m_address_size, + "XMSS_Address must be of 256 bits size."); + } + + protected: + secure_vector m_data; + + private: + static const size_t m_address_size = 32; + + inline uint32_t get_hi32(size_t offset) const + { + return ((0x000000FF & m_data[8 * offset + 3]) | + (0x000000FF & m_data[8 * offset + 2]) << 8 | + (0x000000FF & m_data[8 * offset + 1]) << 16 | + (0x000000FF & m_data[8 * offset ]) << 24); + } + + inline void set_hi32(size_t offset, uint32_t value) + { + m_data[offset * 8 ] = ((value >> 24) & 0xFF); + m_data[offset * 8 + 1] = ((value >> 16) & 0xFF); + m_data[offset * 8 + 2] = ((value >> 8) & 0xFF); + m_data[offset * 8 + 3] = ((value ) & 0xFF); + } + + inline uint32_t get_lo32(size_t offset) const + { + return ((0x000000FF & m_data[8 * offset + 7]) | + (0x000000FF & m_data[8 * offset + 6]) << 8 | + (0x000000FF & m_data[8 * offset + 5]) << 16 | + (0x000000FF & m_data[8 * offset + 4]) << 24); + } + + inline void set_lo32(size_t offset, uint32_t value) + { + m_data[offset * 8 + 4] = ((value >> 24) & 0xFF); + m_data[offset * 8 + 5] = ((value >> 16) & 0xFF); + m_data[offset * 8 + 6] = ((value >> 8) & 0xFF); + m_data[offset * 8 + 7] = ((value ) & 0xFF); + } + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_common_ops.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_common_ops.cpp new file mode 100644 index 0000000000..9a3fe085ab --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_common_ops.cpp @@ -0,0 +1,74 @@ +/* + * XMSS Common Ops + * Operations shared by XMSS signature generation and verification operations. + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include + +namespace Botan { + +void +XMSS_Common_Ops::randomize_tree_hash(secure_vector& result, + const secure_vector& left, + const secure_vector& right, + XMSS_Address& adrs, + const secure_vector& seed, + XMSS_Hash& hash, + const XMSS_Parameters& params) + { + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Key_Mode); + secure_vector key { hash.prf(seed, adrs.bytes()) }; + + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Mask_MSB_Mode); + secure_vector bitmask_l { hash.prf(seed, adrs.bytes()) }; + + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Mask_LSB_Mode); + secure_vector bitmask_r { hash.prf(seed, adrs.bytes()) }; + + BOTAN_ASSERT(bitmask_l.size() == left.size() && + bitmask_r.size() == right.size(), + "Bitmask size doesn't match node size."); + + secure_vector concat_xor(params.element_size() * 2); + for(size_t i = 0; i < left.size(); i++) + { + concat_xor[i] = left[i] ^ bitmask_l[i]; + concat_xor[i + left.size()] = right[i] ^ bitmask_r[i]; + } + + hash.h(result, key, concat_xor); + } + + +void +XMSS_Common_Ops::create_l_tree(secure_vector& result, + wots_keysig_t pk, + XMSS_Address& adrs, + const secure_vector& seed, + XMSS_Hash& hash, + const XMSS_Parameters& params) + { + size_t l = params.len(); + adrs.set_tree_height(0); + + while(l > 1) + { + for(size_t i = 0; i < l >> 1; i++) + { + adrs.set_tree_index(static_cast(i)); + randomize_tree_hash(pk[i], pk[2 * i], pk[2 * i + 1], adrs, seed, hash, params); + } + if(l & 0x01) + { + pk[l >> 1] = pk[l - 1]; + } + l = (l >> 1) + (l & 0x01); + adrs.set_tree_height(adrs.get_tree_height() + 1); + } + result = pk[0]; + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_common_ops.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_common_ops.h new file mode 100644 index 0000000000..77fdc9dc1e --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_common_ops.h @@ -0,0 +1,83 @@ +/* + * XMSS Common Ops + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_COMMON_OPS_H_ +#define BOTAN_XMSS_COMMON_OPS_H_ + +#include +#include +#include +#include +#include + +BOTAN_FUTURE_INTERNAL_HEADER(xmss_common_ops.h) + +namespace Botan { + +typedef std::vector> wots_keysig_t; + +/** + * Operations shared by XMSS signature generation and verification operations. + **/ +class XMSS_Common_Ops + { + public: + /** + * Algorithm 7: "RAND_HASH" + * + * Generates a randomized hash. + * + * This overload is used in multithreaded scenarios, where it is + * required to provide seperate instances of XMSS_Hash to each + * thread. + * + * @param[out] result The resulting randomized hash. + * @param[in] left Left half of the hash function input. + * @param[in] right Right half of the hash function input. + * @param[in] adrs Adress of the hash function call. + * @param[in] seed The seed for G. + * @param[in] hash Instance of XMSS_Hash, that may only by the thead + * executing generate_public_key. + * @param[in] params + **/ + static void randomize_tree_hash( + secure_vector& result, + const secure_vector& left, + const secure_vector& right, + XMSS_Address& adrs, + const secure_vector& seed, + XMSS_Hash& hash, + const XMSS_Parameters& params); + + /** + * Algorithm 8: "ltree" + * Create an L-tree used to compute the leaves of the binary hash tree. + * Takes a WOTS+ public key and compresses it to a single n-byte value. + * + * This overload is used in multithreaded scenarios, where it is + * required to provide seperate instances of XMSS_Hash to each thread. + * + * @param[out] result Public key compressed to a single n-byte value + * pk[0]. + * @param[in] pk Winternitz One Time Signatures+ public key. + * @param[in] adrs Address encoding the address of the L-Tree + * @param[in] seed The seed generated during the public key generation. + * @param[in] hash Instance of XMSS_Hash, that may only be used by the + * thead executing create_l_tree. + * @param[in] params + **/ + static void create_l_tree(secure_vector& result, + wots_keysig_t pk, + XMSS_Address& adrs, + const secure_vector& seed, + XMSS_Hash& hash, + const XMSS_Parameters& params); + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_hash.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_hash.cpp new file mode 100644 index 0000000000..cd714873ca --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_hash.cpp @@ -0,0 +1,80 @@ +/* + * XMSS Hash + * A collection of pseudorandom hash functions required for XMSS and WOTS + * computations. + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include + +namespace Botan { + +XMSS_Hash::XMSS_Hash(const XMSS_Hash& hash) + : XMSS_Hash(hash.m_hash_func_name) + { + } + +XMSS_Hash::XMSS_Hash(const std::string& h_func_name) : + m_hash(HashFunction::create(h_func_name)), + m_hash_func_name(h_func_name) + { + if(!m_hash) + throw Lookup_Error("XMSS cannot use hash " + h_func_name + + " because it is unavailable"); + + m_output_length = m_hash->output_length(); + BOTAN_ASSERT(m_output_length > 0, "Hash output length of zero is invalid."); + + m_zero_padding.resize(m_output_length - 1); + m_msg_hash.reset(m_hash->clone()); + } + +void +XMSS_Hash::h(secure_vector& result, + const secure_vector& key, + const secure_vector& data) + { + m_hash->update(m_zero_padding); + m_hash->update(m_id_h); + m_hash->update(key); + m_hash->update(data); + m_hash->final(result); + } + +void XMSS_Hash::h_msg_init(const secure_vector& randomness, + const secure_vector& root, + const secure_vector& index_bytes) + { + m_msg_hash->clear(); + m_msg_hash->update(m_zero_padding); + m_msg_hash->update(m_id_hmsg); + m_msg_hash->update(randomness); + m_msg_hash->update(root); + m_msg_hash->update(index_bytes); + } + +void XMSS_Hash::h_msg_update(const uint8_t data[], size_t size) + { + m_msg_hash->update(data, size); + } + +secure_vector XMSS_Hash::h_msg_final() + { + return m_msg_hash->final(); + } + +secure_vector +XMSS_Hash::h_msg(const secure_vector& randomness, + const secure_vector& root, + const secure_vector& index_bytes, + const secure_vector& data) + { + h_msg_init(randomness, root, index_bytes); + m_msg_hash->update(data); + return m_msg_hash->final(); + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_hash.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_hash.h new file mode 100644 index 0000000000..5d8cbab538 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_hash.h @@ -0,0 +1,156 @@ +/* + * XMSS Hash + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_HASH_H_ +#define BOTAN_XMSS_HASH_H_ + +#include + +//BOTAN_FUTURE_INTERNAL_HEADER(xmss_hash.h) + +namespace Botan { + +/** + * A collection of pseudorandom hash functions required for XMSS and WOTS + * computations. + **/ +class XMSS_Hash final + { + public: + XMSS_Hash(const std::string& h_func_name); + XMSS_Hash(const XMSS_Hash& hash); + + /** + * Pseudoranom function creating a hash out of a key and data using + * a cryptographic hash function. + * + * @param[out] result The hash calculated using key and data. + * @param[in] key An n-byte key value. + * @param[in] data A 32-byte XMSS_Address data value + **/ + inline void prf(secure_vector& result, + const secure_vector& key, + const secure_vector& data) + { + m_hash->update(m_zero_padding); + m_hash->update(m_id_prf); + m_hash->update(key); + m_hash->update(data); + m_hash->final(result); + } + + /** + * Pseudoranom function creating a hash out of a key and data using + * a cryptographic hash function. + * + * @param[in] key An n-byte key value. + * @param[in] data A 32-byte XMSS_Address data value + * @return result The hash calculated using key and data. + **/ + inline secure_vector prf(const secure_vector& key, + const secure_vector& data) + { + m_hash->update(m_zero_padding); + m_hash->update(m_id_prf); + m_hash->update(key); + m_hash->update(data); + return m_hash->final(); + } + + /** + * F is a keyed cryptographic hash function used by the WOTS+ algorithm. + * + * @param[out] result The hash calculated using key and data. + * @param[in] key key of length n bytes. + * @param[in] data string of arbitrary length. + **/ + void f(secure_vector& result, + const secure_vector& key, + const secure_vector& data) + { + m_hash->update(m_zero_padding); + m_hash->update(m_id_f); + m_hash->update(key); + m_hash->update(data); + m_hash->final(result); + } + + /** + * Cryptographic hash function h accepting n byte keys and 2n byte + * strings of data. + * + * @param[out] result The hash calculated using key and data. + * @param[in] key key of length n bytes. + * @param[in] data string of 2n bytes length. + **/ + void h(secure_vector& result, + const secure_vector& key, + const secure_vector& data); + + /** + * Cryptographic hash function h accepting 3n byte keys and data + * strings of arbitrary length. + * + * @param randomness n-byte value. + * @param root n-byte root node. + * @param index_bytes Index value padded with leading zeros. + * @param data string of arbitrary length. + * + * @return hash value of n-bytes length. + **/ + secure_vector h_msg(const secure_vector& randomness, + const secure_vector& root, + const secure_vector& index_bytes, + const secure_vector& data); + + /** + * Initializes buffered h_msg computation with prefix data. + * + * @param randomness random n-byte value. + * @param root n-byte root node. + * @param index_bytes Index value padded with leading zeros. + **/ + void h_msg_init(const secure_vector& randomness, + const secure_vector& root, + const secure_vector& index_bytes); + + /** + * Adds a message block to buffered h_msg computation. + * + * @param data A message block + * @param size Length of the message block in bytes. + **/ + void h_msg_update(const uint8_t data[], size_t size); + + /** + * Finalizes buffered h_msg computation and retrieves the result. + * + * @return Hash calculated using the prefix set by h_msg_init() and + * message blocks provided through calls to h_msg_update(). + **/ + secure_vector h_msg_final(); + + size_t output_length() const { return m_output_length; } + + private: + static const uint8_t m_id_f = 0x00; + static const uint8_t m_id_h = 0x01; + static const uint8_t m_id_hmsg = 0x02; + static const uint8_t m_id_prf = 0x03; + + std::unique_ptr m_hash; + std::unique_ptr m_msg_hash; + //32 byte id prefixes prepended to the hash input. + std::vector m_zero_padding; + size_t m_output_length; + const std::string m_hash_func_name; + + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_index_registry.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_index_registry.cpp new file mode 100644 index 0000000000..8709d8026f --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_index_registry.cpp @@ -0,0 +1,84 @@ +/* + * XMSS Index Registry + * A registry for XMSS private keys, keeps track of the leaf index for + * independend copies of the same key. + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include +#include + +namespace Botan { + +const std::string XMSS_Index_Registry::m_index_hash_function = "SHA-256"; + +uint64_t XMSS_Index_Registry::make_key_id( + const secure_vector& private_seed, + const secure_vector& prf) const + { + std::unique_ptr hash = + HashFunction::create(m_index_hash_function); + BOTAN_ASSERT(hash != nullptr, "XMSS_Index_Registry requires SHA-256"); + hash->update(private_seed); + hash->update(prf); + secure_vector result = hash->final(); + uint64_t key_id = 0; + for(size_t i = 0; i < sizeof(key_id); i++) + { + key_id = ((key_id << 8) | result[i]); + } + + return key_id; + } + +std::shared_ptr> +XMSS_Index_Registry::get(const secure_vector& private_seed, + const secure_vector& prf) + { + size_t pos = get(make_key_id(private_seed, prf)); + + if(pos < std::numeric_limits::max()) + { + return m_leaf_indices[pos]; + } + else + { + return m_leaf_indices[add(make_key_id(private_seed, prf))]; + } + } + +size_t XMSS_Index_Registry::get(uint64_t id) const + { + for(size_t i = 0; i < m_key_ids.size(); i++) + { + if(m_key_ids[i] == id) + { + return i; + } + } + + return std::numeric_limits::max(); + } + +size_t XMSS_Index_Registry::add(uint64_t id, size_t last_unused) + { + lock_guard_type lock(m_mutex); + size_t pos = get(id); + if(pos < m_key_ids.size()) + { + if(last_unused > *(m_leaf_indices[pos])) + { + m_leaf_indices[pos] = std::make_shared>(last_unused); + } + return pos; + } + + m_key_ids.push_back(id); + m_leaf_indices.push_back(std::make_shared>(last_unused)); + return m_key_ids.size() - 1; + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_index_registry.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_index_registry.h new file mode 100644 index 0000000000..91166db4ba --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_index_registry.h @@ -0,0 +1,105 @@ +/* + * XMSS Index Registry + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_INDEX_REGISTRY_H_ +#define BOTAN_XMSS_INDEX_REGISTRY_H_ + +#include + +#include +#include +#include + +//BOTAN_FUTURE_INTERNAL_HEADER(xmss_index_registry.h) + +namespace Botan { + +/** + * A registry for XMSS private keys, keeps track of the leaf index for + * independend copies of the same key. + **/ +class XMSS_Index_Registry final + { + public: + XMSS_Index_Registry(const XMSS_Index_Registry&) = delete; + XMSS_Index_Registry& operator=(const XMSS_Index_Registry&) = delete; + + /** + * Retrieves a handle to the process-wide unique XMSS index registry. + * + * @return Reference to unique XMSS index registry. + **/ + static XMSS_Index_Registry& get_instance() + { + static XMSS_Index_Registry self; + return self; + } + + /** + * Retrieves the last unused leaf index for the private key identified + * by private_seed and prf. The leaf index will be updated properly + * across independent copies of private_key. + * + * @param private_seed Part of the unique identifier for an + * XMSS_PrivateKey. + * @param prf Part of the unique identifier for an XMSS_PrivateKey. + * + * @return last unused leaf index for private_key. + **/ + std::shared_ptr> + get(const secure_vector& private_seed, + const secure_vector& prf); + + private: + XMSS_Index_Registry() = default; + + static const std::string m_index_hash_function; + + /** + * Creates a unique 64-bit id for an XMSS_Private key, by interpreting + * the first 64-bit of HASH(PRIVATE_SEED || PRF) as 64 bit integer + * value. + * + * @return unique integral identifier for an XMSS private key. + **/ + uint64_t make_key_id(const secure_vector& private_seed, + const secure_vector& prf) const; + + /** + * Retrieves the index position of a key within the registry or + * max(size_t) if key has not been found. + * + * @param id unique id of the XMSS private key (see make_key_id()). + * + * @return index position of key or max(size_t) if key not found. + **/ + size_t get(uint64_t id) const; + + /** + * If XMSS_PrivateKey identified by id is already registered, the + * position of the according registry entry is returned. If last_unused + * is bigger than the last unused index stored for the key identified by + * id the unused leaf index for this key is set to last_unused. If no key + * matching id is registed yet, an entry of id is added, with the last + * unused leaf index initialized to the value of last_unused. + * + * @last_unused Initial value for the last unused leaf index of the + * registered key. + * + * @return positon of leaf index registry entry for key identified + * by id. + **/ + size_t add(uint64_t id, size_t last_unused = 0); + + std::vector m_key_ids; + std::vector>> m_leaf_indices; + mutex_type m_mutex; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_key_pair.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_key_pair.h new file mode 100644 index 0000000000..19e23c7776 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_key_pair.h @@ -0,0 +1,49 @@ +/* + * XMSS Key Pair + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_KEY_PAIR_H_ +#define BOTAN_XMSS_KEY_PAIR_H_ + +#include + +BOTAN_DEPRECATED_HEADER(xmss_key_pair.h) + +namespace Botan { + +/** + * A pair of XMSS public and private key. + **/ +class BOTAN_PUBLIC_API(2,0) XMSS_Key_Pair + { + public: + XMSS_Key_Pair(XMSS_Parameters::xmss_algorithm_t xmss_oid, + RandomNumberGenerator& rng) + : m_priv_key(xmss_oid, rng), m_pub_key(m_priv_key) {} + + XMSS_Key_Pair(const XMSS_PublicKey& pub_key, + const XMSS_PrivateKey& priv_key) + : m_priv_key(priv_key), m_pub_key(pub_key) + {} + + XMSS_Key_Pair(XMSS_PublicKey&& pub_key, + XMSS_PrivateKey&& priv_key) + : m_priv_key(std::move(priv_key)), m_pub_key(std::move(pub_key)) {} + + const XMSS_PublicKey& public_key() const { return m_pub_key; } + XMSS_PublicKey& public_key() { return m_pub_key; } + + const XMSS_PrivateKey& private_key() const { return m_priv_key; } + XMSS_PrivateKey& private_key() { return m_priv_key; } + + private: + XMSS_PrivateKey m_priv_key; + XMSS_PublicKey m_pub_key; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_parameters.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_parameters.cpp new file mode 100644 index 0000000000..55084c8b92 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_parameters.cpp @@ -0,0 +1,184 @@ +/* + * XMSS Parameters + * Descibes a signature method for XMSS, as defined in: + * [1] XMSS: Extended Hash-Based Signatures, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + * + * (C) 2016,2017,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include + +namespace Botan { + +XMSS_Parameters::xmss_algorithm_t XMSS_Parameters::xmss_id_from_string(const std::string& param_set) + { + if(param_set == "XMSS-SHA2_10_256") + { return XMSS_SHA2_10_256; } + if(param_set == "XMSS-SHA2_16_256") + { return XMSS_SHA2_16_256; } + if(param_set == "XMSS-SHA2_20_256") + { return XMSS_SHA2_20_256; } + if(param_set == "XMSS-SHA2_10_512") + { return XMSS_SHA2_10_512; } + if(param_set == "XMSS-SHA2_16_512") + { return XMSS_SHA2_16_512; } + if(param_set == "XMSS-SHA2_20_512") + { return XMSS_SHA2_20_512; } + if(param_set == "XMSS-SHAKE_10_256") + { return XMSS_SHAKE_10_256; } + if(param_set == "XMSS-SHAKE_16_256") + { return XMSS_SHAKE_16_256; } + if(param_set == "XMSS-SHAKE_20_256") + { return XMSS_SHAKE_20_256; } + if(param_set == "XMSS-SHAKE_10_512") + { return XMSS_SHAKE_10_512; } + if(param_set == "XMSS-SHAKE_16_512") + { return XMSS_SHAKE_16_512; } + if(param_set == "XMSS-SHAKE_20_512") + { return XMSS_SHAKE_20_512; } + throw Lookup_Error("Unknown XMSS algorithm param '" + param_set + "'"); + } + +XMSS_Parameters::XMSS_Parameters(const std::string& param_set) + : XMSS_Parameters(XMSS_Parameters::xmss_id_from_string(param_set)) + { + } + +XMSS_Parameters::XMSS_Parameters(xmss_algorithm_t oid) + : m_oid(oid) + { + switch(oid) + { + case XMSS_SHA2_10_256: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_tree_height = 10; + m_name = "XMSS-SHA2_10_256"; + m_hash_name = "SHA-256"; + m_strength = 256; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_256; + break; + case XMSS_SHA2_16_256: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_tree_height = 16; + m_name = "XMSS-SHA2_16_256"; + m_hash_name = "SHA-256"; + m_strength = 256; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_256; + break; + case XMSS_SHA2_20_256: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_tree_height = 20; + m_name = "XMSS-SHA2_20_256"; + m_hash_name = "SHA-256"; + m_strength = 256; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_256; + break; + case XMSS_SHA2_10_512: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_tree_height = 10; + m_name = "XMSS-SHA2_10_512"; + m_hash_name = "SHA-512"; + m_strength = 512; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_512; + break; + case XMSS_SHA2_16_512: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_tree_height = 16; + m_name = "XMSS-SHA2_16_512"; + m_hash_name = "SHA-512"; + m_strength = 512; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_512; + break; + case XMSS_SHA2_20_512: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_tree_height = 20; + m_name = "XMSS-SHA2_20_512"; + m_hash_name = "SHA-512"; + m_strength = 512; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_512; + break; + case XMSS_SHAKE_10_256: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_tree_height = 10; + m_name = "XMSS-SHAKE_10_256"; + m_hash_name = "SHAKE-128(256)"; + m_strength = 256; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE_256; + break; + case XMSS_SHAKE_16_256: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_tree_height = 16; + m_name = "XMSS-SHAKE_16_256"; + m_hash_name = "SHAKE-128(256)"; + m_strength = 256; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE_256; + break; + case XMSS_SHAKE_20_256: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_tree_height = 20; + m_name = "XMSS-SHAKE_20_256"; + m_hash_name = "SHAKE-128(256)"; + m_strength = 256; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE_256; + break; + case XMSS_SHAKE_10_512: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_tree_height = 10; + m_name = "XMSS-SHAKE_10_512"; + m_hash_name = "SHAKE-256(512)"; + m_strength = 512; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE_512; + break; + case XMSS_SHAKE_16_512: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_tree_height = 16; + m_name = "XMSS-SHAKE_16_512"; + m_hash_name = "SHAKE-256(512)"; + m_strength = 512; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE_512; + break; + case XMSS_SHAKE_20_512: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_tree_height = 20; + m_name = "XMSS-SHAKE_20_512"; + m_hash_name = "SHAKE-256(512)"; + m_strength = 512; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE_512; + break; + default: + throw Not_Implemented("Algorithm id does not match any known XMSS algorithm id:" + std::to_string(oid)); + break; + } + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_parameters.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_parameters.h new file mode 100644 index 0000000000..2f186ac53b --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_parameters.h @@ -0,0 +1,119 @@ +/* + * XMSS Parameters + * (C) 2016,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_PARAMETERS_H_ +#define BOTAN_XMSS_PARAMETERS_H_ + +#include +#include + +namespace Botan { + +/** + * Descibes a signature method for XMSS, as defined in: + * [1] XMSS: Extended Hash-Based Signatures, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + **/ +class BOTAN_PUBLIC_API(2,0) XMSS_Parameters + { + public: + enum xmss_algorithm_t + { + XMSS_SHA2_10_256 = 0x00000001, + XMSS_SHA2_16_256 = 0x00000002, + XMSS_SHA2_20_256 = 0x00000003, + XMSS_SHA2_10_512 = 0x00000004, + XMSS_SHA2_16_512 = 0x00000005, + XMSS_SHA2_20_512 = 0x00000006, + XMSS_SHAKE_10_256 = 0x00000007, + XMSS_SHAKE_16_256 = 0x00000008, + XMSS_SHAKE_20_256 = 0x00000009, + XMSS_SHAKE_10_512 = 0x0000000a, + XMSS_SHAKE_16_512 = 0x0000000b, + XMSS_SHAKE_20_512 = 0x0000000c + }; + + static xmss_algorithm_t xmss_id_from_string(const std::string& algo_name); + + XMSS_Parameters(const std::string& algo_name); + XMSS_Parameters(xmss_algorithm_t oid); + + /** + * @return XMSS registry name for the chosen parameter set. + **/ + const std::string& name() const + { + return m_name; + } + + const std::string& hash_function_name() const + { + return m_hash_name; + } + + /** + * Retrieves the uniform length of a message, and the size of + * each node. This correlates to XMSS parameter "n" defined + * in [1]. + * + * @return element length in bytes. + **/ + size_t element_size() const { return m_element_size; } + + /** + * @returns The height (number of levels - 1) of the tree + **/ + size_t tree_height() const { return m_tree_height; } + + /** + * The Winternitz parameter. + * + * @return numeric base used for internal representation of + * data. + **/ + size_t wots_parameter() const { return m_w; } + + size_t len() const { return m_len; } + + xmss_algorithm_t oid() const { return m_oid; } + + XMSS_WOTS_Parameters::ots_algorithm_t ots_oid() const + { + return m_wots_oid; + } + + /** + * Returns the estimated pre-quantum security level of + * the chosen algorithm. + **/ + size_t estimated_strength() const + { + return m_strength; + } + + bool operator==(const XMSS_Parameters& p) const + { + return m_oid == p.m_oid; + } + + private: + xmss_algorithm_t m_oid; + XMSS_WOTS_Parameters::ots_algorithm_t m_wots_oid; + std::string m_name; + std::string m_hash_name; + size_t m_element_size; + size_t m_tree_height; + size_t m_w; + size_t m_len; + size_t m_strength; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_privatekey.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_privatekey.cpp new file mode 100644 index 0000000000..c497be003a --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_privatekey.cpp @@ -0,0 +1,405 @@ +/* + * XMSS Private Key + * An XMSS: Extended Hash-Based Siganture private key. + * The XMSS private key does not support the X509 and PKCS7 standard. Instead + * the raw format described in [1] is used. + * + * [1] XMSS: Extended Hash-Based Signatures, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + * + * (C) 2016,2017,2018 Matthias Gierlings + * (C) 2019 Jack Lloyd + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include +#include +#include +#include +#include +#include + +#if defined(BOTAN_HAS_THREAD_UTILS) + #include +#endif + +namespace Botan { + +namespace { + +// fall back to raw decoding for previous versions, which did not encode an OCTET STRING +secure_vector extract_raw_key(const secure_vector& key_bits) + { + secure_vector raw_key; + try + { + BER_Decoder(key_bits).decode(raw_key, OCTET_STRING); + } + catch(Decoding_Error&) + { + raw_key = key_bits; + } + return raw_key; + } + +} + +XMSS_PrivateKey::XMSS_PrivateKey(const secure_vector& key_bits) + : XMSS_PublicKey(unlock(key_bits)), + m_wots_priv_key(m_wots_params.oid(), m_public_seed), + m_hash(xmss_hash_function()), + m_index_reg(XMSS_Index_Registry::get_instance()) + { + /* + The code requires sizeof(size_t) >= ceil(tree_height / 8) + + Maximum supported tree height is 20, ceil(20/8) == 3, so 4 byte + size_t is sufficient for all defined parameters, or even a + (hypothetical) tree height 32, which would be extremely slow to + compute. + */ + static_assert(sizeof(size_t) >= 4, "size_t is big enough to support leaf index"); + + secure_vector raw_key = extract_raw_key(key_bits); + + if(raw_key.size() != XMSS_PrivateKey::size()) + { + throw Decoding_Error("Invalid XMSS private key size"); + } + + // extract & copy unused leaf index from raw_key + uint64_t unused_leaf = 0; + auto begin = (raw_key.begin() + XMSS_PublicKey::size()); + auto end = raw_key.begin() + XMSS_PublicKey::size() + sizeof(uint32_t); + + for(auto& i = begin; i != end; i++) + { + unused_leaf = ((unused_leaf << 8) | *i); + } + + if(unused_leaf >= (1ull << XMSS_PublicKey::m_xmss_params.tree_height())) + { + throw Decoding_Error("XMSS private key leaf index out of bounds"); + } + + begin = end; + end = begin + XMSS_PublicKey::m_xmss_params.element_size(); + m_prf.clear(); + m_prf.reserve(XMSS_PublicKey::m_xmss_params.element_size()); + std::copy(begin, end, std::back_inserter(m_prf)); + + begin = end; + end = begin + m_wots_params.element_size(); + m_wots_priv_key.set_private_seed(secure_vector(begin, end)); + set_unused_leaf_index(static_cast(unused_leaf)); + } + +XMSS_PrivateKey::XMSS_PrivateKey( + XMSS_Parameters::xmss_algorithm_t xmss_algo_id, + RandomNumberGenerator& rng) + : XMSS_PublicKey(xmss_algo_id, rng), + m_wots_priv_key(XMSS_PublicKey::m_xmss_params.ots_oid(), + public_seed(), + rng), + m_hash(xmss_hash_function()), + m_prf(rng.random_vec(XMSS_PublicKey::m_xmss_params.element_size())), + m_index_reg(XMSS_Index_Registry::get_instance()) + { + XMSS_Address adrs; + set_root(tree_hash(0, + XMSS_PublicKey::m_xmss_params.tree_height(), + adrs)); + } + + +XMSS_PrivateKey::XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id, + size_t idx_leaf, + const secure_vector& wots_priv_seed, + const secure_vector& prf, + const secure_vector& root, + const secure_vector& public_seed) + : XMSS_PublicKey(xmss_algo_id, root, public_seed), + m_wots_priv_key(XMSS_PublicKey::m_xmss_params.ots_oid(), + public_seed, + wots_priv_seed), + m_hash(XMSS_PublicKey::m_xmss_params.hash_function_name()), + m_prf(prf), + m_index_reg(XMSS_Index_Registry::get_instance()) + { + set_unused_leaf_index(idx_leaf); + } + +secure_vector +XMSS_PrivateKey::tree_hash(size_t start_idx, + size_t target_node_height, + XMSS_Address& adrs) + { + BOTAN_ASSERT_NOMSG(target_node_height <= 30); + BOTAN_ASSERT((start_idx % (static_cast(1) << target_node_height)) == 0, + "Start index must be divisible by 2^{target node height}."); + +#if defined(BOTAN_HAS_THREAD_UTILS) + // dertermine number of parallel tasks to split the tree_hashing into. + + Thread_Pool& thread_pool = Thread_Pool::global_instance(); + + const size_t split_level = std::min(target_node_height, thread_pool.worker_count()); + + // skip parallelization overhead for leaf nodes. + if(split_level == 0) + { + secure_vector result; + tree_hash_subtree(result, start_idx, target_node_height, adrs); + return result; + } + + const size_t subtrees = static_cast(1) << split_level; + const size_t last_idx = (static_cast(1) << (target_node_height)) + start_idx; + const size_t offs = (last_idx - start_idx) / subtrees; + // this cast cannot overflow because target_node_height is limited + uint8_t level = static_cast(split_level); // current level in the tree + + BOTAN_ASSERT((last_idx - start_idx) % subtrees == 0, + "Number of worker threads in tree_hash need to divide range " + "of calculated nodes."); + + std::vector> nodes( + subtrees, + secure_vector(XMSS_PublicKey::m_xmss_params.element_size())); + std::vector node_addresses(subtrees, adrs); + std::vector xmss_hash(subtrees, m_hash); + std::vector> work; + + // Calculate multiple subtrees in parallel. + for(size_t i = 0; i < subtrees; i++) + { + using tree_hash_subtree_fn_t = + void (XMSS_PrivateKey::*)(secure_vector&, + size_t, + size_t, + XMSS_Address&, + XMSS_Hash&); + + tree_hash_subtree_fn_t work_fn = &XMSS_PrivateKey::tree_hash_subtree; + + work.push_back(thread_pool.run( + work_fn, + this, + std::ref(nodes[i]), + start_idx + i * offs, + target_node_height - split_level, + std::ref(node_addresses[i]), + std::ref(xmss_hash[i]))); + } + + for(auto& w : work) + { + w.get(); + } + work.clear(); + + // Parallelize the top tree levels horizontally + while(level-- > 1) + { + std::vector> ro_nodes( + nodes.begin(), nodes.begin() + (static_cast(1) << (level+1))); + + for(size_t i = 0; i < (static_cast(1) << level); i++) + { + BOTAN_ASSERT_NOMSG(xmss_hash.size() > i); + + node_addresses[i].set_tree_height(static_cast(target_node_height - (level + 1))); + node_addresses[i].set_tree_index( + (node_addresses[2 * i + 1].get_tree_index() - 1) >> 1); + + work.push_back(thread_pool.run( + &XMSS_Common_Ops::randomize_tree_hash, + std::ref(nodes[i]), + std::cref(ro_nodes[2 * i]), + std::cref(ro_nodes[2 * i + 1]), + std::ref(node_addresses[i]), + std::cref(this->public_seed()), + std::ref(xmss_hash[i]), + std::cref(m_xmss_params))); + } + + for(auto &w : work) + { + w.get(); + } + work.clear(); + } + + // Avoid creation an extra thread to calculate root node. + node_addresses[0].set_tree_height(static_cast(target_node_height - 1)); + node_addresses[0].set_tree_index( + (node_addresses[1].get_tree_index() - 1) >> 1); + XMSS_Common_Ops::randomize_tree_hash(nodes[0], + nodes[0], + nodes[1], + node_addresses[0], + this->public_seed(), + m_hash, + m_xmss_params); + return nodes[0]; +#else + secure_vector result; + tree_hash_subtree(result, start_idx, target_node_height, adrs, m_hash); + return result; +#endif + } + +void +XMSS_PrivateKey::tree_hash_subtree(secure_vector& result, + size_t start_idx, + size_t target_node_height, + XMSS_Address& adrs, + XMSS_Hash& hash) + { + const secure_vector& seed = this->public_seed(); + + std::vector> nodes( + target_node_height + 1, + secure_vector(XMSS_PublicKey::m_xmss_params.element_size())); + + // node stack, holds all nodes on stack and one extra "pending" node. This + // temporary node referred to as "node" in the XMSS standard document stays + // a pending element, meaning it is not regarded as element on the stack + // until level is increased. + std::vector node_levels(target_node_height + 1); + + uint8_t level = 0; // current level on the node stack. + XMSS_WOTS_PublicKey pk(m_wots_priv_key.wots_parameters().oid(), seed); + const size_t last_idx = (static_cast(1) << target_node_height) + start_idx; + + for(size_t i = start_idx; i < last_idx; i++) + { + adrs.set_type(XMSS_Address::Type::OTS_Hash_Address); + adrs.set_ots_address(static_cast(i)); + this->wots_private_key().generate_public_key( + pk, + // getWOTS_SK(SK, s + i), reference implementation uses adrs + // instead of zero padded index s + i. + this->wots_private_key().at(adrs, hash), + adrs, + hash); + adrs.set_type(XMSS_Address::Type::LTree_Address); + adrs.set_ltree_address(static_cast(i)); + XMSS_Common_Ops::create_l_tree(nodes[level], pk, adrs, seed, hash, m_xmss_params); + node_levels[level] = 0; + + adrs.set_type(XMSS_Address::Type::Hash_Tree_Address); + adrs.set_tree_height(0); + adrs.set_tree_index(static_cast(i)); + + while(level > 0 && node_levels[level] == + node_levels[level - 1]) + { + adrs.set_tree_index(((adrs.get_tree_index() - 1) >> 1)); + XMSS_Common_Ops::randomize_tree_hash(nodes[level - 1], + nodes[level - 1], + nodes[level], + adrs, + seed, + hash, + m_xmss_params); + node_levels[level - 1]++; + level--; //Pop stack top element + adrs.set_tree_height(adrs.get_tree_height() + 1); + } + level++; //push temporary node to stack + } + result = nodes[level - 1]; + } + +secure_vector XMSS_PrivateKey::private_key_bits() const + { + return DER_Encoder().encode(raw_private_key(), OCTET_STRING).get_contents(); + } + +std::shared_ptr> +XMSS_PrivateKey::recover_global_leaf_index() const + { + BOTAN_ASSERT(m_wots_priv_key.private_seed().size() == + XMSS_PublicKey::m_xmss_params.element_size() && + m_prf.size() == XMSS_PublicKey::m_xmss_params.element_size(), + "Trying to retrieve index for partially initialized key"); + return m_index_reg.get(m_wots_priv_key.private_seed(), m_prf); + } + +void XMSS_PrivateKey::set_unused_leaf_index(size_t idx) + { + if(idx >= (1ull << XMSS_PublicKey::m_xmss_params.tree_height())) + { + throw Decoding_Error("XMSS private key leaf index out of bounds"); + } + else + { + std::atomic& index = + static_cast&>(*recover_global_leaf_index()); + size_t current = 0; + + do + { + current = index.load(); + if(current > idx) + { return; } + } + while(!index.compare_exchange_strong(current, idx)); + } + } + +size_t XMSS_PrivateKey::reserve_unused_leaf_index() + { + size_t idx = (static_cast&>( + *recover_global_leaf_index())).fetch_add(1); + if(idx >= (1ull << XMSS_PublicKey::m_xmss_params.tree_height())) + { + throw Decoding_Error("XMSS private key, one time signatures exhaused"); + } + return idx; + } + +size_t XMSS_PrivateKey::unused_leaf_index() const + { + return *recover_global_leaf_index(); + } + +secure_vector XMSS_PrivateKey::raw_private_key() const + { + std::vector pk { raw_public_key() }; + secure_vector result(pk.begin(), pk.end()); + result.reserve(size()); + + for(int i = 3; i >= 0; i--) + { + result.push_back( + static_cast( + static_cast(unused_leaf_index()) >> 8 * i)); + } + + std::copy(m_prf.begin(), m_prf.end(), std::back_inserter(result)); + std::copy(m_wots_priv_key.private_seed().begin(), + m_wots_priv_key.private_seed().end(), + std::back_inserter(result)); + + return result; + } + +std::unique_ptr +XMSS_PrivateKey::create_signature_op(RandomNumberGenerator&, + const std::string&, + const std::string& provider) const + { + if(provider == "base" || provider.empty()) + return std::unique_ptr( + new XMSS_Signature_Operation(*this)); + + throw Provider_Not_Found(algo_name(), provider); + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_privatekey.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_privatekey.h new file mode 100644 index 0000000000..dc040e4437 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_privatekey.h @@ -0,0 +1,13 @@ +/* + * (C) 2016,2017,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_PRIVATEKEY_H_ +#define BOTAN_XMSS_PRIVATEKEY_H_ + +#include +BOTAN_DEPRECATED_HEADER(xmss_privatekey.h) + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_publickey.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_publickey.cpp new file mode 100644 index 0000000000..f6db6d5026 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_publickey.cpp @@ -0,0 +1,129 @@ +/* + * XMSS Public Key + * An XMSS: Extended Hash-Based Siganture 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, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + * + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include +#include +#include +#include + +namespace Botan { + +namespace { + +// fall back to raw decoding for previous versions, which did not encode an OCTET STRING +std::vector extract_raw_key(const std::vector& key_bits) + { + std::vector raw_key; + try + { + BER_Decoder(key_bits).decode(raw_key, OCTET_STRING); + } + catch(Decoding_Error&) + { + raw_key = key_bits; + } + return raw_key; + } + +} + +XMSS_PublicKey::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())) + {} + +XMSS_PublicKey::XMSS_PublicKey(const std::vector& key_bits) + : m_raw_key(extract_raw_key(key_bits)), + m_xmss_params(XMSS_PublicKey::deserialize_xmss_oid(m_raw_key)), + m_wots_params(m_xmss_params.ots_oid()) + { + if(m_raw_key.size() < XMSS_PublicKey::size()) + { + throw Decoding_Error("Invalid XMSS public key size detected"); + } + + // extract & copy root from raw key + m_root.clear(); + m_root.reserve(m_xmss_params.element_size()); + auto begin = m_raw_key.begin() + sizeof(uint32_t); + auto end = begin + m_xmss_params.element_size(); + std::copy(begin, end, std::back_inserter(m_root)); + + // extract & copy public seed from raw key + begin = end; + end = begin + m_xmss_params.element_size(); + m_public_seed.clear(); + m_public_seed.reserve(m_xmss_params.element_size()); + std::copy(begin, end, std::back_inserter(m_public_seed)); + } + +XMSS_Parameters::xmss_algorithm_t +XMSS_PublicKey::deserialize_xmss_oid(const std::vector& raw_key) + { + if(raw_key.size() < 4) + { + throw Decoding_Error("XMSS signature OID missing."); + } + + // extract and convert algorithm id to enum type + uint32_t raw_id = 0; + for(size_t i = 0; i < 4; i++) + { raw_id = ((raw_id << 8) | raw_key[i]); } + + return static_cast(raw_id); + } + +std::unique_ptr +XMSS_PublicKey::create_verification_op(const std::string&, + const std::string& provider) const + { + if(provider == "base" || provider.empty()) + { + return std::unique_ptr( + new XMSS_Verification_Operation(*this)); + } + throw Provider_Not_Found(algo_name(), provider); + } + +std::vector XMSS_PublicKey::raw_public_key() const + { + std::vector result + { + static_cast(m_xmss_params.oid() >> 24), + static_cast(m_xmss_params.oid() >> 16), + static_cast(m_xmss_params.oid() >> 8), + static_cast(m_xmss_params.oid()) + }; + + std::copy(m_root.begin(), m_root.end(), std::back_inserter(result)); + std::copy(m_public_seed.begin(), + m_public_seed.end(), + std::back_inserter(result)); + + return result; + } + +std::vector XMSS_PublicKey::public_key_bits() const + { + std::vector output; + DER_Encoder(output).encode(raw_public_key(), OCTET_STRING); + return output; + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_publickey.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_publickey.h new file mode 100644 index 0000000000..eba27fc95f --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_publickey.h @@ -0,0 +1,14 @@ +/* + * (C) 2016,2017,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_PUBLICKEY_H_ +#define BOTAN_XMSS_PUBLICKEY_H_ + +#include +BOTAN_DEPRECATED_HEADER(xmss_publickey.h) + +#endif + diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature.cpp new file mode 100644 index 0000000000..98fadff358 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature.cpp @@ -0,0 +1,92 @@ +/* + * XMSS Signature + * (C) 2016,2017,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include + +namespace Botan { + +XMSS_Signature::XMSS_Signature(XMSS_Parameters::xmss_algorithm_t oid, + const secure_vector& raw_sig) + : m_leaf_idx(0), m_randomness(0, 0x00), m_tree_sig() + { + XMSS_Parameters xmss_params(oid); + + if(raw_sig.size() != (xmss_params.len() + xmss_params.tree_height() + 1) + * xmss_params.element_size() + sizeof(uint32_t)) + { + throw Decoding_Error("XMSS signature size invalid."); + } + + for(size_t i = 0; i < 4; i++) + { m_leaf_idx = ((m_leaf_idx << 8) | raw_sig[i]); } + + if(m_leaf_idx >= (1ull << xmss_params.tree_height())) + { + throw Decoding_Error("XMSS signature leaf index out of bounds."); + } + + auto begin = raw_sig.begin() + sizeof(uint32_t); + auto end = begin + xmss_params.element_size(); + std::copy(begin, end, std::back_inserter(m_randomness)); + + for(size_t i = 0; i < xmss_params.len(); i++) + { + begin = end; + end = begin + xmss_params.element_size(); + m_tree_sig.ots_signature().push_back(secure_vector(0)); + m_tree_sig.ots_signature().back().reserve( + xmss_params.element_size()); + std::copy(begin, + end, + std::back_inserter(m_tree_sig.ots_signature().back())); + } + + for(size_t i = 0; i < xmss_params.tree_height(); i++) + { + begin = end; + end = begin + xmss_params.element_size(); + m_tree_sig.authentication_path().push_back(secure_vector(0)); + m_tree_sig.authentication_path().back().reserve( + xmss_params.element_size()); + std::copy(begin, + end, + std::back_inserter(m_tree_sig.authentication_path().back())); + } + } + +secure_vector XMSS_Signature::bytes() const + { + secure_vector result + { + static_cast(m_leaf_idx >> 24U), + static_cast(m_leaf_idx >> 16U), + static_cast(m_leaf_idx >> 8U), + static_cast(m_leaf_idx) + }; + + std::copy(m_randomness.begin(), + m_randomness.end(), + std::back_inserter(result)); + + for(const auto& sig : tree().ots_signature()) + { + std::copy(sig.begin(), + sig.end(), + std::back_inserter(result)); + } + + for(const auto& auth : tree().authentication_path()) + { + std::copy(auth.begin(), + auth.end(), + std::back_inserter(result)); + } + return result; + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature.h new file mode 100644 index 0000000000..d791dbedb8 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature.h @@ -0,0 +1,127 @@ +/* + * XMSS Signature + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_SIGNATURE_H_ +#define BOTAN_XMSS_SIGNATURE_H_ + +#include +#include +#include +#include +#include +#include + +namespace Botan { + +class XMSS_Signature final + { + public: + /** + * Creates a signature from an XMSS signature method and a uint8_t sequence + * representing a raw signature. + * + * @param oid XMSS signature method + * @param raw_sig An XMSS signature serialized using + * XMSS_Signature::bytes(). + **/ + XMSS_Signature(XMSS_Parameters::xmss_algorithm_t oid, + const secure_vector& raw_sig); + + /** + * Creates an XMSS Signature from a leaf index used for signature + * generation, a random value and a tree signature. + * + * @param leaf_idx Leaf index used to generate the signature. + * @param randomness A random value. + * @param tree_sig A tree signature. + **/ + XMSS_Signature(size_t leaf_idx, + const secure_vector& randomness, + const XMSS_WOTS_PublicKey::TreeSignature& tree_sig) + : m_leaf_idx(leaf_idx), m_randomness(randomness), + m_tree_sig(tree_sig) {} + + /** + * Creates an XMSS Signature from a leaf index used for signature + * generation, a random value and a tree signature. + * + * @param leaf_idx Leaf index used to generate the signature. + * @param randomness A random value. + * @param tree_sig A tree signature. + **/ + XMSS_Signature(size_t leaf_idx, + secure_vector&& randomness, + XMSS_WOTS_PublicKey::TreeSignature&& tree_sig) + : m_leaf_idx(leaf_idx), m_randomness(std::move(randomness)), + m_tree_sig(std::move(tree_sig)) {} + + size_t unused_leaf_index() const { return m_leaf_idx; } + void set_unused_leaf_idx(size_t idx) { m_leaf_idx = idx; } + + const secure_vector randomness() const + { + return m_randomness; + } + + secure_vector& randomness() + { + return m_randomness; + } + + void set_randomness(const secure_vector& randomness) + { + m_randomness = randomness; + } + + void set_randomness(secure_vector&& randomness) + { + m_randomness = std::move(randomness); + } + + const XMSS_WOTS_PublicKey::TreeSignature& tree() const + { + return m_tree_sig; + } + + XMSS_WOTS_PublicKey::TreeSignature& tree() + { + return m_tree_sig; + } + + void set_tree(const XMSS_WOTS_PublicKey::TreeSignature& tree_sig) + { + m_tree_sig = tree_sig; + } + + void set_tree(XMSS_WOTS_PublicKey::TreeSignature&& tree_sig) + { + m_tree_sig = std::move(tree_sig); + } + + /** + * Generates a serialized representation of XMSS Signature by + * concatenating the following elements in order: + * 4-byte leaf index, n-bytes randomness, ots_signature, + * authentication path. + * + * n is the element_size(), len equal to len(), h the tree height + * defined by the chosen XMSS signature method. + * + * @return serialized signature, a sequence of + * 4+(len + h + 1)n bytes. + **/ + secure_vector bytes() const; + + private: + size_t m_leaf_idx; + secure_vector m_randomness; + XMSS_WOTS_PublicKey::TreeSignature m_tree_sig; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature_operation.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature_operation.cpp new file mode 100644 index 0000000000..49f1041d90 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature_operation.cpp @@ -0,0 +1,120 @@ +/* + * XMSS Signature Operation + * Signature generation operation for Extended Hash-Based Signatures (XMSS) as + * defined in: + * + * [1] XMSS: Extended Hash-Based Signatures, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + * + * (C) 2016,2017,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include + +namespace Botan { + +XMSS_Signature_Operation::XMSS_Signature_Operation( + const XMSS_PrivateKey& private_key) : + m_priv_key(private_key), + m_xmss_params(private_key.xmss_oid()), + m_hash(private_key.xmss_hash_function()), + m_randomness(0), + m_leaf_idx(0), + m_is_initialized(false) + {} + +XMSS_WOTS_PublicKey::TreeSignature +XMSS_Signature_Operation::generate_tree_signature(const secure_vector& 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& 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; + } + +size_t XMSS_Signature_Operation::signature_length() const + { + return sizeof(uint64_t) + // size of leaf index + m_xmss_params.element_size() + + m_xmss_params.len() * m_xmss_params.element_size() + + m_xmss_params.tree_height() * m_xmss_params.element_size(); + } + +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 / (1ULL << j)) ^ 0x01; + auth_path[j] = priv_key.tree_hash(k * (1ULL << j), j, adrs); + } + + return auth_path; + } + +void XMSS_Signature_Operation::update(const uint8_t msg[], size_t msg_len) + { + initialize(); + m_hash.h_msg_update(msg, msg_len); + } + +secure_vector +XMSS_Signature_Operation::sign(RandomNumberGenerator&) + { + initialize(); + secure_vector 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 index_bytes; + // reserve leaf index so it can not be reused in by another signature + // operation using the same private key. + m_leaf_idx = static_cast(m_priv_key.reserve_unused_leaf_index()); + + // write prefix for message hashing into buffer. + XMSS_Tools::concat(index_bytes, m_leaf_idx, 32); + m_randomness = m_hash.prf(m_priv_key.prf(), index_bytes); + index_bytes.clear(); + XMSS_Tools::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; + } + +} + diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature_operation.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature_operation.h new file mode 100644 index 0000000000..e6fb2c7114 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_signature_operation.h @@ -0,0 +1,89 @@ +/* + * XMSS Signature Operation + * (C) 2016,2017,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_SIGNATURE_OPERATION_H_ +#define BOTAN_XMSS_SIGNATURE_OPERATION_H_ + +#include +#include +#include +#include +#include + +namespace Botan { + +/** + * Signature generation operation for Extended Hash-Based Signatures (XMSS) as + * defined in: + * + * [1] XMSS: Extended Hash-Based Signatures, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + **/ +class XMSS_Signature_Operation final : public virtual PK_Ops::Signature + { + public: + XMSS_Signature_Operation(const XMSS_PrivateKey& private_key); + + /** + * Creates an XMSS signature for the message provided through call to + * update(). + * + * @return serialized XMSS signature. + **/ + secure_vector sign(RandomNumberGenerator&) override; + + void update(const uint8_t msg[], size_t msg_len) override; + + size_t signature_length() const override; + + private: + /** + * Algorithm 11: "treeSig" + * Generate a WOTS+ signature on a message with corresponding auth path. + * + * @param msg A message. + * @param xmss_priv_key A XMSS private key. + * @param adrs A XMSS Address. + **/ + XMSS_WOTS_PublicKey::TreeSignature generate_tree_signature( + const secure_vector& msg, + XMSS_PrivateKey& xmss_priv_key, + XMSS_Address& adrs); + + /** + * Algorithm 12: "XMSS_sign" + * Generate an XMSS signature and update the XMSS secret key + * + * @param msg A message to sign of arbitrary length. + * @param [out] xmss_priv_key A XMSS private key. The private key will be + * updated during the signing process. + * + * @return The signature of msg signed using xmss_priv_key. + **/ + XMSS_Signature sign( + const secure_vector& msg, + XMSS_PrivateKey& xmss_priv_key); + + wots_keysig_t build_auth_path(XMSS_PrivateKey& priv_key, + XMSS_Address& adrs); + + void initialize(); + + XMSS_PrivateKey m_priv_key; + const XMSS_Parameters m_xmss_params; + XMSS_Hash m_hash; + secure_vector m_randomness; + uint32_t m_leaf_idx; + bool m_is_initialized; + }; + +} + +#endif + diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_tools.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_tools.h new file mode 100644 index 0000000000..81d17f5bfe --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_tools.h @@ -0,0 +1,108 @@ +/* + * XMSS Tools + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_TOOLS_H_ +#define BOTAN_XMSS_TOOLS_H_ + +#include +#include +#include +#include + +//BOTAN_FUTURE_INTERNAL_HEADER(xmss_tools.h) + +namespace Botan { + +/** + * Helper tools for low level byte operations required + * for the XMSS implementation. + **/ +class XMSS_Tools final + { + public: + XMSS_Tools(const XMSS_Tools&) = delete; + void operator=(const XMSS_Tools&) = delete; + + /** + * Concatenates the byte representation in big-endian order of any + * integral value to a secure_vector. + * + * @param target Vector to concatenate the byte representation of the + * integral value to. + * @param src integral value to concatenate. + **/ + template::value, + void>::type> + static void concat(secure_vector& target, const T& src); + + /** + * Concatenates the last n bytes of the byte representation in big-endian + * order of any integral value to a to a secure_vector. + * + * @param target Vector to concatenate the byte representation of the + * integral value to. + * @param src Integral value to concatenate. + * @param len number of bytes to concatenate. This value must be smaller + * or equal to the size of type T. + **/ + template ::value, + void>::type> + static void concat(secure_vector& target, const T& src, size_t len); + + private: + XMSS_Tools(); + }; + +template +void XMSS_Tools::concat(secure_vector& target, const T& src) + { + const uint8_t* src_bytes = reinterpret_cast(&src); + if(CPUID::is_little_endian()) + { + std::reverse_copy(src_bytes, + src_bytes + sizeof(src), + std::back_inserter(target)); + } + else + { + std::copy(src_bytes, + src_bytes + sizeof(src), + std::back_inserter(target)); + } + } + + +template +void XMSS_Tools::concat(secure_vector& target, + const T& src, + size_t len) + { + size_t c = static_cast(std::min(len, sizeof(src))); + if(len > sizeof(src)) + { + target.resize(target.size() + len - sizeof(src), 0); + } + + const uint8_t* src_bytes = reinterpret_cast(&src); + if(CPUID::is_little_endian()) + { + std::reverse_copy(src_bytes, + src_bytes + c, + std::back_inserter(target)); + } + else + { + std::copy(src_bytes + sizeof(src) - c, + src_bytes + sizeof(src), + std::back_inserter(target)); + } + } +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_verification_operation.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_verification_operation.cpp new file mode 100644 index 0000000000..b9442aa03d --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_verification_operation.cpp @@ -0,0 +1,138 @@ +/* + * XMSS Verification Operation + * Provides signature verification capabilities for Extended Hash-Based + * Signatures (XMSS). + * + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include +#include +#include + +namespace Botan { + +XMSS_Verification_Operation::XMSS_Verification_Operation( + const XMSS_PublicKey& public_key) : + m_pub_key(public_key), + m_hash(public_key.xmss_hash_function()), + m_msg_buf(0) + { + } + +secure_vector +XMSS_Verification_Operation::root_from_signature(const XMSS_Signature& sig, + const secure_vector& msg, + XMSS_Address& adrs, + const secure_vector& seed) + { + const auto params = m_pub_key.xmss_parameters(); + + const uint32_t next_index = static_cast(sig.unused_leaf_index()); + adrs.set_type(XMSS_Address::Type::OTS_Hash_Address); + adrs.set_ots_address(next_index); + + XMSS_WOTS_PublicKey pub_key_ots(m_pub_key.wots_parameters().oid(), + msg, + sig.tree().ots_signature(), + adrs, + seed); + + adrs.set_type(XMSS_Address::Type::LTree_Address); + adrs.set_ltree_address(next_index); + + std::array, 2> node; + XMSS_Common_Ops::create_l_tree(node[0], pub_key_ots, adrs, seed, m_hash, params); + + adrs.set_type(XMSS_Address::Type::Hash_Tree_Address); + adrs.set_tree_index(next_index); + + for(size_t k = 0; k < params.tree_height(); k++) + { + adrs.set_tree_height(static_cast(k)); + if(((next_index / (static_cast(1) << k)) & 0x01) == 0) + { + adrs.set_tree_index(adrs.get_tree_index() >> 1); + XMSS_Common_Ops::randomize_tree_hash(node[1], + node[0], + sig.tree().authentication_path()[k], + adrs, + seed, + m_hash, + params); + } + else + { + adrs.set_tree_index((adrs.get_tree_index() - 1) >> 1); + XMSS_Common_Ops::randomize_tree_hash(node[1], + sig.tree().authentication_path()[k], + node[0], + adrs, + seed, + m_hash, + params); + } + node[0] = node[1]; + } + return node[0]; + } + +bool +XMSS_Verification_Operation::verify(const XMSS_Signature& sig, + const secure_vector& msg, + const XMSS_PublicKey& public_key) + { + XMSS_Address adrs; + secure_vector index_bytes; + XMSS_Tools::concat(index_bytes, + sig.unused_leaf_index(), + m_pub_key.xmss_parameters().element_size()); + secure_vector msg_digest = + m_hash.h_msg(sig.randomness(), + public_key.root(), + index_bytes, + msg); + + secure_vector node = root_from_signature(sig, + msg_digest, + adrs, + public_key.public_seed()); + + return (node == public_key.root()); + } + +// FIXME: XMSS signature verification requires the "randomness" parameter out +// of the XMSS signature, which is part of the prefix that is hashed before +// msg. 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, make sign a parameterless member call. +void XMSS_Verification_Operation::update(const uint8_t msg[], size_t msg_len) + { + std::copy(msg, msg + msg_len, std::back_inserter(m_msg_buf)); + } + +bool XMSS_Verification_Operation::is_valid_signature(const uint8_t sig[], + size_t sig_len) + { + try + { + XMSS_Signature signature(m_pub_key.xmss_parameters().oid(), + secure_vector(sig, sig + sig_len)); + bool result = verify(signature, m_msg_buf, m_pub_key); + m_msg_buf.clear(); + return result; + } + catch(...) + { + m_msg_buf.clear(); + return false; + } + } + +} + diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_verification_operation.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_verification_operation.h new file mode 100644 index 0000000000..f96b3803bc --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_verification_operation.h @@ -0,0 +1,71 @@ +/* + * XMSS Verification Operation + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_VERIFICATION_OPERATION_H_ +#define BOTAN_XMSS_VERIFICATION_OPERATION_H_ + +#include +#include +#include + +namespace Botan { + +/** + * Provides signature verification capabilities for Extended Hash-Based + * Signatures (XMSS). + **/ + class XMSS_Verification_Operation final : public virtual PK_Ops::Verification + { + public: + XMSS_Verification_Operation( + const XMSS_PublicKey& public_key); + + bool is_valid_signature(const uint8_t sig[], size_t sig_len) override; + + void update(const uint8_t msg[], size_t msg_len) override; + + private: + /** + * Algorithm 13: "XMSS_rootFromSig" + * Computes a root node using an XMSS signature, a message and a seed. + * + * @param msg A message. + * @param sig The XMSS signature for msg. + * @param ards A XMSS tree address. + * @param seed A seed. + * + * @return An n-byte string holding the value of the root of a tree + * defined by the input parameters. + **/ + secure_vector root_from_signature( + const XMSS_Signature& sig, + const secure_vector& msg, + XMSS_Address& ards, + const secure_vector& seed); + + /** + * Algorithm 14: "XMSS_verify" + * Verifies a XMSS signature using the corresponding XMSS public key. + * + * @param sig A XMSS signature. + * @param msg The message signed with sig. + * @param pub_key the public key + * + * @return true if signature sig is valid for msg, false otherwise. + **/ + bool verify(const XMSS_Signature& sig, + const secure_vector& msg, + const XMSS_PublicKey& pub_key); + + const XMSS_PublicKey& m_pub_key; + XMSS_Hash m_hash; + secure_vector m_msg_buf; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots.h new file mode 100644 index 0000000000..d85e889bfb --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots.h @@ -0,0 +1,752 @@ +/* + * XMSS WOTS + * (C) 2016,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_WOTS_H_ +#define BOTAN_XMSS_WOTS_H_ + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace Botan { + +/** + * Descibes a signature method for XMSS Winternitz One Time Signatures, + * as defined in: + * [1] XMSS: Extended Hash-Based Signatures, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + **/ +class XMSS_WOTS_Parameters final + { + public: + enum ots_algorithm_t + { + WOTSP_SHA2_256 = 0x00000001, + WOTSP_SHA2_512 = 0x00000002, + WOTSP_SHAKE_256 = 0x00000003, + WOTSP_SHAKE_512 = 0x00000004 + }; + + XMSS_WOTS_Parameters(const std::string& algo_name); + XMSS_WOTS_Parameters(ots_algorithm_t ots_spec); + + static ots_algorithm_t xmss_wots_id_from_string(const std::string& param_set); + + /** + * Algorithm 1: convert input string to base. + * + * @param msg Input string (referred to as X in [1]). + * @param out_size size of message in base w. + * + * @return Input string converted to the given base. + **/ + secure_vector base_w(const secure_vector& msg, size_t out_size) const; + + secure_vector base_w(size_t value) const; + + void append_checksum(secure_vector& data); + + /** + * @return XMSS WOTS registry name for the chosen parameter set. + **/ + const std::string& name() const + { + return m_name; + } + + /** + * @return Botan name for the hash function used. + **/ + const std::string& hash_function_name() const + { + return m_hash_name; + } + + /** + * Retrieves the uniform length of a message, and the size of + * each node. This correlates to XMSS parameter "n" defined + * in [1]. + * + * @return element length in bytes. + **/ + size_t element_size() const { return m_element_size; } + + /** + * The Winternitz parameter. + * + * @return numeric base used for internal representation of + * data. + **/ + size_t wots_parameter() const { return m_w; } + + size_t len() const { return m_len; } + + size_t len_1() const { return m_len_1; } + + size_t len_2() const { return m_len_2; } + + size_t lg_w() const { return m_lg_w; } + + ots_algorithm_t oid() const { return m_oid; } + + size_t estimated_strength() const { return m_strength; } + + bool operator==(const XMSS_WOTS_Parameters& p) const + { + return m_oid == p.m_oid; + } + + private: + static const std::map m_oid_name_lut; + ots_algorithm_t m_oid; + std::string m_name; + std::string m_hash_name; + size_t m_element_size; + size_t m_w; + size_t m_len_1; + size_t m_len_2; + size_t m_len; + size_t m_strength; + uint8_t m_lg_w; + }; + +class XMSS_Address; + +typedef std::vector> wots_keysig_t; + +/** + * A Winternitz One Time Signature public key for use with Extended Hash-Based + * Signatures. + **/ +class XMSS_WOTS_PublicKey : virtual public Public_Key + { + public: + class TreeSignature final + { + public: + TreeSignature() = default; + + 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 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&& 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& 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& msg, + const wots_keysig_t& sig, + XMSS_Address& adrs, + const secure_vector& 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& operator[](size_t i) const { return m_key[i]; } + secure_vector& 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& public_seed() const { return m_public_seed; } + + secure_vector& public_seed() { return m_public_seed; } + + void set_public_seed(const secure_vector& public_seed) + { + m_public_seed = public_seed; + } + + void set_public_seed(secure_vector&& 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; + } + + std::string algo_name() const override + { + return m_wots_params.name(); + } + + AlgorithmIdentifier algorithm_identifier() const override + { + throw Not_Implemented("No AlgorithmIdentifier available for XMSS-WOTS."); + } + + bool check_key(RandomNumberGenerator&, bool) const override + { + return true; + } + + size_t estimated_strength() const override + { + return m_wots_params.estimated_strength(); + } + + size_t key_length() const override + { + return m_wots_params.estimated_strength(); + } + + std::vector public_key_bits() const override + { + throw Not_Implemented("No 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". + * + * This overload is used in multithreaded scenarios, where it is + * required to provide seperate instances of XMSS_Hash to each + * thread. + * + * @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. + * @param hash Instance of XMSS_Hash, that may only by the thead + * executing chain. + **/ + void chain(secure_vector& x, + size_t start_idx, + size_t steps, + XMSS_Address& adrs, + const secure_vector& public_seed, + XMSS_Hash& hash); + + /** + * 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. + **/ + inline void chain(secure_vector& x, + size_t start_idx, + size_t steps, + XMSS_Address& adrs, + const secure_vector& public_seed) + { + chain(x, start_idx, steps, adrs, public_seed, m_hash); + } + + XMSS_WOTS_Parameters m_wots_params; + XMSS_Hash m_hash; + wots_keysig_t m_key; + secure_vector 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& msg, + const wots_keysig_t& sig, + XMSS_Address& adrs, + const secure_vector& public_seed); + }; + +/** A Winternitz One Time Signature private key for use with Extended Hash-Based + * Signatures. + **/ +class XMSS_WOTS_PrivateKey final : public virtual XMSS_WOTS_PublicKey, + public virtual Private_Key + { + public: + /** + * Creates a WOTS private key for the chosen XMSS WOTS signature method. + * Members need to be initialized manually. + * + * @param oid Identifier for the selected signature method. + **/ + XMSS_WOTS_PrivateKey(XMSS_WOTS_Parameters::ots_algorithm_t oid) + : XMSS_WOTS_PublicKey(oid) + {} + + /** + * Creates a WOTS private key for the chosen XMSS WOTS signature method. + * + * @param oid Identifier for the selected signature method. + * @param rng A random number generator to use for key generation. + **/ + XMSS_WOTS_PrivateKey(XMSS_WOTS_Parameters::ots_algorithm_t oid, + RandomNumberGenerator& rng) + : XMSS_WOTS_PublicKey(oid, rng), + m_private_seed(rng.random_vec(m_wots_params.element_size())) + { + set_key_data(generate(m_private_seed)); + } + + /** + * Constructs a WOTS private key. Chains will be generated on demand + * applying a hash function to a unique value generated from a secret + * seed and a counter. The secret seed of length n, will be + * automatically generated using AutoSeeded_RNG(). "n" equals + * the element size of the chosen WOTS security parameter set. + * + * @param oid Identifier for the selected signature method. + * @param public_seed A public seed used for the pseudo random generation + * of public keys derived from this private key. + * @param rng A random number generator to use for key generation. + **/ + XMSS_WOTS_PrivateKey(XMSS_WOTS_Parameters::ots_algorithm_t oid, + const secure_vector& public_seed, + RandomNumberGenerator& rng) + : XMSS_WOTS_PublicKey(oid, public_seed), + m_private_seed(rng.random_vec(m_wots_params.element_size())) + { + set_key_data(generate(m_private_seed)); + } + + /** + * Constructs a WOTS private key. Chains will be generated on demand + * applying a hash function to a unique value generated from a secret + * seed and a counter. The secret seed of length n, will be + * automatically generated using AutoSeeded_RNG(). "n" equals + * the element size of the chosen WOTS security parameter set. + * + * @param oid Identifier for the selected signature method. + * @param public_seed A public seed used for the pseudo random generation + * of public keys derived from this private key. + **/ + XMSS_WOTS_PrivateKey(XMSS_WOTS_Parameters::ots_algorithm_t oid, + const secure_vector& public_seed) + : XMSS_WOTS_PublicKey(oid, public_seed) + {} + + /** + * Constructs a WOTS private key. Chains will be generated on demand + * applying a hash function to a unique value generated from the + * secret seed and a counter. + * + * @param oid Identifier for the selected signature method. + * @param public_seed A public seed used for the pseudo random generation + * of public keys derived from this private key. + * @param private_seed A secret uniformly random n-byte value. + **/ + XMSS_WOTS_PrivateKey(XMSS_WOTS_Parameters::ots_algorithm_t oid, + const secure_vector& public_seed, + const secure_vector& private_seed) + : XMSS_WOTS_PublicKey(oid, public_seed), + m_private_seed(private_seed) + { + set_key_data(generate(private_seed)); + } + + /** + * Retrieves the i-th WOTS private key using pseudo random key + * (re-)generation. + * + * This overload is used in multithreaded scenarios, where it is + * required to provide seperate instances of XMSS_Hash to each + * thread. + * + * @param i Index of the key to retrieve. + * @param hash Instance of XMSS_Hash, that may only be used by the + * thead executing at. + * + * @return WOTS secret key. + **/ + wots_keysig_t at(size_t i, XMSS_Hash& hash); + + /** + * Retrieves the i-th WOTS private key using pseudo random key + * (re-)generation. + * + * @param i Index of the key to retrieve. + * + * @return WOTS secret key. + **/ + inline wots_keysig_t operator[](size_t i) + { + return this->at(i, m_hash); + } + + /** + * Retrieves the i-th WOTS private key using pseudo random key + * (re-)generation. + * + * This overload is used in multithreaded scenarios, where it is + * required to provide seperate instances of XMSS_Hash to each + * thread. + * + * @param adrs The address of the key to retrieve. + * @param hash Instance of XMSS_Hash, that may only be used by the + * thead executing at. + * + * @return WOTS secret key. + **/ + wots_keysig_t at(const XMSS_Address& adrs, XMSS_Hash& hash); + + inline wots_keysig_t operator[](const XMSS_Address& adrs) + { + return this->at(adrs, m_hash); + } + + wots_keysig_t generate_private_key(const secure_vector& priv_seed); + + /** + * Algorithm 4: "WOTS_genPK" + * Generates a Winternitz One Time Signature+ (WOTS+) Public Key from a + * given private key. + * + * @param adrs Hash function address encoding the address of the WOTS+ + * key pair within a greater structure. + * + * @return A XMSS_WOTS_PublicKey. + **/ + XMSS_WOTS_PublicKey generate_public_key(XMSS_Address& adrs); + + /** + * Algorithm 4: "WOTS_genPK" + * Initializes a Winternitz One Time Signature+ (WOTS+) Public Key's + * key_data() member, with data derived from in_key_data using the + * WOTS chaining function. + * + * This overload is used in multithreaded scenarios, where it is + * required to provide seperate instances of XMSS_Hash to each + * thread. + * + * @param[out] pub_key Public key to initialize key_data() member on. + * @param in_key_data Input key material from private key used for + * public key generation. + * @param adrs Hash function address encoding the address of + * the WOTS+ key pair within a greater structure. + * @param hash Instance of XMSS_Hash, that may only by the thead + * executing generate_public_key. + **/ + void generate_public_key(XMSS_WOTS_PublicKey& pub_key, + wots_keysig_t&& in_key_data, + XMSS_Address& adrs, + XMSS_Hash& hash); + /** + * Algorithm 4: "WOTS_genPK" + * Initializes a Winternitz One Time Signature+ (WOTS+) Public Key's + * key_data() member, with data derived from in_key_data using the + * WOTS chaining function. + * + * @param[out] pub_key Public key to initialize key_data() member on. + * @param in_key_data Input key material from private key used for + * public key generation. + * @param adrs Hash function address encoding the address of + * the WOTS+ key pair within a greater structure. + **/ + inline void generate_public_key(XMSS_WOTS_PublicKey& pub_key, + wots_keysig_t&& in_key_data, + XMSS_Address& adrs) + { + generate_public_key(pub_key, std::forward(in_key_data), adrs, m_hash); + } + + /** + * Algorithm 5: "WOTS_sign" + * Generates a signature from a private key and a message. + * + * @param msg A message to sign. + * @param adrs An OTS hash address identifying the WOTS+ key pair + * used for signing. + * + * @return signature for msg. + **/ + inline wots_keysig_t sign(const secure_vector& msg, + XMSS_Address& adrs) + { + return sign(msg, adrs, m_hash); + } + + /** + * Algorithm 5: "WOTS_sign" + * Generates a signature from a private key and a message. + * + * This overload is used in multithreaded scenarios, where it is + * required to provide seperate instances of XMSS_Hash to each + * thread. + * + * @param msg A message to sign. + * @param adrs An OTS hash address identifying the WOTS+ key pair + * used for signing. + * @param hash Instance of XMSS_Hash, that may only be used by the + * thead executing sign. + * + * @return signature for msg. + **/ + wots_keysig_t sign(const secure_vector& msg, + XMSS_Address& adrs, + XMSS_Hash& hash); + + /** + * Retrieves the secret seed used to generate WOTS+ chains. The seed + * should be a uniformly random n-byte value. + * + * @return secret seed. + **/ + const secure_vector& private_seed() const + { + return m_private_seed; + } + + /** + * Sets the secret seed used to generate WOTS+ chains. The seed + * should be a uniformly random n-byte value. + * + * @param private_seed Uniformly random n-byte value. + **/ + void set_private_seed(const secure_vector& private_seed) + { + m_private_seed = private_seed; + } + + /** + * Sets the secret seed used to generate WOTS+ chains. The seed + * should be a uniformly random n-byte value. + * + * @param private_seed Uniformly random n-byte value. + **/ + void set_private_seed(secure_vector&& private_seed) + { + m_private_seed = std::move(private_seed); + } + + AlgorithmIdentifier + pkcs8_algorithm_identifier() const override + { + throw Not_Implemented("No AlgorithmIdentifier available for XMSS-WOTS."); + } + + secure_vector private_key_bits() const override + { + throw Not_Implemented("No PKCS8 key format defined for XMSS-WOTS."); + } + + private: + /** + * Algorithm 3: "Generating a WOTS+ Private Key". + * Generates a private key. + * + * This overload is used in multithreaded scenarios, where it is + * required to provide seperate instances of XMSS_Hash to each thread. + * + * @param private_seed Uniformly random n-byte value. + * @param[in] hash Instance of XMSS_Hash, that may only be used by the + * thead executing generate. + * + * @returns a vector of length key_size() of vectors of n bytes length + * containing uniformly random data. + **/ + wots_keysig_t generate(const secure_vector& private_seed, + XMSS_Hash& hash); + + inline wots_keysig_t generate(const secure_vector& private_seed) + { + return generate(private_seed, m_hash); + } + + secure_vector m_private_seed; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_addressed_privatekey.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_addressed_privatekey.h new file mode 100644 index 0000000000..debd00ff18 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_addressed_privatekey.h @@ -0,0 +1,68 @@ +/** + * XMSS WOTS Addressed Private Key + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_WOTS_ADDRESSED_PRIVATEKEY_H_ +#define BOTAN_XMSS_WOTS_ADDRESSED_PRIVATEKEY_H_ + +#include +#include +#include + +namespace Botan { + +/** + * Wrapper class to pair an XMSS_WOTS_PrivateKey with an XMSS Address. Since + * the PK_Ops::Signature interface does not allow an extra address + * parameter to be passed to the sign(RandomNumberGenerator&), the address + * needs to be stored together with the key and passed to the + * XMSS_WOTS_Signature_Operation() on creation. + **/ +class XMSS_WOTS_Addressed_PrivateKey final : + public virtual XMSS_WOTS_Addressed_PublicKey, + public virtual Private_Key + { + public: + XMSS_WOTS_Addressed_PrivateKey(const XMSS_WOTS_PrivateKey& private_key) + : XMSS_WOTS_Addressed_PublicKey(private_key), + m_priv_key(private_key) {} + + XMSS_WOTS_Addressed_PrivateKey(const XMSS_WOTS_PrivateKey& private_key, + const XMSS_Address& adrs) + : XMSS_WOTS_Addressed_PublicKey(private_key, adrs), + m_priv_key(private_key) {} + + XMSS_WOTS_Addressed_PrivateKey(XMSS_WOTS_PrivateKey&& private_key) + : XMSS_WOTS_Addressed_PublicKey(XMSS_WOTS_PublicKey(private_key)), + m_priv_key(std::move(private_key)) {} + + XMSS_WOTS_Addressed_PrivateKey(XMSS_WOTS_PrivateKey&& private_key, + XMSS_Address&& adrs) + : XMSS_WOTS_Addressed_PublicKey(XMSS_WOTS_PublicKey(private_key), + std::move(adrs)), + m_priv_key(std::move(private_key)) {} + + const XMSS_WOTS_PrivateKey& private_key() const { return m_priv_key; } + XMSS_WOTS_PrivateKey& private_key() { return m_priv_key; } + + AlgorithmIdentifier + pkcs8_algorithm_identifier() const override + { + return m_priv_key.pkcs8_algorithm_identifier(); + } + + secure_vector private_key_bits() const override + { + return m_priv_key.private_key_bits(); + } + + private: + XMSS_WOTS_PrivateKey m_priv_key; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_addressed_publickey.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_addressed_publickey.h new file mode 100644 index 0000000000..78d150d214 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_addressed_publickey.h @@ -0,0 +1,96 @@ +/** + * XMSS WOTS Addressed Public Key + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + + +#ifndef BOTAN_XMSS_WOTS_ADDRESSED_PUBLICKEY_H_ +#define BOTAN_XMSS_WOTS_ADDRESSED_PUBLICKEY_H_ + +#include +#include + +namespace Botan { + +/** + * Wrapper class to pair a XMSS_WOTS_PublicKey with an XMSS Address. Since + * the PK_Ops::Verification interface does not allow an extra address + * parameter to be passed to the sign(RandomNumberGenerator&), the address + * needs to be stored together with the key and passed to the + * XMSS_WOTS_Verification_Operation() on creation. + **/ +class XMSS_WOTS_Addressed_PublicKey : public virtual Public_Key + { + public: + XMSS_WOTS_Addressed_PublicKey(const XMSS_WOTS_PublicKey& public_key) + : m_pub_key(public_key), m_adrs() {} + + XMSS_WOTS_Addressed_PublicKey(const XMSS_WOTS_PublicKey& public_key, + const XMSS_Address& adrs) + : m_pub_key(public_key), m_adrs(adrs) {} + + XMSS_WOTS_Addressed_PublicKey(XMSS_WOTS_PublicKey&& public_key) + : m_pub_key(std::move(public_key)), m_adrs() {} + + XMSS_WOTS_Addressed_PublicKey(XMSS_WOTS_PublicKey&& public_key, + XMSS_Address&& adrs) + : m_pub_key(std::move(public_key)), m_adrs(std::move(adrs)) {} + + const XMSS_WOTS_PublicKey& public_key() const { return m_pub_key; } + XMSS_WOTS_PublicKey& public_key() { return m_pub_key; } + + const XMSS_Address& address() const { return m_adrs; } + XMSS_Address& address() { return m_adrs; } + + std::string algo_name() const override + { + return m_pub_key.algo_name(); + } + + AlgorithmIdentifier algorithm_identifier() const override + { + return m_pub_key.algorithm_identifier(); + } + + bool check_key(RandomNumberGenerator& rng, bool strong) const override + { + return m_pub_key.check_key(rng, strong); + } + + std::unique_ptr + create_verification_op(const std::string& params, + const std::string& provider) const override + { + return m_pub_key.create_verification_op(params, provider); + } + + OID get_oid() const override + { + return m_pub_key.get_oid(); + } + + size_t estimated_strength() const override + { + return m_pub_key.estimated_strength(); + } + + size_t key_length() const override + { + return m_pub_key.estimated_strength(); + } + + std::vector public_key_bits() const override + { + return m_pub_key.public_key_bits(); + } + + protected: + XMSS_WOTS_PublicKey m_pub_key; + XMSS_Address m_adrs; + }; + +} + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_parameters.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_parameters.cpp new file mode 100644 index 0000000000..ef89c081c0 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_parameters.cpp @@ -0,0 +1,137 @@ +/* + * XMSS WOTS Parameters + * Descibes a signature method for XMSS Winternitz One Time Signatures, + * as defined in: + * [1] XMSS: Extended Hash-Based Signatures, + * Request for Comments: 8391 + * Release: May 2018. + * https://datatracker.ietf.org/doc/rfc8391/ + * + * (C) 2016,2017,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include +#include +#include + +namespace Botan { + +XMSS_WOTS_Parameters::ots_algorithm_t +XMSS_WOTS_Parameters::xmss_wots_id_from_string(const std::string& param_set) + { + if(param_set == "WOTSP-SHA2_256") + { return WOTSP_SHA2_256; } + if(param_set == "WOTSP-SHA2_512") + { return WOTSP_SHA2_512; } + if(param_set == "WOTSP-SHAKE_256") + { return WOTSP_SHAKE_256; } + if(param_set == "WOTSP-SHAKE_512") + { return WOTSP_SHAKE_512; } + throw Invalid_Argument("Unknown XMSS-WOTS algorithm param '" + param_set + "'"); + } + +XMSS_WOTS_Parameters::XMSS_WOTS_Parameters(const std::string& param_set) + : XMSS_WOTS_Parameters(xmss_wots_id_from_string(param_set)) + {} + +XMSS_WOTS_Parameters::XMSS_WOTS_Parameters(ots_algorithm_t oid) + : m_oid(oid) + { + switch(oid) + { + case WOTSP_SHA2_256: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_name = "WOTSP-SHA2_256"; + m_hash_name = "SHA-256"; + m_strength = 256; + break; + case WOTSP_SHA2_512: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_name = "WOTSP-SHA2_512"; + m_hash_name = "SHA-512"; + m_strength = 512; + break; + case WOTSP_SHAKE_256: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_name = "WOTSP-SHAKE_256"; + m_hash_name = "SHAKE-128(256)"; + m_strength = 256; + break; + case WOTSP_SHAKE_512: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_name = "WOTSP-SHAKE_512"; + m_hash_name = "SHAKE-256(512)"; + m_strength = 512; + break; + default: + throw Not_Implemented("Algorithm id does not match any known XMSS WOTS algorithm id."); + break; + } + + m_lg_w = (m_w == 16) ? 4 : 2; + m_len_1 = static_cast(std::ceil((8 * element_size()) / m_lg_w)); + m_len_2 = static_cast( + floor(log2(m_len_1 * (wots_parameter() - 1)) / m_lg_w) + 1); + BOTAN_ASSERT(m_len == m_len_1 + m_len_2, "Invalid XMSS WOTS parameter " + "\"len\" detedted."); + } + +secure_vector +XMSS_WOTS_Parameters::base_w(const secure_vector& msg, size_t out_size) const + { + secure_vector result; + size_t in = 0; + size_t total = 0; + size_t bits = 0; + + for(size_t i = 0; i < out_size; i++) + { + if(bits == 0) + { + total = msg[in]; + in++; + bits += 8; + } + bits -= m_lg_w; + result.push_back(static_cast((total >> bits) & (m_w - 1))); + } + return result; + } + +secure_vector +XMSS_WOTS_Parameters::base_w(size_t value) const + { + value <<= (8 - ((m_len_2 * m_lg_w) % 8)); + size_t len_2_bytes = static_cast( + std::ceil(static_cast(m_len_2 * m_lg_w) / 8.f)); + secure_vector result; + XMSS_Tools::concat(result, value, len_2_bytes); + return base_w(result, m_len_2); + } + +void +XMSS_WOTS_Parameters::append_checksum(secure_vector& data) + { + size_t csum = 0; + + for(size_t i = 0; i < data.size(); i++) + { + csum += wots_parameter() - 1 - data[i]; + } + + secure_vector csum_bytes = base_w(csum); + std::move(csum_bytes.begin(), csum_bytes.end(), std::back_inserter(data)); + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_parameters.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_parameters.h new file mode 100644 index 0000000000..e8c3e2b4a3 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_parameters.h @@ -0,0 +1,14 @@ +/* + * XMSS WOTS Parameters + * (C) 2016,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_WOTS_PARAMETERS_H_ +#define BOTAN_XMSS_WOTS_PARAMETERS_H_ + +#include +BOTAN_DEPRECATED_HEADER(xmss_wots_parameters.h) + +#endif diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_privatekey.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_privatekey.cpp new file mode 100644 index 0000000000..7293f2538a --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_privatekey.cpp @@ -0,0 +1,99 @@ +/* + * XMSS WOTS Private Key + * A Winternitz One Time Signature private key for use with Extended Hash-Based + * Signatures. + * + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include +#include + +namespace Botan { + +wots_keysig_t +XMSS_WOTS_PrivateKey::generate(const secure_vector& priv_seed, + XMSS_Hash& hash) + { + wots_keysig_t priv_key(m_wots_params.len(), + secure_vector(0)); + + for(size_t i = 0; i < m_wots_params.len(); i++) + { + XMSS_Tools::concat(priv_key[i], i, 32); + hash.prf(priv_key[i], priv_seed, priv_key[i]); + } + return priv_key; + } + + +XMSS_WOTS_PublicKey +XMSS_WOTS_PrivateKey::generate_public_key(XMSS_Address& adrs) + { + XMSS_WOTS_PublicKey pub_key(m_wots_params.oid(), + public_seed()); + generate_public_key(pub_key, wots_keysig_t((*this)[adrs]), adrs); + return pub_key; + } + +void +XMSS_WOTS_PrivateKey::generate_public_key(XMSS_WOTS_PublicKey& pub_key, + wots_keysig_t&& in_key_data, + XMSS_Address& adrs, + XMSS_Hash& hash) + { + BOTAN_ASSERT(wots_parameters() == pub_key.wots_parameters() && + public_seed() == pub_key.public_seed(), + "Conflicting public key data."); + + pub_key.set_key_data(std::move(in_key_data)); + for(size_t i = 0; i < m_wots_params.len(); i++) + { + adrs.set_chain_address(static_cast(i)); + chain(pub_key[i], 0, m_wots_params.wots_parameter() - 1, adrs, + public_seed(), hash); + } + } + +wots_keysig_t +XMSS_WOTS_PrivateKey::sign(const secure_vector& msg, + XMSS_Address& adrs, + XMSS_Hash& hash) + + { + secure_vector msg_digest + { + m_wots_params.base_w(msg, m_wots_params.len_1()) + }; + + m_wots_params.append_checksum(msg_digest); + wots_keysig_t sig(this->at(adrs, hash)); + + for(size_t i = 0; i < m_wots_params.len(); i++) + { + adrs.set_chain_address(static_cast(i)); + chain(sig[i], 0 , msg_digest[i], adrs, m_public_seed, hash); + } + + return sig; + } + +wots_keysig_t XMSS_WOTS_PrivateKey::at(const XMSS_Address& adrs, XMSS_Hash& hash) + { + secure_vector result; + hash.prf(result, m_private_seed, adrs.bytes()); + return generate(result, hash); + } + +wots_keysig_t XMSS_WOTS_PrivateKey::at(size_t i, XMSS_Hash& hash) + { + secure_vector idx_bytes; + XMSS_Tools::concat(idx_bytes, i, m_wots_params.element_size()); + hash.h(idx_bytes, m_private_seed, idx_bytes); + return generate(idx_bytes, hash); + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_privatekey.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_privatekey.h new file mode 100644 index 0000000000..2d631598bb --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_privatekey.h @@ -0,0 +1,15 @@ +/* + * XMSS WOTS Private Key + * (C) 2016,2017 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_WOTS_PRIVATEKEY_H_ +#define BOTAN_XMSS_WOTS_PRIVATEKEY_H_ + +#include +BOTAN_DEPRECATED_HEADER(xmss_wots_privatekey.h) + +#endif + diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_publickey.cpp b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_publickey.cpp new file mode 100644 index 0000000000..70ff1b7bad --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_publickey.cpp @@ -0,0 +1,72 @@ +/* + * XMSS WOTS Public Key + * A Winternitz One Time Signature public key for use with Extended Hash-Based + * Signatures. + * + * (C) 2016,2017,2018 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include +#include + +namespace Botan { + +void +XMSS_WOTS_PublicKey::chain(secure_vector& result, + size_t start_idx, + size_t steps, + XMSS_Address& adrs, + const secure_vector& seed, + XMSS_Hash& hash) + { + secure_vector prf_output(hash.output_length()); + + for(size_t i = start_idx; + i < (start_idx + steps) && i < m_wots_params.wots_parameter(); + i++) + { + adrs.set_hash_address(static_cast(i)); + + //Calculate tmp XOR bitmask + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Mask_Mode); + hash.prf(prf_output, seed, adrs.bytes()); + xor_buf(result, prf_output, result.size()); + + // Calculate key + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Key_Mode); + + //Calculate f(key, tmp XOR bitmask) + hash.prf(prf_output, seed, adrs.bytes()); + hash.f(result, prf_output, result); + } + } + +wots_keysig_t +XMSS_WOTS_PublicKey::pub_key_from_signature(const secure_vector& msg, + const wots_keysig_t& sig, + XMSS_Address& adrs, + const secure_vector& seed) + { + secure_vector msg_digest + { + m_wots_params.base_w(msg, m_wots_params.len_1()) + }; + + m_wots_params.append_checksum(msg_digest); + wots_keysig_t result(sig); + + for(size_t i = 0; i < m_wots_params.len(); i++) + { + adrs.set_chain_address(static_cast(i)); + chain(result[i], + msg_digest[i], + m_wots_params.wots_parameter() - 1 - msg_digest[i], + adrs, + seed); + } + return result; + } + +} diff --git a/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_publickey.h b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_publickey.h new file mode 100644 index 0000000000..796bf4c308 --- /dev/null +++ b/comm/third_party/botan/src/lib/pubkey/xmss/xmss_wots_publickey.h @@ -0,0 +1,14 @@ +/* + * XMSS WOTS Public Key + * (C) 2016,2017,2018 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 +BOTAN_DEPRECATED_HEADER(xmss_wots_publickey.h) + +#endif -- cgit v1.2.3