Botan 3.5.0
Crypto and TLS for C&
lms.cpp
Go to the documentation of this file.
1/**
2 * LMS - Leighton-Micali Hash-Based Signatures (RFC 8554)
3 * (C) 2023 Jack Lloyd
4 * 2023 Fabian Albert, Philippe Lieser - Rohde & Schwarz Cybersecurity GmbH
5 *
6 * Botan is released under the Simplified BSD License (see license.txt)
7 */
8
9#include <botan/internal/lms.h>
10
11#include <botan/internal/int_utils.h>
12#include <botan/internal/loadstor.h>
13#include <botan/internal/tree_hash.h>
14
15namespace Botan {
16namespace {
17
18/**
19 * @brief Domain-separation parameter when computing the hash of the leaf of an LMS tree.
20 */
21constexpr uint16_t D_LEAF = 0x8282;
22
23/**
24 * @brief Domain-separation parameter when computing the hash of an interior node of an LMS tree.
25 */
26constexpr uint16_t D_INTR = 0x8383;
27
28/// Index of the layer in a tree starting with 0 for the bottom level to the root layer
29using LMS_TreeLayerIndex = Strong<uint32_t, struct LMS_TreeLayerIndex_, EnableArithmeticWithPlainNumber>;
30
31class TreeAddress final {
32 public:
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");
35 }
36
37 TreeAddress& set_address(LMS_TreeLayerIndex tree_layer, LMS_Tree_Node_Idx tree_index) {
38 BOTAN_ARG_CHECK(tree_index.get() < (1 << m_h), "Invalid tree index");
39 BOTAN_ARG_CHECK(tree_layer.get() <= m_h, "Invalid tree index");
40 m_r = (1 << (m_h - tree_layer)).get() + tree_index.get();
41 return *this;
42 }
43
44 uint32_t r() const { return m_r; }
45
46 bool is_leaf() const { return m_r >= (1 << m_h); }
47
48 LMS_Tree_Node_Idx q() const {
49 BOTAN_STATE_CHECK(is_leaf());
50 return LMS_Tree_Node_Idx(m_r - (1 << m_h.get()));
51 }
52
53 private:
54 LMS_TreeLayerIndex m_h;
55 uint32_t m_r;
56};
57
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) {
63 hash->update(I);
64 hash->update(store_be(address.r()));
65 hash->update(store_be(D_INTR));
66 hash->update(left);
67 hash->update(right);
68 hash->final(out);
69 };
70}
71
72void lms_gen_leaf(StrongSpan<LMS_Tree_Node> out,
73 const LMOTS_Public_Key& lmots_pk,
74 const TreeAddress& tree_address,
75 HashFunction& hash) {
76 hash.update(lmots_pk.identifier());
77 hash.update(store_be(tree_address.r()));
78 hash.update(store_be(D_LEAF));
79 hash.update(lmots_pk.K());
80 hash.final(out);
81}
82
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);
88 };
89}
90
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());
98
99 treehash(out_root,
100 out_auth_path,
101 leaf_idx,
102 lms_sk.lms_params().m(),
103 LMS_TreeLayerIndex(lms_sk.lms_params().h()),
104 0,
105 std::move(hash_pair_func),
106 std::move(gen_leaf),
107 lms_tree_address);
108}
109
110} // namespace
111
113 auto [hash_name, height] = [](const LMS_Algorithm_Type& lms_type) -> std::pair<std::string_view, uint8_t> {
114 switch(lms_type) {
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};
155 default:
156 throw Decoding_Error("Unsupported LMS algorithm type");
157 }
158 }(type);
159
160 return LMS_Params(type, hash_name, height);
161}
162
163LMS_Params LMS_Params::create_or_throw(std::string_view hash_name, uint8_t height) {
164 LMS_Algorithm_Type type = [](std::string_view hash, uint8_t h) -> LMS_Algorithm_Type {
165 if(hash == "SHA-256") {
166 switch(h) {
167 case 5:
169 case 10:
171 case 15:
173 case 20:
175 case 25:
177 default:
178 throw Decoding_Error("Unsupported height for hash function");
179 }
180 }
181 if(hash == "Truncated(SHA-256,192)") {
182 switch(h) {
183 case 5:
185 case 10:
187 case 15:
189 case 20:
191 case 25:
193 default:
194 throw Decoding_Error("Unsupported height for hash function");
195 }
196 }
197 if(hash == "SHAKE-256(256)") {
198 switch(h) {
199 case 5:
201 case 10:
203 case 15:
205 case 20:
207 case 25:
209 default:
210 throw Decoding_Error("Unsupported height for hash function");
211 }
212 }
213 if(hash == "SHAKE-256(192)") {
214 switch(h) {
215 case 5:
217 case 10:
219 case 15:
221 case 20:
223 case 25:
225 default:
226 throw Decoding_Error("Unsupported height for hash function");
227 }
228 }
229 throw Decoding_Error("Unsupported hash function");
230 }(hash_name, height);
231
232 return LMS_Params(type, hash_name, height);
233}
234
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) {
237 const auto hash = HashFunction::create_or_throw(m_hash_name);
238 m_m = hash->output_length();
239}
240
243 const LMS_Message& msg) const {
244 // Pre-alloc space for the signature
245 BOTAN_ARG_CHECK(out_sig.size() == LMS_Signature::size(lms_params(), lmots_params()), "Invalid output buffer size");
246
247 BufferStuffer sig_stuffer(out_sig);
248 sig_stuffer.append(store_be(q));
249 const LMOTS_Private_Key lmots_sk(lmots_params(), identifier(), q, seed());
250 lmots_sk.sign(sig_stuffer.next<LMOTS_Signature_Bytes>(LMOTS_Signature::size(lmots_params())), msg);
251 sig_stuffer.append(store_be(lms_params().algorithm_type()));
252 const auto auth_path_buffer = sig_stuffer.next<LMS_AuthenticationPath>(lms_params().m() * lms_params().h());
253
254 BOTAN_ASSERT_NOMSG(sig_stuffer.full());
255
256 TreeAddress lms_tree_address(lms_params().h());
257 LMS_Tree_Node pk_buffer(lms_params().m());
258 lms_treehash(StrongSpan<LMS_Tree_Node>(pk_buffer.get()), auth_path_buffer, q, *this);
259
260 return LMS_PublicKey(lms_params(), lmots_params(), identifier(), std::move(pk_buffer));
261}
262
264 size_t total_remaining_bytes = slicer.remaining();
265 // Alg. 6. 1. (4 bytes are sufficient until the next check)
266 if(total_remaining_bytes < sizeof(LMS_Algorithm_Type)) {
267 throw Decoding_Error("Too few bytes while parsing LMS public key.");
268 }
269 // Alg. 6. 2.a.
270 auto lms_type = load_be<LMS_Algorithm_Type>(slicer.take<sizeof(LMS_Algorithm_Type)>());
271 // Alg. 6. 2.c.
273 // Alg. 6. 2.d.
274 if(total_remaining_bytes < LMS_PublicKey::size(lms_params)) {
275 throw Decoding_Error("Too few bytes while parsing LMS public key.");
276 }
277 // Alg. 6. 2.b.
278 auto lmots_type = load_be<LMOTS_Algorithm_Type>(slicer.take<sizeof(LMOTS_Algorithm_Type)>());
280
282 throw Decoding_Error("No support for HSS-LMS instances with multiple hash functions.");
283 }
284
285 // Alg. 6. 2.e.
286 auto I = slicer.copy<LMS_Identifier>(LMS_IDENTIFIER_LEN);
287 // Alg. 6. 2.f.
288 auto lms_root = slicer.copy<LMS_Tree_Node>(lms_params.m());
289
290 return LMS_PublicKey(std::move(lms_params), std::move(lmots_params), std::move(I), std::move(lms_root));
291}
292
293std::vector<uint8_t> LMS_PublicKey::to_bytes() const {
294 // clang-format off
296 store_be(lms_params().algorithm_type()),
297 store_be(lmots_params().algorithm_type()),
298 identifier(),
299 m_lms_root);
300 // clang-format on
301}
302
304 LMOTS_Params lmots_params,
306 LMS_Tree_Node lms_root) :
307 LMS_Instance(std::move(lms_params), std::move(lmots_params), std::move(I)), m_lms_root(std::move(lms_root)) {
308 BOTAN_ARG_CHECK(identifier().size() == LMS_IDENTIFIER_LEN, "Invalid LMS identifier");
309 BOTAN_ARG_CHECK(m_lms_root.size() == this->lms_params().m(), "Invalid LMS root");
310}
311
312size_t LMS_PublicKey::size(const LMS_Params& lms_params) {
314}
315
317 size_t total_remaining_bytes = slicer.remaining();
318 // Alg. 6a 1. (next 4 bytes are checked in LMOTS_Signature::from_bytes_or_throw)
319 if(total_remaining_bytes < sizeof(LMS_Tree_Node_Idx)) {
320 throw Decoding_Error("Too few signature bytes while parsing LMS signature.");
321 }
322 // Alg. 6a 2.a.
323 auto q = load_be<LMS_Tree_Node_Idx>(slicer.take<sizeof(LMS_Tree_Node_Idx)>());
324
325 // Alg. 6a 2.b.-e.
328
329 if(slicer.remaining() < sizeof(LMS_Algorithm_Type)) {
330 throw Decoding_Error("Too few signature bytes while parsing LMS signature.");
331 }
332 // Alg. 6a 2.f.
334 // Alg. 6a 2.h.
336 // Alg. 6a 2.i. (signature is not exactly [...] bytes long)
337 if(total_remaining_bytes < size(lms_params, lmots_params)) {
338 throw Decoding_Error("Too few signature bytes while parsing LMS signature.");
339 }
340
341 // Alg. 6a 2.j.
342 auto auth_path = slicer.copy<LMS_AuthenticationPath>(lms_params.m() * lms_params.h());
343
344 return LMS_Signature(q, std::move(lmots_sig), lms_type, std::move(auth_path));
345}
346
347LMS_PublicKey::LMS_PublicKey(const LMS_PrivateKey& sk) : LMS_Instance(sk), m_lms_root(sk.lms_params().m()) {
348 lms_treehash(StrongSpan<LMS_Tree_Node>(m_lms_root), std::nullopt, std::nullopt, sk);
349}
350
352 if(lms_root().size() != lms_params().m()) {
353 // LMS public key (T[1] part) has unexpected length
354 return false;
355 }
356 if(lms_params().algorithm_type() != sig.lms_type()) {
357 // LMS algorithm type does not match with the signature's
358 return false;
359 }
360 // Alg. 6a 2.g.
361 if(lmots_params().algorithm_type() != sig.lmots_sig().algorithm_type()) {
362 // LMOTS algorithm type does not match with the signature's
363 return false;
364 }
365 // Alg. 6a 2.i.
366 if(sig.q() >= (1ULL << uint64_t(lms_params().h()))) {
367 return false;
368 }
369 // Alg 6. 3.
370 std::optional<LMS_Tree_Node> Tc = lms_compute_root_from_sig(msg, sig);
371 if(!Tc.has_value()) {
372 return false;
373 }
374 // Alg 6. 4.
375 return Tc.value() == lms_root();
376}
377
378std::optional<LMS_Tree_Node> LMS_PublicKey::lms_compute_root_from_sig(const LMS_Message& msg,
379 const LMS_Signature& sig) const {
380 // Alg. 6a 2.c, 2.g
381 if(lms_params().algorithm_type() != sig.lms_type() ||
382 lmots_params().algorithm_type() != sig.lmots_sig().algorithm_type()) {
383 return std::nullopt;
384 }
385 try {
386 const LMS_Params lms_params = LMS_Params::create_or_throw(sig.lms_type());
387 const LMOTS_Signature& lmots_sig = sig.lmots_sig();
388 const LMOTS_Params lmots_params = LMOTS_Params::create_or_throw(lmots_sig.algorithm_type());
389 const LMOTS_K Kc = lmots_compute_pubkey_from_sig(lmots_sig, msg, identifier(), sig.q());
390 const auto hash = lms_params.hash();
391
392 auto hash_pair_func = get_hash_pair_func_for_identifier(lms_params, identifier());
393
394 auto lms_address = TreeAddress(lms_params.h());
395 lms_address.set_address(LMS_TreeLayerIndex(0), LMS_Tree_Node_Idx(sig.q().get()));
396
397 LMOTS_Public_Key pk_candidate(lmots_params, identifier(), sig.q(), Kc);
399 lms_gen_leaf(tmp, pk_candidate, lms_address, *hash);
400
402
403 compute_root(StrongSpan<LMS_Tree_Node>(root),
404 sig.auth_path(),
405 sig.q(),
406 StrongSpan<const LMS_Tree_Node>(tmp),
407 lms_params.m(),
408 LMS_TreeLayerIndex(lms_params.h()),
409 0,
410 std::move(hash_pair_func),
411 lms_address);
412 return LMS_Tree_Node(root);
413 } catch(const Decoding_Error&) {
414 return std::nullopt;
415 }
416}
417
418size_t LMS_Signature::size(const LMS_Params& lms_params, const LMOTS_Params& lmots_params) {
419 return sizeof(uint32_t) + LMOTS_Signature::size(lmots_params) + sizeof(uint32_t) + lms_params.h() * lms_params.m();
420}
421
422} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:41
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
size_t remaining() const
Definition stl_util.h:127
auto copy(const size_t count)
Definition stl_util.h:89
std::span< const uint8_t > take(const size_t count)
Definition stl_util.h:98
Helper class to ease in-place marshalling of concatenated fixed-length values.
Definition stl_util.h:142
constexpr void append(std::span< const uint8_t > buffer)
Definition stl_util.h:177
constexpr std::span< uint8_t > next(size_t bytes)
Definition stl_util.h:150
constexpr bool full() const
Definition stl_util.h:187
static std::unique_ptr< HashFunction > create_or_throw(std::string_view algo_spec, std::string_view provider="")
Definition hash.cpp:298
The LM-OTS parameters.
Definition lm_ots.h:100
static LMOTS_Params create_or_throw(LMOTS_Algorithm_Type type)
Create the LM-OTS parameters from a known algorithm type.
Definition lm_ots.cpp:99
const std::string & hash_name() const
Name of the hash function to use.
Definition lm_ots.h:150
Representation of an LMOTS private key.
Definition lm_ots.h:257
void sign(StrongSpan< LMOTS_Signature_Bytes > out_sig, const LMS_Message &msg) const
Generate a new LMOTS signature.
Definition lm_ots.cpp:275
static size_t size(const LMOTS_Params &params)
The expected size of the signature.
Definition lm_ots.h:207
LMOTS_Algorithm_Type algorithm_type() const
Returns the LM-OTS algorithm type.
Definition lm_ots.h:192
static LMOTS_Signature from_bytes_or_throw(BufferSlicer &slicer)
Parse a LM-OTS signature.
Definition lm_ots.cpp:234
Base class for LMS private and public key. Contains public data associated with this LMS instance.
Definition lms.h:150
const LMS_Params & lms_params() const
The LMS parameters for this LMS instance.
Definition lms.h:163
const LMOTS_Params & lmots_params() const
The LMOTS parameters used for OTS instances of this LMS instance.
Definition lms.h:168
const LMS_Identifier & identifier() const
The identifier of this LMS tree ('I' in RFC 8554)
Definition lms.h:173
The LMS parameters.
Definition lms.h:88
const std::string & hash_name() const
Returns the name of the hash function to use.
Definition lms.h:123
size_t m() const
Returns the number of bytes associated with each node.
Definition lms.h:118
std::unique_ptr< HashFunction > hash() const
Construct a new hash instance for the LMS instance.
Definition lms.h:128
uint8_t h() const
Returns the height of the LMS tree.
Definition lms.h:113
static LMS_Params create_or_throw(LMS_Algorithm_Type type)
Create the LMS parameters from a known algorithm type.
Definition lms.cpp:112
Representation of an LMS Private key.
Definition lms.h:189
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).
Definition lms.cpp:241
const LMS_Seed & seed() const
The secret seed used for LMOTS' WOTS chain input creation (RFC 8554 Appendix A)
Definition lms.h:200
The LMS public key.
Definition lms.h:224
static size_t size(const LMS_Params &lms_params)
The expected size of an LMS public key for given lms_params.
Definition lms.cpp:312
std::vector< uint8_t > to_bytes() const
Bytes of the full lms public key according to 8554 5.3.
Definition lms.cpp:293
static LMS_PublicKey from_bytes_or_throw(BufferSlicer &slicer)
Parse a public LMS key.
Definition lms.cpp:263
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.
Definition lms.cpp:303
bool verify_signature(const LMS_Message &msg, const LMS_Signature &sig) const
Verify a LMS signature.
Definition lms.cpp:351
Container for LMS Signature data.
Definition lms.h:290
const LMOTS_Signature & lmots_sig() const
The LMOTS signature object containing the parsed LMOTS signature bytes contained in the LMS signature...
Definition lms.h:310
LMS_Tree_Node_Idx q() const
The index of the signing leaf given by the signature.
Definition lms.h:304
static LMS_Signature from_bytes_or_throw(BufferSlicer &slicer)
Parse the bytes of a lms signature into a LMS Signature object.
Definition lms.cpp:316
LMS_Algorithm_Type lms_type() const
The LMS algorithm type given by the signature.
Definition lms.h:315
StrongSpan< const LMS_AuthenticationPath > auth_path() const
The authentication path bytes given by the signature.
Definition lms.h:322
static size_t size(const LMS_Params &lms_params, const LMOTS_Params &lmots_params)
Definition lms.cpp:418
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.
Definition lm_ots.cpp:325
Strong< std::vector< uint8_t >, struct LMOTS_K_ > LMOTS_K
The K value from the LM-OTS public key.
Definition lm_ots.h:35
Gf448Elem root(const Gf448Elem &elem)
Compute the root of elem in the field.
LMS_Algorithm_Type
Enum of available LMS algorithm types.
Definition lms.h:29
constexpr size_t LMS_IDENTIFIER_LEN
The length in bytes of the LMS identifier (I).
Definition lms.h:66
Strong< std::vector< uint8_t >, struct LMS_Tree_Node_ > LMS_Tree_Node
A node with the LMS tree.
Definition lms.h:76
Strong< std::vector< uint8_t >, struct LMS_Identifier_ > LMS_Identifier
The identifier of an LMS tree (I in RFC 8554)
Definition lm_ots.h:50
LMOTS_Algorithm_Type
Enum of available LM-OTS algorithm types.
Definition lm_ots.h:65
constexpr auto concat(Rs &&... ranges)
Definition stl_util.h:262
Strong< uint32_t, struct LMS_Tree_Node_Idx_, EnableArithmeticWithPlainNumber > LMS_Tree_Node_Idx
The index of a node within a specific LMS tree layer.
Definition lm_ots.h:45
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:707
constexpr auto load_be(ParamTs &&... params)
Definition loadstor.h:467
void treehash(StrongSpan< SphincsTreeNode > out_root, StrongSpan< SphincsAuthenticationPath > out_auth_path, const Sphincs_Parameters &params, 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 &params, 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)