9#include <botan/internal/lm_ots.h>
11#include <botan/exceptn.h>
12#include <botan/strong_type.h>
13#include <botan/internal/bit_ops.h>
14#include <botan/internal/buffer_slicer.h>
15#include <botan/internal/buffer_stuffer.h>
16#include <botan/internal/ct_utils.h>
17#include <botan/internal/hash_engine.h>
18#include <botan/internal/hss_lms_utils.h>
19#include <botan/internal/int_utils.h>
24constexpr uint16_t D_PBLC = 0x8080;
25constexpr uint16_t D_MESG = 0x8181;
27constexpr uint16_t C_INDEX = 0xFFFD;
37class Batch_Chain_Generator {
39 Batch_Chain_Generator(
42 m_prefix_len(identifier.size() + sizeof(uint32_t) + sizeof(uint16_t) + sizeof(uint8_t)),
43 m_prefixes(q_count * p * m_prefix_len) {
44 for(
size_t lane = 0; lane != q_count * p; ++lane) {
45 BufferStuffer prefix(chain_prefix(lane));
46 prefix.append(identifier);
48 prefix.append(
store_be(
static_cast<uint16_t
>(lane % p)));
49 prefix.next(1)[0] = 0;
54 Batch_Chain_Generator(engine, identifier, q, 1, p) {}
56 void process(std::span<const uint16_t> lanes,
58 std::span<std::span<uint8_t>> outputs,
59 std::span<std::span<const uint8_t>> inputs) {
60 m_prefix_spans.resize(lanes.size());
61 for(
size_t c = 0; c != lanes.size(); ++c) {
62 const auto prefix = chain_prefix(lanes[c]);
63 prefix[m_prefix_len - 1] = j;
64 m_prefix_spans[c] = prefix;
66 m_engine.batch_hash(outputs, m_prefix_spans, inputs);
70 std::span<uint8_t> chain_prefix(
size_t lane) {
71 return std::span(m_prefixes).subspan(lane * m_prefix_len, m_prefix_len);
74 Hash_Engine& m_engine;
76 std::vector<uint8_t> m_prefixes;
77 std::vector<std::span<const uint8_t>> m_prefix_spans;
81uint8_t
byte(std::span<const uint8_t> S, uint32_t i) {
87uint8_t coef(std::span<const uint8_t> S, uint32_t i,
const LMOTS_Params& params) {
88 const uint8_t w_bit_mask = params.coef_max();
89 const uint8_t coef_byte =
byte(S, (i * params.w()) / 8);
90 const uint8_t shift = 8 - (params.w() * (i % (8 / params.w())) + params.w());
92 return w_bit_mask & (coef_byte >> shift);
96uint16_t checksum(
const LMOTS_Params& params, std::span<const uint8_t> S) {
98 for(uint32_t i = 0; i < (params.n() * 8 / params.w()); ++i) {
99 sum += params.coef_max() - coef(S, i, params);
104std::vector<uint8_t> gen_Q_with_cksm(
const LMOTS_Params& params,
107 std::span<const uint8_t> C,
109 std::vector<uint8_t> Q_with_cksm(params.n() +
sizeof(uint16_t));
111 const auto hash = params.hash();
112 hash->update(identifier);
117 const auto Q_span = qwc_stuffer.next(params.n());
120 qwc_stuffer.append(
store_be(checksum(params, Q_span)));
135 return {
"SHA-256",
static_cast<uint8_t
>(1)};
137 return {
"SHA-256",
static_cast<uint8_t
>(2)};
139 return {
"SHA-256",
static_cast<uint8_t
>(4)};
141 return {
"SHA-256",
static_cast<uint8_t
>(8)};
143 return {
"Truncated(SHA-256,192)",
static_cast<uint8_t
>(1)};
145 return {
"Truncated(SHA-256,192)",
static_cast<uint8_t
>(2)};
147 return {
"Truncated(SHA-256,192)",
static_cast<uint8_t
>(4)};
149 return {
"Truncated(SHA-256,192)",
static_cast<uint8_t
>(8)};
151 return {
"SHAKE-256(256)",
static_cast<uint8_t
>(1)};
153 return {
"SHAKE-256(256)",
static_cast<uint8_t
>(2)};
155 return {
"SHAKE-256(256)",
static_cast<uint8_t
>(4)};
157 return {
"SHAKE-256(256)",
static_cast<uint8_t
>(8)};
159 return {
"SHAKE-256(192)",
static_cast<uint8_t
>(1)};
161 return {
"SHAKE-256(192)",
static_cast<uint8_t
>(2)};
163 return {
"SHAKE-256(192)",
static_cast<uint8_t
>(4)};
165 return {
"SHAKE-256(192)",
static_cast<uint8_t
>(8)};
176 if(
w != 1 &&
w != 2 &&
w != 4 &&
w != 8) {
180 if(
hash ==
"SHA-256") {
194 if(
hash ==
"Truncated(SHA-256,192)") {
208 if(
hash ==
"SHAKE-256(256)") {
222 if(
hash ==
"SHAKE-256(192)") {
242LMOTS_Params::LMOTS_Params(
LMOTS_Algorithm_Type algorithm_type, std::string_view hash_name, uint8_t w) :
243 m_algorithm_type(algorithm_type), m_w(w), m_hash_name(hash_name) {
245 m_n =
hash->output_length();
255 std::vector<uint8_t> C,
256 std::vector<uint8_t> y_buffer) :
257 m_algorithm_type(lmots_type), m_C(std::move(C)), m_y_buffer(std::move(y_buffer)) {
266 const size_t n = m_C.
size();
267 BOTAN_ARG_CHECK((
static_cast<size_t>(chain_idx) + 1) * n <= m_y_buffer.size(),
"Invalid LM-OTS chain index");
272 const size_t total_remaining_bytes = slicer.
remaining();
275 throw Decoding_Error(
"Too few signature bytes while parsing LMOTS signature.");
283 if(total_remaining_bytes <
size(params)) {
284 throw Decoding_Error(
"Too few signature bytes while parsing LMOTS signature.");
292 return LMOTS_Signature(
algorithm_type, std::move(
C), std::move(m_y_buffer));
307 const uint16_t p =
params.p();
310 std::vector<uint16_t> chains(p);
311 std::vector<std::span<uint8_t>> outputs(p);
312 std::vector<std::span<const uint8_t>> inputs(p);
313 for(uint16_t i = 0; i < p; ++i) {
314 m_ots_sk.emplace_back(
params.n());
316 outputs[i] = std::span<uint8_t>(m_ots_sk.back().get());
317 inputs[i] = std::span<const uint8_t>(seed.
get());
320 Batch_Chain_Generator chain_gen(engine,
identifier,
q, p);
321 chain_gen.process(chains, 0xff, outputs, inputs);
329 const auto C = sig_stuffer.
next(
params().n());
334 derive_random_C(C, *hash);
339 const uint16_t p =
params().
p();
341 const auto y = sig_stuffer.
next(p * n);
344 std::vector<uint8_t> a(p);
345 for(uint16_t i = 0; i < p; ++i) {
346 a[i] = coef(Q_with_cksm, i,
params());
351 Batch_Chain_Generator chain_gen(*engine,
identifier(),
q(), p);
353 std::vector<uint16_t> active;
354 std::vector<std::span<uint8_t>> outputs;
355 std::vector<std::span<const uint8_t>> inputs;
361 for(uint8_t j = 0;; ++j) {
365 for(uint16_t i = 0; i < p; ++i) {
368 const auto node = y.subspan(i * n, n);
369 outputs.push_back(node);
370 inputs.push_back(node);
376 chain_gen.process(active, j, outputs, inputs);
380void LMOTS_Private_Key::derive_random_C(std::span<uint8_t> out,
HashFunction& hash)
const {
383 gen.set_q(
q().get());
387 gen.gen(out, hash, m_seed);
395 const uint16_t p = lmots_sk.
params().p();
396 const size_t n = lmots_sk.
params().n();
400 std::vector<uint16_t> chains(p);
401 std::vector<std::span<uint8_t>> outputs(p);
402 std::vector<std::span<const uint8_t>> inputs(p);
403 for(uint16_t i = 0; i < p; ++i) {
405 const auto node = std::span(nodes).subspan(i * n, n);
411 Batch_Chain_Generator chain_gen(engine, lmots_sk.
identifier(), lmots_sk.
q(), p);
412 for(uint8_t j = 0; j < lmots_sk.
params().coef_max(); ++j) {
413 chain_gen.process(chains, j, outputs, inputs);
416 const auto pk_hash = lmots_sk.
params().
hash();
420 pk_hash->update(nodes);
421 m_K = pk_hash->final<
LMOTS_K>();
433 const uint16_t p = params.
p();
434 const size_t n = params.
n();
435 const size_t lanes = count * p;
440 std::vector<uint16_t> lane_ids(lanes);
441 std::vector<std::span<uint8_t>> outputs(lanes);
442 std::vector<std::span<const uint8_t>> inputs(lanes);
443 for(
size_t l = 0; l != lanes; ++l) {
444 lane_ids[l] =
static_cast<uint16_t
>(l);
445 outputs[l] = std::span(nodes).subspan(l * n, n);
446 inputs[l] = std::span<const uint8_t>(seed.
get());
449 Batch_Chain_Generator chain_gen(engine, identifier, first_q, count, p);
452 chain_gen.process(lane_ids, 0xff, outputs, inputs);
455 for(
size_t l = 0; l != lanes; ++l) {
456 inputs[l] = outputs[l];
458 for(uint8_t j = 0; j < params.
coef_max(); ++j) {
459 chain_gen.process(lane_ids, j, outputs, inputs);
463 const size_t k_prefix_len = identifier.
size() +
sizeof(uint32_t) +
sizeof(uint16_t);
464 std::vector<uint8_t> k_prefixes(count * k_prefix_len);
465 std::vector<std::span<uint8_t>> k_outs(count);
466 std::vector<std::span<const uint8_t>> k_prefix_spans(count);
467 std::vector<std::span<const uint8_t>> k_nodes(count);
468 for(
size_t i = 0; i != count; ++i) {
469 const auto prefix_span = std::span(k_prefixes).subspan(i * k_prefix_len, k_prefix_len);
471 prefix.
append(identifier);
474 k_prefix_spans[i] = prefix_span;
475 k_outs[i] = out_ks.subspan(i * n, n);
476 k_nodes[i] = std::span(nodes).subspan(i * p * n, p * n);
478 engine.
batch_hash(k_outs, k_prefix_spans, k_nodes);
489 const auto Q_with_cksm = gen_Q_with_cksm(params, identifier, q, sig.
C(), msg);
491 const uint16_t p = params.p();
492 const size_t n = params.n();
495 std::vector<uint8_t> a(p);
496 for(uint16_t i = 0; i < p; ++i) {
497 a[i] = coef(Q_with_cksm, i, params);
498 copy_mem(std::span(nodes).subspan(i * n, n), sig.
y(i));
502 Batch_Chain_Generator chain_gen(*engine, identifier, q, p);
504 std::vector<uint16_t> active;
505 std::vector<std::span<uint8_t>> outputs;
506 std::vector<std::span<const uint8_t>> inputs;
512 for(uint8_t j = 0; j < params.coef_max(); ++j) {
516 for(uint16_t i = 0; i < p; ++i) {
519 const auto node = std::span(nodes).subspan(i * n, n);
520 outputs.push_back(node);
521 inputs.push_back(node);
524 if(!active.empty()) {
525 chain_gen.process(active, j, outputs, inputs);
530 const auto pk_hash = params.hash();
531 pk_hash->update(identifier);
534 pk_hash->update(nodes);
536 return pk_hash->final<
LMOTS_K>();
#define BOTAN_ASSERT_NOMSG(expr)
#define BOTAN_ARG_CHECK(expr, msg)
std::span< const uint8_t > take(const size_t count)
auto copy_as_vector(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="")
void batch_hash(std::span< std::span< uint8_t > > outputs, std::span< std::span< const uint8_t > > inputs)
static LMOTS_Params create_or_throw(LMOTS_Algorithm_Type type)
Create the LM-OTS parameters from a known algorithm type.
uint8_t coef_max() const
The maximum the winternitz coefficients can have.
std::unique_ptr< HashFunction > hash() const
Construct a new hash instance for the OTS instance.
size_t n() const
The number of bytes of the output of the hash function.
uint8_t w() const
The width (in bits) of the Winternitz coefficients.
const std::string & hash_name() const
Name of the hash function to use.
uint16_t p() const
The number of n-byte string elements that make up the LM-OTS signature.
Representation of an LMOTS private key.
const LMOTS_Node & chain_input(uint16_t chain_idx) const
The secret chain input at a given chain index. (x[] in RFC 8554 4.2).
void sign(StrongSpan< LMOTS_Signature_Bytes > out_sig, const LMS_Message &msg) const
Generate a new LMOTS signature.
LMOTS_Private_Key(const LMOTS_Params ¶ms, const LMS_Identifier &identifier, LMS_Tree_Node_Idx q, const LMS_Seed &seed)
Derive a LMOTS private key for a given seed.
LMOTS_Public_Key(const LMOTS_Private_Key &lmots_sk)
Derivivation of an LMOTS public key using an LMOTS_Private_Key as defined in RFC 8554 4....
Representation of a LM-OTS signature.
static size_t size(const LMOTS_Params ¶ms)
The expected size of the signature.
StrongSpan< const LMOTS_Node > y(uint16_t chain_idx) const
Returns the part of the signature for chain_idx.
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.
std::span< const uint8_t > C() const
The n-byte randomizer of the signature.
const LMS_Identifier & identifier() const
The LMS identifier of the LMS tree containing this OTS instance ('I' in RFC 8554).
OTS_Instance(const LMOTS_Params ¶ms, const LMS_Identifier &identifier, LMS_Tree_Node_Idx q)
Constructor storing the specific OTS parameters.
LMS_Tree_Node_Idx q() const
The index of the LMS tree leaf associated with this OTS instance.
const LMOTS_Params & params() const
The LMOTS parameters.
Helper class used to derive secret values based in the pseudorandom key generation described in RFC 8...
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
size_type size() const noexcept(noexcept(this->get().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.
BOTAN_FORCE_INLINE constexpr T ceil_division(T a, T b)
constexpr RT checked_cast_to(AT i)
Strong< std::vector< uint8_t >, struct LMS_Identifier_ > LMS_Identifier
The identifier of an LMS tree (I in RFC 8554).
constexpr void copy_mem(T *out, const T *in, size_t n)
LMOTS_Algorithm_Type
Enum of available LM-OTS algorithm types.
Strong< secure_vector< uint8_t >, struct LMS_SEED_ > LMS_Seed
Seed of the LMS tree, used to generate the LM-OTS private keys.
Strong< std::vector< uint8_t >, struct LMS_Message_ > LMS_Message
A message that is signed with an LMS tree.
BOTAN_FORCE_INLINE constexpr size_t high_bit(T n)
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.
std::vector< T, secure_allocator< T > > secure_vector
std::uint8_t byte
Unsigned 8 bit integer; retained for compatibility with older versions.
constexpr auto store_be(ParamTs &&... params)
constexpr auto load_be(ParamTs &&... params)