Botan 3.14.1
Crypto and TLS for C&
sp_fors.cpp
Go to the documentation of this file.
1/*
2 * FORS - Forest of Random Subsets (FIPS 205, Section 8)
3 * (C) 2023 Jack Lloyd
4 * 2023 Fabian Albert, René Meusel, Amos Treiber - Rohde & Schwarz Cybersecurity
5 *
6 * Parts of this file have been adapted from https://github.com/sphincs/sphincsplus
7 *
8 * Botan is released under the Simplified BSD License (see license.txt)
9 */
10
11#include <botan/internal/sp_fors.h>
12
13#include <botan/assert.h>
14#include <botan/sp_parameters.h>
15
16#include <botan/internal/buffer_slicer.h>
17#include <botan/internal/buffer_stuffer.h>
18#include <botan/internal/sp_address.h>
19#include <botan/internal/sp_hash.h>
20#include <botan/internal/sp_treehash.h>
21#include <botan/internal/sp_types.h>
22
23namespace Botan {
24
25namespace {
26
27/// FIPS 205, Algorithm 4: base_2^b(X,b,out_len) with b = a and out_len = k (for usage in FORS)
28std::vector<TreeNodeIndex> fors_message_to_indices(std::span<const uint8_t> message, const Sphincs_Parameters& params) {
29 BOTAN_ASSERT_NOMSG((message.size() * 8) >= (params.k() * params.a()));
30
31 std::vector<TreeNodeIndex> indices(params.k());
32
33 uint32_t offset = 0;
34
35 // This is one of the few places where the logic of SPHINCS+ round 3.1 and SLH-DSA differs
36 const auto update_idx = [&]() -> std::function<void(TreeNodeIndex&, uint32_t)> {
37#if defined(BOTAN_HAS_SLH_DSA_WITH_SHA2) || defined(BOTAN_HAS_SLH_DSA_WITH_SHAKE)
38 if(params.is_slh_dsa()) {
39 return [&](TreeNodeIndex& idx, uint32_t i) {
40 idx ^= (((message[offset >> 3] >> (~offset & 0x7)) & 0x1) << (params.a() - 1 - i));
41 };
42 }
43#endif
44#if defined(BOTAN_HAS_SPHINCS_PLUS_WITH_SHA2) || defined(BOTAN_HAS_SPHINCS_PLUS_WITH_SHAKE)
45 if(!params.is_slh_dsa()) {
46 return [&](TreeNodeIndex& idx, uint32_t i) { idx ^= (((message[offset >> 3] >> (offset & 0x7)) & 0x1) << i); };
47 }
48#endif
49 throw Internal_Error("Missing FORS index update logic for SPHINCS+ or SLH-DSA");
50 }();
51
52 for(auto& idx : indices) {
53 for(uint32_t i = 0; i < params.a(); ++i, ++offset) {
54 update_idx(idx, i);
55 }
56 }
57
58 return indices;
59}
60
61} // namespace
62
64 const SphincsHashedMessage& hashed_message,
65 const SphincsSecretSeed& secret_seed,
66 const Sphincs_Address& address,
67 const Sphincs_Parameters& params,
68 Sphincs_Hash_Functions& hashes) {
69 BOTAN_ASSERT_NOMSG(sig_out.size() == params.fors_signature_bytes());
70
71 const auto indices = fors_message_to_indices(hashed_message, params);
72
73 auto fors_tree_addr = Sphincs_Address::as_keypair_from(address);
74
75 const auto fors_pk_addr =
76 Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTreeRootsCompression);
77
78 std::vector<uint8_t> roots_buffer(params.k() * params.n());
79 BufferStuffer roots(roots_buffer);
80 BufferStuffer sig(sig_out);
81
82 // Scratch space for batched leaf generation, reused across subtrees
83 std::vector<Sphincs_Address> leaf_addrs;
84 secure_vector<uint8_t> leaf_secrets;
85 std::vector<std::span<uint8_t>> secret_spans;
86 std::vector<std::span<const uint8_t>> csecret_spans;
87 std::vector<std::span<uint8_t>> leaf_spans;
88
89 // Each leaf is the hash of a secret derived from the leaf's address
90 const GenerateLeavesFunction fors_gen_leaves = [&](std::span<uint8_t> out, TreeNodeIndex first_idx, uint32_t count) {
91 leaf_addrs.assign(count, fors_tree_addr);
92 leaf_secrets.resize(count * params.n());
93 secret_spans.resize(count);
94 csecret_spans.resize(count);
95 leaf_spans.resize(count);
96
97 for(uint32_t j = 0; j != count; ++j) {
98 leaf_addrs[j]
100 .set_tree_height(TreeLayerIndex(0))
101 .set_tree_index(first_idx + j);
102 secret_spans[j] = std::span(leaf_secrets).subspan(j * params.n(), params.n());
103 csecret_spans[j] = secret_spans[j];
104 leaf_spans[j] = out.subspan(j * params.n(), params.n());
105 }
106
107 hashes.PRF_batch(secret_spans, secret_seed, leaf_addrs);
108
109 for(uint32_t j = 0; j != count; ++j) {
110 leaf_addrs[j].set_type(Sphincs_Address_Type::ForsTree);
111 }
112
113 hashes.T_batch(leaf_spans, leaf_addrs, csecret_spans);
114 };
115
116 // For each of the k FORS subtrees: Compute the secret leaf, the authentication path
117 // and the trees' root and append the signature respectively
118 BOTAN_ASSERT_NOMSG(indices.size() == params.k());
119 for(uint32_t i = 0; i < params.k(); ++i) {
120 const uint32_t idx_offset = i * (1 << params.a());
121
122 // Compute the secret leaf given by the chunk of the message and append it to the signature
123 fors_tree_addr.set_type(Sphincs_Address_Type::ForsKeyGeneration)
124 .set_tree_height(TreeLayerIndex(0))
125 .set_tree_index(indices[i] + idx_offset);
126
127 hashes.PRF(sig.next<ForsLeafSecret>(params.n()), secret_seed, fors_tree_addr);
128
129 // Compute the authentication path and root for this leaf node
130 fors_tree_addr.set_type(Sphincs_Address_Type::ForsTree);
131
132 treehash(roots.next<SphincsTreeNode>(params.n()),
133 sig.next<SphincsAuthenticationPath>(params.a() * params.n()),
134 params,
135 hashes,
136 indices[i],
137 idx_offset,
138 params.a(),
139 fors_gen_leaves,
140 fors_tree_addr);
141 }
142
144 BOTAN_ASSERT_NOMSG(roots.full());
145
146 // Compute the public key by the hash of the concatenation of all roots
147 return hashes.T<SphincsTreeNode>(fors_pk_addr, roots_buffer);
148}
149
152 const Sphincs_Address& address,
153 const Sphincs_Parameters& params,
154 Sphincs_Hash_Functions& hashes) {
155 const auto indices = fors_message_to_indices(hashed_message, params);
156
157 auto fors_tree_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTree);
158
159 const auto fors_pk_addr =
160 Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTreeRootsCompression);
161
162 BufferSlicer s(signature);
163 std::vector<uint8_t> roots_buffer(params.k() * params.n());
164 BufferStuffer roots(roots_buffer);
165
166 // For each of the k FORS subtrees: Reconstruct the subtree's root node by using the
167 // leaf and the authentication path offered in the FORS signature.
168 BOTAN_ASSERT_NOMSG(indices.size() == params.k());
169 for(uint32_t i = 0; i < params.k(); ++i) {
170 const uint32_t idx_offset = i * (1 << params.a());
171
172 // Compute the FORS leaf by using the secret leaf contained in the signature
173 fors_tree_addr.set_tree_height(TreeLayerIndex(0)).set_tree_index(indices[i] + idx_offset);
174 const auto fors_leaf_secret = s.take<ForsLeafSecret>(params.n());
175 const auto auth_path = s.take<SphincsAuthenticationPath>(params.n() * params.a());
176 const auto leaf = hashes.T<SphincsTreeNode>(fors_tree_addr, fors_leaf_secret);
177
178 // Reconstruct the subtree's root using the authentication path
179 compute_root(roots.next<SphincsTreeNode>(params.n()),
180 params,
181 hashes,
182 leaf,
183 indices[i],
184 idx_offset,
185 auth_path,
186 params.a(),
187 fors_tree_addr);
188 }
189
190 BOTAN_ASSERT_NOMSG(roots.full());
191
192 // Reconstruct the public key the signature creates with the hash of the concatenation of all roots
193 // Only if the signature is valid, the pk is the correct FORS pk.
194 return hashes.T<SphincsTreeNode>(fors_pk_addr, roots_buffer);
195}
196
197} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
std::span< const uint8_t > take(const size_t count)
Helper class to ease in-place marshalling of concatenated fixed-length values.
constexpr std::span< uint8_t > next(size_t bytes)
constexpr bool full() const
Sphincs_Address & set_type(Sphincs_Address_Type type)
Definition sp_address.h:71
static Sphincs_Address as_keypair_from(const Sphincs_Address &other)
Definition sp_address.h:128
void T_batch(std::span< std::span< uint8_t > > outputs, std::span< const Sphincs_Address > addresses, std::span< std::span< const uint8_t > > inputs)
Definition sp_hash.cpp:32
void T(std::span< uint8_t > out, const Sphincs_Address &address, const BufferTs &... in)
Definition sp_hash.h:59
void PRF_batch(std::span< std::span< uint8_t > > outputs, const SphincsSecretSeed &sk_seed, std::span< const Sphincs_Address > addresses)
Definition sp_hash.cpp:56
void PRF(StrongSpan< ForsLeafSecret > out, const SphincsSecretSeed &sk_seed, const Sphincs_Address &address)
Definition sp_hash.h:72
uint32_t fors_signature_bytes() const
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
Strong< std::vector< uint8_t >, struct SphincsTreeNode_ > SphincsTreeNode
Either an XMSS or FORS tree node or leaf.
Definition sp_types.h:70
SphincsTreeNode fors_sign_and_pkgen(StrongSpan< ForsSignature > sig_out, const SphincsHashedMessage &hashed_message, const SphincsSecretSeed &secret_seed, const Sphincs_Address &address, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes)
FIPS 205, Algorithm 16: fors_sign (with simultaneous FORS pk generation).
Definition sp_fors.cpp:63
Strong< secure_vector< uint8_t >, struct ForsLeafSecret_ > ForsLeafSecret
Definition sp_types.h:71
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)
Strong< secure_vector< uint8_t >, struct SphincsSecretSeed_ > SphincsSecretSeed
Definition sp_types.h:61
Strong< std::vector< uint8_t >, struct SphincsHashedMessage_ > SphincsHashedMessage
Definition sp_types.h:59
Strong< uint32_t, struct TreeNodeIndex_, EnableArithmeticWithPlainNumber > TreeNodeIndex
Index of an individual node inside an XMSS or FORS tree.
Definition sp_types.h:92
SphincsTreeNode fors_public_key_from_signature(const SphincsHashedMessage &hashed_message, StrongSpan< const ForsSignature > signature, const Sphincs_Address &address, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes)
FIPS 205, Algorithm 17: fors_pkFromSig.
Definition sp_fors.cpp:150
Strong< std::vector< uint8_t >, struct SphincsAuthenticationPath_ > SphincsAuthenticationPath
Definition sp_types.h:67
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
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)