Botan 3.14.1
Crypto and TLS for C&
xmss_privatekey.cpp
Go to the documentation of this file.
1/*
2 * XMSS Private Key
3 * An XMSS: Extended Hash-Based Signature private key.
4 * The XMSS private key does not support the X509 and PKCS7 standard. Instead
5 * the raw format described in [1] is used.
6 *
7 * [1] XMSS: Extended Hash-Based Signatures,
8 * Request for Comments: 8391
9 * Release: May 2018.
10 * https://datatracker.ietf.org/doc/rfc8391/
11 *
12 * (C) 2016,2017,2018 Matthias Gierlings
13 * (C) 2019,2026 Jack Lloyd
14 * (C) 2023 René Meusel - Rohde & Schwarz Cybersecurity
15 *
16 * Botan is released under the Simplified BSD License (see license.txt)
17 **/
18
19#include <botan/xmss.h>
20
21#include <botan/ber_dec.h>
22#include <botan/der_enc.h>
23#include <botan/pk_options.h>
24#include <botan/rng.h>
25#include <botan/internal/buffer_slicer.h>
26#include <botan/internal/concat_util.h>
27#include <botan/internal/int_utils.h>
28#include <botan/internal/loadstor.h>
29#include <botan/internal/pk_options_impl.h>
30#include <botan/internal/stateful_key_index_registry.h>
31#include <botan/internal/xmss_hash.h>
32#include <botan/internal/xmss_signature_operation.h>
33#include <botan/internal/xmss_tree_builder.h>
34
35namespace Botan {
36
37namespace {
38
39// fall back to raw decoding for previous versions, which did not encode an OCTET STRING
40secure_vector<uint8_t> extract_raw_private_key(std::span<const uint8_t> key_bits, const XMSS_Parameters& xmss_params) {
42
43 // The public part of the input key bits was already parsed, so we can
44 // decide depending on the buffer length whether this must be BER decoded.
45 if(key_bits.size() == xmss_params.raw_private_key_size() ||
46 key_bits.size() == xmss_params.raw_legacy_private_key_size()) {
47 raw_key.assign(key_bits.begin(), key_bits.end());
48 } else {
50 }
51
52 return raw_key;
53}
54
55bool is_known_wots_derivation_method(WOTS_Derivation_Method method) {
57}
58
59/*
60* The identity consists of the inputs to the WOTS+ key derivation, so that
61* keys with the same WOTS+ keys share one leaf index. SK_PRF is not one of
62* these inputs, and neither is the public seed when using Botan2x derivation.
63*/
65 WOTS_Derivation_Method wots_derivation_method,
66 std::span<const uint8_t> private_seed,
67 std::span<const uint8_t> public_seed) {
68 const auto algo_params = concat<std::vector<uint8_t>>(store_be(static_cast<uint32_t>(params.oid())),
69 std::array{static_cast<uint8_t>(wots_derivation_method)});
70
71 const bool derivation_uses_public_seed = (wots_derivation_method == WOTS_Derivation_Method::NIST_SP800_208);
72
74 algo_params,
75 params.total_number_of_signatures(),
76 private_seed,
77 derivation_uses_public_seed ? public_seed : std::span<const uint8_t>());
78}
79
80} // namespace
81
82class XMSS_PrivateKey_Internal final {
83 public:
84 XMSS_PrivateKey_Internal(XMSS_Parameters::xmss_algorithm_t xmss_algo_id,
85 WOTS_Derivation_Method wots_derivation_method,
86 std::span<const uint8_t> public_seed,
87 secure_vector<uint8_t> private_seed,
89 m_xmss_params(XMSS_Parameters::from_id(xmss_algo_id)),
90 m_wots_params(m_xmss_params.wots_parameters()),
91 m_wots_derivation_method(wots_derivation_method),
92 m_prf(std::move(prf)),
93 m_private_seed(std::move(private_seed)),
94 m_keyid(xmss_key_id(m_xmss_params, m_wots_derivation_method, m_private_seed, public_seed)) {
95 // Callers update the registry afterwards, so all validation must happen here
96 BOTAN_ARG_CHECK(is_known_wots_derivation_method(m_wots_derivation_method),
97 "XMSS: unknown WOTS+ derivation method");
98 BOTAN_ARG_CHECK(m_prf.size() == m_xmss_params.element_size(), "XMSS: unexpected byte length of PRF value");
99 BOTAN_ARG_CHECK(m_private_seed.size() == m_xmss_params.element_size(),
100 "XMSS: unexpected byte length of private seed");
101 }
102
103 XMSS_PrivateKey_Internal(XMSS_Parameters::xmss_algorithm_t xmss_algo_id, std::span<const uint8_t> key_bits) :
104 m_xmss_params(XMSS_Parameters::from_id(xmss_algo_id)), m_wots_params(m_xmss_params.wots_parameters()) {
105 /*
106 The code requires sizeof(size_t) >= ceil(tree_height / 8)
107
108 Maximum supported tree height is 20, ceil(20/8) == 3, so 4 byte
109 size_t is sufficient for all defined parameters, or even a
110 (hypothetical) tree height 32, which would be extremely slow to
111 compute.
112 */
113 static_assert(sizeof(size_t) >= 4, "size_t is big enough to support leaf index");
114
115 const secure_vector<uint8_t> raw_key = extract_raw_private_key(key_bits, m_xmss_params);
116
117 if(raw_key.size() != m_xmss_params.raw_private_key_size() &&
118 raw_key.size() != m_xmss_params.raw_legacy_private_key_size()) {
119 throw Decoding_Error("Invalid XMSS private key size");
120 }
121
122 BufferSlicer s(raw_key);
123
124 // The OID and root were already parsed by XMSS_PublicKey; the public
125 // seed is needed here as part of the key identity
126 s.skip(4 + m_xmss_params.element_size());
127 const auto public_seed = s.take(m_xmss_params.element_size());
128
129 const auto unused_leaf_bytes = s.take(sizeof(uint32_t));
130 const size_t unused_leaf = load_be<uint32_t>(unused_leaf_bytes.data(), 0);
131
132 m_prf = s.copy_as_secure_vector(m_xmss_params.element_size());
133 m_private_seed = s.copy_as_secure_vector(m_xmss_params.element_size());
134
135 // Legacy keys generated prior to Botan 3.x don't feature a
136 // WOTS+ key derivation method encoded in their private key.
137 m_wots_derivation_method =
138 (s.empty()) ? WOTS_Derivation_Method::Botan2x : static_cast<WOTS_Derivation_Method>(s.take_byte());
139
140 if(!is_known_wots_derivation_method(m_wots_derivation_method)) {
141 throw Decoding_Error("XMSS private key has an unknown WOTS+ derivation method");
142 }
143
144 BOTAN_ASSERT_NOMSG(s.empty());
145
146 m_keyid = xmss_key_id(m_xmss_params, m_wots_derivation_method, m_private_seed, public_seed);
147
148 // Note m_keyid must be initialized before set_unused_leaf_index is called!
149 // This comes last, after every check that can reject the encoding, since
150 // it raises the index lower bound shared by all copies of this key.
151 set_unused_leaf_index(unused_leaf);
152 }
153
154 secure_vector<uint8_t> serialize(std::vector<uint8_t> raw_public_key) const {
155 std::vector<uint8_t> unused_index(4);
156 store_be(checked_cast_to<uint32_t>(unused_leaf_index()), unused_index.data());
157
158 std::vector<uint8_t> wots_derivation_method;
159 wots_derivation_method.push_back(static_cast<uint8_t>(m_wots_derivation_method));
160
162 raw_public_key, unused_index, m_prf, m_private_seed, wots_derivation_method);
163 }
164
165 const secure_vector<uint8_t>& prf_value() const { return m_prf; }
166
167 const secure_vector<uint8_t>& private_seed() const { return m_private_seed; }
168
169 const XMSS_WOTS_Parameters& wots_parameters() const { return m_wots_params; }
170
171 WOTS_Derivation_Method wots_derivation_method() const { return m_wots_derivation_method; }
172
173 // The signing state (leaf index) lives in the process-wide
174 // Stateful_Key_Index_Registry keyed by m_keyid, not in this object, so the
175 // methods that advance it leave *this unchanged and are therefore const.
176 void set_unused_leaf_index(size_t idx) const {
177 // An index equal to 2^h is valid and denotes an exhausted key
178 if(idx > (1ULL << m_xmss_params.tree_height())) {
179 throw Decoding_Error("XMSS private key leaf index out of bounds");
180 } else {
182 }
183 }
184
185 size_t reserve_unused_leaf_index() const {
187 if(!idx.has_value()) {
188 throw Invalid_State("XMSS private key, one time signatures exhausted");
189 }
190 // Cast is safe even on 32 bit since total_number_of_signatures will be less
191 return static_cast<size_t>(idx.value());
192 }
193
194 size_t unused_leaf_index() const {
195 const uint64_t idx = Stateful_Key_Index_Registry::global().current_index(m_keyid);
196 return checked_cast_to<size_t>(idx);
197 }
198
199 uint64_t remaining_signatures() const {
201 }
202
203 private:
204 XMSS_Parameters m_xmss_params;
205 XMSS_WOTS_Parameters m_wots_params;
206 WOTS_Derivation_Method m_wots_derivation_method;
207
209 secure_vector<uint8_t> m_private_seed;
210 Stateful_Key_Index_Registry::KeyId m_keyid;
211};
212
213XMSS_PrivateKey::XMSS_PrivateKey(std::span<const uint8_t> key_bits) :
215
216XMSS_PrivateKey::XMSS_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) :
217 XMSS_PublicKey(alg_id, key_bits, Key_Encoding::PrivateKey),
218 m_private(std::make_shared<XMSS_PrivateKey_Internal>(xmss_parameters().oid(), key_bits)) {}
219
220struct XMSS_PrivateKey::Keygen_Material {
221 secure_vector<uint8_t> private_seed;
225};
226
227XMSS_PrivateKey::Keygen_Material XMSS_PrivateKey::generate_keygen_material(
229 RandomNumberGenerator& rng,
230 WOTS_Derivation_Method wots_derivation_method) {
231 BOTAN_ARG_CHECK(is_known_wots_derivation_method(wots_derivation_method), "XMSS: unknown WOTS+ derivation method");
232
233 const auto params = XMSS_Parameters::from_id(xmss_algo_id);
234 const size_t n = params.element_size();
235
236 // The order in which the seeds are drawn from the RNG (public seed, then
237 // prf, then private seed) must match the historical two-phase construction
238 // so that a deterministic RNG reproduces the same key material.
239 auto public_seed = rng.random_vec(n);
240 auto prf = rng.random_vec(n);
241 auto private_seed = rng.random_vec(n);
242
243 const XMSS_Address adrs;
244 XMSS_Hash hash(params);
245 const XMSS_Tree_Builder builder(params.wots_parameters(), wots_derivation_method, public_seed, private_seed);
246 auto root = builder.tree_hash(0, params.tree_height(), adrs, hash);
247
248 return Keygen_Material{std::move(private_seed), std::move(prf), std::move(public_seed), std::move(root)};
249}
250
256
258 WOTS_Derivation_Method wots_derivation_method,
259 Keygen_Material material) :
260 XMSS_PublicKey(xmss_algo_id, std::move(material.root), std::move(material.public_seed)),
261 m_private(std::make_shared<XMSS_PrivateKey_Internal>(xmss_algo_id,
262 wots_derivation_method,
263 this->public_seed(),
264 std::move(material.private_seed),
265 std::move(material.prf))) {}
266
268 size_t idx_leaf,
269 secure_vector<uint8_t> wots_priv_seed,
274 XMSS_PublicKey(xmss_algo_id, std::move(root), std::move(public_seed)),
275 m_private(std::make_shared<XMSS_PrivateKey_Internal>(
276 xmss_algo_id, wots_derivation_method, this->public_seed(), std::move(wots_priv_seed), std::move(prf))) {
277 m_private->set_unused_leaf_index(idx_leaf);
278}
279
280bool XMSS_PrivateKey::check_key(RandomNumberGenerator& /*rng*/, bool strong) const {
281 if(strong) {
282 // Check that the stored root is consistent with the seeds by
283 // recomputing it. This costs about as much as a key generation.
284 const XMSS_Address adrs;
286 return tree_hash(0, xmss_parameters().tree_height(), adrs, hash) == root();
287 }
288 return true;
289}
290
291secure_vector<uint8_t> XMSS_PrivateKey::tree_hash(size_t start_idx,
292 size_t target_node_height,
293 const XMSS_Address& adrs,
294 XMSS_Hash& hash) const {
295 return XMSS_Tree_Builder(
296 xmss_parameters().wots_parameters(), wots_derivation_method(), public_seed(), m_private->private_seed())
297 .tree_hash(start_idx, target_node_height, adrs, hash);
298}
299
300XMSS_WOTS_PrivateKey XMSS_PrivateKey::wots_private_key_for(const XMSS_Address& adrs, XMSS_Hash& hash) const {
301 return XMSS_Tree_Builder(
302 xmss_parameters().wots_parameters(), wots_derivation_method(), public_seed(), m_private->private_seed())
303 .wots_private_key_for(adrs, hash);
304}
305
309
310size_t XMSS_PrivateKey::reserve_unused_leaf_index() {
311 return m_private->reserve_unused_leaf_index();
312}
313
315 return m_private->unused_leaf_index();
316}
317
319 return checked_cast_to<size_t>(m_private->remaining_signatures());
320}
321
322std::optional<uint64_t> XMSS_PrivateKey::remaining_operations() const {
323 return m_private->remaining_signatures();
324}
325
326const secure_vector<uint8_t>& XMSS_PrivateKey::prf_value() const {
327 return m_private->prf_value();
328}
329
331 return m_private->serialize(raw_public_key());
332}
333
335 return m_private->wots_derivation_method();
336}
337
338std::unique_ptr<Public_Key> XMSS_PrivateKey::public_key() const {
339 return std::make_unique<XMSS_PublicKey>(xmss_parameters().oid(), root(), public_seed());
340}
341
342std::unique_ptr<PK_Ops::Signature> XMSS_PrivateKey::_create_signature_op(
343 RandomNumberGenerator& rng, const PK_Signature_Options_Reader& options) const {
344 BOTAN_UNUSED(rng);
345
346 validate_for_hash_based_signature(options, "XMSS", xmss_parameters().hash_function_name());
348
350
351 return std::make_unique<XMSS_Signature_Operation>(*this);
352}
353
354} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:151
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
static Limits DER()
Definition ber_dec.h:44
BER_Decoder & decode(bool &out)
Definition ber_dec.h:361
BER_Decoder & verify_end()
Definition ber_dec.cpp:471
secure_vector< uint8_t > get_contents()
Definition der_enc.cpp:161
DER_Encoder & encode(bool b)
Definition der_enc.cpp:313
uint64_t remaining_operations(const KeyId &key_id)
std::optional< uint64_t > reserve_next_index(const KeyId &key_id)
void set_index_lower_bound(const KeyId &key_id, uint64_t min)
static Stateful_Key_Index_Registry & global()
static XMSS_Parameters from_id(xmss_algorithm_t id)
std::unique_ptr< Public_Key > public_key() const override
std::unique_ptr< PK_Ops::Signature > _create_signature_op(RandomNumberGenerator &rng, const PK_Signature_Options_Reader &options) const override
size_t remaining_signatures() const
size_t unused_leaf_index() const
bool check_key(RandomNumberGenerator &rng, bool strong) const override
std::optional< uint64_t > remaining_operations() const override
Retrieves the number of remaining operations if this is a stateful private key.
WOTS_Derivation_Method wots_derivation_method() const
secure_vector< uint8_t > raw_private_key() const
secure_vector< uint8_t > private_key_bits() const override
XMSS_PrivateKey(XMSS_Parameters::xmss_algorithm_t xmss_algo_id, RandomNumberGenerator &rng, WOTS_Derivation_Method wots_derivation_method=WOTS_Derivation_Method::NIST_SP800_208)
const secure_vector< uint8_t > & root() const
const secure_vector< uint8_t > & public_seed() const
const XMSS_Parameters & xmss_parameters() const
std::vector< uint8_t > raw_public_key() const
std::string algo_name() const override
Definition xmss.h:81
XMSS_PublicKey(XMSS_Parameters::xmss_algorithm_t xmss_oid, RandomNumberGenerator &rng)
secure_vector< uint8_t > tree_hash(size_t start_idx, size_t target_node_height, const XMSS_Address &adrs, XMSS_Hash &hash) const
Gf448Elem root(const Gf448Elem &elem)
Compute the root of elem in the field.
void acknowledge_always_deterministic(const PK_Signature_Options_Reader &options)
constexpr RT checked_cast_to(AT i)
Definition int_utils.h:104
void require_software_provider(const OptionsT &options, std::string_view algo_name)
void validate_for_hash_based_signature(const PK_Signature_Options_Reader &options, std::string_view algo_name, std::string_view hash_fn)
constexpr auto concat(Rs &&... ranges)
Definition concat_util.h:95
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745
WOTS_Derivation_Method
Definition xmss.h:151
constexpr auto load_be(ParamTs &&... params)
Definition loadstor.h:504