Botan 3.14.1
Crypto and TLS for C&
sp_wots.cpp
Go to the documentation of this file.
1/*
2* WOTS+ - Winternitz One Time Signature Plus Scheme (FIPS 205, Section 5)
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_wots.h>
10
11#include <botan/mem_ops.h>
12#include <botan/internal/loadstor.h>
13#include <botan/internal/sp_hash.h>
14
15namespace Botan {
16namespace {
17
18/**
19 * FIPS 205, Algorithm 4: base_2^b for WOTS+
20 *
21 * Interprets an array of bytes as integers in base w = 2^b.
22 * This only works when lg_w is a divisor of 8.
23 */
24void base_2_b(std::span<WotsHashIndex> output, std::span<const uint8_t> input, const Sphincs_Parameters& params) {
25 BOTAN_ASSERT_NOMSG(output.size() <= 8 * input.size() / params.log_w());
26
27 size_t input_offset = 0;
28 uint8_t current_byte = 0;
29 uint32_t remaining_bits_in_current_byte = 0;
30
31 for(auto& out : output) {
32 if(remaining_bits_in_current_byte == 0) {
33 current_byte = input[input_offset];
34 ++input_offset;
35 remaining_bits_in_current_byte = 8;
36 }
37 remaining_bits_in_current_byte -= params.log_w();
38 out = WotsHashIndex((current_byte >> remaining_bits_in_current_byte) & (params.w() - 1));
39 }
40}
41
42/**
43 * Computes the WOTS+ checksum over a message (in base_2^b).
44 * Corresponds to FIPS 205, Algorithm 7 or 8, Step 7.
45 */
46void wots_checksum(std::span<WotsHashIndex> output,
47 std::span<const WotsHashIndex> msg_base_w,
48 const Sphincs_Parameters& params) {
49 uint32_t csum = 0;
50
51 // Compute checksum.
52 for(auto wots_hash_index : msg_base_w) {
53 csum += params.w() - 1 - wots_hash_index.get();
54 }
55
56 // Convert checksum to base_w.
57 csum = csum << ((8 - ((params.wots_len_2() * params.log_w()) % 8)) % 8);
58
59 std::array<uint8_t, 4> csum_bytes{};
60 store_be(csum, csum_bytes.data());
61
62 const size_t csum_bytes_size = params.wots_checksum_bytes();
63 BOTAN_ASSERT_NOMSG(csum_bytes.size() >= csum_bytes_size);
64 base_2_b(output, std::span(csum_bytes).last(csum_bytes_size), params);
65}
66
67} // namespace
68
69std::vector<WotsHashIndex> chain_lengths(const SphincsTreeNode& msg, const Sphincs_Parameters& params) {
70 std::vector<WotsHashIndex> result(params.wots_len_1() + params.wots_len_2());
71
72 const auto msg_base_w = std::span(result).first(params.wots_len_1());
73 const auto checksum_base_w = std::span(result).last(params.wots_len_2());
74
75 base_2_b(msg_base_w, msg.get(), params);
76 wots_checksum(checksum_base_w, msg_base_w, params);
77
78 return result;
79}
80
83 const Sphincs_Address& address,
84 const Sphincs_Parameters& params,
85 Sphincs_Hash_Functions& hashes) {
86 const std::vector<WotsHashIndex> lengths = chain_lengths(hashed_message, params);
87 const size_t len = params.wots_len();
88 const size_t n = params.n();
89
90 // The chains start with the nodes in the signature
91 WotsPublicKey pk_buffer(len * n);
92 std::copy(signature.begin(), signature.end(), pk_buffer.begin());
93 const std::span<uint8_t> pk_bytes(pk_buffer.get());
94
95 std::vector<Sphincs_Address> chain_addrs(len, address);
96 for(size_t i = 0; i != len; ++i) {
97 chain_addrs[i].set_chain_address(WotsChainIndex(static_cast<uint32_t>(i)));
98 }
99
100 std::vector<Sphincs_Address> addrs;
101 std::vector<std::span<uint8_t>> outs;
102 std::vector<std::span<const uint8_t>> ins;
103 addrs.reserve(len);
104 outs.reserve(len);
105 ins.reserve(len);
106
107 // Walk the chains in lock-step; chain i joins in once the step counter
108 // reaches its position in the signature
109 for(WotsHashIndex k(0); k < params.w() - 1; k++) {
110 addrs.clear();
111 outs.clear();
112 ins.clear();
113
114 for(size_t i = 0; i != len; ++i) {
115 if(lengths[i] <= k) {
116 chain_addrs[i].set_hash_address(k);
117 addrs.push_back(chain_addrs[i]);
118 const auto node = pk_bytes.subspan(i * n, n);
119 outs.push_back(node);
120 ins.push_back(node);
121 }
122 }
123
124 hashes.T_batch(outs, addrs, ins);
125 }
126
127 return pk_buffer;
128}
129
131 std::span<uint8_t> leaves_out,
132 const SphincsSecretSeed& secret_seed,
133 TreeNodeIndex first_leaf_idx,
134 size_t leaf_count,
135 std::optional<TreeNodeIndex> sign_leaf_idx,
136 const std::vector<WotsHashIndex>& wots_steps,
137 Sphincs_Address& leaf_addr,
138 Sphincs_Address& pk_addr,
139 const Sphincs_Parameters& params,
140 Sphincs_Hash_Functions& hashes) {
141 // `wots_steps` are needed only if `sign_leaf_idx` is set
142 BOTAN_ASSERT_NOMSG(!sign_leaf_idx.has_value() || wots_steps.size() == params.wots_len());
144 BOTAN_ASSERT_NOMSG(leaves_out.size() == leaf_count * params.n());
145
146 const size_t len = params.wots_len();
147 const size_t n = params.n();
148 const size_t lanes = leaf_count * len;
149
150 // WOTS public key buffers of all leaves, one lane per chain
151 secure_vector<uint8_t> pk_buffers(leaf_count * params.wots_bytes());
152
153 // The chains share their leaf's address except for their chain field
155 leaf_addr.set_hash_address(WotsHashIndex(0));
156
157 std::vector<Sphincs_Address> addrs;
158 addrs.reserve(lanes);
159 std::vector<std::span<uint8_t>> nodes(lanes);
160 std::vector<std::span<const uint8_t>> cnodes(lanes);
161 for(size_t j = 0; j != leaf_count; ++j) {
162 leaf_addr.set_keypair_address(first_leaf_idx + static_cast<uint32_t>(j));
163 for(size_t i = 0; i != len; ++i) {
164 addrs.push_back(leaf_addr);
165 addrs.back().set_chain_address(WotsChainIndex(static_cast<uint32_t>(i)));
166 const auto node = std::span(pk_buffers).subspan((j * len + i) * n, n);
167 nodes[j * len + i] = node;
168 cnodes[j * len + i] = node;
169 }
170 }
171
172 // Start each chain with its secret seed
173 hashes.PRF_batch(nodes, secret_seed, addrs);
174
175 for(auto& addr : addrs) {
176 addr.set_type(Sphincs_Address_Type::WotsHash);
177 }
178
179 const bool signing_in_batch = sign_leaf_idx.has_value() && sign_leaf_idx.value() >= first_leaf_idx &&
180 sign_leaf_idx.value() < first_leaf_idx + static_cast<uint32_t>(leaf_count);
181 const size_t sign_j = signing_in_batch ? static_cast<size_t>(sign_leaf_idx.value().get() - first_leaf_idx.get()) : 0;
182
183 // Iterate down all chains of all leaves in lock-step
184 for(WotsHashIndex k(0);; k++) {
185 // Check for values that need to be saved as a part of the WOTS signature
186 if(signing_in_batch) {
187 for(size_t i = 0; i != len; ++i) {
188 if(wots_steps[i] == k) {
189 copy_mem(sig_out.get().subspan(i * n, n), nodes[sign_j * len + i]);
190 }
191 }
192 }
193
194 // Check if the top of the chains was hit
195 if(k == params.w() - 1) {
196 break;
197 }
198
199 for(auto& addr : addrs) {
200 addr.set_hash_address(k);
201 }
202
203 hashes.T_batch(nodes, addrs, cnodes);
204 }
205
206 // Do the final thashes compressing each leaf's WOTS public key
207 std::vector<Sphincs_Address> pk_addrs;
208 pk_addrs.reserve(leaf_count);
209 std::vector<std::span<uint8_t>> leaf_outs(leaf_count);
210 std::vector<std::span<const uint8_t>> pk_spans(leaf_count);
211 for(size_t j = 0; j != leaf_count; ++j) {
212 pk_addr.set_keypair_address(first_leaf_idx + static_cast<uint32_t>(j));
213 pk_addrs.push_back(pk_addr);
214 leaf_outs[j] = leaves_out.subspan(j * n, n);
215 pk_spans[j] = std::span(pk_buffers).subspan(j * params.wots_bytes(), params.wots_bytes());
216 }
217 hashes.T_batch(leaf_outs, pk_addrs, pk_spans);
218}
219
220} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
Sphincs_Address_Type get_type() const
Definition sp_address.h:134
Sphincs_Address & set_hash_address(WotsHashIndex hash)
Definition sp_address.h:91
Sphincs_Address & set_keypair_address(TreeNodeIndex keypair)
Definition sp_address.h:76
Sphincs_Address & set_type(Sphincs_Address_Type type)
Definition sp_address.h:71
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 PRF_batch(std::span< std::span< uint8_t > > outputs, const SphincsSecretSeed &sk_seed, std::span< const Sphincs_Address > addresses)
Definition sp_hash.cpp:56
uint32_t wots_bytes() const
uint32_t wots_len_2() const
uint32_t wots_len_1() const
uint32_t wots_len() const
decltype(auto) begin() noexcept(noexcept(this->m_span.begin()))
underlying_span get() const
decltype(auto) end() noexcept(noexcept(this->m_span.end()))
decltype(auto) begin() noexcept(noexcept(this->get().begin()))
constexpr T & get() &
Definition strong_type.h:81
Strong< std::vector< uint8_t >, struct SphincsTreeNode_ > SphincsTreeNode
Either an XMSS or FORS tree node or leaf.
Definition sp_types.h:70
Strong< uint8_t, struct WotsHashIndex_, EnableArithmeticWithPlainNumber > WotsHashIndex
Index of a hash application inside a single WOTS chain (integers in "base_w").
Definition sp_types.h:98
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
WotsPublicKey wots_public_key_from_signature(const SphincsTreeNode &hashed_message, StrongSpan< const WotsSignature > signature, const Sphincs_Address &address, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes)
FIPS 205, Algorithm 8: wots_pkFromSig.
Definition sp_wots.cpp:81
Strong< std::vector< uint8_t >, struct WotsPublicKey_ > WotsPublicKey
Definition sp_types.h:73
Strong< uint32_t, struct WotsChainIndex_ > WotsChainIndex
Index of a WOTS chain within a single usage of WOTS.
Definition sp_types.h:95
Strong< secure_vector< uint8_t >, struct SphincsSecretSeed_ > SphincsSecretSeed
Definition sp_types.h:61
Strong< uint32_t, struct TreeNodeIndex_, EnableArithmeticWithPlainNumber > TreeNodeIndex
Index of an individual node inside an XMSS or FORS tree.
Definition sp_types.h:92
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
void wots_sign_and_pkgen(StrongSpan< WotsSignature > sig_out, std::span< uint8_t > leaves_out, const SphincsSecretSeed &secret_seed, TreeNodeIndex first_leaf_idx, size_t leaf_count, std::optional< TreeNodeIndex > sign_leaf_idx, const std::vector< WotsHashIndex > &wots_steps, Sphincs_Address &leaf_addr, Sphincs_Address &pk_addr, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes)
FIPS 205, Algorithm 6 and 7: wots_pkGen and wots_sign.
Definition sp_wots.cpp:130
std::vector< WotsHashIndex > chain_lengths(const SphincsTreeNode &msg, const Sphincs_Parameters &params)
Definition sp_wots.cpp:69
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745