9#include <botan/internal/lms.h>
11#include <botan/internal/int_utils.h>
12#include <botan/internal/loadstor.h>
13#include <botan/internal/tree_hash.h>
21constexpr uint16_t D_LEAF = 0x8282;
26constexpr uint16_t D_INTR = 0x8383;
29using LMS_TreeLayerIndex = Strong<uint32_t, struct LMS_TreeLayerIndex_, EnableArithmeticWithPlainNumber>;
31class TreeAddress
final {
33 explicit TreeAddress(uint32_t total_tree_height) : m_h(total_tree_height), m_r(0) {
34 BOTAN_ARG_CHECK(total_tree_height > 0 && total_tree_height < 32,
"Invalid tree height");
37 TreeAddress& set_address(LMS_TreeLayerIndex tree_layer,
LMS_Tree_Node_Idx tree_index) {
40 m_r = (1 << (m_h - tree_layer)).get() + tree_index.get();
44 uint32_t r()
const {
return m_r; }
46 bool is_leaf()
const {
return m_r >= (1 << m_h); }
54 LMS_TreeLayerIndex m_h;
58auto get_hash_pair_func_for_identifier(
const LMS_Params& lms_params,
LMS_Identifier identifier) {
59 return [hash = lms_params.hash(), I = std::move(identifier)](StrongSpan<LMS_Tree_Node> out,
60 const TreeAddress& address,
61 StrongSpan<const LMS_Tree_Node> left,
62 StrongSpan<const LMS_Tree_Node> right) {
72void lms_gen_leaf(StrongSpan<LMS_Tree_Node> out,
73 const LMOTS_Public_Key& lmots_pk,
74 const TreeAddress& tree_address,
76 hash.update(lmots_pk.identifier());
77 hash.update(
store_be(tree_address.r()));
79 hash.update(lmots_pk.K());
83auto lms_gen_leaf_func(
const LMS_PrivateKey& lms_sk) {
84 return [hash = lms_sk.lms_params().hash(), lms_sk](StrongSpan<LMS_Tree_Node> out,
const TreeAddress& tree_address) {
85 auto lmots_sk = LMOTS_Private_Key(lms_sk.lmots_params(), lms_sk.identifier(), tree_address.q(), lms_sk.seed());
86 auto lmots_pk = LMOTS_Public_Key(lmots_sk);
87 lms_gen_leaf(out, lmots_pk, tree_address, *hash);
91void lms_treehash(StrongSpan<LMS_Tree_Node> out_root,
92 std::optional<StrongSpan<LMS_AuthenticationPath>> out_auth_path,
93 std::optional<LMS_Tree_Node_Idx> leaf_idx,
94 const LMS_PrivateKey& lms_sk) {
95 auto hash_pair_func = get_hash_pair_func_for_identifier(lms_sk.lms_params(), lms_sk.identifier());
96 auto gen_leaf = lms_gen_leaf_func(lms_sk);
97 TreeAddress lms_tree_address(lms_sk.lms_params().h());
102 lms_sk.lms_params().m(),
103 LMS_TreeLayerIndex(lms_sk.lms_params().h()),
105 std::move(hash_pair_func),
116 return {
"SHA-256", 5};
118 return {
"SHA-256", 10};
120 return {
"SHA-256", 15};
122 return {
"SHA-256", 20};
124 return {
"SHA-256", 25};
126 return {
"Truncated(SHA-256,192)", 5};
128 return {
"Truncated(SHA-256,192)", 10};
130 return {
"Truncated(SHA-256,192)", 15};
132 return {
"Truncated(SHA-256,192)", 20};
134 return {
"Truncated(SHA-256,192)", 25};
136 return {
"SHAKE-256(256)", 5};
138 return {
"SHAKE-256(256)", 10};
140 return {
"SHAKE-256(256)", 15};
142 return {
"SHAKE-256(256)", 20};
144 return {
"SHAKE-256(256)", 25};
146 return {
"SHAKE-256(192)", 5};
148 return {
"SHAKE-256(192)", 10};
150 return {
"SHAKE-256(192)", 15};
152 return {
"SHAKE-256(192)", 20};
154 return {
"SHAKE-256(192)", 25};
165 if(
hash ==
"SHA-256") {
181 if(
hash ==
"Truncated(SHA-256,192)") {
197 if(
hash ==
"SHAKE-256(256)") {
213 if(
hash ==
"SHAKE-256(192)") {
235LMS_Params::LMS_Params(
LMS_Algorithm_Type algorithm_type, std::string_view hash_name, uint8_t h) :
236 m_algorithm_type(algorithm_type), m_h(h), m_hash_name(hash_name) {
238 m_m =
hash->output_length();
256 TreeAddress lms_tree_address(
lms_params().h());
264 size_t total_remaining_bytes = slicer.
remaining();
267 throw Decoding_Error(
"Too few bytes while parsing LMS public key.");
275 throw Decoding_Error(
"Too few bytes while parsing LMS public key.");
282 throw Decoding_Error(
"No support for HSS-LMS instances with multiple hash functions.");
307 LMS_Instance(std::move(lms_params), std::move(lmots_params), std::move(I)), m_lms_root(std::move(lms_root)) {
309 BOTAN_ARG_CHECK(m_lms_root.size() == this->lms_params().m(),
"Invalid LMS root");
317 size_t total_remaining_bytes = slicer.
remaining();
320 throw Decoding_Error(
"Too few signature bytes while parsing LMS signature.");
330 throw Decoding_Error(
"Too few signature bytes while parsing LMS signature.");
337 if(total_remaining_bytes <
size(lms_params, lmots_params)) {
338 throw Decoding_Error(
"Too few signature bytes while parsing LMS signature.");
366 if(sig.
q() >= (1ULL << uint64_t(
lms_params().h()))) {
370 std::optional<LMS_Tree_Node> Tc = lms_compute_root_from_sig(msg, sig);
371 if(!Tc.has_value()) {
375 return Tc.value() == lms_root();
378std::optional<LMS_Tree_Node> LMS_PublicKey::lms_compute_root_from_sig(
const LMS_Message& msg,
387 const LMOTS_Signature& lmots_sig = sig.
lmots_sig();
399 lms_gen_leaf(tmp, pk_candidate, lms_address, *hash);
406 StrongSpan<const LMS_Tree_Node>(tmp),
410 std::move(hash_pair_func),
413 }
catch(
const Decoding_Error&) {
419 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 LMOTS_Params create_or_throw(LMOTS_Algorithm_Type type)
Create the LM-OTS parameters from a known algorithm type.
const std::string & hash_name() const
Name of the hash function to use.
Representation of an LMOTS private key.
void sign(StrongSpan< LMOTS_Signature_Bytes > out_sig, const LMS_Message &msg) const
Generate a new LMOTS signature.
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.
Base class for LMS private and public key. Contains public data associated with this LMS instance.
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)
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()))
int(* final)(unsigned char *, CTX *)
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.
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.
constexpr auto concat(Rs &&... ranges)
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 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 GenerateLeafFunction &gen_leaf, Sphincs_Address &tree_address)
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)