9#include <botan/internal/lms.h>
11#include <botan/exceptn.h>
12#include <botan/hash.h>
13#include <botan/internal/buffer_slicer.h>
14#include <botan/internal/buffer_stuffer.h>
15#include <botan/internal/concat_util.h>
16#include <botan/internal/hash_engine.h>
17#include <botan/internal/loadstor.h>
18#include <botan/internal/tree_hash.h>
26constexpr uint16_t D_LEAF = 0x8282;
31constexpr uint16_t D_INTR = 0x8383;
36class TreeAddress final {
38 explicit TreeAddress(uint32_t total_tree_height) : m_h(total_tree_height), m_r(0) {
39 BOTAN_ARG_CHECK(total_tree_height > 0 && total_tree_height < 32,
"Invalid tree height");
42 TreeAddress& set_address(LMS_TreeLayerIndex tree_layer,
LMS_Tree_Node_Idx tree_index) {
45 m_r = (1 << (m_h - tree_layer)).get() + tree_index.get();
49 uint32_t r()
const {
return m_r; }
51 bool is_leaf()
const {
return m_r >= (1 << m_h); }
59 LMS_TreeLayerIndex m_h;
65 const TreeAddress& address,
79 const TreeAddress& tree_address,
81 hash.update(lmots_pk.identifier());
82 hash.update(
store_be(tree_address.r()));
84 hash.update(lmots_pk.K());
92 const size_t m = lms_sk.lms_params().m();
93 const auto& identifier = lms_sk.identifier();
96 std::vector<uint8_t> ks(count * m);
97 lmots_compute_pubkeys(ks, lms_sk.lmots_params(), identifier, first_idx, count, lms_sk.seed(), *engine);
100 const size_t prefix_len = identifier.size() +
sizeof(uint32_t) +
sizeof(uint16_t);
101 std::vector<uint8_t> prefixes(count * prefix_len);
102 std::vector<std::span<uint8_t>> outs(count);
103 std::vector<std::span<const uint8_t>> prefix_spans(count);
104 std::vector<std::span<const uint8_t>> k_spans(count);
105 for(
size_t i = 0; i != count; ++i) {
106 const uint32_t r = (uint32_t(1) << lms_sk.lms_params().h()) + first_idx.get() +
static_cast<uint32_t
>(i);
107 const auto prefix_span = std::span(prefixes).subspan(i * prefix_len, prefix_len);
109 prefix.append(identifier);
112 prefix_spans[i] = prefix_span;
113 outs[i] = out.subspan(i * m, m);
114 k_spans[i] = std::span(ks).subspan(i * m, m);
116 engine->batch_hash(outs, prefix_spans, k_spans);
122 std::optional<LMS_Tree_Node_Idx> leaf_idx,
124 auto hash_pair_func = get_hash_pair_func_for_identifier(lms_sk.lms_params(), lms_sk.identifier());
125 auto gen_leaves = lms_gen_leaves_func(lms_sk);
126 TreeAddress lms_tree_address(lms_sk.lms_params().h());
131 lms_sk.lms_params().m(),
132 LMS_TreeLayerIndex(lms_sk.lms_params().h()),
134 std::move(hash_pair_func),
135 std::move(gen_leaves),
149 return {
"SHA-256",
static_cast<uint8_t
>(5)};
151 return {
"SHA-256",
static_cast<uint8_t
>(10)};
153 return {
"SHA-256",
static_cast<uint8_t
>(15)};
155 return {
"SHA-256",
static_cast<uint8_t
>(20)};
157 return {
"SHA-256",
static_cast<uint8_t
>(25)};
159 return {
"Truncated(SHA-256,192)",
static_cast<uint8_t
>(5)};
161 return {
"Truncated(SHA-256,192)",
static_cast<uint8_t
>(10)};
163 return {
"Truncated(SHA-256,192)",
static_cast<uint8_t
>(15)};
165 return {
"Truncated(SHA-256,192)",
static_cast<uint8_t
>(20)};
167 return {
"Truncated(SHA-256,192)",
static_cast<uint8_t
>(25)};
169 return {
"SHAKE-256(256)",
static_cast<uint8_t
>(5)};
171 return {
"SHAKE-256(256)",
static_cast<uint8_t
>(10)};
173 return {
"SHAKE-256(256)",
static_cast<uint8_t
>(15)};
175 return {
"SHAKE-256(256)",
static_cast<uint8_t
>(20)};
177 return {
"SHAKE-256(256)",
static_cast<uint8_t
>(25)};
179 return {
"SHAKE-256(192)",
static_cast<uint8_t
>(5)};
181 return {
"SHAKE-256(192)",
static_cast<uint8_t
>(10)};
183 return {
"SHAKE-256(192)",
static_cast<uint8_t
>(15)};
185 return {
"SHAKE-256(192)",
static_cast<uint8_t
>(20)};
187 return {
"SHAKE-256(192)",
static_cast<uint8_t
>(25)};
193 return LMS_Params(type,
hash_name, height);
198 if(
hash ==
"SHA-256") {
214 if(
hash ==
"Truncated(SHA-256,192)") {
230 if(
hash ==
"SHAKE-256(256)") {
246 if(
hash ==
"SHAKE-256(192)") {
265 return LMS_Params(type,
hash_name, height);
268LMS_Params::LMS_Params(
LMS_Algorithm_Type algorithm_type, std::string_view hash_name, uint8_t h) :
269 m_algorithm_type(algorithm_type), m_h(h), m_hash_name(hash_name) {
271 m_m =
hash->output_length();
289 const TreeAddress lms_tree_address(
lms_params().h());
298 const size_t total_remaining_bytes = slicer.
remaining();
301 throw Decoding_Error(
"Too few bytes while parsing LMS public key.");
309 throw Decoding_Error(
"Too few bytes while parsing LMS public key.");
316 throw Decoding_Error(
"No support for HSS-LMS instances with multiple hash functions.");
343 BOTAN_ARG_CHECK(m_lms_root.size() == this->lms_params().m(),
"Invalid LMS root");
351 const size_t total_remaining_bytes = slicer.
remaining();
354 throw Decoding_Error(
"Too few signature bytes while parsing LMS signature.");
364 throw Decoding_Error(
"Too few signature bytes while parsing LMS signature.");
371 if(total_remaining_bytes <
size(lms_params, lmots_params)) {
372 throw Decoding_Error(
"Too few signature bytes while parsing LMS signature.");
401 if(sig.
q() >= (1ULL << uint64_t(
lms_params().h()))) {
405 std::optional<LMS_Tree_Node> Tc = lms_compute_root_from_sig(msg, sig);
406 if(!Tc.has_value()) {
410 return Tc.value() == lms_root();
413std::optional<LMS_Tree_Node> LMS_PublicKey::lms_compute_root_from_sig(
const LMS_Message& msg,
422 const LMOTS_Signature& lmots_sig = sig.
lmots_sig();
434 lms_gen_leaf(tmp, pk_candidate, lms_address, *hash);
441 StrongSpan<const LMS_Tree_Node>(tmp),
445 std::move(hash_pair_func),
448 }
catch(
const Decoding_Error&) {
454 return sizeof(uint32_t) +
LMOTS_Signature::size(lmots_params) +
sizeof(uint32_t) + lms_params.
h() * lms_params.
m();
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_STATE_CHECK(expr)
#define BOTAN_ARG_CHECK(expr, msg)
auto copy(const size_t count)
std::span< const uint8_t > take(const size_t count)
Helper class to ease in-place marshalling of concatenated fixed-length values.
constexpr void append(std::span< const uint8_t > buffer)
constexpr std::span< uint8_t > next(size_t bytes)
constexpr bool full() const
static std::unique_ptr< HashFunction > create_or_throw(std::string_view algo_spec, std::string_view provider="")
static std::unique_ptr< Hash_Engine > create_or_throw(std::string_view hash_fn, std::span< const uint8_t > common_prefix={}, std::string_view provider="")
static LMOTS_Params create_or_throw(LMOTS_Algorithm_Type type)
Create the LM-OTS parameters from a known algorithm type.
Representation of an LMOTS private key.
void sign(StrongSpan< LMOTS_Signature_Bytes > out_sig, const LMS_Message &msg) const
Generate a new LMOTS signature.
Representation of an OTS public key.
static size_t size(const LMOTS_Params ¶ms)
The expected size of the signature.
LMOTS_Algorithm_Type algorithm_type() const
Returns the LM-OTS algorithm type.
static LMOTS_Signature from_bytes_or_throw(BufferSlicer &slicer)
Parse a LM-OTS signature.
const LMS_Params & lms_params() const
The LMS parameters for this LMS instance.
const LMOTS_Params & lmots_params() const
The LMOTS parameters used for OTS instances of this LMS instance.
const LMS_Identifier & identifier() const
The identifier of this LMS tree ('I' in RFC 8554).
LMS_Instance(LMS_Params lms_params, LMOTS_Params lmots_params, LMS_Identifier identifier)
Constructor storing the provided LMS data.
const std::string & hash_name() const
Returns the name of the hash function to use.
size_t m() const
Returns the number of bytes associated with each node.
std::unique_ptr< HashFunction > hash() const
Construct a new hash instance for the LMS instance.
uint8_t h() const
Returns the height of the LMS tree.
static LMS_Params create_or_throw(LMS_Algorithm_Type type)
Create the LMS parameters from a known algorithm type.
Representation of an LMS Private key.
LMS_PublicKey sign_and_get_pk(StrongSpan< LMS_Signature_Bytes > out_sig, LMS_Tree_Node_Idx q, const LMS_Message &msg) const
Sign a message using an LMS_PrivateKey and the used leaf index (RFC 8554 5.4.1).
const LMS_Seed & seed() const
The secret seed used for LMOTS' WOTS chain input creation (RFC 8554 Appendix A).
static size_t size(const LMS_Params &lms_params)
The expected size of an LMS public key for given lms_params.
std::vector< uint8_t > to_bytes() const
Bytes of the full lms public key according to 8554 5.3.
static LMS_PublicKey from_bytes_or_throw(BufferSlicer &slicer)
Parse a public LMS key.
LMS_PublicKey(LMS_Params lms_params, LMOTS_Params lmots_params, LMS_Identifier I, LMS_Tree_Node lms_root)
Construct a public key for given public key data.
bool verify_signature(const LMS_Message &msg, const LMS_Signature &sig) const
Verify a LMS signature.
Container for LMS Signature data.
const LMOTS_Signature & lmots_sig() const
The LMOTS signature object containing the parsed LMOTS signature bytes contained in the LMS signature...
LMS_Tree_Node_Idx q() const
The index of the signing leaf given by the signature.
static LMS_Signature from_bytes_or_throw(BufferSlicer &slicer)
Parse the bytes of a lms signature into a LMS Signature object.
LMS_Algorithm_Type lms_type() const
The LMS algorithm type given by the signature.
StrongSpan< const LMS_AuthenticationPath > auth_path() const
The authentication path bytes given by the signature.
static size_t size(const LMS_Params &lms_params, const LMOTS_Params &lmots_params)
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
constexpr void unpoison(const T *p, size_t n)
LMOTS_K lmots_compute_pubkey_from_sig(const LMOTS_Signature &sig, const LMS_Message &msg, const LMS_Identifier &identifier, LMS_Tree_Node_Idx q)
Compute a public key candidate for an OTS-signature-message pair and the OTS instance parameters.
Strong< std::vector< uint8_t >, struct LMOTS_K_ > LMOTS_K
The K value from the LM-OTS public key.
Gf448Elem root(const Gf448Elem &elem)
Compute the root of elem in the field.
LMS_Algorithm_Type
Enum of available LMS algorithm types.
constexpr size_t LMS_IDENTIFIER_LEN
The length in bytes of the LMS identifier (I).
Strong< std::vector< uint8_t >, struct LMS_Tree_Node_ > LMS_Tree_Node
A node with the LMS tree.
void treehash(StrongSpan< SphincsTreeNode > out_root, StrongSpan< SphincsAuthenticationPath > out_auth_path, const Sphincs_Parameters ¶ms, Sphincs_Hash_Functions &hashes, std::optional< TreeNodeIndex > leaf_idx, uint32_t idx_offset, uint32_t total_tree_height, const GenerateLeavesFunction &gen_leaves, Sphincs_Address &tree_address)
Strong< std::vector< uint8_t >, struct LMS_AuthenticationPath_ > LMS_AuthenticationPath
The authentication path of an LMS signature.
Strong< std::vector< uint8_t >, struct LMS_Identifier_ > LMS_Identifier
The identifier of an LMS tree (I in RFC 8554).
LMOTS_Algorithm_Type
Enum of available LM-OTS algorithm types.
Strong< std::vector< uint8_t >, struct LMS_Message_ > LMS_Message
A message that is signed with an LMS tree.
constexpr auto concat(Rs &&... ranges)
void lmots_compute_pubkeys(std::span< uint8_t > out_ks, const LMOTS_Params ¶ms, const LMS_Identifier &identifier, LMS_Tree_Node_Idx first_q, size_t count, const LMS_Seed &seed, Hash_Engine &engine)
Compute the public key hash values K (RFC 8554 4.3) of count consecutive LM-OTS instances beginning a...
Strong< uint32_t, struct LMS_Tree_Node_Idx_, EnableArithmeticWithPlainNumber > LMS_Tree_Node_Idx
The index of a node within a specific LMS tree layer.
constexpr auto store_be(ParamTs &&... params)
constexpr auto load_be(ParamTs &&... params)
void compute_root(StrongSpan< SphincsTreeNode > out, const Sphincs_Parameters ¶ms, Sphincs_Hash_Functions &hashes, const SphincsTreeNode &leaf, TreeNodeIndex leaf_idx, uint32_t idx_offset, StrongSpan< const SphincsAuthenticationPath > authentication_path, uint32_t total_tree_height, Sphincs_Address &tree_address)
Strong< std::vector< uint8_t >, struct LMOTS_Signature_Bytes_ > LMOTS_Signature_Bytes
Byte vector of an LM-OTS signature.