Botan 3.14.1
Crypto and TLS for C&
hash_engine_mdx.h
Go to the documentation of this file.
1/*
2* (C) 2026 Jack Lloyd
3*
4* Botan is released under the Simplified BSD License (see license.txt)
5*/
6
7#ifndef BOTAN_HASH_ENGINE_MDX_H_
8#define BOTAN_HASH_ENGINE_MDX_H_
9
10#include <botan/assert.h>
11#include <botan/mem_ops.h>
12#include <botan/internal/hash_engine.h>
13#include <botan/internal/int_utils.h>
14#include <botan/internal/loadstor.h>
15#include <algorithm>
16#include <array>
17#include <concepts>
18
19namespace Botan {
20
21/**
22* Generic multi-buffer engine for big-endian Merkle-Damgard hashes
23*
24* The states buffer passed to the compression function holds the 8
25* chaining variables for each lane, as little-endian words in
26* variable-major order (all lanes of A, then all lanes of B, ...).
27* blocks[l] points to the first of nblocks contiguous blocks for lane l.
28*
29* The extract function transposes the states into digests, which holds
30* the full (untruncated) big-endian digest of each lane in lane order.
31*/
32template <std::unsigned_integral W>
33class MDx_MB_Engine final : public Hash_Engine {
34 public:
35 using compress_fn = void (*)(uint8_t* states, const uint8_t* const* blocks, size_t nblocks);
36 using extract_fn = void (*)(const uint8_t* states, uint8_t* digests);
37
38 MDx_MB_Engine(std::string_view name,
39 size_t output_length,
40 std::span<const uint8_t> common_prefix,
41 std::string_view provider,
42 size_t lanes,
43 size_t block_bytes,
44 size_t ctr_bytes,
45 std::span<const W> midstate,
46 compress_fn compress,
47 extract_fn extract) :
49 m_name(name),
50 m_provider(provider),
51 m_output_length(output_length),
52 m_lanes(lanes),
53 m_block_bytes(block_bytes),
54 m_ctr_bytes(ctr_bytes),
55 m_prefix_full_bytes(common_prefix.size() - common_prefix.size() % block_bytes),
56 m_compress(compress),
57 m_extract(extract),
58 m_initial_states(8 * lanes * sizeof(W)),
59 m_states(8 * lanes * sizeof(W)),
60 m_digests(8 * lanes * sizeof(W)),
61 m_ptrs(lanes) {
62 BOTAN_ASSERT_NOMSG(midstate.size() == 8);
63
64 for(size_t j = 0; j != 8; ++j) {
65 for(size_t l = 0; l != m_lanes; ++l) {
66 store_le(midstate[j], &m_initial_states[(j * m_lanes + l) * sizeof(W)]);
67 }
68 }
69 }
70
71 std::string name() const override { return m_name; }
72
73 std::string provider() const override { return m_provider; }
74
75 size_t output_length() const override { return m_output_length; }
76
77 size_t parallelism() const override { return m_lanes; }
78
79 size_t uncached_prefix_bytes() const override { return common_prefix().size() - m_prefix_full_bytes; }
80
81 void batch_hash(std::span<std::span<uint8_t>> outputs,
82 std::span<std::span<const uint8_t>> inputs1,
83 std::span<std::span<const uint8_t>> inputs2) override {
84 check_batch_args(outputs, inputs1, inputs2);
85
86 const size_t count = inputs1.size();
87 if(count == 0) {
88 return;
89 }
90
91 // The logical stream hashed for lane i is
92 // rem || inputs1[i] || inputs2[i] || padding
93 // where rem is the part of the prefix not covered by the midstate
94 const auto rem = common_prefix().subspan(m_prefix_full_bytes);
95 const size_t r = rem.size();
96 const size_t len1 = inputs1[0].size();
97 const size_t len2 = inputs2.empty() ? 0 : inputs2[0].size();
98
99 // Checked so that the padded length and the offsets derived from
100 // it cannot wrap for huge inputs, which matters on 32-bit targets
101 const auto padded_end = checked_add(r, len1, len2, 1 + m_ctr_bytes + (m_block_bytes - 1));
102 BOTAN_ARG_CHECK(padded_end.has_value(), "Hash_Engine::batch_hash inputs too long");
103
104 const size_t stream_len = r + len1 + len2;
105 const size_t blocks = *padded_end / m_block_bytes;
106 const size_t padded_len = m_block_bytes * blocks;
107 const uint64_t total_bits = 8 * static_cast<uint64_t>(common_prefix().size() + len1 + len2);
108
109 // Ranges of blocks lying entirely within one input are hashed
110 // directly from the caller's buffers. All other blocks are
111 // assembled in scratch, each in its own slot, since everything
112 // in them except the input bytes is the same for every lane.
113 const size_t d1_lo = (r + m_block_bytes - 1) / m_block_bytes;
114 const size_t d1_hi = (r + len1) / m_block_bytes;
115 const size_t d2_lo = (r + len1 + m_block_bytes - 1) / m_block_bytes;
116 const size_t d2_hi = (r + len1 + len2) / m_block_bytes;
117
118 std::array<Step, MAX_STEPS> steps{};
119 size_t nsteps = 0;
120 size_t scratch_blocks = 0;
121
122 for(size_t b = 0; b < blocks;) {
123 BOTAN_ASSERT_NOMSG(nsteps < MAX_STEPS);
124 Step& step = steps[nsteps++];
125
126 if(b >= d1_lo && b < d1_hi) {
127 step = Step{Step::Kind::Direct1, b, d1_hi, 0};
128 } else if(b >= d2_lo && b < d2_hi) {
129 step = Step{Step::Kind::Direct2, b, d2_hi, 0};
130 } else {
131 size_t e = blocks;
132 if(b < d1_lo && d1_lo < d1_hi) {
133 e = std::min(e, d1_lo);
134 }
135 if(b < d2_lo && d2_lo < d2_hi) {
136 e = std::min(e, d2_lo);
137 }
138 step = Step{Step::Kind::Scratch, b, e, scratch_blocks};
139 scratch_blocks += e - b;
140 }
141
142 b = step.hi;
143 }
144
145 const size_t lane_stride = scratch_blocks * m_block_bytes;
146 if(m_scratch.size() < m_lanes * lane_stride) {
147 m_scratch.resize(m_lanes * lane_stride);
148 }
149 const auto scratch = [&](size_t lane, const Step& step) {
150 return &m_scratch[lane * lane_stride + step.slot * m_block_bytes];
151 };
152
153 // Write the lane invariant parts of the scratch blocks: the
154 // prefix remainder, the padding byte, zeros and the counter
155 for(size_t i = 0; i != nsteps; ++i) {
156 const Step& step = steps[i];
157 if(step.kind != Step::Kind::Scratch) {
158 continue;
159 }
160 const size_t lo = step.lo * m_block_bytes;
161 const size_t hi = step.hi * m_block_bytes;
162
163 for(size_t l = 0; l != m_lanes; ++l) {
164 uint8_t* dest = scratch(l, step);
165 clear_mem(dest, hi - lo);
166 copy_overlap(dest, lo, hi, rem, 0);
167 if(stream_len >= lo && stream_len < hi) {
168 dest[stream_len - lo] = 0x80;
169 }
170 // Low 8 bytes of the counter; any high bytes stay zero
171 if(hi == padded_len) {
172 store_be(total_bits, dest + (padded_len - 8 - lo));
173 }
174 }
175 }
176
177 for(size_t base = 0; base < count; base += m_lanes) {
178 // Excess lanes of the last batch just recompute the final message
179 const auto lane_idx = [&](size_t l) { return std::min(base + l, count - 1); };
180
181 copy_mem(m_states, m_initial_states);
182
183 for(size_t i = 0; i != nsteps; ++i) {
184 const Step& step = steps[i];
185 const size_t lo = step.lo * m_block_bytes;
186 const size_t hi = step.hi * m_block_bytes;
187
188 if(step.kind == Step::Kind::Direct1) {
189 for(size_t l = 0; l != m_lanes; ++l) {
190 m_ptrs[l] = inputs1[lane_idx(l)].data() + (lo - r);
191 }
192 } else if(step.kind == Step::Kind::Direct2) {
193 for(size_t l = 0; l != m_lanes; ++l) {
194 m_ptrs[l] = inputs2[lane_idx(l)].data() + (lo - r - len1);
195 }
196 } else {
197 for(size_t l = 0; l != m_lanes; ++l) {
198 uint8_t* dest = scratch(l, step);
199 copy_overlap(dest, lo, hi, inputs1[lane_idx(l)], r);
200 if(!inputs2.empty()) {
201 copy_overlap(dest, lo, hi, inputs2[lane_idx(l)], r + len1);
202 }
203 m_ptrs[l] = dest;
204 }
205 }
206
207 m_compress(m_states.data(), m_ptrs.data(), step.hi - step.lo);
208 }
209
210 m_extract(m_states.data(), m_digests.data());
211
212 const size_t used_lanes = std::min(m_lanes, count - base);
213 for(size_t l = 0; l != used_lanes; ++l) {
214 copy_mem(outputs[base + l].first(m_output_length),
215 std::span(m_digests).subspan(l * DIGEST_BYTES, m_output_length));
216 }
217 }
218 }
219
220 private:
221 static constexpr size_t DIGEST_BYTES = 8 * sizeof(W);
222
223 /**
224 * One range of blocks [lo, hi) of the padded stream, either hashed
225 * directly from the first or second input, or from scratch slot
226 * slot onwards
227 */
228 struct Step {
229 enum class Kind : uint8_t { Direct1, Direct2, Scratch };
230
231 Kind kind;
232 size_t lo;
233 size_t hi;
234 size_t slot;
235 };
236
237 // At most scratch, direct1, scratch, direct2, scratch
238 static constexpr size_t MAX_STEPS = 5;
239
240 /**
241 * Copy the part of src (which starts at offset in the stream) that
242 * lies within the stream bytes [lo, hi) to dest
243 */
244 static void copy_overlap(uint8_t* dest, size_t lo, size_t hi, std::span<const uint8_t> src, size_t offset) {
245 const size_t i0 = std::max(lo, offset);
246 const size_t i1 = std::min(hi, offset + src.size());
247 if(i0 < i1) {
248 copy_mem(dest + (i0 - lo), src.data() + (i0 - offset), i1 - i0);
249 }
250 }
251
252 std::string m_name;
253 std::string m_provider;
254 size_t m_output_length;
255 size_t m_lanes;
256 size_t m_block_bytes;
257 size_t m_ctr_bytes;
258 size_t m_prefix_full_bytes;
259 compress_fn m_compress;
260 extract_fn m_extract;
261 secure_vector<uint8_t> m_initial_states;
262 secure_vector<uint8_t> m_states;
263 secure_vector<uint8_t> m_digests;
264 secure_vector<uint8_t> m_scratch;
265 std::vector<const uint8_t*> m_ptrs;
266};
267
268} // namespace Botan
269
270#endif
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
void check_batch_args(std::span< std::span< uint8_t > > outputs, std::span< std::span< const uint8_t > > inputs1, std::span< std::span< const uint8_t > > inputs2) const
std::span< const uint8_t > common_prefix() const
Hash_Engine(const Hash_Engine &other)=delete
std::string name() const override
size_t uncached_prefix_bytes() const override
void(*)(const uint8_t *states, uint8_t *digests) extract_fn
MDx_MB_Engine(std::string_view name, size_t output_length, std::span< const uint8_t > common_prefix, std::string_view provider, size_t lanes, size_t block_bytes, size_t ctr_bytes, std::span< const W > midstate, compress_fn compress, extract_fn extract)
void(*)(uint8_t *states, const uint8_t *const *blocks, size_t nblocks) compress_fn
void batch_hash(std::span< std::span< uint8_t > > outputs, std::span< std::span< const uint8_t > > inputs1, std::span< std::span< const uint8_t > > inputs2) override
size_t output_length() const override
std::string provider() const override
size_t parallelism() const override
constexpr std::optional< T > checked_add(T a, T b)
Definition int_utils.h:19
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
constexpr auto store_be(ParamTs &&... params)
Definition loadstor.h:745
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118