Botan 3.5.0
Crypto and TLS for C&
sp_fors.cpp
Go to the documentation of this file.
1/*
2 * FORS - Forest of Random Subsets
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_fors.h>
10
11#include <botan/assert.h>
12#include <botan/hash.h>
13#include <botan/sp_parameters.h>
14
15#include <botan/internal/sp_address.h>
16#include <botan/internal/sp_hash.h>
17#include <botan/internal/sp_treehash.h>
18#include <botan/internal/sp_types.h>
19#include <botan/internal/stl_util.h>
20
21#include <functional>
22#include <utility>
23
24namespace Botan {
25
26namespace {
27
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 for(auto& idx : indices) {
36 for(uint32_t i = 0; i < params.a(); ++i, ++offset) {
37 idx ^= (((message[offset >> 3] >> (offset & 0x7)) & 0x1) << i);
38 }
39 }
40
41 return indices;
42}
43
44} // namespace
45
47 const SphincsHashedMessage& hashed_message,
48 const SphincsSecretSeed& secret_seed,
49 const Sphincs_Address& address,
50 const Sphincs_Parameters& params,
51 Sphincs_Hash_Functions& hashes) {
52 BOTAN_ASSERT_NOMSG(sig_out.size() == params.fors_signature_bytes());
53
54 const auto indices = fors_message_to_indices(hashed_message, params);
55
56 auto fors_tree_addr = Sphincs_Address::as_keypair_from(address);
57
58 auto fors_pk_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTreeRootsCompression);
59
60 std::vector<uint8_t> roots_buffer(params.k() * params.n());
61 BufferStuffer roots(roots_buffer);
62 BufferStuffer sig(sig_out);
63
64 // Buffer to hold the FORS leafs during tree traversal
65 // (Avoids a secure_vector allocation/deallocation in the hot path)
66 ForsLeafSecret fors_leaf_secret(params.n());
67
68 // For each of the k FORS subtrees: Compute the secret leaf, the authentication path
69 // and the trees' root and append the signature respectively
70 BOTAN_ASSERT_NOMSG(indices.size() == params.k());
71 for(uint32_t i = 0; i < params.k(); ++i) {
72 uint32_t idx_offset = i * (1 << params.a());
73
74 // Compute the secret leaf given by the chunk of the message and append it to the signature
75 fors_tree_addr.set_tree_height(TreeLayerIndex(0))
76 .set_tree_index(indices[i] + idx_offset)
78
79 hashes.PRF(sig.next<ForsLeafSecret>(params.n()), secret_seed, fors_tree_addr);
80
81 // Compute the authentication path and root for this leaf node
82 fors_tree_addr.set_type(Sphincs_Address_Type::ForsTree);
83
84 GenerateLeafFunction fors_gen_leaf = [&](StrongSpan<SphincsTreeNode> out_root, TreeNodeIndex address_index) {
85 fors_tree_addr.set_tree_index(address_index);
86 fors_tree_addr.set_type(Sphincs_Address_Type::ForsKeyGeneration);
87
88 hashes.PRF(fors_leaf_secret, secret_seed, fors_tree_addr);
89
90 fors_tree_addr.set_type(Sphincs_Address_Type::ForsTree);
91 hashes.T(out_root, fors_tree_addr, fors_leaf_secret);
92 };
93
94 treehash(roots.next<SphincsTreeNode>(params.n()),
95 sig.next<SphincsAuthenticationPath>(params.a() * params.n()),
96 params,
97 hashes,
98 indices[i],
99 idx_offset,
100 params.a(),
101 fors_gen_leaf,
102 fors_tree_addr);
103 }
104
106 BOTAN_ASSERT_NOMSG(roots.full());
107
108 // Compute the public key by the hash of the concatenation of all roots
109 return hashes.T<SphincsTreeNode>(fors_pk_addr, roots_buffer);
110}
111
114 const Sphincs_Address& address,
115 const Sphincs_Parameters& params,
116 Sphincs_Hash_Functions& hashes) {
117 const auto indices = fors_message_to_indices(hashed_message, params);
118
119 auto fors_tree_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTree);
120
121 auto fors_pk_addr = Sphincs_Address::as_keypair_from(address).set_type(Sphincs_Address::ForsTreeRootsCompression);
122
123 BufferSlicer s(signature);
124 std::vector<uint8_t> roots_buffer(params.k() * params.n());
125 BufferStuffer roots(roots_buffer);
126
127 // For each of the k FORS subtrees: Reconstruct the subtree's root node by using the
128 // leaf and the authentication path offered in the FORS signature.
129 BOTAN_ASSERT_NOMSG(indices.size() == params.k());
130 for(uint32_t i = 0; i < params.k(); ++i) {
131 uint32_t idx_offset = i * (1 << params.a());
132
133 // Compute the FORS leaf by using the secret leaf contained in the signature
134 fors_tree_addr.set_tree_height(TreeLayerIndex(0)).set_tree_index(indices[i] + idx_offset);
135 auto fors_leaf_secret = s.take<ForsLeafSecret>(params.n());
136 auto auth_path = s.take<SphincsAuthenticationPath>(params.n() * params.a());
137 auto leaf = hashes.T<SphincsTreeNode>(fors_tree_addr, fors_leaf_secret);
138
139 // Reconstruct the subtree's root using the authentication path
140 compute_root(roots.next<SphincsTreeNode>(params.n()),
141 params,
142 hashes,
143 leaf,
144 indices[i],
145 idx_offset,
146 auth_path,
147 params.a(),
148 fors_tree_addr);
149 }
150
151 BOTAN_ASSERT_NOMSG(roots.full());
152
153 // Reconstruct the public key the signature creates with the hash of the concatenation of all roots
154 // Only if the signature is valid, the pk is the correct FORS pk.
155 return hashes.T<SphincsTreeNode>(fors_pk_addr, roots_buffer);
156}
157
158} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
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 & set_type(Sphincs_Address_Type type)
Definition sp_address.h:67
static Sphincs_Address as_keypair_from(const Sphincs_Address &other)
Definition sp_address.h:126
void T(std::span< uint8_t > out, const Sphincs_Address &address, BufferTs &&... in)
Definition sp_hash.h:56
void PRF(StrongSpan< ForsLeafSecret > out, const SphincsSecretSeed &sk_seed, const Sphincs_Address &address)
Definition sp_hash.h:69
uint32_t fors_signature_bytes() const
decltype(auto) size() const noexcept(noexcept(this->m_span.size()))
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)
Definition sp_fors.cpp:46
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)
Definition sp_fors.cpp:112
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
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)