/src/botan/build/include/internal/botan/internal/lm_ots.h

Source (jump to first uncovered line)
/**
 * LM-OTS - Leighton-Micali One-Time Signatures (RFC 8554 Section 4)
 * (C) 2023 Jack Lloyd
 *     2023 Fabian Albert, Philippe Lieser - Rohde & Schwarz Cybersecurity GmbH
 *
 * Botan is released under the Simplified BSD License (see license.txt)
 */

#ifndef BOTAN_LM_OTS_H_
#define BOTAN_LM_OTS_H_

#include <botan/hash.h>
#include <botan/internal/stl_util.h>

#include <span>
#include <string>
#include <string_view>
#include <vector>

namespace Botan {

/**
 * @brief Seed of the LMS tree, used to generate the LM-OTS private keys.
 */
using LMS_Seed = Strong<secure_vector<uint8_t>, struct LMS_SEED_>;

/**
 * @brief One node within one LM-OTS hash chain.
 */
using LMOTS_Node = Strong<secure_vector<uint8_t>, struct LMOTS_Node_>;

/**
 * @brief The K value from the LM-OTS public key.
 */
using LMOTS_K = Strong<std::vector<uint8_t>, struct LMOTS_K_>;

/**
 * @brief Byte vector of an LM-OTS signature.
 */
using LMOTS_Signature_Bytes = Strong<std::vector<uint8_t>, struct LMOTS_Signature_Bytes_>;

/**
 * @brief The index of a node within a specific LMS tree layer
 */
using LMS_Tree_Node_Idx = Strong<uint32_t, struct LMS_Tree_Node_Idx_, EnableArithmeticWithPlainNumber>;

/**
 * @brief The identifier of an LMS tree (I in RFC 8554)
 */
using LMS_Identifier = Strong<std::vector<uint8_t>, struct LMS_Identifier_>;

/**
 * @brief A message that is signed with an LMS tree
 */
using LMS_Message = Strong<std::vector<uint8_t>, struct LMS_Message_>;

/**
 * @brief Enum of available LM-OTS algorithm types.
 *
 * The supported parameter sets are defined in RFC 8554 Section 4.1. and
 * draft-fluhrer-lms-more-parm-sets-11 Section 4. HSS/LMS typecodes are
 * introduced in RFC 8554 Section 3.2. and their format specified in
 * Section 3.3.
 */
enum class LMOTS_Algorithm_Type : uint32_t {
   // --- RFC 8554 ---
   RESERVED = 0x00,

   // SHA-256 based
   SHA256_N32_W1 = 0x01,
   SHA256_N32_W2 = 0x02,
   SHA256_N32_W4 = 0x03,
   SHA256_N32_W8 = 0x04,

   // --- draft-fluhrer-lms-more-parm-sets-11 ---
   // SHA-256/192 based
   SHA256_N24_W1 = 0x05,
   SHA256_N24_W2 = 0x06,
   SHA256_N24_W4 = 0x07,
   SHA256_N24_W8 = 0x08,

   // SHAKE-256/256 based
   SHAKE_N32_W1 = 0x09,
   SHAKE_N32_W2 = 0x0a,
   SHAKE_N32_W4 = 0x0b,
   SHAKE_N32_W8 = 0x0c,

   // SHAKE-256/192 based
   SHAKE_N24_W1 = 0x0d,
   SHAKE_N24_W2 = 0x0e,
   SHAKE_N24_W4 = 0x0f,
   SHAKE_N24_W8 = 0x10,
};

/**
 * @brief The LM-OTS parameters.
 *
 * See RFC 8554 Section 4.1.
 */
class BOTAN_TEST_API LMOTS_Params final {
   public:
      /**
       * @brief Create the LM-OTS parameters from a known algorithm type.
       * @throws Decoding_Error If the algorithm type is unknown
       */
      static LMOTS_Params create_or_throw(LMOTS_Algorithm_Type type);

      /**
       * @brief Create the LM-OTS parameters from a hash function and width.
       *
       * @param hash_name tha name of the hash function to use.
       * @param w the width (in bits) of the Winternitz coefficients.
       * @throws Decoding_Error If the algorithm type is unknown
       */
      static LMOTS_Params create_or_throw(std::string_view hash_name, uint8_t w);

      /**
       * @brief Returns the LM-OTS algorithm type.
       */
      LMOTS_Algorithm_Type algorithm_type() const { return m_algorithm_type; }

      /**
       * @brief The number of bytes of the output of the hash function.
       */
      size_t n() const { return m_n; }

      /**
       * @brief The width (in bits) of the Winternitz coefficients.
       */
      uint8_t w() const { return m_w; }

      /**
       * @brief The maximum the winternitz coefficients can have.
       */
      uint8_t coef_max() const { return (1 << m_w) - 1; }

      /**
       * @brief The number of n-byte string elements that make up the LM-OTS signature.
       */
      uint16_t p() const { return m_p; }

      /**
       * @brief The number of left-shift bits used in the checksum function Cksm.
       */
      uint8_t ls() const { return m_ls; }

      /**
       * @brief Name of the hash function to use.
       */
      const std::string& hash_name() const { return m_hash_name; }

      /**
       * @brief Construct a new hash instance for the OTS instance.
       */
      std::unique_ptr<HashFunction> hash() const { return HashFunction::create_or_throw(hash_name()); }

   private:
      /**
       * @brief Construct a new LM-OTS parameter object.
       *
       * @param algorithm_type The algorithm type.
       * @param hash_name The name of the hash function to use.
       * @param w The width (in bits) of the Winternitz coefficients.
       */
      LMOTS_Params(LMOTS_Algorithm_Type algorithm_type, std::string_view hash_name, uint8_t w);

      LMOTS_Algorithm_Type m_algorithm_type;
      size_t m_n;
      uint8_t m_w;
      uint16_t m_p;
      uint8_t m_ls;
      std::string m_hash_name;
};

/**
 * @brief Representation of a LM-OTS signature.
 */
class BOTAN_TEST_API LMOTS_Signature final {
   public:
      /**
       * @brief Parse a LM-OTS signature.
       *
       * @param slicer The private key bytes to parse.
       * @return The LM-OTS signature.
       * @throws Decoding_Error If parsing the signature fails.
       */
      static LMOTS_Signature from_bytes_or_throw(BufferSlicer& slicer);

      /**
       * @brief Returns the LM-OTS algorithm type.
       */
      LMOTS_Algorithm_Type algorithm_type() const { return m_algorithm_type; }

      /**
       * @brief The n-byte randomizer of the signature.
       */
      std::span<const uint8_t> C() const { return m_C; }

      /**
       * @brief Returns the part of the signature for @p chain_idx.
       */
      StrongSpan<const LMOTS_Node> y(uint16_t chain_idx) const { return m_y.at(chain_idx); }

      /**
       * @brief The expected size of the signature.
       */
      static size_t size(const LMOTS_Params& params) { return 4 + params.n() * (params.p() + 1); }

   private:
      LMOTS_Signature(LMOTS_Algorithm_Type lmots_type, std::vector<uint8_t> C, std::vector<uint8_t> y_buffer);

      LMOTS_Algorithm_Type m_algorithm_type;
      std::vector<uint8_t> m_C;
      std::vector<uint8_t> m_y_buffer;
      std::vector<StrongSpan<const LMOTS_Node>> m_y;
};

/**
 * @brief Base class for LMOTS private and public key. Contains the parameters for
 *        the specific OTS instance
 */
class BOTAN_TEST_API OTS_Instance {
   public:
      /**
       * @brief Constructor storing the specific OTS parameters
       */
      OTS_Instance(const LMOTS_Params& params, const LMS_Identifier& identifier, LMS_Tree_Node_Idx q) :
            m_params(params), m_identifier(identifier), m_q(q) {}

      /**
       * @brief The LMOTS parameters
       */
      const LMOTS_Params& params() const { return m_params; }

      /**
       * @brief The LMS identifier of the LMS tree containing this OTS instance ('I' in RFC 8554)
       */
      const LMS_Identifier& identifier() const { return m_identifier; }

      /**
       * @brief The index of the LMS tree leaf associated with this OTS instance
       */
      LMS_Tree_Node_Idx q() const { return m_q; }

   private:
      LMOTS_Params m_params;
      LMS_Identifier m_identifier;
      LMS_Tree_Node_Idx m_q;
};

/**
 * @brief Representation of an LMOTS private key.
 *
 * Contains the OTS params, I, q, the secret LMS seed and its derived
 * secret chain inputs (x[] in RFC 8554 4.2)
 */
class BOTAN_TEST_API LMOTS_Private_Key final : public OTS_Instance {
   public:
      /**
       * @brief Derive a LMOTS private key for a given @p seed.
       *
       * Implements RFC 8554 4.2 using derivation of Appendix A
       */
      LMOTS_Private_Key(const LMOTS_Params& params,
                        const LMS_Identifier& identifier,
                        LMS_Tree_Node_Idx q,
                        const LMS_Seed& seed);

      /**
       * @brief The secret chain input at a given chain index. (x[] in RFC 8554 4.2).
       */
      const LMOTS_Node& chain_input(uint16_t chain_idx) const { return m_ots_sk.at(chain_idx); }

      /**
       * @brief Generate a new LMOTS signature.
       *
       * Defined in RFC 8554 4.5
       */
      void sign(StrongSpan<LMOTS_Signature_Bytes> out_sig, const LMS_Message& msg) const;

   private:
      /**
       * @brief Derive random value C
       *
       * Derive the randomized value C as in the reference implementation (cisco):
       * C = HASH(I || Q || 0xFFFD || 0xFF || SEED)
       *
       * Note that this derivation is important if we do not store the signature of root LMS nodes
       * in the private key. Otherwise these root nodes are signed twice with different C values,
       * resulting in a broken OTS signature.
       */
      void derive_random_C(std::span<uint8_t> out, HashFunction& hash) const;

      LMS_Seed m_seed;
      std::vector<LMOTS_Node> m_ots_sk;
};

/**
 * @brief Representation of an OTS public key.
 *
 * Contains the public key bytes
 * as defined in RFC 8554 4.3:
 *
 * u32str(type) || I || u32str(q) || K
 */
class BOTAN_TEST_API LMOTS_Public_Key final : public OTS_Instance {
   public:
      /**
       * @brief Derivivation of an LMOTS public key using an LMOTS_Private_Key as defined
       * in RFC 8554 4.3
       */
      LMOTS_Public_Key(const LMOTS_Private_Key& lmots_sk);

      /**
       * @brief Construct a new LMOTS public key object using the bytes.
       *
       * Note that the passed params, identifier and
       * q value should match with the prefix in @p pub_key_bytes.
       */
      LMOTS_Public_Key(const LMOTS_Params& params, const LMS_Identifier& identifier, LMS_Tree_Node_Idx q, LMOTS_K K) :
            OTS_Instance(params, identifier, q), m_K(std::move(K)) {}

      /**
       * @brief The public key final hash value (K in RFC 8554 4.3 )
       *
       * @return const LMOTS_K&
       */
      const LMOTS_K& K() const { return m_K; }

   private:
      LMOTS_K m_K;
};

/**
 * @brief Compute a public key candidate for an OTS-signature-message pair and the OTS instance parameters.
 *
 * Defined in RFC 8554 4.6 - Algorithm 4b
 */
BOTAN_TEST_API LMOTS_K lmots_compute_pubkey_from_sig(const LMOTS_Signature& sig,
                                                     const LMS_Message& msg,
                                                     const LMS_Identifier& identifier,
                                                     LMS_Tree_Node_Idx q);

}  // namespace Botan

#endif

Coverage Report

Created: 2025-04-11 06:34

Line	Count	Source (jump to first uncovered line)
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/hash.h>
13		#include <botan/internal/stl_util.h>
14
15		#include <span>
16		#include <string>
17		#include <string_view>
18		#include <vector>
19
20		namespace Botan {
21
22		/**
23		* @brief Seed of the LMS tree, used to generate the LM-OTS private keys.
24		*/
25		using LMS_Seed = Strong<secure_vector<uint8_t>, struct LMS_SEED_>;
26
27		/**
28		* @brief One node within one LM-OTS hash chain.
29		*/
30		using LMOTS_Node = Strong<secure_vector<uint8_t>, struct LMOTS_Node_>;
31
32		/**
33		* @brief The K value from the LM-OTS public key.
34		*/
35		using LMOTS_K = Strong<std::vector<uint8_t>, struct LMOTS_K_>;
36
37		/**
38		* @brief Byte vector of an LM-OTS signature.
39		*/
40		using LMOTS_Signature_Bytes = Strong<std::vector<uint8_t>, struct LMOTS_Signature_Bytes_>;
41
42		/**
43		* @brief The index of a node within a specific LMS tree layer
44		*/
45		using LMS_Tree_Node_Idx = Strong<uint32_t, struct LMS_Tree_Node_Idx_, EnableArithmeticWithPlainNumber>;
46
47		/**
48		* @brief The identifier of an LMS tree (I in RFC 8554)
49		*/
50		using LMS_Identifier = Strong<std::vector<uint8_t>, struct LMS_Identifier_>;
51
52		/**
53		* @brief A message that is signed with an LMS tree
54		*/
55		using LMS_Message = Strong<std::vector<uint8_t>, struct LMS_Message_>;
56
57		/**
58		* @brief Enum of available LM-OTS algorithm types.
59		*
60		* The supported parameter sets are defined in RFC 8554 Section 4.1. and
61		* draft-fluhrer-lms-more-parm-sets-11 Section 4. HSS/LMS typecodes are
62		* introduced in RFC 8554 Section 3.2. and their format specified in
63		* Section 3.3.
64		*/
65		enum class LMOTS_Algorithm_Type : uint32_t {
66		// --- RFC 8554 ---
67		RESERVED = 0x00,
68
69		// SHA-256 based
70		SHA256_N32_W1 = 0x01,
71		SHA256_N32_W2 = 0x02,
72		SHA256_N32_W4 = 0x03,
73		SHA256_N32_W8 = 0x04,
74
75		// --- draft-fluhrer-lms-more-parm-sets-11 ---
76		// SHA-256/192 based
77		SHA256_N24_W1 = 0x05,
78		SHA256_N24_W2 = 0x06,
79		SHA256_N24_W4 = 0x07,
80		SHA256_N24_W8 = 0x08,
81
82		// SHAKE-256/256 based
83		SHAKE_N32_W1 = 0x09,
84		SHAKE_N32_W2 = 0x0a,
85		SHAKE_N32_W4 = 0x0b,
86		SHAKE_N32_W8 = 0x0c,
87
88		// SHAKE-256/192 based
89		SHAKE_N24_W1 = 0x0d,
90		SHAKE_N24_W2 = 0x0e,
91		SHAKE_N24_W4 = 0x0f,
92		SHAKE_N24_W8 = 0x10,
93		};
94
95		/**
96		* @brief The LM-OTS parameters.
97		*
98		* See RFC 8554 Section 4.1.
99		*/
100		class BOTAN_TEST_API LMOTS_Params final {
101		public:
102		/**
103		* @brief Create the LM-OTS parameters from a known algorithm type.
104		* @throws Decoding_Error If the algorithm type is unknown
105		*/
106		static LMOTS_Params create_or_throw(LMOTS_Algorithm_Type type);
107
108		/**
109		* @brief Create the LM-OTS parameters from a hash function and width.
110		*
111		* @param hash_name tha name of the hash function to use.
112		* @param w the width (in bits) of the Winternitz coefficients.
113		* @throws Decoding_Error If the algorithm type is unknown
114		*/
115		static LMOTS_Params create_or_throw(std::string_view hash_name, uint8_t w);
116
117		/**
118		* @brief Returns the LM-OTS algorithm type.
119		*/
120	0	LMOTS_Algorithm_Type algorithm_type() const { return m_algorithm_type; }
121
122		/**
123		* @brief The number of bytes of the output of the hash function.
124		*/
125	0	size_t n() const { return m_n; }
126
127		/**
128		* @brief The width (in bits) of the Winternitz coefficients.
129		*/
130	0	uint8_t w() const { return m_w; }
131
132		/**
133		* @brief The maximum the winternitz coefficients can have.
134		*/
135	0	uint8_t coef_max() const { return (1 << m_w) - 1; }
136
137		/**
138		* @brief The number of n-byte string elements that make up the LM-OTS signature.
139		*/
140	0	uint16_t p() const { return m_p; }
141
142		/**
143		* @brief The number of left-shift bits used in the checksum function Cksm.
144		*/
145	0	uint8_t ls() const { return m_ls; }
146
147		/**
148		* @brief Name of the hash function to use.
149		*/
150	0	const std::string& hash_name() const { return m_hash_name; }
151
152		/**
153		* @brief Construct a new hash instance for the OTS instance.
154		*/
155	0	std::unique_ptr<HashFunction> hash() const { return HashFunction::create_or_throw(hash_name()); }
156
157		private:
158		/**
159		* @brief Construct a new LM-OTS parameter object.
160		*
161		* @param algorithm_type The algorithm type.
162		* @param hash_name The name of the hash function to use.
163		* @param w The width (in bits) of the Winternitz coefficients.
164		*/
165		LMOTS_Params(LMOTS_Algorithm_Type algorithm_type, std::string_view hash_name, uint8_t w);
166
167		LMOTS_Algorithm_Type m_algorithm_type;
168		size_t m_n;
169		uint8_t m_w;
170		uint16_t m_p;
171		uint8_t m_ls;
172		std::string m_hash_name;
173		};
174
175		/**
176		* @brief Representation of a LM-OTS signature.
177		*/
178		class BOTAN_TEST_API LMOTS_Signature final {
179		public:
180		/**
181		* @brief Parse a LM-OTS signature.
182		*
183		* @param slicer The private key bytes to parse.
184		* @return The LM-OTS signature.
185		* @throws Decoding_Error If parsing the signature fails.
186		*/
187		static LMOTS_Signature from_bytes_or_throw(BufferSlicer& slicer);
188
189		/**
190		* @brief Returns the LM-OTS algorithm type.
191		*/
192	0	LMOTS_Algorithm_Type algorithm_type() const { return m_algorithm_type; }
193
194		/**
195		* @brief The n-byte randomizer of the signature.
196		*/
197	0	std::span<const uint8_t> C() const { return m_C; }
198
199		/**
200		* @brief Returns the part of the signature for @p chain_idx.
201		*/
202	0	StrongSpan<const LMOTS_Node> y(uint16_t chain_idx) const { return m_y.at(chain_idx); }
203
204		/**
205		* @brief The expected size of the signature.
206		*/
207	0	static size_t size(const LMOTS_Params& params) { return 4 + params.n() * (params.p() + 1); }
208
209		private:
210		LMOTS_Signature(LMOTS_Algorithm_Type lmots_type, std::vector<uint8_t> C, std::vector<uint8_t> y_buffer);
211
212		LMOTS_Algorithm_Type m_algorithm_type;
213		std::vector<uint8_t> m_C;
214		std::vector<uint8_t> m_y_buffer;
215		std::vector<StrongSpan<const LMOTS_Node>> m_y;
216		};
217
218		/**
219		* @brief Base class for LMOTS private and public key. Contains the parameters for
220		* the specific OTS instance
221		*/
222		class BOTAN_TEST_API OTS_Instance {
223		public:
224		/**
225		* @brief Constructor storing the specific OTS parameters
226		*/
227		OTS_Instance(const LMOTS_Params& params, const LMS_Identifier& identifier, LMS_Tree_Node_Idx q) :
228	0	m_params(params), m_identifier(identifier), m_q(q) {}
229
230		/**
231		* @brief The LMOTS parameters
232		*/
233	0	const LMOTS_Params& params() const { return m_params; }
234
235		/**
236		* @brief The LMS identifier of the LMS tree containing this OTS instance ('I' in RFC 8554)
237		*/
238	0	const LMS_Identifier& identifier() const { return m_identifier; }
239
240		/**
241		* @brief The index of the LMS tree leaf associated with this OTS instance
242		*/
243	0	LMS_Tree_Node_Idx q() const { return m_q; }
244
245		private:
246		LMOTS_Params m_params;
247		LMS_Identifier m_identifier;
248		LMS_Tree_Node_Idx m_q;
249		};
250
251		/**
252		* @brief Representation of an LMOTS private key.
253		*
254		* Contains the OTS params, I, q, the secret LMS seed and its derived
255		* secret chain inputs (x[] in RFC 8554 4.2)
256		*/
257		class BOTAN_TEST_API LMOTS_Private_Key final : public OTS_Instance {
258		public:
259		/**
260		* @brief Derive a LMOTS private key for a given @p seed.
261		*
262		* Implements RFC 8554 4.2 using derivation of Appendix A
263		*/
264		LMOTS_Private_Key(const LMOTS_Params& params,
265		const LMS_Identifier& identifier,
266		LMS_Tree_Node_Idx q,
267		const LMS_Seed& seed);
268
269		/**
270		* @brief The secret chain input at a given chain index. (x[] in RFC 8554 4.2).
271		*/
272	0	const LMOTS_Node& chain_input(uint16_t chain_idx) const { return m_ots_sk.at(chain_idx); }
273
274		/**
275		* @brief Generate a new LMOTS signature.
276		*
277		* Defined in RFC 8554 4.5
278		*/
279		void sign(StrongSpan<LMOTS_Signature_Bytes> out_sig, const LMS_Message& msg) const;
280
281		private:
282		/**
283		* @brief Derive random value C
284		*
285		* Derive the randomized value C as in the reference implementation (cisco):
286		* C = HASH(I \|\| Q \|\| 0xFFFD \|\| 0xFF \|\| SEED)
287		*
288		* Note that this derivation is important if we do not store the signature of root LMS nodes
289		* in the private key. Otherwise these root nodes are signed twice with different C values,
290		* resulting in a broken OTS signature.
291		*/
292		void derive_random_C(std::span<uint8_t> out, HashFunction& hash) const;
293
294		LMS_Seed m_seed;
295		std::vector<LMOTS_Node> m_ots_sk;
296		};
297
298		/**
299		* @brief Representation of an OTS public key.
300		*
301		* Contains the public key bytes
302		* as defined in RFC 8554 4.3:
303		*
304		* u32str(type) \|\| I \|\| u32str(q) \|\| K
305		*/
306		class BOTAN_TEST_API LMOTS_Public_Key final : public OTS_Instance {
307		public:
308		/**
309		* @brief Derivivation of an LMOTS public key using an LMOTS_Private_Key as defined
310		* in RFC 8554 4.3
311		*/
312		LMOTS_Public_Key(const LMOTS_Private_Key& lmots_sk);
313
314		/**
315		* @brief Construct a new LMOTS public key object using the bytes.
316		*
317		* Note that the passed params, identifier and
318		* q value should match with the prefix in @p pub_key_bytes.
319		*/
320		LMOTS_Public_Key(const LMOTS_Params& params, const LMS_Identifier& identifier, LMS_Tree_Node_Idx q, LMOTS_K K) :
321	0	OTS_Instance(params, identifier, q), m_K(std::move(K)) {}
322
323		/**
324		* @brief The public key final hash value (K in RFC 8554 4.3 )
325		*
326		* @return const LMOTS_K&
327		*/
328	0	const LMOTS_K& K() const { return m_K; }
329
330		private:
331		LMOTS_K m_K;
332		};
333
334		/**
335		* @brief Compute a public key candidate for an OTS-signature-message pair and the OTS instance parameters.
336		*
337		* Defined in RFC 8554 4.6 - Algorithm 4b
338		*/
339		BOTAN_TEST_API LMOTS_K lmots_compute_pubkey_from_sig(const LMOTS_Signature& sig,
340		const LMS_Message& msg,
341		const LMS_Identifier& identifier,
342		LMS_Tree_Node_Idx q);
343
344		} // namespace Botan
345
346		#endif