Botan 3.5.0
Crypto and TLS for C&
sp_hypertree.cpp
Go to the documentation of this file.
1/*
2* Sphincs+ hypertree logic
3* (C) 2023 Jack Lloyd
4* 2023 Fabian Albert, René Meusel, Amos Treiber - Rohde & Schwarz Cybersecurity
5*
6* Botan is released under the Simplified BSD License (see license.txt)
7**/
8
9#include <botan/internal/sp_hypertree.h>
10
11#include <botan/sp_parameters.h>
12#include <botan/internal/sp_address.h>
13#include <botan/internal/sp_hash.h>
14#include <botan/internal/sp_treehash.h>
15#include <botan/internal/sp_wots.h>
16#include <botan/internal/sp_xmss.h>
17#include <botan/internal/stl_util.h>
18
19namespace Botan {
20
22 const SphincsTreeNode& message_to_sign,
23 const SphincsSecretSeed& secret_seed,
24 XmssTreeIndexInLayer tree_index_in_layer,
25 TreeNodeIndex idx_leaf,
26 const Sphincs_Parameters& params,
27 Sphincs_Hash_Functions& hashes) {
28 BOTAN_ASSERT_NOMSG(out_sig.size() == params.ht_signature_bytes());
29 BufferStuffer ht_signature(out_sig);
30
32 wots_addr.set_tree(tree_index_in_layer).set_keypair(idx_leaf);
33
35
36 SphincsTreeNode xmss_root;
37 for(HypertreeLayerIndex layer_idx(0); layer_idx < params.d(); layer_idx++) {
38 // The first XMSS tree signs the message, the others their underlying XMSS tree root
39 const SphincsTreeNode& node_to_xmss_sign = (layer_idx == 0U) ? message_to_sign : xmss_root;
40
41 tree_addr.set_layer(layer_idx).set_tree(tree_index_in_layer);
42 wots_addr.copy_subtree_from(tree_addr).set_keypair(idx_leaf);
43
44 xmss_root = xmss_sign_and_pkgen(ht_signature.next<SphincsXmssSignature>(params.xmss_signature_bytes()),
45 node_to_xmss_sign,
46 secret_seed,
47 wots_addr,
48 tree_addr,
49 idx_leaf,
50 params,
51 hashes);
52
53 // Update the indices for the next layer.
54 idx_leaf = TreeNodeIndex(tree_index_in_layer.get() & ((1 << params.xmss_tree_height()) - 1));
55 tree_index_in_layer = tree_index_in_layer >> params.xmss_tree_height();
56 }
57
58 BOTAN_ASSERT_NOMSG(ht_signature.full());
59}
60
61bool ht_verify(const SphincsTreeNode& signed_msg,
63 const SphincsTreeNode& pk_root,
64 XmssTreeIndexInLayer tree_index_in_layer,
65 TreeNodeIndex idx_leaf,
66 const Sphincs_Parameters& params,
67 Sphincs_Hash_Functions& hashes) {
68 BOTAN_ASSERT_NOMSG(ht_sig.size() == params.ht_signature_bytes());
69 BufferSlicer sig_s(ht_sig);
70
74
75 SphincsTreeNode reconstructed_root(params.n());
76
77 // Each iteration reconstructs the root of one XMSS tree of the hypertree
78 for(HypertreeLayerIndex layer_idx(0); layer_idx < params.d(); layer_idx++) {
79 // The first XMSS tree signs the message, the others their underlying XMSS tree root
80 const SphincsTreeNode& current_root = (layer_idx == 0U) ? signed_msg : reconstructed_root;
81
82 tree_addr.set_layer(layer_idx);
83 tree_addr.set_tree(tree_index_in_layer);
84
85 wots_addr.copy_subtree_from(tree_addr);
86 wots_addr.set_keypair(idx_leaf);
87
88 wots_pk_addr.copy_keypair_from(wots_addr);
89
90 const auto wots_pk = wots_public_key_from_signature(
91 current_root, sig_s.take<WotsSignature>(params.wots_bytes()), wots_addr, params, hashes);
92
93 // Compute the leaf node using the WOTS public key.
94 const auto leaf = hashes.T<SphincsTreeNode>(wots_pk_addr, wots_pk);
95
96 // Compute the root node of this subtree.
97 compute_root(StrongSpan<SphincsTreeNode>(reconstructed_root),
98 params,
99 hashes,
100 leaf,
101 idx_leaf,
102 0,
103 sig_s.take<SphincsAuthenticationPath>(params.xmss_tree_height() * params.n()),
104 params.xmss_tree_height(),
105 tree_addr);
106
107 // Update the indices for the next layer.
108 idx_leaf = TreeNodeIndex(tree_index_in_layer.get() & ((1 << params.xmss_tree_height()) - 1));
109 tree_index_in_layer = tree_index_in_layer >> params.xmss_tree_height();
110 }
111
112 BOTAN_ASSERT_NOMSG(sig_s.empty());
113
114 // Check if the root node equals the root node in the public key.
115 return reconstructed_root == pk_root;
116}
117
118} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
bool empty() const
Definition stl_util.h:129
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 std::span< uint8_t > next(size_t bytes)
Definition stl_util.h:150
constexpr bool full() const
Definition stl_util.h:187
Sphincs_Address & copy_subtree_from(const Sphincs_Address &other)
Definition sp_address.h:101
Sphincs_Address & set_layer(HypertreeLayerIndex layer)
Definition sp_address.h:55
Sphincs_Address & set_keypair(TreeNodeIndex keypair)
Definition sp_address.h:74
Sphincs_Address & copy_keypair_from(const Sphincs_Address other)
Definition sp_address.h:116
Sphincs_Address & set_tree(XmssTreeIndexInLayer tree)
Definition sp_address.h:60
void T(std::span< uint8_t > out, const Sphincs_Address &address, BufferTs &&... in)
Definition sp_hash.h:56
uint32_t wots_bytes() const
uint32_t xmss_tree_height() const
uint32_t ht_signature_bytes() const
uint32_t xmss_signature_bytes() const
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
SphincsTreeNode xmss_sign_and_pkgen(StrongSpan< SphincsXmssSignature > out_sig, const SphincsTreeNode &root, const SphincsSecretSeed &secret_seed, Sphincs_Address &wots_addr, Sphincs_Address &tree_addr, std::optional< TreeNodeIndex > idx_leaf, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes)
Definition sp_xmss.cpp:19
WotsPublicKey wots_public_key_from_signature(const SphincsTreeNode &hashed_message, StrongSpan< const WotsSignature > signature, Sphincs_Address &address, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes)
Definition sp_wots.cpp:97
void ht_sign(StrongSpan< SphincsHypertreeSignature > out_sig, const SphincsTreeNode &message_to_sign, const SphincsSecretSeed &secret_seed, XmssTreeIndexInLayer tree_index_in_layer, TreeNodeIndex idx_leaf, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes)
bool ht_verify(const SphincsTreeNode &signed_msg, StrongSpan< const SphincsHypertreeSignature > ht_sig, const SphincsTreeNode &pk_root, XmssTreeIndexInLayer tree_index_in_layer, TreeNodeIndex idx_leaf, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes)
Strong< uint32_t, struct TreeNodeIndex_, EnableArithmeticWithPlainNumber > TreeNodeIndex
Index of an individual node inside an XMSS or FORS tree.
Definition sp_types.h:78
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)