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