Botan 3.5.0
Crypto and TLS for C&
lm_ots.cpp
Go to the documentation of this file.
1/**
2 * LM-OTS - Leighton-Micali One-Time Signatures
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/lm_ots.h>
10
11#include <botan/exceptn.h>
12#include <botan/strong_type.h>
13#include <botan/internal/bit_ops.h>
14#include <botan/internal/hss_lms_utils.h>
15#include <botan/internal/int_utils.h>
16
17namespace Botan {
18
19namespace {
20constexpr uint16_t D_PBLC = 0x8080;
21constexpr uint16_t D_MESG = 0x8181;
22/// For derivation of C as in https://github.com/cisco/hash-sigs
23constexpr uint16_t C_INDEX = 0xFFFD;
24
25class Chain_Generator {
26 public:
27 Chain_Generator(const LMS_Identifier& identifier, LMS_Tree_Node_Idx q) : m_gen(identifier) {
28 m_gen.set_q(q.get());
29 }
30
31 void process(HashFunction& hash,
32 uint16_t chain_idx,
33 uint8_t start,
34 uint8_t end,
35 std::span<const uint8_t> in,
36 std::span<uint8_t> out) {
37 BOTAN_ARG_CHECK(start <= end, "Start value is bigger than end value");
38
39 copy_mem(out, in);
40 m_gen.set_i(chain_idx);
41
42 for(uint8_t j = start; j < end; ++j) {
43 m_gen.set_j(j);
44 m_gen.gen(out, hash, out);
45 }
46 }
47
48 private:
49 PseudorandomKeyGeneration m_gen;
50};
51
52// RFC 8554 3.1.1
53uint8_t byte(std::span<const uint8_t> S, uint32_t i) {
54 BOTAN_ARG_CHECK(i < S.size(), "Index out of range");
55 return S[i];
56}
57
58// RFC 8554 3.1.3
59uint8_t coef(std::span<const uint8_t> S, uint32_t i, const LMOTS_Params& params) {
60 const uint8_t w_bit_mask = params.coef_max();
61 const uint8_t coef_byte = byte(S, (i * params.w()) / 8);
62 const uint8_t shift = 8 - (params.w() * (i % (8 / params.w())) + params.w());
63
64 return w_bit_mask & (coef_byte >> shift);
65}
66
67// RFC 8554 4.4
68uint16_t checksum(const LMOTS_Params& params, std::span<const uint8_t> S) {
69 size_t sum = 0;
70 for(uint32_t i = 0; i < (params.n() * 8 / params.w()); ++i) {
71 sum += params.coef_max() - coef(S, i, params);
72 }
73 return checked_cast_to<uint16_t>(sum << params.ls());
74}
75
76std::vector<uint8_t> gen_Q_with_cksm(const LMOTS_Params& params,
77 const LMS_Identifier& identifier,
78 const LMS_Tree_Node_Idx& q,
79 std::span<const uint8_t> C,
80 const LMS_Message& msg) {
81 std::vector<uint8_t> Q_with_cksm(params.n() + sizeof(uint16_t));
82 BufferStuffer qwc_stuffer(Q_with_cksm);
83 const auto hash = params.hash();
84 hash->update(identifier);
85 hash->update(store_be(q));
86 hash->update(store_be(D_MESG));
87 hash->update(C);
88 hash->update(msg);
89 auto Q_span = qwc_stuffer.next(params.n());
90 hash->final(Q_span);
91
92 qwc_stuffer.append(store_be(checksum(params, Q_span)));
93
94 return Q_with_cksm;
95}
96
97} // namespace
98
100 auto [hash_name, w] = [](const LMOTS_Algorithm_Type& lmots_type) -> std::pair<std::string_view, uint8_t> {
101 switch(lmots_type) {
103 return {"SHA-256", 1};
105 return {"SHA-256", 2};
107 return {"SHA-256", 4};
109 return {"SHA-256", 8};
111 return {"Truncated(SHA-256,192)", 1};
113 return {"Truncated(SHA-256,192)", 2};
115 return {"Truncated(SHA-256,192)", 4};
117 return {"Truncated(SHA-256,192)", 8};
119 return {"SHAKE-256(256)", 1};
121 return {"SHAKE-256(256)", 2};
123 return {"SHAKE-256(256)", 4};
125 return {"SHAKE-256(256)", 8};
127 return {"SHAKE-256(192)", 1};
129 return {"SHAKE-256(192)", 2};
131 return {"SHAKE-256(192)", 4};
133 return {"SHAKE-256(192)", 8};
135 throw Decoding_Error("Unsupported LMS algorithm type");
136 }
137 throw Decoding_Error("Unsupported LMS algorithm type");
138 }(type);
139
140 return LMOTS_Params(type, hash_name, w);
141}
142
143LMOTS_Params LMOTS_Params::create_or_throw(std::string_view hash_name, uint8_t w) {
144 if(w != 1 && w != 2 && w != 4 && w != 8) {
145 throw Decoding_Error("Invalid Winternitz parameter");
146 }
147 LMOTS_Algorithm_Type type = [](std::string_view hash, uint8_t w_p) -> LMOTS_Algorithm_Type {
148 if(hash == "SHA-256") {
149 switch(w_p) {
150 case 1:
152 case 2:
154 case 4:
156 case 8:
158 default:
159 throw Decoding_Error("Unsupported Winternitz parameter");
160 }
161 }
162 if(hash == "Truncated(SHA-256,192)") {
163 switch(w_p) {
164 case 1:
166 case 2:
168 case 4:
170 case 8:
172 default:
173 throw Decoding_Error("Unsupported Winternitz parameter");
174 }
175 }
176 if(hash == "SHAKE-256(256)") {
177 switch(w_p) {
178 case 1:
180 case 2:
182 case 4:
184 case 8:
186 default:
187 throw Decoding_Error("Unsupported Winternitz parameter");
188 }
189 }
190 if(hash == "SHAKE-256(192)") {
191 switch(w_p) {
192 case 1:
194 case 2:
196 case 4:
198 case 8:
200 default:
201 throw Decoding_Error("Unsupported Winternitz parameter");
202 }
203 }
204 throw Decoding_Error("Unsupported hash function");
205 }(hash_name, w);
206
207 return LMOTS_Params(type, hash_name, w);
208}
209
210LMOTS_Params::LMOTS_Params(LMOTS_Algorithm_Type algorithm_type, std::string_view hash_name, uint8_t w) :
211 m_algorithm_type(algorithm_type), m_w(w), m_hash_name(hash_name) {
212 const auto hash = HashFunction::create_or_throw(m_hash_name);
213 m_n = hash->output_length();
214 // RFC 8553 Appendix B - Parameter Computation
215 auto u = ceil_division<size_t>(8 * m_n, m_w); // ceil(8*n/w)
216 auto v = ceil_division<size_t>(high_bit(((1 << m_w) - 1) * u), m_w); // ceil((floor(lg[(2^w - 1) * u]) + 1) / w)
217 m_ls = checked_cast_to<uint8_t>(16 - (v * w));
218 m_p = checked_cast_to<uint16_t>(u + v);
219}
220
221LMOTS_Signature::LMOTS_Signature(LMOTS_Algorithm_Type lmots_type,
222 std::vector<uint8_t> C,
223 std::vector<uint8_t> y_buffer) :
224 m_algorithm_type(lmots_type), m_C(std::move(C)), m_y_buffer(std::move(y_buffer)) {
225 LMOTS_Params params = LMOTS_Params::create_or_throw(m_algorithm_type);
226
227 BufferSlicer y_slicer(m_y_buffer);
228 for(uint16_t i = 0; i < params.p(); ++i) {
229 m_y.push_back(y_slicer.take<LMOTS_Node>(params.n()));
230 }
231 BOTAN_ASSERT_NOMSG(y_slicer.empty());
232}
233
235 size_t total_remaining_bytes = slicer.remaining();
236 // Alg. 6a. 1. (last 4 bytes) / Alg. 4b. 1.
237 if(total_remaining_bytes < sizeof(LMOTS_Algorithm_Type)) {
238 throw Decoding_Error("Too few signature bytes while parsing LMOTS signature.");
239 }
240 // Alg. 6a. 2.b. / Alg. 4b. 2.a.
242
243 // Alg. 6a. 2.d. / Alg. 4b. 2.c.
245
246 if(total_remaining_bytes < size(params)) {
247 throw Decoding_Error("Too few signature bytes while parsing LMOTS signature.");
248 }
249
250 // Alg. 4b. 2.d.
251 auto C = slicer.copy_as_vector(params.n());
252 // Alg. 4b. 2.e.
253 auto m_y_buffer = slicer.copy_as_vector(params.p() * params.n());
254
255 return LMOTS_Signature(algorithm_type, std::move(C), std::move(m_y_buffer));
256}
257
259 const LMS_Identifier& identifier,
261 const LMS_Seed& seed) :
262 OTS_Instance(params, identifier, q), m_seed(seed) {
264 const auto hash = params.hash();
265
266 gen.set_q(q.get());
267 gen.set_j(0xff);
268
269 for(uint16_t i = 0; i < params.p(); ++i) {
270 gen.set_i(i);
271 m_ots_sk.push_back(gen.gen<LMOTS_Node>(*hash, seed));
272 }
273}
274
276 BOTAN_ARG_CHECK(out_sig.size() == LMOTS_Signature::size(params()), "Invalid output buffer size");
277 BufferStuffer sig_stuffer(out_sig);
278 const auto hash = params().hash();
279 sig_stuffer.append(store_be(params().algorithm_type()));
280 const auto C = sig_stuffer.next(params().n());
281
282 // Since we do not store the signatures of the lms trees in the HSS sk,
283 // we need deterministic signatures to avoid reusing a OTS key to generate multiple signatures.
284 // See also: https://github.com/cisco/hash-sigs/blob/b0631b8891295bf2929e68761205337b7c031726/lm_ots_sign.c#L110-L115
285 derive_random_C(C, *hash);
286
287 const auto Q_with_cksm = gen_Q_with_cksm(params(), identifier(), q(), C, msg);
288
289 Chain_Generator chain_gen(identifier(), q());
290 for(uint16_t i = 0; i < params().p(); ++i) {
291 const auto y_i = sig_stuffer.next(params().n());
292 const uint8_t a = coef(Q_with_cksm, i, params());
293 chain_gen.process(*hash, i, 0, a, chain_input(i), y_i);
294 }
295 BOTAN_ASSERT_NOMSG(sig_stuffer.full());
296}
297
298void LMOTS_Private_Key::derive_random_C(std::span<uint8_t> out, HashFunction& hash) const {
300
301 gen.set_q(q().get());
302 gen.set_i(C_INDEX);
303 gen.set_j(0xff);
304
305 gen.gen(out, hash, m_seed);
306}
307
309 const auto pk_hash = lmots_sk.params().hash();
310 pk_hash->update(lmots_sk.identifier());
311 pk_hash->update(store_be(lmots_sk.q()));
312 pk_hash->update(store_be(D_PBLC));
313
314 Chain_Generator chain_gen(lmots_sk.identifier(), lmots_sk.q());
315 const auto hash = lmots_sk.params().hash();
316 LMOTS_Node tmp(lmots_sk.params().n());
317 for(uint16_t i = 0; i < lmots_sk.params().p(); ++i) {
318 chain_gen.process(*hash, i, 0, lmots_sk.params().coef_max(), lmots_sk.chain_input(i), tmp);
319 pk_hash->update(tmp);
320 }
321
322 m_K = pk_hash->final<LMOTS_K>();
323}
324
326 const LMS_Message& msg,
327 const LMS_Identifier& identifier,
330
331 // Alg. 4b 3.
332
333 const auto Q_with_cksm = gen_Q_with_cksm(params, identifier, q, sig.C(), msg);
334
335 // Prefill the final hash object
336 const auto pk_hash = params.hash();
337 pk_hash->update(identifier);
338 pk_hash->update(store_be(q));
339 pk_hash->update(store_be(D_PBLC));
340
341 Chain_Generator chain_gen(identifier, q);
342 const auto hash = params.hash();
343 LMOTS_Node tmp(params.n());
344 for(uint16_t i = 0; i < params.p(); ++i) {
345 const uint8_t a = coef(Q_with_cksm, i, params);
346 chain_gen.process(*hash, i, a, params.coef_max(), sig.y(i), tmp);
347 pk_hash->update(tmp);
348 }
349 // Alg. 4b 4.
350 return pk_hash->final<LMOTS_K>();
351}
352
353} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:29
size_t remaining() const
Definition stl_util.h:127
std::span< const uint8_t > take(const size_t count)
Definition stl_util.h:98
auto copy_as_vector(const size_t count)
Definition stl_util.h:94
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
uint8_t coef_max() const
The maximum the winternitz coefficients can have.
Definition lm_ots.h:135
std::unique_ptr< HashFunction > hash() const
Construct a new hash instance for the OTS instance.
Definition lm_ots.h:155
size_t n() const
The number of bytes of the output of the hash function.
Definition lm_ots.h:125
uint8_t w() const
The width (in bits) of the Winternitz coefficients.
Definition lm_ots.h:130
const std::string & hash_name() const
Name of the hash function to use.
Definition lm_ots.h:150
uint16_t p() const
The number of n-byte string elements that make up the LM-OTS signature.
Definition lm_ots.h:140
Representation of an LMOTS private key.
Definition lm_ots.h:257
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:272
void sign(StrongSpan< LMOTS_Signature_Bytes > out_sig, const LMS_Message &msg) const
Generate a new LMOTS signature.
Definition lm_ots.cpp:275
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:258
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:308
Representation of a LM-OTS signature.
Definition lm_ots.h:178
static size_t size(const LMOTS_Params &params)
The expected size of the signature.
Definition lm_ots.h:207
StrongSpan< const LMOTS_Node > y(uint16_t chain_idx) const
Returns the part of the signature for chain_idx.
Definition lm_ots.h:202
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
std::span< const uint8_t > C() const
The n-byte randomizer of the signature.
Definition lm_ots.h:197
Base class for LMOTS private and public key. Contains the parameters for the specific OTS instance.
Definition lm_ots.h:222
const LMS_Identifier & identifier() const
The LMS identifier of the LMS tree containing this OTS instance ('I' in RFC 8554)
Definition lm_ots.h:238
LMS_Tree_Node_Idx q() const
The index of the LMS tree leaf associated with this OTS instance.
Definition lm_ots.h:243
const LMOTS_Params & params() const
The LMOTS parameters.
Definition lm_ots.h:233
Helper class used to derive secret values based in the pseudorandom key generation described in RFC 8...
void set_i(uint16_t i)
Specify the value for the u16str(i) hash input field.
void set_j(uint8_t j)
Specify the value for the u8str(j) hash input field.
T gen(HashFunction &hash, std::span< const uint8_t > seed) const
Create a hash value using the preconfigured prefix and a seed.
void set_q(uint32_t q)
Specify the value for the u32str(q) hash input field.
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
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
constexpr RT checked_cast_to(AT i)
Definition int_utils.h:109
constexpr size_t high_bit(T n)
Definition bit_ops.h:58
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 T ceil_division(T a, T b)
Definition bit_ops.h:149
Strong< secure_vector< uint8_t >, struct LMOTS_Node_ > LMOTS_Node
One node within one LM-OTS hash chain.
Definition lm_ots.h:30
Strong< std::vector< uint8_t >, struct LMS_Message_ > LMS_Message
A message that is signed with an LMS tree.
Definition lm_ots.h:55
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
std::uint8_t byte
Definition types.h:94
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:146
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:707
constexpr auto load_be(ParamTs &&... params)
Definition loadstor.h:467