Botan 3.14.1
Crypto and TLS for C&
sp_treehash.cpp
Go to the documentation of this file.
1/*
2* SLH-DSA treehash 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_treehash.h>
10
11#include <botan/internal/buffer_slicer.h>
12#include <botan/internal/sp_address.h>
13#include <botan/internal/sp_hash.h>
14
15namespace Botan {
16
19 const Sphincs_Parameters& params,
21 std::optional<TreeNodeIndex> leaf_idx,
22 uint32_t idx_offset,
23 uint32_t total_tree_height,
24 const GenerateLeavesFunction& gen_leaves,
25 Sphincs_Address& tree_address) {
26 BOTAN_ASSERT_NOMSG(out_root.size() == params.n());
27 BOTAN_ASSERT_NOMSG(out_auth_path.size() == params.n() * total_tree_height);
28 BOTAN_ASSERT_NOMSG(total_tree_height < 32);
29
30 const TreeNodeIndex max_idx((uint32_t(1) << total_tree_height) - 1);
31 // Not has_value() || value(), which GCC may compile to test the payload first
32 BOTAN_ASSERT_NOMSG(leaf_idx.value_or(TreeNodeIndex(0)) <= max_idx);
33
34 std::vector<uint8_t> stack(total_tree_height * params.n());
35
36 // Leaves are created in batches to enable batched hashing. Both the batch
37 // size and the leaf count are powers of two, so batches are always full.
38 const uint32_t leaves_per_batch = std::min<uint32_t>(uint32_t(1) << total_tree_height, 128);
39 std::vector<uint8_t> leaves(leaves_per_batch * params.n());
40
41 /* Traverse the tree from the left-most leaf, matching siblings and up until
42 * the root (Post-order traversal). Collect the adjacent nodes (A) to build
43 * the authentication path (X) along the way.
44 *
45 * 7R
46 * / \
47 * 3X 6A
48 * / \ / \
49 * 1X 2A 4 5
50 */
51 for(TreeNodeIndex idx(0); true; ++idx) {
52 const uint32_t batch_pos = idx.get() % leaves_per_batch;
53 if(batch_pos == 0) {
54 gen_leaves(leaves, idx + idx_offset, leaves_per_batch);
55 }
56 // Current logical node, evolved in place as siblings are combined
57 const auto current_node = std::span(leaves).subspan(batch_pos * params.n(), params.n());
58
59 // Now combine the freshly generated right node with previously generated
60 // left ones
61 uint32_t internal_idx_offset = idx_offset;
62 TreeNodeIndex internal_idx = idx;
63 auto internal_leaf = leaf_idx;
64
65 for(TreeLayerIndex h(0); true; ++h) {
66 // Check if we hit the top of the tree
67 if(h.get() == total_tree_height) {
68 copy_mem(out_root, current_node);
69 return;
70 }
71
72 // Check if the node we have is a part of the authentication path; if
73 // it is, write it out. The XOR sum of both nodes (at internal_idx and internal_leaf)
74 // is 1 iff they have the same parent node in the FORS tree
75 if(internal_leaf.has_value() && (internal_idx ^ internal_leaf.value()) == 0x01U) {
76 const auto auth_path_location = out_auth_path.get().subspan(h.get() * params.n(), params.n());
77 copy_mem(auth_path_location, current_node);
78 }
79
80 // At this point we know that we'll need to use the stack. Get a
81 // reference to the correct location.
82 const auto stack_location = std::span(stack).subspan(h.get() * params.n(), params.n());
83
84 // Check if we're at a left child; if so, stop going up the stack
85 // Exception: if we've reached the end of the tree, keep on going (so
86 // we combine the last 4 nodes into the one root node in two more
87 // iterations)
88 if((internal_idx & 1) == 0U && idx < max_idx) {
89 // We've hit a left child; save the current for when we get the
90 // corresponding right child.
91 copy_mem(stack_location, current_node);
92 break;
93 }
94
95 // Ok, we're at a right node. Now combine the left and right logical
96 // nodes together.
97
98 // Set the address of the node we're creating.
99 internal_idx_offset /= 2;
100 tree_address.set_tree_height(h + 1);
101 tree_address.set_tree_index(internal_idx / 2 + internal_idx_offset);
102
103 hashes.T(current_node, tree_address, stack_location, current_node);
104
105 internal_idx /= 2;
106 if(internal_leaf.has_value()) {
107 internal_leaf.value() /= 2;
108 }
109 }
110 }
111}
112
114 const Sphincs_Parameters& params,
116 const SphincsTreeNode& leaf,
117 TreeNodeIndex leaf_idx,
118 uint32_t idx_offset,
120 uint32_t total_tree_height,
121 Sphincs_Address& tree_address) {
122 BOTAN_ASSERT_NOMSG(out.size() == params.n());
123 BOTAN_ASSERT_NOMSG(authentication_path.size() == params.n() * total_tree_height);
124 BOTAN_ASSERT_NOMSG(leaf.size() == params.n());
125
126 // Use the `out` parameter as intermediate buffer for left/right nodes
127 // while traversing the tree.
128 copy_mem(out, leaf);
129
130 // Views into either `auth_path` or `out` depending on the tree location.
133
134 BufferSlicer auth_path(authentication_path);
135
136 // The leaf is put in the left or right buffer, depending on its indexes parity.
137 // Same for the first node of the authentication path
138
139 for(TreeLayerIndex i(0); i < total_tree_height; i++) {
140 // The input of the hash function takes the current node and the node
141 // given in the authentication path. If the current node is a right node
142 // in the tree (i.e. its leaf index is uneven) the hash function inputs
143 // must be swapped.
144 left = out;
145 right = auth_path.take<SphincsTreeNode>(params.n());
146
147 if((leaf_idx & 1) == 1U) {
148 std::swap(left, right);
149 }
150
151 leaf_idx /= 2;
152 idx_offset /= 2;
153 tree_address.set_tree_height(i + 1).set_tree_index(leaf_idx + idx_offset);
154
155 hashes.T(out, tree_address, left, right);
156 }
157
158 BOTAN_ASSERT_NOMSG(auth_path.empty());
159}
160
161} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
std::span< const uint8_t > take(const size_t count)
Sphincs_Address & set_tree_height(TreeLayerIndex tree_height)
Definition sp_address.h:86
Sphincs_Address & set_tree_index(TreeNodeIndex tree_index)
Definition sp_address.h:96
void T(std::span< uint8_t > out, const Sphincs_Address &address, const BufferTs &... in)
Definition sp_hash.h:59
underlying_span get() const
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
size_type size() const noexcept(noexcept(this->get().size()))
Strong< std::vector< uint8_t >, struct SphincsTreeNode_ > SphincsTreeNode
Either an XMSS or FORS tree node or leaf.
Definition sp_types.h:70
std::function< void(std::span< uint8_t >, TreeNodeIndex, uint32_t)> GenerateLeavesFunction
Definition sp_treehash.h:30
void treehash(StrongSpan< SphincsTreeNode > out_root, StrongSpan< SphincsAuthenticationPath > out_auth_path, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes, std::optional< TreeNodeIndex > leaf_idx, uint32_t idx_offset, uint32_t total_tree_height, const GenerateLeavesFunction &gen_leaves, Sphincs_Address &tree_address)
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
Strong< uint32_t, struct TreeNodeIndex_, EnableArithmeticWithPlainNumber > TreeNodeIndex
Index of an individual node inside an XMSS or FORS tree.
Definition sp_types.h:92
Strong< uint32_t, struct TreeLayerIndex_, EnableArithmeticWithPlainNumber > TreeLayerIndex
Index of the layer within a FORS/XMSS tree.
Definition sp_types.h:83
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)