Botan 3.14.1
Crypto and TLS for C&
lm_ots.h
Go to the documentation of this file.
1/**
2 * LM-OTS - Leighton-Micali One-Time Signatures (RFC 8554 Section 4)
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#ifndef BOTAN_LM_OTS_H_
10#define BOTAN_LM_OTS_H_
11
12#include <botan/secmem.h>
13#include <botan/strong_type.h>
14#include <memory>
15#include <span>
16#include <string>
17#include <string_view>
18#include <vector>
19
20namespace Botan {
21
22class BufferSlicer;
23class HashFunction;
24class Hash_Engine;
25
26/**
27 * @brief Seed of the LMS tree, used to generate the LM-OTS private keys.
28 */
29using LMS_Seed = Strong<secure_vector<uint8_t>, struct LMS_SEED_>;
30
31/**
32 * @brief One node within one LM-OTS hash chain.
33 */
34using LMOTS_Node = Strong<secure_vector<uint8_t>, struct LMOTS_Node_>;
35
36/**
37 * @brief The K value from the LM-OTS public key.
38 */
39using LMOTS_K = Strong<std::vector<uint8_t>, struct LMOTS_K_>;
40
41/**
42 * @brief Byte vector of an LM-OTS signature.
43 */
44using LMOTS_Signature_Bytes = Strong<std::vector<uint8_t>, struct LMOTS_Signature_Bytes_>;
45
46/**
47 * @brief The index of a node within a specific LMS tree layer
48 */
50
51/**
52 * @brief The identifier of an LMS tree (I in RFC 8554)
53 */
54using LMS_Identifier = Strong<std::vector<uint8_t>, struct LMS_Identifier_>;
55
56/**
57 * @brief A message that is signed with an LMS tree
58 */
59using LMS_Message = Strong<std::vector<uint8_t>, struct LMS_Message_>;
60
61/**
62 * @brief Enum of available LM-OTS algorithm types.
63 *
64 * The supported parameter sets are defined in RFC 8554 Section 4.1. and
65 * draft-fluhrer-lms-more-parm-sets-11 Section 4. HSS/LMS typecodes are
66 * introduced in RFC 8554 Section 3.2. and their format specified in
67 * Section 3.3.
68 */
69enum class LMOTS_Algorithm_Type : uint32_t /* NOLINT(*-enum-size) */ {
70 // --- RFC 8554 ---
71 RESERVED = 0x00,
72
73 // SHA-256 based
78
79 // --- draft-fluhrer-lms-more-parm-sets-11 ---
80 // SHA-256/192 based
85
86 // SHAKE-256/256 based
91
92 // SHAKE-256/192 based
97};
98
99/**
100 * @brief The LM-OTS parameters.
101 *
102 * See RFC 8554 Section 4.1.
103 */
104class BOTAN_TEST_API LMOTS_Params final {
105 public:
106 /**
107 * @brief Create the LM-OTS parameters from a known algorithm type.
108 * @throws Decoding_Error If the algorithm type is unknown
109 */
110 static LMOTS_Params create_or_throw(LMOTS_Algorithm_Type type);
111
112 /**
113 * @brief Create the LM-OTS parameters from a hash function and width.
114 *
115 * @param hash_name the name of the hash function to use.
116 * @param w the width (in bits) of the Winternitz coefficients.
117 * @throws Decoding_Error If the algorithm type is unknown
118 */
119 static LMOTS_Params create_or_throw(std::string_view hash_name, uint8_t w);
120
121 /**
122 * @brief Returns the LM-OTS algorithm type.
123 */
124 LMOTS_Algorithm_Type algorithm_type() const { return m_algorithm_type; }
125
126 /**
127 * @brief The number of bytes of the output of the hash function.
128 */
129 size_t n() const { return m_n; }
130
131 /**
132 * @brief The width (in bits) of the Winternitz coefficients.
133 */
134 uint8_t w() const { return m_w; }
135
136 /**
137 * @brief The maximum the winternitz coefficients can have.
138 */
139 uint8_t coef_max() const { return (1 << m_w) - 1; }
140
141 /**
142 * @brief The number of n-byte string elements that make up the LM-OTS signature.
143 */
144 uint16_t p() const { return m_p; }
145
146 /**
147 * @brief The number of left-shift bits used in the checksum function Cksm.
148 */
149 uint8_t ls() const { return m_ls; }
150
151 /**
152 * @brief Name of the hash function to use.
153 */
154 const std::string& hash_name() const { return m_hash_name; }
155
156 /**
157 * @brief Construct a new hash instance for the OTS instance.
158 */
159 std::unique_ptr<HashFunction> hash() const;
160
161 private:
162 /**
163 * @brief Construct a new LM-OTS parameter object.
164 *
165 * @param algorithm_type The algorithm type.
166 * @param hash_name The name of the hash function to use.
167 * @param w The width (in bits) of the Winternitz coefficients.
168 */
169 LMOTS_Params(LMOTS_Algorithm_Type algorithm_type, std::string_view hash_name, uint8_t w);
170
171 LMOTS_Algorithm_Type m_algorithm_type;
172 size_t m_n;
173 uint8_t m_w;
174 uint16_t m_p;
175 uint8_t m_ls;
176 std::string m_hash_name;
177};
178
179/**
180 * @brief Representation of a LM-OTS signature.
181 */
182class BOTAN_TEST_API LMOTS_Signature final {
183 public:
184 /**
185 * @brief Parse a LM-OTS signature.
186 *
187 * @param slicer The private key bytes to parse.
188 * @return The LM-OTS signature.
189 * @throws Decoding_Error If parsing the signature fails.
190 */
191 static LMOTS_Signature from_bytes_or_throw(BufferSlicer& slicer);
192
193 /**
194 * @brief Returns the LM-OTS algorithm type.
195 */
196 LMOTS_Algorithm_Type algorithm_type() const { return m_algorithm_type; }
197
198 /**
199 * @brief The n-byte randomizer of the signature.
200 */
201 std::span<const uint8_t> C() const { return m_C; }
202
203 /**
204 * @brief Returns the part of the signature for @p chain_idx.
205 */
206 StrongSpan<const LMOTS_Node> y(uint16_t chain_idx) const;
207
208 /**
209 * @brief The expected size of the signature.
210 */
211 static size_t size(const LMOTS_Params& params) { return 4 + params.n() * (params.p() + 1); }
212
213 private:
214 LMOTS_Signature(LMOTS_Algorithm_Type lmots_type, std::vector<uint8_t> C, std::vector<uint8_t> y_buffer);
215
216 LMOTS_Algorithm_Type m_algorithm_type;
217 std::vector<uint8_t> m_C;
218 std::vector<uint8_t> m_y_buffer;
219};
220
221/**
222 * @brief Base class for LMOTS private and public key. Contains the parameters for
223 * the specific OTS instance
224 */
226 public:
227 /**
228 * @brief Constructor storing the specific OTS parameters
229 */
231 m_params(params), m_identifier(identifier), m_q(q) {}
232
233 /**
234 * @brief The LMOTS parameters
235 */
236 const LMOTS_Params& params() const { return m_params; }
237
238 /**
239 * @brief The LMS identifier of the LMS tree containing this OTS instance ('I' in RFC 8554)
240 */
241 const LMS_Identifier& identifier() const { return m_identifier; }
242
243 /**
244 * @brief The index of the LMS tree leaf associated with this OTS instance
245 */
246 LMS_Tree_Node_Idx q() const { return m_q; }
247
248 private:
249 LMOTS_Params m_params;
250 LMS_Identifier m_identifier;
252};
253
254/**
255 * @brief Representation of an LMOTS private key.
256 *
257 * Contains the OTS params, I, q, the secret LMS seed and its derived
258 * secret chain inputs (x[] in RFC 8554 4.2)
259 */
261 public:
262 /**
263 * @brief Derive a LMOTS private key for a given @p seed.
264 *
265 * Implements RFC 8554 4.2 using derivation of Appendix A
266 */
270 const LMS_Seed& seed);
271
272 /**
273 * @brief As above, but using a caller-provided hash engine, allowing
274 * its reuse over many key derivations
275 */
279 const LMS_Seed& seed,
280 Hash_Engine& engine);
281
282 /**
283 * @brief The secret chain input at a given chain index. (x[] in RFC 8554 4.2).
284 */
285 const LMOTS_Node& chain_input(uint16_t chain_idx) const { return m_ots_sk.at(chain_idx); }
286
287 /**
288 * @brief Generate a new LMOTS signature.
289 *
290 * Defined in RFC 8554 4.5
291 */
292 void sign(StrongSpan<LMOTS_Signature_Bytes> out_sig, const LMS_Message& msg) const;
293
294 private:
295 /**
296 * @brief Derive random value C
297 *
298 * Derive the randomized value C as in the reference implementation (cisco):
299 * C = HASH(I || Q || 0xFFFD || 0xFF || SEED)
300 *
301 * Note that this derivation is important if we do not store the signature of root LMS nodes
302 * in the private key. Otherwise these root nodes are signed twice with different C values,
303 * resulting in a broken OTS signature.
304 */
305 void derive_random_C(std::span<uint8_t> out, HashFunction& hash) const;
306
307 LMS_Seed m_seed;
308 std::vector<LMOTS_Node> m_ots_sk;
309};
310
311/**
312 * @brief Representation of an OTS public key.
313 *
314 * Contains the public key bytes
315 * as defined in RFC 8554 4.3:
316 *
317 * u32str(type) || I || u32str(q) || K
318 */
320 public:
321 /**
322 * @brief Derivivation of an LMOTS public key using an LMOTS_Private_Key as defined
323 * in RFC 8554 4.3
324 */
325 explicit LMOTS_Public_Key(const LMOTS_Private_Key& lmots_sk);
326
327 /**
328 * @brief As above, but using a caller-provided hash engine, allowing
329 * its reuse over many key derivations
330 */
331 LMOTS_Public_Key(const LMOTS_Private_Key& lmots_sk, Hash_Engine& engine);
332
333 /**
334 * @brief Construct a new LMOTS public key object using the bytes.
335 *
336 * Note that the passed params, identifier and
337 * q value should match with the prefix in @p pub_key_bytes.
338 */
341
342 /**
343 * @brief The public key final hash value (K in RFC 8554 4.3 )
344 *
345 * @return const LMOTS_K&
346 */
347 const LMOTS_K& K() const { return m_K; }
348
349 private:
350 LMOTS_K m_K;
351};
352
353/**
354 * @brief Compute the public key hash values K (RFC 8554 4.3) of @p count
355 * consecutive LM-OTS instances beginning at @p first_q, deriving the
356 * instances' secrets from @p seed. The hashing is batched across all
357 * instances' chains.
358 */
359BOTAN_TEST_API void lmots_compute_pubkeys(std::span<uint8_t> out_ks,
360 const LMOTS_Params& params,
361 const LMS_Identifier& identifier,
362 LMS_Tree_Node_Idx first_q,
363 size_t count,
364 const LMS_Seed& seed,
365 Hash_Engine& engine);
366
367/**
368 * @brief Compute a public key candidate for an OTS-signature-message pair and the OTS instance parameters.
369 *
370 * Defined in RFC 8554 4.6 - Algorithm 4b
371 */
372BOTAN_TEST_API LMOTS_K lmots_compute_pubkey_from_sig(const LMOTS_Signature& sig,
373 const LMS_Message& msg,
374 const LMS_Identifier& identifier,
376
377} // namespace Botan
378
379#endif
#define BOTAN_TEST_API
Definition api.h:41
The LM-OTS parameters.
Definition lm_ots.h:104
static LMOTS_Params create_or_throw(LMOTS_Algorithm_Type type)
Create the LM-OTS parameters from a known algorithm type.
Definition lm_ots.cpp:131
uint8_t coef_max() const
The maximum the winternitz coefficients can have.
Definition lm_ots.h:139
LMOTS_Algorithm_Type algorithm_type() const
Returns the LM-OTS algorithm type.
Definition lm_ots.h:124
size_t n() const
The number of bytes of the output of the hash function.
Definition lm_ots.h:129
uint8_t w() const
The width (in bits) of the Winternitz coefficients.
Definition lm_ots.h:134
const std::string & hash_name() const
Name of the hash function to use.
Definition lm_ots.h:154
uint8_t ls() const
The number of left-shift bits used in the checksum function Cksm.
Definition lm_ots.h:149
uint16_t p() const
The number of n-byte string elements that make up the LM-OTS signature.
Definition lm_ots.h:144
Representation of an LMOTS private key.
Definition lm_ots.h:260
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).
Definition lm_ots.h:285
LMOTS_Private_Key(const LMOTS_Params &params, const LMS_Identifier &identifier, LMS_Tree_Node_Idx q, const LMS_Seed &seed)
Derive a LMOTS private key for a given seed.
Definition lm_ots.cpp:295
const LMOTS_K & K() const
The public key final hash value (K in RFC 8554 4.3 ).
Definition lm_ots.h:347
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....
Definition lm_ots.cpp:390
LMOTS_Public_Key(const LMOTS_Params &params, const LMS_Identifier &identifier, LMS_Tree_Node_Idx q, LMOTS_K K)
Construct a new LMOTS public key object using the bytes.
Definition lm_ots.h:339
Representation of a LM-OTS signature.
Definition lm_ots.h:182
static size_t size(const LMOTS_Params &params)
The expected size of the signature.
Definition lm_ots.h:211
LMOTS_Algorithm_Type algorithm_type() const
Returns the LM-OTS algorithm type.
Definition lm_ots.h:196
static LMOTS_Signature from_bytes_or_throw(BufferSlicer &slicer)
Parse a LM-OTS signature.
Definition lm_ots.cpp:271
std::span< const uint8_t > C() const
The n-byte randomizer of the signature.
Definition lm_ots.h:201
const LMS_Identifier & identifier() const
The LMS identifier of the LMS tree containing this OTS instance ('I' in RFC 8554).
Definition lm_ots.h:241
OTS_Instance(const LMOTS_Params &params, const LMS_Identifier &identifier, LMS_Tree_Node_Idx q)
Constructor storing the specific OTS parameters.
Definition lm_ots.h:230
LMS_Tree_Node_Idx q() const
The index of the LMS tree leaf associated with this OTS instance.
Definition lm_ots.h:246
const LMOTS_Params & params() const
The LMOTS parameters.
Definition lm_ots.h:236
auto at(size_type i) const
Definition bitvector.h:1481
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:481
Strong< std::vector< uint8_t >, struct LMOTS_K_ > LMOTS_K
The K value from the LM-OTS public key.
Definition lm_ots.h:39
Strong< std::vector< uint8_t >, struct LMS_Identifier_ > LMS_Identifier
The identifier of an LMS tree (I in RFC 8554).
Definition lm_ots.h:54
LMOTS_Algorithm_Type
Enum of available LM-OTS algorithm types.
Definition lm_ots.h:69
Strong< secure_vector< uint8_t >, struct LMS_SEED_ > LMS_Seed
Seed of the LMS tree, used to generate the LM-OTS private keys.
Definition lm_ots.h:29
Strong< secure_vector< uint8_t >, struct LMOTS_Node_ > LMOTS_Node
One node within one LM-OTS hash chain.
Definition lm_ots.h:34
Strong< std::vector< uint8_t >, struct LMS_Message_ > LMS_Message
A message that is signed with an LMS tree.
Definition lm_ots.h:59
void lmots_compute_pubkeys(std::span< uint8_t > out_ks, const LMOTS_Params &params, 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...
Definition lm_ots.cpp:424
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:49
Strong< std::vector< uint8_t >, struct LMOTS_Signature_Bytes_ > LMOTS_Signature_Bytes
Byte vector of an LM-OTS signature.
Definition lm_ots.h:44