Botan 3.5.0
Crypto and TLS for C&
sp_wots.cpp
Go to the documentation of this file.
1/*
2* WOTS+ - Winternitz One Time Signature+
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/internal/sp_hash.h>
12#include <botan/internal/stl_util.h>
13
14namespace Botan {
15namespace {
16
17/**
18 * Computes a WOTS+ hash chain for @p steps steps beginning with value
19 * @p wots_chain_key at index @p start.
20 */
21void gen_chain(StrongSpan<WotsPublicKeyNode> out,
22 StrongSpan<const WotsNode> wots_chain_key,
23 WotsHashIndex start,
24 uint8_t steps,
25 Sphincs_Address& addr,
26 Sphincs_Hash_Functions& hashes,
27 const Sphincs_Parameters& params) {
28 // Initialize out with the value at position 'start'.
29 std::copy(wots_chain_key.begin(), wots_chain_key.end(), out.begin());
30
31 // Iterate 'steps' calls to the hash function.
32 for(WotsHashIndex i = start; i < (start + steps) && i < params.w(); i++) {
33 addr.set_hash(i);
34 hashes.T(out, addr, out);
35 }
36}
37
38/**
39 * base_w algorithm as described in draft.
40 * Interprets an array of bytes as integers in base w.
41 * This only works when log_w is a divisor of 8.
42 */
43void base_w(std::span<WotsHashIndex> output, std::span<const uint8_t> input, const Sphincs_Parameters& params) {
44 BOTAN_ASSERT_NOMSG(output.size() <= 8 * input.size() / params.log_w());
45
46 size_t input_offset = 0;
47 uint8_t current_byte = 0;
48 uint32_t remaining_bits_in_current_byte = 0;
49
50 for(auto& out : output) {
51 if(remaining_bits_in_current_byte == 0) {
52 current_byte = input[input_offset];
53 ++input_offset;
54 remaining_bits_in_current_byte = 8;
55 }
56 remaining_bits_in_current_byte -= params.log_w();
57 out = WotsHashIndex((current_byte >> remaining_bits_in_current_byte) & (params.w() - 1));
58 }
59}
60
61/** Computes the WOTS+ checksum over a message (in base_w). */
62void wots_checksum(std::span<WotsHashIndex> output,
63 std::span<const WotsHashIndex> msg_base_w,
64 const Sphincs_Parameters& params) {
65 uint32_t csum = 0;
66
67 // Compute checksum.
68 for(auto wots_hash_index : msg_base_w) {
69 csum += params.w() - 1 - wots_hash_index.get();
70 }
71
72 // Convert checksum to base_w.
73 csum = csum << ((8 - ((params.wots_len_2() * params.log_w()) % 8)) % 8);
74
75 std::array<uint8_t, 4> csum_bytes;
76 store_be(csum, csum_bytes.data());
77
78 const size_t csum_bytes_size = params.wots_checksum_bytes();
79 BOTAN_ASSERT_NOMSG(csum_bytes.size() >= csum_bytes_size);
80 base_w(output, std::span(csum_bytes).last(csum_bytes_size), params);
81}
82
83} // namespace
84
85std::vector<WotsHashIndex> chain_lengths(const SphincsTreeNode& msg, const Sphincs_Parameters& params) {
86 std::vector<WotsHashIndex> result(params.wots_len_1() + params.wots_len_2());
87
88 auto msg_base_w = std::span(result).first(params.wots_len_1());
89 auto checksum_base_w = std::span(result).last(params.wots_len_2());
90
91 base_w(msg_base_w, msg.get(), params);
92 wots_checksum(checksum_base_w, msg_base_w, params);
93
94 return result;
95}
96
99 Sphincs_Address& address,
100 const Sphincs_Parameters& params,
101 Sphincs_Hash_Functions& hashes) {
102 const std::vector<WotsHashIndex> lengths = chain_lengths(hashed_message, params);
103 WotsPublicKey pk_buffer(params.wots_len() * params.n());
104 BufferSlicer sig(signature);
105 BufferStuffer pk(pk_buffer);
106
107 for(WotsChainIndex i(0); i < params.wots_len(); i++) {
108 address.set_chain(i);
109
110 // params.w() can be one of {4, 8, 256}
111 const WotsHashIndex start_index = lengths[i.get()];
112 const uint8_t steps_to_take = static_cast<uint8_t>(params.w() - 1) - start_index.get();
113
114 gen_chain(pk.next<WotsPublicKeyNode>(params.n()),
115 sig.take<WotsNode>(params.n()),
116 start_index,
117 steps_to_take,
118 address,
119 hashes,
120 params);
121 }
122
123 return pk_buffer;
124}
125
128 const SphincsSecretSeed& secret_seed,
129 TreeNodeIndex leaf_idx,
130 std::optional<TreeNodeIndex> sign_leaf_idx,
131 const std::vector<WotsHashIndex>& wots_steps,
132 Sphincs_Address& leaf_addr,
133 Sphincs_Address& pk_addr,
134 const Sphincs_Parameters& params,
135 Sphincs_Hash_Functions& hashes) {
136 // `wots_steps` are needed only if `sign_leaf_idx` is set
137 BOTAN_ASSERT_NOMSG(!sign_leaf_idx.has_value() || wots_steps.size() == params.wots_len());
139
140 secure_vector<uint8_t> wots_sig;
141 WotsPublicKey wots_pk_buffer(params.wots_bytes());
142
143 BufferStuffer wots_pk(wots_pk_buffer);
144 BufferStuffer sig(sig_out);
145
146 leaf_addr.set_keypair(leaf_idx);
147 pk_addr.set_keypair(leaf_idx);
148
149 for(WotsChainIndex i(0); i < params.wots_len(); i++) {
150 // If the current leaf is part of the signature wots_k stores the chain index
151 // of the value neccessary for the signature. Otherwise: nullopt (no signature)
152 const auto wots_k = [&]() -> std::optional<WotsHashIndex> {
153 if(sign_leaf_idx.has_value() && leaf_idx == sign_leaf_idx.value()) {
154 return wots_steps[i.get()];
155 } else {
156 return std::nullopt;
157 }
158 }();
159
160 // Start with the secret seed
161 leaf_addr.set_chain(i);
162 leaf_addr.set_hash(WotsHashIndex(0));
164
165 auto buffer_s = wots_pk.next<WotsNode>(params.n());
166
167 hashes.PRF(buffer_s, secret_seed, leaf_addr);
168
170
171 // Iterates down the WOTS chain
172 for(WotsHashIndex k(0);; k++) {
173 // Check if this is the value that needs to be saved as a part of the WOTS signature
174 if(wots_k.has_value() && k == wots_k.value()) {
175 std::copy(buffer_s.begin(), buffer_s.end(), sig.next<WotsNode>(params.n()).begin());
176 }
177
178 // Check if the top of the chain was hit
179 if(k == params.w() - 1) {
180 break;
181 }
182
183 // Iterate one step on the chain
184 leaf_addr.set_hash(k);
185
186 hashes.T(buffer_s, leaf_addr, buffer_s);
187 }
188 }
189
190 // Do the final thash to generate the public keys
191 hashes.T(leaf_out, pk_addr, wots_pk_buffer);
192}
193
194} // 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
Sphincs_Address & set_chain(WotsChainIndex chain)
Definition sp_address.h:79
Sphincs_Address_Type get_type() const
Definition sp_address.h:132
Sphincs_Address & set_keypair(TreeNodeIndex keypair)
Definition sp_address.h:74
Sphincs_Address & set_hash(WotsHashIndex hash)
Definition sp_address.h:84
Sphincs_Address & set_type(Sphincs_Address_Type type)
Definition sp_address.h:67
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 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->get().begin()))
Definition strong_type.h:99
WotsPublicKey wots_public_key_from_signature(const SphincsTreeNode &hashed_message, StrongSpan< const WotsSignature > signature, Sphincs_Address &address, const Sphincs_Parameters &params, Sphincs_Hash_Functions &hashes)
Definition sp_wots.cpp:97
void wots_sign_and_pkgen(StrongSpan< WotsSignature > sig_out, StrongSpan< SphincsTreeNode > leaf_out, const SphincsSecretSeed &secret_seed, TreeNodeIndex leaf_idx, 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)
Definition sp_wots.cpp:126
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:84
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
std::vector< WotsHashIndex > chain_lengths(const SphincsTreeNode &msg, const Sphincs_Parameters &params)
Definition sp_wots.cpp:85
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:707