diff options
| author | Matthias Gierlings <[email protected]> | 2016-10-08 20:45:53 +0200 |
|---|---|---|
| committer | Matthias Gierlings <[email protected]> | 2016-11-11 12:52:26 +0100 |
| commit | 8b06b4fe5fbe189c7d5250becb189bf2b87b9013 (patch) | |
| tree | c73fbb3bf4eddcddf1d3f37983799d80204e8f2c /src/lib/pubkey | |
| parent | 618f890fd7ede74c728612ca8bc590c72ee353f1 (diff) | |
Added Extended Hash-Based Signatures (XMSS)
[1] XMSS: Extended Hash-Based Signatures,
draft-itrf-cfrg-xmss-hash-based-signatures-06
Release: July 2016.
https://datatracker.ietf.org/doc/
draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1
Provides XMSS_PublicKey and XMSS_PrivateKey classes as well as implementations
for the Botan interfaces PK_Ops::Signature and PK_Ops::Verification. XMSS has
been integrated into the Botan test bench, signature generation and verification
can be tested independently by invoking "botan-test xmss_sign" and
"botan-test xmss_verify"
- Some headers that are not required to be exposed to users of the library have
to be declared as public in `info.txt`. Declaring those headers private will
cause the amalgamation build to fail. The following headers have been
declared public inside `info.txt`, even though they are only intended for
internal use:
* atomic.h
* xmss_hash.h
* xmss_index_registry.h
* xmss_address.h
* xmss_common_ops.h
* xmss_tools.h
* xmss_wots_parameters.h
* xmss_wots_privatekey.h
* xmss_wots_publickey.h
- XMSS_Verification_Operation Requires the "randomness" parameter out of the
XMSS signature. "Randomness" is part of the prefix that is hashed *before*
the message. Since the signature is unknown till sign() is called, all
message content has to be buffered. For large messages this can be
inconvenient or impossible.
**Possible solution**: Change PK_Ops::Verification interface to take
the signature as constructor argument, and provide a setter method to be able
to update reuse the instance on multiple signatures. Make sign a parameterless
member call. This solution requires interface changes in botan.
**Suggested workaround** for signing large messages is to not sign the message
itself, but to precompute the message hash manually using Botan::HashFunctio
and sign the message hash instead of the message itself.
- Some of the available test vectors for the XMSS signature verification have
been commented out in order to reduce testbench runtime.
Diffstat (limited to 'src/lib/pubkey')
32 files changed, 4121 insertions, 0 deletions
diff --git a/src/lib/pubkey/pk_algs.cpp b/src/lib/pubkey/pk_algs.cpp index e7d744ae9..7cccd0168 100644 --- a/src/lib/pubkey/pk_algs.cpp +++ b/src/lib/pubkey/pk_algs.cpp @@ -52,6 +52,10 @@ #include <botan/mceliece.h> #endif +#if defined(BOTAN_HAS_XMSS) + #include <botan/xmss.h> +#endif + namespace Botan { std::unique_ptr<Public_Key> @@ -117,6 +121,11 @@ load_public_key(const AlgorithmIdentifier& alg_id, return std::unique_ptr<Public_Key>(new GOST_3410_PublicKey(alg_id, key_bits)); #endif +#if defined(BOTAN_HAS_XMSS) + if(alg_name == "XMSS") + return std::unique_ptr<Public_Key>(new XMSS_PublicKey(key_bits)); +#endif + throw Decoding_Error("Unhandled PK algorithm " + alg_name); } @@ -183,6 +192,11 @@ load_private_key(const AlgorithmIdentifier& alg_id, return std::unique_ptr<Private_Key>(new ElGamal_PrivateKey(alg_id, key_bits)); #endif +#if defined(BOTAN_HAS_XMSS) + if(alg_name == "XMSS") + return std::unique_ptr<Private_Key>(new XMSS_PrivateKey(key_bits)); +#endif + throw Decoding_Error("Unhandled PK algorithm " + alg_name); } @@ -224,6 +238,14 @@ create_private_key(const std::string& alg_name, } #endif +#if defined(BOTAN_HAS_XMSS) + if(alg_name == "XMSS") + { + return std::unique_ptr<Private_Key>( + new XMSS_PrivateKey(XMSS_Parameters(params).oid(), rng)); + } +#endif + // ECC crypto #if defined(BOTAN_HAS_ECC_PUBLIC_KEY_CRYPTO) diff --git a/src/lib/pubkey/xmss/atomic.h b/src/lib/pubkey/xmss/atomic.h new file mode 100644 index 000000000..485728d54 --- /dev/null +++ b/src/lib/pubkey/xmss/atomic.h @@ -0,0 +1,51 @@ +/** + * 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 <atomic> +#include <memory> + +namespace Botan { + +template <typename T> +/** + * 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 + { + public: + Atomic() : m_data() {}; + Atomic(const Atomic& data) : m_data(data.m_data.load()) {} + Atomic(const std::atomic<T>& data) : m_data(data.load()) {} + + Atomic& operator=(const Atomic& a) + { + m_data.store(a.m_data.load()); + return *this; + } + + Atomic& operator=(const std::atomic<T>& a) + { + m_data.store(a.load()); + return *this; + } + + operator std::atomic<T>& () { return m_data; } + operator T() { return m_data.load(); } + + private: + std::atomic<T> m_data; + }; + +} + +#endif diff --git a/src/lib/pubkey/xmss/info.txt b/src/lib/pubkey/xmss/info.txt new file mode 100644 index 000000000..a92b06beb --- /dev/null +++ b/src/lib/pubkey/xmss/info.txt @@ -0,0 +1,46 @@ +define XMSS 20161008 + +<source> +xmss_common_ops.cpp +xmss_hash.cpp +xmss_index_registry.cpp +xmss_parameters.cpp +xmss_privatekey.cpp +xmss_publickey.cpp +xmss_signature.cpp +xmss_signature_operation.cpp +xmss_tools.cpp +xmss_verification_operation.cpp +xmss_wots_parameters.cpp +xmss_wots_privatekey.cpp +xmss_wots_publickey.cpp +</source> + +<header:public> +atomic.h +xmss.h +xmss_hash.h +xmss_index_registry.h +xmss_address.h +xmss_common_ops.h +xmss_parameters.h +xmss_key_pair.h +xmss_privatekey.h +xmss_publickey.h +xmss_tools.h +xmss_wots_parameters.h +xmss_wots_privatekey.h +xmss_wots_publickey.h +</header:public> + +<header:internal> +xmss_signature.h +xmss_signature_operation.h +xmss_verification_operation.h +</header:internal> + +<requires> +asn1 +rng +hash +</requires> diff --git a/src/lib/pubkey/xmss/xmss.h b/src/lib/pubkey/xmss/xmss.h new file mode 100644 index 000000000..f12871672 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss.h @@ -0,0 +1,15 @@ +/** + * XMSS + * Includes XMSS headers. + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_H__ +#define BOTAN_XMSS_H__ + +#include <botan/xmss_publickey.h> +#include <botan/xmss_privatekey.h> + +#endif diff --git a/src/lib/pubkey/xmss/xmss_address.h b/src/lib/pubkey/xmss/xmss_address.h new file mode 100644 index 000000000..438059cba --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_address.h @@ -0,0 +1,409 @@ +/** + * 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 <cstdint> +#include <limits> +#include <botan/xmss_tools.h> + +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 + { + 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<Type>(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<byte>(type); + std::fill(m_data.begin() + 16, m_data.end(), 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<byte>(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. + * + * @return chain 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<byte>& bytes() const + { + return m_data; + } + + secure_vector<byte>& 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<byte>& data) : m_data(data) + { + BOTAN_ASSERT(m_data.size() == m_address_size, + "XMSS_Address must be of 256 bits size."); + } + + XMSS_Address(secure_vector<byte>&& 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<byte> 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/src/lib/pubkey/xmss/xmss_common_ops.cpp b/src/lib/pubkey/xmss/xmss_common_ops.cpp new file mode 100644 index 000000000..dd139a349 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_common_ops.cpp @@ -0,0 +1,70 @@ +/** + * XMSS Common Ops + * Operations shared by XMSS signature generation and verification operations. + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/xmss_common_ops.h> + +namespace Botan { + +void +XMSS_Common_Ops::randomize_tree_hash(secure_vector<byte>& result, + const secure_vector<byte>& left, + const secure_vector<byte>& right, + XMSS_Address& adrs, + const secure_vector<byte>& seed) + { + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Key_Mode); + secure_vector<byte> key { m_hash.prf(seed, adrs.bytes()) }; + + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Mask_MSB_Mode); + secure_vector<byte> bitmask_l { m_hash.prf(seed, adrs.bytes()) }; + + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Mask_LSB_Mode); + secure_vector<byte> bitmask_r { m_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<byte> concat_xor(m_xmss_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]; + } + + m_hash.h(result, key, concat_xor); + } + + +void +XMSS_Common_Ops::create_l_tree(secure_vector<byte>& result, + wots_keysig_t pk, + XMSS_Address& adrs, + const secure_vector<byte>& seed) + { + size_t l = m_xmss_params.len(); + adrs.set_tree_height(0); + + while(l > 1) + { + for(size_t i = 0; i < l >> 1; i++) + { + adrs.set_tree_index(i); + randomize_tree_hash(pk[i], pk[2 * i], pk[2 * i + 1], adrs, seed); + } + 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/src/lib/pubkey/xmss/xmss_common_ops.h b/src/lib/pubkey/xmss/xmss_common_ops.h new file mode 100644 index 000000000..74ae52a78 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_common_ops.h @@ -0,0 +1,75 @@ +/** + * XMSS Common Ops + * (C) 2016 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 <vector> +#include <botan/secmem.h> +#include <botan/assert.h> +#include <botan/xmss_parameters.h> +#include <botan/xmss_address.h> +#include <botan/xmss_hash.h> + +namespace Botan { + +typedef std::vector<secure_vector<byte>> wots_keysig_t; + +/** + * Operations shared by XMSS signature generation and verification operations. + **/ +class XMSS_Common_Ops + { + public: + XMSS_Common_Ops(XMSS_Parameters::xmss_algorithm_t oid) + : m_xmss_params(oid), m_hash(m_xmss_params.hash_function_name()) {}; + + protected: + /** + * Algorithm 7: "RAND_HASH" + * + * Generates a randomized hash. + * + * @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. + **/ + void randomize_tree_hash( + secure_vector<byte>& result, + const secure_vector<byte>& left, + const secure_vector<byte>& right, + XMSS_Address& adrs, + const secure_vector<byte>& seed); + + /** + * 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. + * + * @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. + **/ + void create_l_tree( + secure_vector<byte>& result, + wots_keysig_t pk, + XMSS_Address& adrs, + const secure_vector<byte>& seed); + + protected: + XMSS_Parameters m_xmss_params; + XMSS_Hash m_hash; + + }; + +} + +#endif diff --git a/src/lib/pubkey/xmss/xmss_hash.cpp b/src/lib/pubkey/xmss/xmss_hash.cpp new file mode 100644 index 000000000..15cdab509 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_hash.cpp @@ -0,0 +1,88 @@ +/** + * XMSS Hash + * A collection of pseudorandom hash functions required for XMSS and WOTS + * computations. + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/xmss_hash.h> + +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_msg_hash(HashFunction::create(h_func_name)), + m_output_length(m_hash->output_length()), + m_zero_padding(m_output_length - 1, 0x00), + m_hash_func_name(h_func_name) + { + BOTAN_ASSERT(m_output_length > 0, "Hash output length of zero is invalid."); + } + +void +XMSS_Hash::h(secure_vector<byte>& result, + const secure_vector<byte>& key, + const secure_vector<byte>& 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<byte>& randomness, + const secure_vector<byte>& root, + const secure_vector<byte>& 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 secure_vector<byte>& data) + { + m_msg_hash->update(data); + } + +void XMSS_Hash::h_msg_update(const byte data[], size_t size) + { + m_msg_hash->update(data, size); + } + +secure_vector<byte> XMSS_Hash::h_msg_final() + { + return m_msg_hash->final(); + } + +secure_vector<byte> +XMSS_Hash::h_msg(const secure_vector<byte>& randomness, + const secure_vector<byte>& root, + const secure_vector<byte>& index_bytes, + const secure_vector<byte>& data) + { + h_msg_init(randomness, root, index_bytes); + m_msg_hash->update(data); + return m_msg_hash->final(); + } + +XMSS_Hash& XMSS_Hash::operator=(XMSS_Hash hash) + { + std::swap(m_hash, hash.m_hash); + std::swap(m_msg_hash, hash.m_msg_hash); + std::swap(m_output_length, hash.m_output_length); + std::swap(m_zero_padding, hash.m_zero_padding); + return *this; + } + +} diff --git a/src/lib/pubkey/xmss/xmss_hash.h b/src/lib/pubkey/xmss/xmss_hash.h new file mode 100644 index 000000000..da059fb7b --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_hash.h @@ -0,0 +1,166 @@ +/** + * XMSS Hash + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_HASH_H__ +#define BOTAN_XMSS_HASH_H__ + +#include <cstddef> +#include <string> +#include <botan/assert.h> +#include <botan/hash.h> +#include <botan/secmem.h> +#include <botan/types.h> + +namespace Botan { + +/** + * A collection of pseudorandom hash functions required for XMSS and WOTS + * computations. + **/ +class XMSS_Hash + { + public: + XMSS_Hash(const std::string& h_func_name); + XMSS_Hash(const XMSS_Hash& hash); + XMSS_Hash& operator=(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<byte>& result, + const secure_vector<byte>& key, + const secure_vector<byte>& 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<byte> prf(const secure_vector<byte>& key, + const secure_vector<byte>& 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<byte>& result, + const secure_vector<byte>& key, + const secure_vector<byte>& 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<byte>& result, + const secure_vector<byte>& key, + const secure_vector<byte>& 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<byte> h_msg(const secure_vector<byte>& randomness, + const secure_vector<byte>& root, + const secure_vector<byte>& index_bytes, + const secure_vector<byte>& 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<byte>& randomness, + const secure_vector<byte>& root, + const secure_vector<byte>& index_bytes); + + /** + * Adds a message block to buffered h_msg computation. + * + * @param data A message block + **/ + void h_msg_update(const secure_vector<byte>& data); + + /** + * 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 byte 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<byte> h_msg_final(); + + size_t output_length() const { return m_output_length; }; + + private: + std::unique_ptr<HashFunction> m_hash; + std::unique_ptr<HashFunction> m_msg_hash; + size_t m_output_length; + + //32 byte id prefixes prepended to the hash input. + std::vector<byte> m_zero_padding; + static const byte m_id_f = 0x00; + static const byte m_id_h = 0x01; + static const byte m_id_hmsg = 0x02; + static const byte m_id_prf = 0x03; + const std::string m_hash_func_name; + }; + +} + +#endif diff --git a/src/lib/pubkey/xmss/xmss_index_registry.cpp b/src/lib/pubkey/xmss/xmss_index_registry.cpp new file mode 100644 index 000000000..f7f4ec470 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_index_registry.cpp @@ -0,0 +1,82 @@ +/** + * 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 <botan/xmss_index_registry.h> + +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<byte>& private_seed, + const secure_vector<byte>& prf) const + { + std::unique_ptr<HashFunction> 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<byte> 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<Atomic<size_t>> +XMSS_Index_Registry::get(const secure_vector<byte>& private_seed, + const secure_vector<byte>& prf) + { + size_t pos = get(make_key_id(private_seed, prf)); + + if(pos < std::numeric_limits<size_t>::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<size_t>::max(); + } + +size_t XMSS_Index_Registry::add(uint64_t id, size_t last_unused) + { + std::lock_guard<std::mutex> 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<Atomic<size_t>>(last_unused); + } + return pos; + } + + m_key_ids.push_back(id); + m_leaf_indices.push_back(std::make_shared<Atomic<size_t>>(last_unused)); + return m_key_ids.size() - 1; + } + +} diff --git a/src/lib/pubkey/xmss/xmss_index_registry.h b/src/lib/pubkey/xmss/xmss_index_registry.h new file mode 100644 index 000000000..5dcb6d31b --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_index_registry.h @@ -0,0 +1,109 @@ +/** + * 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 <stdint.h> +#include <cstddef> +#include <limits> +#include <memory> +#include <mutex> +#include <string> +#include <botan/hash.h> +#include <botan/secmem.h> +#include <botan/types.h> +#include <botan/atomic.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 + { + 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<Atomic<size_t>> + get(const secure_vector<byte>& private_seed, + const secure_vector<byte>& prf); + + private: + XMSS_Index_Registry() + : m_key_ids(), m_leaf_indices(), m_mutex() {} + + 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<byte>& private_seed, + const secure_vector<byte>& prf) const; + + /** + * Retrieves the index position of a key within the registry or + * max(size_t) if key has not been found. + * + * @param 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<uint64_t> m_key_ids; + std::vector<std::shared_ptr<Atomic<size_t>>> m_leaf_indices; + std::mutex m_mutex; + }; + +} + +#endif diff --git a/src/lib/pubkey/xmss/xmss_key_pair.h b/src/lib/pubkey/xmss/xmss_key_pair.h new file mode 100644 index 000000000..4d86f1766 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_key_pair.h @@ -0,0 +1,52 @@ +/** + * 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/botan.h> +#include <botan/rng.h> +#include <botan/xmss_parameters.h> +#include <botan/xmss_wots_parameters.h> +#include <botan/xmss_publickey.h> +#include <botan/xmss_privatekey.h> + +namespace Botan { + +/** + * A pair of XMSS public and private key. + **/ +class BOTAN_DLL 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/src/lib/pubkey/xmss/xmss_parameters.cpp b/src/lib/pubkey/xmss/xmss_parameters.cpp new file mode 100644 index 000000000..5a106320b --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_parameters.cpp @@ -0,0 +1,179 @@ +/** + * XMSS Parameters + * Descibes a signature method for XMSS, as defined in: + * [1] XMSS: Extended Hash-Based Signatures, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + * + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/xmss_parameters.h> + +namespace Botan { + +const std::map<std::string, XMSS_Parameters::xmss_algorithm_t> + XMSS_Parameters::m_oid_name_lut = + { + { "XMSS_SHA2-256_W16_H10", XMSS_SHA2_256_W16_H10 }, + { "XMSS_SHA2-256_W16_H16", XMSS_SHA2_256_W16_H16 }, + { "XMSS_SHA2-256_W16_H20", XMSS_SHA2_256_W16_H20 }, + { "XMSS_SHA2-512_W16_H10", XMSS_SHA2_512_W16_H10 }, + { "XMSS_SHA2-512_W16_H16", XMSS_SHA2_512_W16_H16 }, + { "XMSS_SHA2-512_W16_H20", XMSS_SHA2_512_W16_H20 } +// { "XMSS_SHAKE128_W16_H10", xmss_algorithm_t::XMSS_SHAKE128_W16_H10 }, +// { "XMSS_SHAKE128_W16_H16", xmss_algorithm_t::XMSS_SHAKE128_W16_H16 }, +// { "XMSS_SHAKE128_W16_H20", xmss_algorithm_t::XMSS_SHAKE128_W16_H20 }, +// { "XMSS_SHAKE256_W16_H10", xmss_algorithm_t::XMSS_SHAKE256_W16_H10 }, +// { "XMSS_SHAKE256_W16_H16", xmss_algorithm_t::XMSS_SHAKE256_W16_H16 }, +// { "XMSS_SHAKE256_W16_H20", xmss_algorithm_t::XMSS_SHAKE256_W16_H20 } + }; + +XMSS_Parameters::XMSS_Parameters(const std::string& algo_name) + : XMSS_Parameters(m_oid_name_lut.at(algo_name)) + {} + +XMSS_Parameters::XMSS_Parameters(xmss_algorithm_t oid) + : m_oid(oid) + { + switch(oid) + { + case XMSS_SHA2_256_W16_H10: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_tree_height = 10; + m_name = "XMSS_SHA2-256_W16_H10"; + m_hash_name = "SHA-256"; + m_strength = 256; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_256_W16; + break; + case XMSS_SHA2_256_W16_H16: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_tree_height = 16; + m_name = "XMSS_SHA2-256_W16_H16"; + m_hash_name = "SHA-256"; + m_strength = 256; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_256_W16; + break; + case XMSS_SHA2_256_W16_H20: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_tree_height = 20; + m_name = "XMSS_SHA2-256_W16_H20"; + m_hash_name = "SHA-256"; + m_strength = 256; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_256_W16; + break; + case XMSS_SHA2_512_W16_H10: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_tree_height = 10; + m_name = "XMSS_SHA2-512_W16_H10"; + m_hash_name = "SHA-512"; + m_strength = 512; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_512_W16; + break; + case XMSS_SHA2_512_W16_H16: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_tree_height = 16; + m_name = "XMSS_SHA2-512_W16_H16"; + m_hash_name = "SHA-512"; + m_strength = 512; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_512_W16; + break; + case XMSS_SHA2_512_W16_H20: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_tree_height = 20; + m_name = "XMSS_SHA2-512_W16_H20"; + m_hash_name = "SHA-512"; + m_strength = 512; + m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHA2_512_W16; + break; +// FIXME: Uncomment once SHAKE128/256 implementation is available in Botan. +// case XMSS_SHAKE128_W16_H10: +// m_element_size = 32; +// m_w = 16; +// m_len = 67; +// m_tree_height = 10; +// m_name = "XMSS_SHAKE128_W16_H10"; +// m_hash_name = ""; +// m_strength = 256; +// m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE128_W16; +// BOTAN_ASSERT(false, "XMSS_SHAKE128_W16_H10 not implemented."); +// break; +// case XMSS_SHAKE128_W16_H16: +// m_element_size = 32; +// m_w = 16; +// m_len = 67; +// m_tree_height = 16; +// m_name = "XMSS_SHAKE128_W16_H16"; +// m_hash_name = ""; +// m_strength = 256; +// m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE128_W16; +// BOTAN_ASSERT(false, "XMSS_SHAKE128_W16_H16 not implemented."); +// break; +// case XMSS_SHAKE128_W16_H20: +// m_element_size = 32; +// m_w = 16; +// m_len = 67; +// m_tree_height = 20; +// m_name = "XMSS_SHAKE128_W16_H20"; +// m_hash_name = ""; +// m_strength = 256; +// m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE128_W16; +// BOTAN_ASSERT(false, "XMSS_SHAKE128_W16_H20 not implemented."); +// break; +// case XMSS_SHAKE256_W16_H10: +// m_element_size = 64; +// m_w = 16; +// m_len = 131; +// m_tree_height = 10; +// m_name = "XMSS_SHAKE256_W16_H10"; +// m_hash_name = ""; +// m_strength = 512; +// m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE256_W16; +// BOTAN_ASSERT(false, "XMSS_SHAKE256_W16_H10 not implemented."); +// break; +// case XMSS_SHAKE256_W16_H16: +// m_element_size = 64; +// m_w = 16; +// m_len = 131; +// m_tree_height = 16; +// m_name = "XMSS_SHAKE256_W16_H16"; +// m_hash_name = ""; +// m_strength = 512; +// m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE256_W16; +// BOTAN_ASSERT(false, "XMSS_SHAKE256_W16_H16 not implemented."); +// break; +// case XMSS_SHAKE256_W16_H20: +// m_element_size = 64; +// m_w = 16; +// m_len = 131; +// m_tree_height = 20; +// m_name = "XMSS_SHAKE256_W16_H20"; +// m_hash_name = ""; +// m_strength = 512; +// m_wots_oid = XMSS_WOTS_Parameters::ots_algorithm_t::WOTSP_SHAKE256_W16; +// BOTAN_ASSERT(false, "XMSS_SHAKE256_W16_H20 not implemented."); +// break; + default: + throw Unsupported_Argument( + "Algorithm id does not match any XMSS algorithm id."); + break; + } + } + +} diff --git a/src/lib/pubkey/xmss/xmss_parameters.h b/src/lib/pubkey/xmss/xmss_parameters.h new file mode 100644 index 000000000..eb5ff4422 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_parameters.h @@ -0,0 +1,125 @@ +/** + * XMSS Parameters + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_PARAMETERS_H__ +#define BOTAN_XMSS_PARAMETERS_H__ + +#include <cstddef> +#include <map> +#include <string> +#include <botan/assert.h> +#include <botan/types.h> +#include <botan/xmss_wots_parameters.h> + +namespace Botan { + +/** + * Descibes a signature method for XMSS, as defined in: + * [1] XMSS: Extended Hash-Based Signatures, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + **/ +class BOTAN_DLL XMSS_Parameters + { + public: + enum xmss_algorithm_t + { + XMSS_SHA2_256_W16_H10 = 0x01000001, + XMSS_SHA2_256_W16_H16 = 0x02000002, + XMSS_SHA2_256_W16_H20 = 0x03000003, + XMSS_SHA2_512_W16_H10 = 0x04000004, + XMSS_SHA2_512_W16_H16 = 0x05000005, + XMSS_SHA2_512_W16_H20 = 0x06000006, +// FIXME: Uncomment once SHAKE128/256 implementation is available in Botan. +// XMSS_SHAKE128_W16_H10 = 0x07000007, +// XMSS_SHAKE128_W16_H16 = 0x08000008, +// XMSS_SHAKE128_W16_H20 = 0x09000009, +// XMSS_SHAKE256_W16_H10 = 0x0a00000a, +// XMSS_SHAKE256_W16_H16 = 0x0b00000b, +// XMSS_SHAKE256_W16_H20 = 0x0c00000c + }; + + 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: + static const std::map<std::string, xmss_algorithm_t> + m_oid_name_lut; + 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/src/lib/pubkey/xmss/xmss_privatekey.cpp b/src/lib/pubkey/xmss/xmss_privatekey.cpp new file mode 100644 index 000000000..18d712a5f --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_privatekey.cpp @@ -0,0 +1,188 @@ +/** + * 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, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + * + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/internal/xmss_signature_operation.h> +#include <botan/xmss_privatekey.h> + +namespace Botan { + +XMSS_PrivateKey::XMSS_PrivateKey(const secure_vector<byte>& raw_key) + : XMSS_PublicKey(raw_key), + XMSS_Common_Ops(XMSS_PublicKey::m_xmss_params.oid()), + m_wots_priv_key(m_wots_params.oid(), m_public_seed), + m_index_reg(XMSS_Index_Registry::get_instance()) + { + BOTAN_ASSERT(sizeof(size_t) >= ceil( + static_cast<float>(XMSS_PublicKey::m_xmss_params.tree_height()) / 8.f), + "System type \"size_t\" not big enough to support" + " leaf index."); + + if(raw_key.size() != size()) + { + throw Integrity_Failure("Invalid XMSS private key size detected."); + } + + // 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(uint64_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() - 1))) + { + throw Integrity_Failure("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<byte>(begin, end)); + set_unused_leaf_index(static_cast<size_t>(unused_leaf)); + } + +XMSS_PrivateKey::XMSS_PrivateKey( + XMSS_Parameters::xmss_algorithm_t xmss_algo_id, + RandomNumberGenerator& rng) + : XMSS_PublicKey(xmss_algo_id, rng), + XMSS_Common_Ops(xmss_algo_id), + m_wots_priv_key(XMSS_PublicKey::m_xmss_params.ots_oid(), + public_seed(), + rng), + 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)); + } + +secure_vector<byte> +XMSS_PrivateKey::tree_hash(size_t start_idx, + size_t target_node_height, + XMSS_Address& adrs) + { + const secure_vector<byte>& seed = this->public_seed(); + + BOTAN_ASSERT((start_idx % (1 << target_node_height)) == 0, + "Start index must be divisible by 2^{target node height}."); + + std::vector<secure_vector<byte>> nodes( + XMSS_PublicKey::m_xmss_params.tree_height() + 1, + secure_vector<byte>(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<byte> node_levels(XMSS_PublicKey::m_xmss_params.tree_height() + 1); + + byte level = 0; + XMSS_WOTS_PublicKey pk(m_wots_priv_key.wots_parameters().oid(), seed); + + size_t last_idx = static_cast<size_t>(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(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()[adrs], + adrs); + adrs.set_type(XMSS_Address::Type::LTree_Address); + adrs.set_ltree_address(i); + create_l_tree(nodes[level], pk, adrs, seed); + node_levels[level] = 0; + + adrs.set_type(XMSS_Address::Type::Hash_Tree_Address); + adrs.set_tree_height(0); + adrs.set_tree_index(i); + + while(level > 0 && node_levels[level] == + node_levels[level - 1]) + { + adrs.set_tree_index(((adrs.get_tree_index() - 1) >> 1)); + randomize_tree_hash(nodes[level - 1], + nodes[level - 1], + nodes[level], + adrs, + seed); + node_levels[level - 1]++; + level--; //Pop stack top element + adrs.set_tree_height(adrs.get_tree_height() + 1); + } + level++; //push temporary node to stack + } + return nodes[level - 1]; + } + +std::shared_ptr<Atomic<size_t>> +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); + } + +secure_vector<byte> XMSS_PrivateKey::raw_private_key() const + { + std::vector<byte> pk { raw_public_key() }; + secure_vector<byte> result(pk.begin(), pk.end()); + result.reserve(size()); + + for(int i = 7; i >= 0; i--) + { + result.push_back( + static_cast<byte>( + static_cast<uint64_t>(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<PK_Ops::Signature> +XMSS_PrivateKey::create_signature_op(RandomNumberGenerator&, + const std::string&, + const std::string& provider) const + { + if(provider == "base" || provider.empty()) + return std::unique_ptr<PK_Ops::Signature>( + new XMSS_Signature_Operation(*this)); + + throw Provider_Not_Found(algo_name(), provider); + } + +} diff --git a/src/lib/pubkey/xmss/xmss_privatekey.h b/src/lib/pubkey/xmss/xmss_privatekey.h new file mode 100644 index 000000000..064d899a8 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_privatekey.h @@ -0,0 +1,258 @@ +/** + * XMSS_PrivateKey.h + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_PRIVATEKEY_H__ +#define BOTAN_XMSS_PRIVATEKEY_H__ + +#include <cstddef> +#include <iterator> +#include <memory> +#include <botan/alg_id.h> +#include <botan/assert.h> +#include <botan/exceptn.h> +#include <botan/pk_keys.h> +#include <botan/rng.h> +#include <botan/types.h> +#include <botan/xmss_parameters.h> +#include <botan/xmss_publickey.h> +#include <botan/atomic.h> +#include <botan/xmss_common_ops.h> +#include <botan/xmss_wots_privatekey.h> +#include <botan/xmss_index_registry.h> + +namespace Botan { + +/** + * 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, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + **/ +class BOTAN_DLL XMSS_PrivateKey : public virtual XMSS_PublicKey, + public XMSS_Common_Ops, + 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 AutoSeeded_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<byte>& 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<byte>& wots_priv_seed, + const secure_vector<byte>& prf, + const secure_vector<byte>& root, + const secure_vector<byte>& public_seed) + : XMSS_PublicKey(xmss_algo_id, root, public_seed), + XMSS_Common_Ops(xmss_algo_id), + m_wots_priv_key(XMSS_PublicKey::m_xmss_params.ots_oid(), + public_seed, + wots_priv_seed), + m_prf(prf), + m_index_reg(XMSS_Index_Registry::get_instance()) + { + set_unused_leaf_index(idx_leaf); + } + + /** + * 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 + { + return *recover_global_leaf_index(); + } + + /** + * 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) + { + if(idx >= (1ull << (XMSS_PublicKey::m_xmss_params.tree_height() - 1))) + { + throw Integrity_Failure("XMSS private key leaf index out of " + "bounds."); + } + else + { + std::atomic<size_t>& index = + static_cast<std::atomic<size_t>&>(*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 reserve_unused_leaf_index() + { + size_t idx = (static_cast<std::atomic<size_t>&>( + *recover_global_leaf_index())).fetch_add(1); + if(idx >= (1ull << (XMSS_PublicKey::m_xmss_params.tree_height() - 1))) + { + throw Integrity_Failure("XMSS private key, one time signatures " + "exhausted."); + } + return idx; + } + + /** + * 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<byte>& prf() const + { + return m_prf; + } + + secure_vector<byte>& prf() + { + return m_prf; + } + + virtual void set_public_seed( + const secure_vector<byte>& public_seed) override + { + m_public_seed = public_seed; + m_wots_priv_key.set_public_seed(public_seed); + } + + virtual void set_public_seed(secure_vector<byte>&& public_seed) override + { + m_public_seed = std::move(public_seed); + m_wots_priv_key.set_public_seed(m_public_seed); + } + + virtual const secure_vector<byte>& public_seed() const override + { + return m_public_seed; + } + + virtual std::unique_ptr<PK_Ops::Signature> + create_signature_op(RandomNumberGenerator&, + const std::string&, + const std::string& provider) const override; + + virtual secure_vector<byte> pkcs8_private_key() const override + { + return raw_private_key(); + } + + virtual size_t size() const override + { + return XMSS_PublicKey::size() + + sizeof(uint64_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. + **/ + virtual secure_vector<byte> 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<byte> tree_hash( + size_t start_idx, + size_t target_node_height, + XMSS_Address& adrs); + + private: + /** + * Fetches shared unused leaf index fromt the index registry + **/ + std::shared_ptr<Atomic<size_t>> recover_global_leaf_index() const; + + XMSS_WOTS_PrivateKey m_wots_priv_key; + secure_vector<byte> m_prf; + XMSS_Index_Registry& m_index_reg; + }; + +} + +#endif + diff --git a/src/lib/pubkey/xmss/xmss_publickey.cpp b/src/lib/pubkey/xmss/xmss_publickey.cpp new file mode 100644 index 000000000..4ec33e5f3 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_publickey.cpp @@ -0,0 +1,93 @@ +/** + * 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, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + * + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/internal/xmss_verification_operation.h> +#include <botan/xmss_publickey.h> + +namespace Botan { + +XMSS_PublicKey::XMSS_PublicKey(const secure_vector<byte>& raw_key) + : m_xmss_params(XMSS_PublicKey::deserialize_xmss_oid(raw_key)), + m_wots_params(m_xmss_params.ots_oid()) + { + if(raw_key.size() < size()) + { + throw Integrity_Failure("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 = 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 secure_vector<byte>& raw_key) + { + if(raw_key.size() < 4) + { + throw Integrity_Failure("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<XMSS_Parameters::xmss_algorithm_t>(raw_id); + } + +std::unique_ptr<PK_Ops::Verification> +XMSS_PublicKey::create_verification_op(const std::string&, + const std::string& provider) const + { + if(provider == "base" || provider.empty()) + { + return std::unique_ptr<PK_Ops::Verification>( + new XMSS_Verification_Operation(*this)); + } + throw Provider_Not_Found(algo_name(), provider); + } + +std::vector<byte> XMSS_PublicKey::raw_public_key() const + { + std::vector<byte> result + { + static_cast<byte>(m_xmss_params.oid() >> 24), + static_cast<byte>(m_xmss_params.oid() >> 16), + static_cast<byte>(m_xmss_params.oid() >> 8), + static_cast<byte>(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; + } + +} diff --git a/src/lib/pubkey/xmss/xmss_publickey.h b/src/lib/pubkey/xmss/xmss_publickey.h new file mode 100644 index 000000000..faa35d80a --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_publickey.h @@ -0,0 +1,273 @@ +/** + * XMSS Public Key + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_PUBLICKEY_H__ +#define BOTAN_XMSS_PUBLICKEY_H__ + +#include <cstddef> +#include <iterator> +#include <limits> +#include <memory> +#include <string> +#include <botan/alg_id.h> +#include <botan/asn1_oid.h> +#include <botan/der_enc.h> +#include <botan/assert.h> +#include <botan/exceptn.h> +#include <botan/rng.h> +#include <botan/types.h> +#include <botan/pk_keys.h> +#include <botan/xmss_parameters.h> +#include <botan/xmss_wots_parameters.h> +#include <botan/internal/pk_ops.h> + +namespace Botan { + +class XMSS_Verification_Operation; + +/** + * An XMSS: Extended Hash-Based Signature public key. + * The XMSS public key does not support the X509 standard. Instead the + * raw format described in [1] is used. + * + * [1] XMSS: Extended Hash-Based Signatures, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + **/ +class BOTAN_DLL XMSS_PublicKey : public virtual Public_Key + { + public: + /** + * Creates a new XMSS public key for the chosen XMSS signature method. + * New public and prf seeds are generated using rng. The appropriate WOTS + * signature method will be automatically set based on the chosen XMSS + * signature method. + * + * @param xmss_oid Identifier for the selected XMSS signature method. + * @param rng A random number generator to use for key generation. + **/ + XMSS_PublicKey(XMSS_Parameters::xmss_algorithm_t xmss_oid, + RandomNumberGenerator& rng) + : m_xmss_params(xmss_oid), m_wots_params(m_xmss_params.ots_oid()), + m_root(m_xmss_params.element_size()), + m_public_seed(rng.random_vec(m_xmss_params.element_size())) {} + + /** + * Creates an XMSS public key from a byte sequence produced by + * raw_private_key(). + **/ + XMSS_PublicKey(const secure_vector<byte>& raw_key); + + /** + * Creates a new XMSS public key for a chosen XMSS signature method as + * well as pre-computed root node and public_seed values. + * + * @param xmss_oid Identifier for the selected XMSS signature method. + * @param root Root node value. + * @param public_seed Public seed value. + **/ + XMSS_PublicKey(XMSS_Parameters::xmss_algorithm_t xmss_oid, + const secure_vector<byte>& root, + const secure_vector<byte>& public_seed) + : m_xmss_params(xmss_oid), m_wots_params(m_xmss_params.ots_oid()), + m_root(root), m_public_seed(public_seed) {} + + /** + * Creates a new XMSS public key for a chosen XMSS signature method as + * well as pre-computed root node and public_seed values. + * + * @param xmss_oid Identifier for the selected XMSS signature method. + * @param root Root node value. + * @param public_seed Public seed value. + **/ + XMSS_PublicKey(XMSS_Parameters::xmss_algorithm_t xmss_oid, + secure_vector<byte>&& root, + secure_vector<byte>&& public_seed) + : m_xmss_params(xmss_oid), m_wots_params(m_xmss_params.ots_oid()), + m_root(std::move(root)), m_public_seed(std::move(public_seed)) {} + + /** + * Retrieves the chosen XMSS signature method. + * + * @return XMSS signature method identifier. + **/ + XMSS_Parameters::xmss_algorithm_t xmss_oid() const + { + return m_xmss_params.oid(); + } + + /** + * Sets the chosen XMSS signature method + * + * @return XMSS signature method identifier. + **/ + void set_xmss_oid(XMSS_Parameters::xmss_algorithm_t xmss_oid) + { + m_xmss_params = XMSS_Parameters(xmss_oid); + m_wots_params = XMSS_WOTS_Parameters(m_xmss_params.ots_oid()); + } + + /** + * Retrieves the XMSS parameters determined by the chosen XMSS Signature + * method. + * + * @return XMSS parameters. + **/ + const XMSS_Parameters& xmss_parameters() const + { + return m_xmss_params; + } + + /** + * Retrieves the Winternitz One Time Signature (WOTS) method, + * corrseponding to the chosen XMSS signature method. + * + * @return XMSS WOTS signature method identifier. + **/ + XMSS_WOTS_Parameters::ots_algorithm_t wots_oid() const + { + return m_wots_params.oid(); + } + + /** + * Retrieves the Winternitz One Time Signature (WOTS) parameters + * corrseponding to the chosen XMSS signature method. + * + * @return XMSS WOTS signature method parameters. + **/ + const XMSS_WOTS_Parameters& wots_parameters() const + { + return m_wots_params; + } + + secure_vector<byte>& root() + { + return m_root; + } + + void set_root(const secure_vector<byte>& root) + { + m_root = root; + } + + void set_root(secure_vector<byte>&& root) + { + m_root = std::move(root); + } + + const secure_vector<byte>& root() const + { + return m_root; + } + + virtual secure_vector<byte>& public_seed() + { + return m_public_seed; + } + + virtual void set_public_seed(const secure_vector<byte>& public_seed) + { + m_public_seed = public_seed; + } + + virtual void set_public_seed(secure_vector<byte>&& public_seed) + { + m_public_seed = std::move(public_seed); + } + + virtual const secure_vector<byte>& public_seed() const + { + return m_public_seed; + } + + std::string algo_name() const override + { + return "XMSS"; + } + + virtual AlgorithmIdentifier algorithm_identifier() const override + { + return AlgorithmIdentifier(get_oid(), AlgorithmIdentifier::USE_NULL_PARAM); + } + + virtual bool check_key(RandomNumberGenerator&, bool) const override + { + BOTAN_ASSERT(false, "No key strength check implemented for XMSS."); + } + + virtual std::unique_ptr<PK_Ops::Verification> + create_verification_op(const std::string&, + const std::string& provider) const override; + + virtual size_t estimated_strength() const override + { + return m_xmss_params.estimated_strength(); + } + + virtual size_t max_input_bits() const override + { + return std::numeric_limits<size_t>::infinity(); + } + + virtual size_t message_part_size() const override + { + return std::numeric_limits<size_t>::infinity(); + } + + virtual size_t message_parts() const override + { + return std::numeric_limits<size_t>::infinity(); + } + + /** + * Currently x509 is not suppoerted for XMSS. x509_subject_public_key() + * returns a raw byte sequence as defined in [1]. This method acts as + * alias for raw_public_key(). + * + * @return raw non x509 compliant public key. + **/ + virtual std::vector<byte> x509_subject_public_key() const override + { + return raw_public_key(); + } + + /** + * Size in bytes of the serialized XMSS public key produced by + * raw_public_key(). + * + * @return size in bytes of serialized Public Key. + **/ + virtual size_t size() const + { + return sizeof(uint32_t) + 2 * m_xmss_params.element_size(); + } + + /** + * Generates a non standartized byte sequence representing the XMSS + * public key, as defined in [1] (p. 23, "XMSS Public Key") + * + * @return 4-byte OID, followed by n-byte root node, followed by + * public seed. + **/ + virtual std::vector<byte> raw_public_key() const; + + protected: + XMSS_Parameters m_xmss_params; + XMSS_WOTS_Parameters m_wots_params; + secure_vector<byte> m_root; + secure_vector<byte> m_public_seed; + + private: + XMSS_Parameters::xmss_algorithm_t deserialize_xmss_oid( + const secure_vector<byte>& raw_key); + }; + +} + +#endif diff --git a/src/lib/pubkey/xmss/xmss_signature.cpp b/src/lib/pubkey/xmss/xmss_signature.cpp new file mode 100644 index 000000000..f31dcd8bb --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_signature.cpp @@ -0,0 +1,96 @@ +/** + * XMSS Signature + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/internal/xmss_signature.h> + +namespace Botan { + +XMSS_Signature::XMSS_Signature(XMSS_Parameters::xmss_algorithm_t oid, + const secure_vector<byte>& raw_sig) + : m_leaf_idx(0), m_randomness(0, 0x00), m_tree_sig() + { + BOTAN_ASSERT(sizeof(size_t) >= ceil(static_cast<float>( + (XMSS_Parameters(oid)).tree_height()) / 8.f), + "System type \"size_t\" not big enough to support" + " leaf index."); + + XMSS_Parameters xmss_params(oid); + uint64_t leaf_idx = 0; + for(size_t i = 0; i < 8; i++) + leaf_idx = ((leaf_idx << 8) | raw_sig[i]); + + if(leaf_idx >= (1ull << (xmss_params.tree_height() - 1))) + { + throw Integrity_Failure("XMSS signature leaf index out of " + "bounds."); + } + m_leaf_idx = static_cast<size_t>(leaf_idx); + + auto begin = raw_sig.begin() + sizeof(uint64_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<byte>(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<byte>(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<byte> XMSS_Signature::bytes() const + { + secure_vector<byte> result + { + static_cast<byte>(static_cast<uint64_t>(m_leaf_idx) >> 56U), + static_cast<byte>(static_cast<uint64_t>(m_leaf_idx) >> 48U), + static_cast<byte>(static_cast<uint64_t>(m_leaf_idx) >> 40U), + static_cast<byte>(static_cast<uint64_t>(m_leaf_idx) >> 32U), + static_cast<byte>(static_cast<uint64_t>(m_leaf_idx) >> 24U), + static_cast<byte>(static_cast<uint64_t>(m_leaf_idx) >> 16U), + static_cast<byte>(static_cast<uint64_t>(m_leaf_idx) >> 8U), + static_cast<byte>(static_cast<uint64_t>(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/src/lib/pubkey/xmss/xmss_signature.h b/src/lib/pubkey/xmss/xmss_signature.h new file mode 100644 index 000000000..3194ad28c --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_signature.h @@ -0,0 +1,128 @@ +/** + * 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 <cstddef> +#include <iterator> +#include <botan/exceptn.h> +#include <botan/types.h> +#include <botan/secmem.h> +#include <botan/xmss_parameters.h> +#include <botan/xmss_wots_publickey.h> + +namespace Botan { + +class BOTAN_DLL XMSS_Signature + { + public: + /** + * Creates a signature from an XMSS signature method and a byte 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<byte>& 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<byte>& 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<byte>&& 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<byte> randomness() const + { + return m_randomness; + } + + secure_vector<byte>& randomness() + { + return m_randomness; + } + + void set_randomness(const secure_vector<byte>& randomness) + { + m_randomness = randomness; + } + + void set_randomness(secure_vector<byte>&& 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: + * 8-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 + * (len + h + 1)n bytes. + **/ + secure_vector<byte> bytes() const; + + private: + size_t m_leaf_idx; + secure_vector<byte> m_randomness; + XMSS_WOTS_PublicKey::TreeSignature m_tree_sig; + }; + +} + +#endif diff --git a/src/lib/pubkey/xmss/xmss_signature_operation.cpp b/src/lib/pubkey/xmss/xmss_signature_operation.cpp new file mode 100644 index 000000000..d223ddef0 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_signature_operation.cpp @@ -0,0 +1,112 @@ +/** + * XMSS Signature Operation + * Signature generation operation for Extended Hash-Based Signatures (XMSS) as + * defined in: + * + * [1] XMSS: Extended Hash-Based Signatures, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + * + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/internal/xmss_signature_operation.h> + +namespace Botan { + +XMSS_Signature_Operation::XMSS_Signature_Operation( + const XMSS_PrivateKey& private_key) + : XMSS_Common_Ops(private_key.xmss_oid()), + m_priv_key(private_key), + m_randomness(0), + m_leaf_idx(0), + m_is_initialized(false) + {} + +XMSS_WOTS_PublicKey::TreeSignature +XMSS_Signature_Operation::generate_tree_signature(const secure_vector<byte>& msg, + XMSS_PrivateKey& xmss_priv_key, + XMSS_Address& adrs) + { + + wots_keysig_t auth_path = build_auth_path(xmss_priv_key, adrs); + adrs.set_type(XMSS_Address::Type::OTS_Hash_Address); + adrs.set_ots_address(m_leaf_idx); + + wots_keysig_t sig_ots = xmss_priv_key.wots_private_key().sign(msg, adrs); + return XMSS_WOTS_PublicKey::TreeSignature(sig_ots, auth_path); + } + +XMSS_Signature +XMSS_Signature_Operation::sign(const secure_vector<byte>& msg_hash, + XMSS_PrivateKey& xmss_priv_key) + { + XMSS_Address adrs; + XMSS_Signature sig(m_leaf_idx, + m_randomness, + generate_tree_signature(msg_hash, xmss_priv_key,adrs)); + return sig; + } + +wots_keysig_t +XMSS_Signature_Operation::build_auth_path(XMSS_PrivateKey& priv_key, + XMSS_Address& adrs) + { + wots_keysig_t auth_path(m_xmss_params.tree_height()); + adrs.set_type(XMSS_Address::Type::Hash_Tree_Address); + + for(size_t j = 0; j < m_xmss_params.tree_height(); j++) + { + size_t k = (m_leaf_idx / (1 << j)) ^ 0x01; + auth_path[j] = priv_key.tree_hash(k * (1 << j), j, adrs); + } + + return auth_path; + } + +void XMSS_Signature_Operation::update(const byte msg[], size_t msg_len) + { + initialize(); + m_hash.h_msg_update(msg, msg_len); + } + + +secure_vector<byte> +XMSS_Signature_Operation::sign(RandomNumberGenerator&) + { + initialize(); + secure_vector<byte> signature(sign(m_hash.h_msg_final(), + m_priv_key).bytes()); + m_is_initialized = false; + return signature; + } + +void XMSS_Signature_Operation::initialize() + { + // return if we already initialized and reserved a leaf index for signing. + if(m_is_initialized) + return; + + secure_vector<byte> index_bytes; + // reserve leaf index so it can not be reused in by another signature + // operation using the same private key. + m_leaf_idx = m_priv_key.reserve_unused_leaf_index(); + + // write prefix for message hashing into buffer. + XMSS_Tools::get().concat(index_bytes, m_leaf_idx, 32); + m_randomness = m_hash.prf(m_priv_key.prf(), index_bytes); + index_bytes.clear(); + XMSS_Tools::get().concat(index_bytes, m_leaf_idx, + m_priv_key.xmss_parameters().element_size()); + m_hash.h_msg_init(m_randomness, + m_priv_key.root(), + index_bytes); + m_is_initialized = true; + } + +} + diff --git a/src/lib/pubkey/xmss/xmss_signature_operation.h b/src/lib/pubkey/xmss/xmss_signature_operation.h new file mode 100644 index 000000000..da84abdbc --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_signature_operation.h @@ -0,0 +1,107 @@ +/** + * XMSS Signature Operation + * (C) 2016 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 <cstddef> +#include <string> +#include <botan/secmem.h> +#include <botan/types.h> +#include <botan/assert.h> +#include <botan/xmss_parameters.h> +#include <botan/xmss_privatekey.h> +#include <botan/xmss_address.h> +#include <botan/xmss_common_ops.h> +#include <botan/internal/pk_ops.h> +#include <botan/internal/xmss_signature.h> +#include <botan/xmss_wots_publickey.h> + +namespace Botan { + +/** + * Signature generation operation for Extended Hash-Based Signatures (XMSS) as + * defined in: + * + * [1] XMSS: Extended Hash-Based Signatures, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + **/ +class BOTAN_DLL XMSS_Signature_Operation : public virtual PK_Ops::Signature, + public XMSS_Common_Ops + { + public: + typedef XMSS_PrivateKey Key_Type; + + XMSS_Signature_Operation(const XMSS_PrivateKey& private_key); + virtual ~XMSS_Signature_Operation() {} + + virtual size_t message_part_size() const override + { + return m_priv_key.message_part_size(); + } + + virtual size_t message_parts() const override + { + return m_priv_key.message_parts(); + } + + /** + * Creates an XMSS signature for the message provided through call to + * update(). + * + * @return serialized XMSS signature. + **/ + secure_vector<byte> sign(RandomNumberGenerator&) override; + + void update(const byte msg[], size_t msg_len) 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<byte>& 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<byte>& 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; + secure_vector<byte> m_randomness; + size_t m_leaf_idx; + bool m_is_initialized; + }; + +} + +#endif + diff --git a/src/lib/pubkey/xmss/xmss_tools.cpp b/src/lib/pubkey/xmss/xmss_tools.cpp new file mode 100644 index 000000000..13e66759c --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_tools.cpp @@ -0,0 +1,32 @@ +/** + * XMSS Tools + * Contains some helper functions. + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ +#include <botan/xmss_tools.h> + +namespace Botan { + +XMSS_Tools::XMSS_Tools() + { +#if defined(BOTAN_TARGET_CPU_HAS_KNOWN_ENDIANESS) +#if defined(BOTAN_TARGET_CPU_IS_LITTLE_ENDIAN) + m_is_little_endian = true; +#else + m_is_little_endian = false; +#endif +#else + uint16_t data = 0x01; + m_is_little_endian = reinterpret_cast<const byte*>(&data)[0] == 0x01; +#endif + } + +const XMSS_Tools& XMSS_Tools::get() + { + static const XMSS_Tools self; + return self; + } + +} diff --git a/src/lib/pubkey/xmss/xmss_tools.h b/src/lib/pubkey/xmss/xmss_tools.h new file mode 100644 index 000000000..07e36ea71 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_tools.h @@ -0,0 +1,111 @@ +/** + * XMSS Address + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_TOOLS_H__ +#define BOTAN_XMSS_TOOLS_H__ + +#include <stdint.h> +#include <iterator> +#include <type_traits> +#include <botan/types.h> +#include <botan/secmem.h> + +namespace Botan { + +/** + * Helper tools for low level byte operations required + * for the XMSS implementation. + **/ + class XMSS_Tools + { + public: + XMSS_Tools(const XMSS_Tools&) = delete; + void operator=(const XMSS_Tools&) = delete; + + static const XMSS_Tools& get(); + + /** + * Retrieves information about endianess + * + * @return true if machine uses little-endian byte order, false + * otherwise. + **/ + inline bool is_little_endian() const { return m_is_little_endian; } + + /** + * 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<typename T, + typename U = typename std::enable_if<std::is_integral<T>::value, + void>::type> + void concat(secure_vector<byte>& target, const T& src) const; + + /** + * 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 <typename T, + typename U = typename std::enable_if<std::is_integral<T>::value, + void>::type> + void concat(secure_vector<byte>& target, const T& src, size_t len) const; + + private: + XMSS_Tools(); + + bool m_is_little_endian; + }; + +template <typename T, typename U> +void XMSS_Tools::concat(secure_vector<byte>& target, const T& src) const + { + const byte* src_bytes = reinterpret_cast<const byte*>(&src); + if(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 <typename T, typename U> +void XMSS_Tools::concat(secure_vector<byte>& target, + const T& src, + size_t len) const + { + size_t c = static_cast<size_t>(std::min(len, sizeof(src))); + if(len > sizeof(src)) + { + target.resize(target.size() + len - sizeof(src), 0); + } + + const byte* src_bytes = reinterpret_cast<const byte*>(&src); + if(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/src/lib/pubkey/xmss/xmss_verification_operation.cpp b/src/lib/pubkey/xmss/xmss_verification_operation.cpp new file mode 100644 index 000000000..20945e8ca --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_verification_operation.cpp @@ -0,0 +1,128 @@ +/** + * XMSS Verification Operation + * Provides signature verification capabilities for Extended Hash-Based + * Signatures (XMSS). + * + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/internal/xmss_verification_operation.h> + +namespace Botan { + +XMSS_Verification_Operation::XMSS_Verification_Operation( + const XMSS_PublicKey& public_key) + : XMSS_Common_Ops(public_key.xmss_oid()), + m_pub_key(public_key), + m_msg_buf(0) + { + } + +secure_vector<byte> +XMSS_Verification_Operation::root_from_signature(const XMSS_Signature& sig, + const secure_vector<byte>& msg, + XMSS_Address& adrs, + const secure_vector<byte>& seed) + { + adrs.set_type(XMSS_Address::Type::OTS_Hash_Address); + adrs.set_ots_address(sig.unused_leaf_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(sig.unused_leaf_index()); + + std::array<secure_vector<byte>, 2> node; + create_l_tree(node[0], pub_key_ots, adrs, seed); + + adrs.set_type(XMSS_Address::Type::Hash_Tree_Address); + adrs.set_tree_index(sig.unused_leaf_index()); + + for(size_t k = 0; k < m_xmss_params.tree_height(); k++) + { + adrs.set_tree_height(k); + if(((sig.unused_leaf_index() / (1 << k)) & 0x01) == 0) + { + adrs.set_tree_index(adrs.get_tree_index() >> 1); + randomize_tree_hash(node[1], + node[0], + sig.tree().authentication_path()[k], + adrs, + seed); + } + else + { + adrs.set_tree_index((adrs.get_tree_index() - 1) >> 1); + randomize_tree_hash(node[1], + sig.tree().authentication_path()[k], + node[0], + adrs, + seed); + } + node[0] = node[1]; + } + return node[0]; + } + +bool +XMSS_Verification_Operation::verify(const XMSS_Signature& sig, + const secure_vector<byte>& msg, + const XMSS_PublicKey& public_key) + { + XMSS_Address adrs; + secure_vector<byte> index_bytes; + XMSS_Tools::get().concat(index_bytes, + sig.unused_leaf_index(), + m_xmss_params.element_size()); + secure_vector<byte> msg_digest = + m_hash.h_msg(sig.randomness(), + public_key.root(), + index_bytes, + msg); + + secure_vector<byte> 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 byte 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 byte sig[], + size_t sig_len) + { + try + { + XMSS_Signature signature(m_pub_key.xmss_parameters().oid(), + secure_vector<byte>(sig, sig + sig_len)); + bool result = verify(signature, m_msg_buf, m_pub_key); + m_msg_buf.clear(); + return result; + } + catch(Integrity_Failure& e) + { + m_msg_buf.clear(); + return false; + } + } + +} + diff --git a/src/lib/pubkey/xmss/xmss_verification_operation.h b/src/lib/pubkey/xmss/xmss_verification_operation.h new file mode 100644 index 000000000..6759e3d43 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_verification_operation.h @@ -0,0 +1,99 @@ +/** + * 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 <array> +#include <cstddef> +#include <iterator> +#include <string> +#include <botan/assert.h> +#include <botan/types.h> +#include <botan/xmss_publickey.h> +#include <botan/xmss_common_ops.h> +#include <botan/internal/pk_ops.h> +#include <botan/internal/xmss_signature.h> + +namespace Botan { + +/** + * Provides signature verification capabilities for Extended Hash-Based + * Signatures (XMSS). + **/ + class BOTAN_DLL XMSS_Verification_Operation + : public virtual PK_Ops::Verification, + public XMSS_Common_Ops + { + public: + typedef XMSS_PublicKey Key_Type; + + XMSS_Verification_Operation( + const XMSS_PublicKey& public_key); + + virtual ~XMSS_Verification_Operation() {} + + virtual size_t max_input_bits() const override + { + return m_pub_key.max_input_bits(); + } + + virtual size_t message_part_size() const override + { + return m_pub_key.message_part_size(); + } + + virtual size_t message_parts() const override + { + return m_pub_key.message_parts(); + } + + virtual bool is_valid_signature(const byte sig[], + size_t sig_len) override; + + void update(const byte 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 adrs 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<byte> root_from_signature( + const XMSS_Signature& sig, + const secure_vector<byte>& msg, + XMSS_Address& ards, + const secure_vector<byte>& 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. + * @paeam pub_key + * + * @return true if signature sig is valid for msg, false otherwise. + **/ + bool verify(const XMSS_Signature& sig, + const secure_vector<byte>& msg, + const XMSS_PublicKey& pub_key); + + XMSS_PublicKey m_pub_key; + secure_vector<byte> m_msg_buf; + }; + +} + +#endif diff --git a/src/lib/pubkey/xmss/xmss_wots_parameters.cpp b/src/lib/pubkey/xmss/xmss_wots_parameters.cpp new file mode 100644 index 000000000..b908afeb4 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_wots_parameters.cpp @@ -0,0 +1,130 @@ +/** + * XMSS WOTS Parameters + * Descibes a signature method for XMSS Winternitz One Time Signatures, + * as defined in: + * [1] XMSS: Extended Hash-Based Signatures, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + * + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/xmss_wots_parameters.h> + +namespace Botan { + +const std::map<std::string, XMSS_WOTS_Parameters::ots_algorithm_t> + XMSS_WOTS_Parameters::m_oid_name_lut = + { + { "WOTSP_SHA2-256_W16", WOTSP_SHA2_256_W16 }, + { "WOTSP_SHA2-512_W16", WOTSP_SHA2_512_W16 } + }; + +XMSS_WOTS_Parameters::XMSS_WOTS_Parameters(const std::string& algo_name) + : XMSS_WOTS_Parameters(m_oid_name_lut.at(algo_name)) + {} + +XMSS_WOTS_Parameters::XMSS_WOTS_Parameters(ots_algorithm_t oid) + : m_oid(oid) + { + switch(oid) + { + case WOTSP_SHA2_256_W16: + m_element_size = 32; + m_w = 16; + m_len = 67; + m_name = "WOTSP_SHA2-256_W16"; + m_hash_name = "SHA-256"; + m_strength = 256; + break; + case WOTSP_SHA2_512_W16: + m_element_size = 64; + m_w = 16; + m_len = 131; + m_name = "WOTSP_SHA2-512_W16"; + m_hash_name = "SHA-512"; + m_strength = 512; + break; +// FIXME: Uncomment once SHAKE128/256 implementation is available in Botan. +// case WOTSP_SHAKE128_W16: +// m_element_size = 32; +// m_w = 16; +// m_len = 67; +// m_name = "WOTSP_SHAKE128_W16"; +// m_hash_name = "<MISSING>"; +// m_strength = 256; +// break; +// case WOTSP_SHAKE256_W16: +// m_element_size = 64; +// m_w = 16; +// m_len = 131; +// m_name = "WOTSP_SHAKE256_W16"; +// m_hash_name = "<MISSING>"; +// m_strength = 512; +// break; + default: + throw Unsupported_Argument( + "Algorithm id does not match any XMSS WOTS algorithm id."); + break; + } + + m_w == 16 ? m_lg_w = 4 : m_lg_w = 2; + m_len_1 = static_cast<size_t>(ceil((8 * element_size()) / m_lg_w)); + m_len_2 = static_cast<size_t>( + 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<byte> +XMSS_WOTS_Parameters::base_w(const secure_vector<byte>& msg, size_t out_size) const + { + secure_vector<byte> 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<byte>((total >> bits) & (m_w - 1))); + } + return result; + } + +secure_vector<byte> +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<size_t>( + ceil(static_cast<float>(m_len_2 * m_lg_w) / 8.f)); + secure_vector<byte> result; + XMSS_Tools::get().concat(result, value, len_2_bytes); + return base_w(result, m_len_2); + } + +void +XMSS_WOTS_Parameters::append_checksum(secure_vector<byte>& data) + { + size_t csum = 0; + + for(size_t i = 0; i < data.size(); i++) + { + csum += wots_parameter() - 1 - data[i]; + } + + secure_vector<byte> csum_bytes = base_w(csum); + std::move(csum_bytes.begin(), csum_bytes.end(), std::back_inserter(data)); + } + +} diff --git a/src/lib/pubkey/xmss/xmss_wots_parameters.h b/src/lib/pubkey/xmss/xmss_wots_parameters.h new file mode 100644 index 000000000..a4840c354 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_wots_parameters.h @@ -0,0 +1,129 @@ +/** + * XMSS WOTS Parameters + * (C) 2016 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 <cstddef> +#include <cstdint> +#include <iterator> +#include <map> +#include <string> +#include <math.h> +#include <botan/assert.h> +#include <botan/types.h> +#include <botan/secmem.h> +#include <botan/exceptn.h> +#include <botan/xmss_tools.h> + +namespace Botan { + +/** + * Descibes a signature method for XMSS Winternitz One Time Signatures, + * as defined in: + * [1] XMSS: Extended Hash-Based Signatures, + * draft-itrf-cfrg-xmss-hash-based-signatures-06 + * Release: July 2016. + * https://datatracker.ietf.org/doc/ + * draft-irtf-cfrg-xmss-hash-based-signatures/?include_text=1 + **/ +class XMSS_WOTS_Parameters + { + public: + enum ots_algorithm_t + { + WOTSP_SHA2_256_W16 = 0x01000001, + WOTSP_SHA2_512_W16 = 0x02000002, +// FIXME: Uncomment once SHAKE128/256 implementation is available in Botan. +// WOTSP_SHAKE128_W16 = 0x03000003, +// WOTSP_SHAKE256_W16 = 0x04000004 + }; + + XMSS_WOTS_Parameters(const std::string& algo_name); + XMSS_WOTS_Parameters(ots_algorithm_t ots_spec); + + /** + * 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<byte> base_w(const secure_vector<byte>& msg, size_t out_size) const; + + secure_vector<byte> base_w(size_t value) const; + + void append_checksum(secure_vector<byte>& 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<std::string, ots_algorithm_t> 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; + }; + +} + +#endif diff --git a/src/lib/pubkey/xmss/xmss_wots_privatekey.cpp b/src/lib/pubkey/xmss/xmss_wots_privatekey.cpp new file mode 100644 index 000000000..f94ba3612 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_wots_privatekey.cpp @@ -0,0 +1,80 @@ +/** + * XMSS WOTS Private Key + * A Winternitz One Time Signature private key for use with Extended Hash-Based + * Signatures. + * + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/xmss_wots_privatekey.h> + +namespace Botan { + +wots_keysig_t +XMSS_WOTS_PrivateKey::generate(const secure_vector<byte>& priv_seed) + { + wots_keysig_t priv_key(m_wots_params.len(), + secure_vector<byte>(0)); + + for(size_t i = 0; i < m_wots_params.len(); i++) + { + XMSS_Tools::get().concat<size_t>(priv_key[i], i, 32); + m_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) + { + 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(i); + chain(pub_key[i], 0, m_wots_params.wots_parameter() - 1, adrs, + public_seed()); + } + } + +wots_keysig_t +XMSS_WOTS_PrivateKey::sign( + const secure_vector<byte>& msg, + XMSS_Address& adrs) + + { + secure_vector<byte> 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)[adrs]); + + for(size_t i = 0; i < m_wots_params.len(); i++) + { + adrs.set_chain_address(i); + chain(sig[i], 0 , msg_digest[i], adrs, m_public_seed); + } + + return sig; + } + +} diff --git a/src/lib/pubkey/xmss/xmss_wots_privatekey.h b/src/lib/pubkey/xmss/xmss_wots_privatekey.h new file mode 100644 index 000000000..422d014f4 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_wots_privatekey.h @@ -0,0 +1,265 @@ +/** + * XMSS WOTS Private Key + * (C) 2016 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 <cstddef> +#include <memory> +#include <botan/alg_id.h> +#include <botan/assert.h> +#include <botan/pk_keys.h> +#include <botan/types.h> +#include <botan/xmss_wots_parameters.h> +#include <botan/xmss_address.h> +#include <botan/xmss_wots_publickey.h> + +namespace Botan { + +/** A Winternitz One Time Signature private key for use with Extended Hash-Based + * Signatures. + **/ +class BOTAN_DLL XMSS_WOTS_PrivateKey : 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<byte>& 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<byte>& 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<byte>& public_seed, + const secure_vector<byte>& 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. + * + * @param i Index of the key to retrieve. + * + * @return WOTS secret key. + **/ + wots_keysig_t operator[](size_t i) + { + secure_vector<byte> idx_bytes; + XMSS_Tools::get().concat(idx_bytes, i, m_wots_params.element_size()); + m_hash.h(idx_bytes, m_private_seed, idx_bytes); + return generate(idx_bytes); + } + + /** + * Retrieves the i-th WOTS private key using pseudo random key + * (re-)generation. + * + * @param adrs The address of the key to retrieve. + * + * @return WOTS secret key. + **/ + wots_keysig_t operator[](const XMSS_Address& adrs) + { + secure_vector<byte> result; + m_hash.prf(result, m_private_seed, adrs.bytes()); + return generate(result); + } + + wots_keysig_t generate_private_key(const secure_vector<byte>& 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. + * + * @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. + **/ + void generate_public_key( + XMSS_WOTS_PublicKey& pub_key, + wots_keysig_t&& in_key_data, + XMSS_Address& adrs); + + /** + * 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. + **/ + wots_keysig_t sign( + const secure_vector<byte>& msg, + XMSS_Address& adrs); + + /** + * 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<byte>& private_seed() const + { + return m_private_seed; + } + + ///** + // * Retrieves the secret seed used to generate WOTS+ chains. The seed + // * should be a uniformly random n-byte value. + // * + // * @return secret seed. + // **/ + //secure_vector<byte>& private_seed() { 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<byte>& 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<byte>&& private_seed) + { + m_private_seed = std::move(private_seed); + } + + virtual AlgorithmIdentifier + pkcs8_algorithm_identifier() const override + { + BOTAN_ASSERT(false, "No AlgorithmIdentifier available for XMSS-WOTS."); + } + + virtual std::unique_ptr<PK_Ops::Signature> + create_signature_op(RandomNumberGenerator&, + const std::string&, + const std::string& provider) const override + { + BOTAN_ASSERT(false, "XMSS_WOTS_Signature_Operation not available."); + } + + virtual secure_vector<byte> pkcs8_private_key() const override + { + BOTAN_ASSERT(false, "No PKCS8 key format defined for XMSS-WOTS."); + } + + private: + /** + * Algorithm 3: "Generating a WOTS+ Private Key". + * Generates a private key. + * + * @param private_seed Uniformly random n-byte value. + * + * @returns a vector of length key_size() of vectors of n bytes length + * containing uniformly random data. + **/ + wots_keysig_t generate(const secure_vector<byte>& private_seed); + + secure_vector<byte> m_private_seed; + }; + +} + +#endif + diff --git a/src/lib/pubkey/xmss/xmss_wots_publickey.cpp b/src/lib/pubkey/xmss/xmss_wots_publickey.cpp new file mode 100644 index 000000000..aa0240be8 --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_wots_publickey.cpp @@ -0,0 +1,66 @@ +/** + * XMSS WOTS Public Key + * A Winternitz One Time Signature public key for use with Extended Hash-Based + * Signatures. + * + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#include <botan/xmss_wots_publickey.h> + +namespace Botan { + +void +XMSS_WOTS_PublicKey::chain(secure_vector<byte>& result, + size_t start_idx, + size_t steps, + XMSS_Address& adrs, + const secure_vector<byte>& seed) + { + for(size_t i = start_idx; + i < (start_idx + steps) && i < m_wots_params.wots_parameter(); + i++) + { + adrs.set_hash_address(i); + + //Calculate tmp XOR bitmask + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Mask_Mode); + xor_buf(result, m_hash.prf(seed, adrs.bytes()), result.size()); + + // Calculate key + adrs.set_key_mask_mode(XMSS_Address::Key_Mask::Key_Mode); + + //Calculate f(key, tmp XOR bitmask) + m_hash.f(result, m_hash.prf(seed, adrs.bytes()), result); + } + } + +wots_keysig_t +XMSS_WOTS_PublicKey::pub_key_from_signature(const secure_vector<byte>& msg, + const wots_keysig_t& sig, + XMSS_Address& adrs, + const secure_vector<byte>& seed) + { + secure_vector<byte> 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(i); + chain(result[i], + msg_digest[i], + m_wots_params.wots_parameter() - 1 - msg_digest[i], + adrs, + seed); + } + return result; + } + +} diff --git a/src/lib/pubkey/xmss/xmss_wots_publickey.h b/src/lib/pubkey/xmss/xmss_wots_publickey.h new file mode 100644 index 000000000..e024c486f --- /dev/null +++ b/src/lib/pubkey/xmss/xmss_wots_publickey.h @@ -0,0 +1,337 @@ +/** + * XMSS WOTS Public Key + * (C) 2016 Matthias Gierlings + * + * Botan is released under the Simplified BSD License (see license.txt) + **/ + +#ifndef BOTAN_XMSS_WOTS_PUBLICKEY_H__ +#define BOTAN_XMSS_WOTS_PUBLICKEY_H__ + +#include <cstddef> +#include <string> +#include <vector> +#include <botan/auto_rng.h> +#include <botan/alg_id.h> +#include <botan/asn1_oid.h> +#include <botan/assert.h> +#include <botan/pk_keys.h> +#include <botan/types.h> +#include <botan/xmss_wots_parameters.h> +#include <botan/xmss_address.h> +#include <botan/xmss_hash.h> + +namespace Botan { + +typedef std::vector<secure_vector<byte>> wots_keysig_t; + +/** + * A Winternitz One Time Signature public key for use with Extended Hash-Based + * Signatures. + **/ +class BOTAN_DLL XMSS_WOTS_PublicKey : virtual public Public_Key + { + public: + class TreeSignature + { + public: + TreeSignature() + : m_ots_sig(), m_auth_path() {} + + TreeSignature(const wots_keysig_t& ots_sig, + const wots_keysig_t& auth_path) + : m_ots_sig(ots_sig), m_auth_path(auth_path) + {} + + TreeSignature(wots_keysig_t&& ots_sig, + wots_keysig_t&& auth_path) + : m_ots_sig(std::move(ots_sig)), + m_auth_path(std::move(auth_path)) + {} + + const wots_keysig_t& ots_signature() const + { + return m_ots_sig; + } + + wots_keysig_t& ots_signature() + { + return m_ots_sig; + } + + const wots_keysig_t& authentication_path() const + { + return m_auth_path; + } + + wots_keysig_t& authentication_path() + { + return m_auth_path; + } + + private: + wots_keysig_t m_ots_sig; + wots_keysig_t m_auth_path; + }; + + /** + * Creates a XMSS_WOTS_PublicKey for the signature method identified by + * oid. The public seed for this key will be initialized with a + * uniformly random n-byte value, where "n" is the element size of the + * selected signature method. + * + * @param oid Identifier for the selected signature method. + **/ + XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid) + : m_wots_params(oid), + m_hash(m_wots_params.hash_function_name()) {} + + /** + * Creates a XMSS_WOTS_PublicKey for the signature method identified by + * oid. The public seed for this key will be initialized with a + * uniformly random n-byte value, where "n" is the element size of the + * selected signature method. + * + * @param oid Identifier for the selected signature method. + * @param rng A random number generate used to generate the public seed. + **/ + XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid, + RandomNumberGenerator& rng) + : m_wots_params(oid), + m_hash(m_wots_params.hash_function_name()), + m_public_seed(rng.random_vec(m_wots_params.element_size())) {} + + /** + * Creates a XMSS_WOTS_PrivateKey for the signature method identified by + * oid, with a precomputed public seed. + * + * @param oid Identifier for the selected signature method. + * @param public_seed A precomputed public seed of n-bytes length. + **/ + XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid, + secure_vector<byte> public_seed) + : m_wots_params(oid), + m_hash(m_wots_params.hash_function_name()), + m_public_seed(public_seed) {} + + /** + * Creates a XMSS_WOTS_PublicKey for the signature method identified by + * oid. The public seed will be initialized with a precomputed seed and + * and precomputed key data which should be derived from a + * XMSS_WOTS_PrivateKey. + * + * @param oid Ident:s/ifier for the selected signature methods. + * @param public_seed A precomputed public seed of n-bytes length. + * @param key Precomputed raw key data of the XMSS_WOTS_PublicKey. + **/ + XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid, + secure_vector<byte>&& public_seed, + wots_keysig_t&& key) + : m_wots_params(oid), + m_hash(m_wots_params.hash_function_name()), + m_key(std::move(key)), + m_public_seed(std::move(public_seed)) + {} + + /** + * Creates a XMSS_WOTS_PublicKey for the signature method identified by + * oid. The public seed will be initialized with a precomputed seed and + * and precomputed key data which should be derived from a + * XMSS_WOTS_PrivateKey. + * + * @param oid Identifier for the selected signature methods. + * @param public_seed A precomputed public seed of n-bytes length. + * @param key Precomputed raw key data of the XMSS_WOTS_PublicKey. + **/ + XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid, + const secure_vector<byte>& public_seed, + const wots_keysig_t& key) + : m_wots_params(oid), + m_hash(m_wots_params.hash_function_name()), + m_key(key), + m_public_seed(public_seed) + {} + + /** + * Creates a XMSS_WOTS_PublicKey form a message and signature using + * Algorithm 6 WOTS_pkFromSig defined in the XMSS standard. This + * overload is used to verify a message using a public key. + * + * @param oid WOTSP algorithm identifier. + * @param msg A message. + * @param sig A WOTS signature for msg. + * @param adrs An XMSS_Address. + * @param public_seed The public public_seed. + **/ + XMSS_WOTS_PublicKey(XMSS_WOTS_Parameters::ots_algorithm_t oid, + const secure_vector<byte>& msg, + const wots_keysig_t& sig, + XMSS_Address& adrs, + const secure_vector<byte>& public_seed) + : m_wots_params(oid), + m_hash(m_wots_params.hash_function_name()), + m_key(pub_key_from_signature(msg, + sig, + adrs, + public_seed)), + m_public_seed(public_seed) + {} + + /** + * Retrieves the i-th element out of the length len chain of + * n-byte elements contained in the public key. + * + * @param i index of the element. + * @returns n-byte element addressed by i. + **/ + const secure_vector<byte>& operator[](size_t i) const { return m_key[i]; } + secure_vector<byte>& operator[](size_t i) { return m_key[i]; } + + /** + * Convert the key into the raw key data. The key becomes a length + * len vector of n-byte elements. + **/ + operator const wots_keysig_t& () const { return m_key; }; + + /** + * Convert the key into the raw key data. The key becomes a length + * len vector of n-byte elements. + **/ + operator wots_keysig_t& () { return m_key; } + + const secure_vector<byte>& public_seed() const { return m_public_seed; } + secure_vector<byte>& public_seed() { return m_public_seed; } + void set_public_seed(const secure_vector<byte>& public_seed) + { + m_public_seed = public_seed; + } + void set_public_seed(secure_vector<byte>&& public_seed) + { + m_public_seed = std::move(public_seed); + } + + const wots_keysig_t& key_data() const { return m_key; } + wots_keysig_t& key_data() { return m_key; } + void set_key_data(const wots_keysig_t& key_data) + { + m_key = key_data; + } + void set_key_data(wots_keysig_t&& key_data) + { + m_key = std::move(key_data); + } + + const XMSS_WOTS_Parameters& wots_parameters() const + { + return m_wots_params; + } + + virtual std::string algo_name() const override + { + return m_wots_params.name(); + } + + virtual AlgorithmIdentifier algorithm_identifier() const override + { + BOTAN_ASSERT(false, "No AlgorithmIdentifier available for XMSS-WOTS."); + } + + virtual bool check_key(RandomNumberGenerator&, bool) const override + { + BOTAN_ASSERT(false, "No key strength check implemented for XMSS-WOTS."); + } + + virtual std::unique_ptr<PK_Ops::Verification> + create_verification_op(const std::string&, + const std::string& provider) const override + { + BOTAN_ASSERT(false, "XMSS_WOTS_Verification_Operation not available."); + } + + virtual size_t estimated_strength() const override + { + return m_wots_params.estimated_strength(); + } + + virtual size_t max_input_bits() const override + { + return message_part_size() * 8; + } + + virtual size_t message_part_size() const override + { + return m_wots_params.element_size(); + } + + virtual size_t message_parts() const override + { + return 1; + } + + virtual std::vector<byte> x509_subject_public_key() const override + { + BOTAN_ASSERT(false, "No x509 key format defined for XMSS-WOTS."); + } + + bool operator==(const XMSS_WOTS_PublicKey& key) + { + return m_key == key.m_key; + } + + bool operator!=(const XMSS_WOTS_PublicKey& key) + { + return !(*this == key); + } + + protected: + /** + * Algorithm 2: Chaining Function. + * + * Takes an n-byte input string and transforms it into a the function + * result iterating the cryptographic hash function "F" steps times on + * the input x using the outputs of the PRNG "G". + * + * + * @param[out] x An n-byte input string, that will be transformed into + * the chaining function result. + * @param start_idx The start index. + * @param steps A number of steps. + * @param adrs An OTS Hash Address. + * @param public_seed A public seed. + * + **/ + void chain(secure_vector<byte>& x, + size_t start_idx, + size_t steps, + XMSS_Address& adrs, + const secure_vector<byte>& public_seed); + + XMSS_WOTS_Parameters m_wots_params; + XMSS_Hash m_hash; + + wots_keysig_t m_key; + secure_vector<byte> m_public_seed; + + private: + /** + * Algorithm 6: "WOTS_pkFromSig" + * Computes a Winternitz One Time Signature+ public key from a message and + * its signature. + * + * @param msg A message. + * @param sig The signature for msg. + * @param adrs An address. + * @param public_seed A public_seed. + * + * @return Temporary WOTS+ public key. + **/ + wots_keysig_t pub_key_from_signature( + const secure_vector<byte>& msg, + const wots_keysig_t& sig, + XMSS_Address& adrs, + const secure_vector<byte>& public_seed); + }; + +} + +#endif |