Botan 3.14.1
Crypto and TLS for C&
hash_engine_keccak.cpp
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#include <botan/internal/hash_engine_keccak.h>
8
9#include <botan/assert.h>
10#include <botan/mem_ops.h>
11#include <botan/internal/algorithm_spec.h>
12#include <botan/internal/fmt.h>
13#include <botan/internal/int_utils.h>
14#include <botan/internal/loadstor.h>
15#include <algorithm>
16
17#if defined(BOTAN_HAS_HASH_ENGINE_KECCAK_AVX2) || defined(BOTAN_HAS_HASH_ENGINE_KECCAK_AVX512)
18 #define BOTAN_HASH_ENGINE_KECCAK_HAS_IMPL
19 #include <botan/internal/cpuid.h>
20#endif
21
22namespace Botan {
23
24#if defined(BOTAN_HASH_ENGINE_KECCAK_HAS_IMPL)
25
26namespace {
27
28class Keccak_MB_Engine final : public Hash_Engine {
29 public:
30 using permute_fn = void (*)(uint64_t* states);
31 using absorb_fn = void (*)(uint64_t* states, const uint8_t* const* blocks, size_t rate_words, size_t nblocks);
32
33 /// Number of rate blocks per fused absorb call, keeping the
34 /// state in registers across that many permutations
35 static constexpr size_t STRIP_BLOCKS = KECCAK_MB_ABSORB_BLOCKS;
36
37 Keccak_MB_Engine(std::string_view name,
38 size_t output_length,
39 size_t rate,
40 uint8_t suffix,
41 std::span<const uint8_t> common_prefix,
42 std::string_view provider,
43 size_t lanes,
44 permute_fn permute,
45 absorb_fn absorb) :
46 Hash_Engine(common_prefix),
47 m_name(name),
48 m_provider(provider),
49 m_output_length(output_length),
50 m_rate(rate),
51 m_suffix(suffix),
52 m_lanes(lanes),
53 m_permute(permute),
54 m_absorb(absorb),
55 m_prefix_full_bytes(common_prefix.size() - common_prefix.size() % rate),
56 m_midstate(25),
57 m_states(25 * lanes),
58 m_block_ptrs(STRIP_BLOCKS * lanes),
59 m_scratch(STRIP_BLOCKS * lanes * rate) {
60 // Absorb any full prefix blocks once, using lane 0 of the kernel
61 for(size_t block = 0; block != m_prefix_full_bytes / m_rate; ++block) {
62 for(size_t w = 0; w != m_rate / 8; ++w) {
63 m_states[w * m_lanes] ^= load_le<uint64_t>(common_prefix.data() + block * m_rate, w);
64 }
65 m_permute(m_states.data());
66 }
67 for(size_t w = 0; w != 25; ++w) {
68 m_midstate[w] = m_states[w * m_lanes];
69 }
70 }
71
72 std::string name() const override { return m_name; }
73
74 std::string provider() const override { return m_provider; }
75
76 size_t output_length() const override { return m_output_length; }
77
78 size_t parallelism() const override { return m_lanes; }
79
80 size_t uncached_prefix_bytes() const override { return common_prefix().size() - m_prefix_full_bytes; }
81
82 void batch_hash(std::span<std::span<uint8_t>> outputs,
83 std::span<std::span<const uint8_t>> inputs1,
84 std::span<std::span<const uint8_t>> inputs2) override {
85 check_batch_args(outputs, inputs1, inputs2);
86
87 const size_t count = inputs1.size();
88 if(count == 0) {
89 return;
90 }
91
92 // The logical stream absorbed for lane i is
93 // rem || inputs1[i] || inputs2[i] || padding
94 // where rem is the part of the prefix not covered by the midstate
95 const auto rem = common_prefix().subspan(m_prefix_full_bytes);
96 const size_t r = rem.size();
97 const size_t len1 = inputs1[0].size();
98 const size_t len2 = inputs2.empty() ? 0 : inputs2[0].size();
99
100 // Checked so that the padded length and the offsets derived from
101 // it cannot wrap for huge inputs, which matters on 32-bit targets
102 BOTAN_ARG_CHECK(checked_add(r, len1, len2, m_rate).has_value(), "Hash_Engine::batch_hash inputs too long");
103
104 const size_t stream_len = r + len1 + len2;
105 const size_t blocks = stream_len / m_rate + 1;
106
107 // Ranges of blocks lying entirely within one input, which are
108 // absorbed directly from the caller's buffers. All other blocks
109 // are assembled into scratch. The final block always contains
110 // padding and so is always assembled.
111 const size_t d1_lo = (r + m_rate - 1) / m_rate;
112 const size_t d1_hi = (r + len1) / m_rate;
113 const size_t d2_lo = (r + len1 + m_rate - 1) / m_rate;
114 const size_t d2_hi = (r + len1 + len2) / m_rate;
115
116 for(size_t base = 0; base < count; base += m_lanes) {
117 // Excess lanes of the last batch just recompute the final message
118 const auto lane_idx = [&](size_t l) { return std::min(base + l, count - 1); };
119
120 for(size_t w = 0; w != 25; ++w) {
121 for(size_t l = 0; l != m_lanes; ++l) {
122 m_states[w * m_lanes + l] = m_midstate[w];
123 }
124 }
125
126 for(size_t b0 = 0; b0 < blocks; b0 += STRIP_BLOCKS) {
127 const size_t strip = std::min(STRIP_BLOCKS, blocks - b0);
128
129 for(size_t bi = 0; bi != strip; ++bi) {
130 const size_t b = b0 + bi;
131
132 for(size_t l = 0; l != m_lanes; ++l) {
133 const size_t idx = lane_idx(l);
134
135 const uint8_t* src = nullptr;
136 if(b >= d1_lo && b < d1_hi) {
137 src = inputs1[idx].data() + (m_rate * b - r);
138 } else if(b >= d2_lo && b < d2_hi) {
139 src = inputs2[idx].data() + (m_rate * b - r - len1);
140 } else {
141 uint8_t* slot = &m_scratch[(bi * m_lanes + l) * m_rate];
142 const auto in2 = inputs2.empty() ? std::span<const uint8_t>() : inputs2[idx];
143 assemble(slot, m_rate * b, m_rate * (b + 1), rem, inputs1[idx], in2, stream_len);
144 src = slot;
145 }
146
147 m_block_ptrs[bi * m_lanes + l] = src;
148 }
149 }
150
151 m_absorb(m_states.data(), m_block_ptrs.data(), m_rate / 8, strip);
152 }
153
154 const size_t used_lanes = std::min(m_lanes, count - base);
155
156 size_t produced = 0;
157 while(true) {
158 const size_t take = std::min(m_rate, m_output_length - produced);
159 for(size_t l = 0; l != used_lanes; ++l) {
160 extract(outputs[base + l].subspan(produced, take), l);
161 }
162 produced += take;
163 if(produced == m_output_length) {
164 break;
165 }
166 m_permute(m_states.data());
167 }
168 }
169 }
170
171 private:
172 /**
173 * Assemble bytes [lo, hi) of the logical padded stream into dest
174 */
175 void assemble(uint8_t* dest,
176 size_t lo,
177 size_t hi,
178 std::span<const uint8_t> rem,
179 std::span<const uint8_t> in1,
180 std::span<const uint8_t> in2,
181 size_t stream_len) const {
182 clear_mem(dest, hi - lo);
183
184 copy_overlap(dest, lo, hi, rem, 0);
185 copy_overlap(dest, lo, hi, in1, rem.size());
186 copy_overlap(dest, lo, hi, in2, rem.size() + in1.size());
187
188 if(stream_len >= lo && stream_len < hi) {
189 dest[stream_len - lo] ^= m_suffix;
190 }
191
192 // The final padding bit lands in the last byte of the last block
193 if(hi == m_rate * (stream_len / m_rate + 1)) {
194 dest[hi - lo - 1] ^= 0x80;
195 }
196 }
197
198 static void copy_overlap(uint8_t* dest, size_t lo, size_t hi, std::span<const uint8_t> src, size_t offset) {
199 const size_t i0 = std::max(lo, offset);
200 const size_t i1 = std::min(hi, offset + src.size());
201 if(i0 < i1) {
202 copy_mem(dest + (i0 - lo), src.data() + (i0 - offset), i1 - i0);
203 }
204 }
205
206 void extract(std::span<uint8_t> out, size_t lane) const {
207 const size_t full_words = out.size() / 8;
208
209 for(size_t w = 0; w != full_words; ++w) {
210 store_le(m_states[w * m_lanes + lane], out.data() + 8 * w);
211 }
212
213 if(out.size() % 8 != 0) {
214 uint8_t last[8];
215 store_le(m_states[full_words * m_lanes + lane], last);
216 copy_mem(out.data() + 8 * full_words, last, out.size() % 8);
217 }
218 }
219
220 std::string m_name;
221 std::string m_provider;
222 size_t m_output_length;
223 size_t m_rate;
224 uint8_t m_suffix;
225 size_t m_lanes;
226 permute_fn m_permute;
227 absorb_fn m_absorb;
228 size_t m_prefix_full_bytes;
229 secure_vector<uint64_t> m_midstate;
230 secure_vector<uint64_t> m_states;
231 std::vector<const uint8_t*> m_block_ptrs;
232 secure_vector<uint8_t> m_scratch;
233};
234
235} // namespace
236
237#endif
238
239std::unique_ptr<Hash_Engine> create_keccak_mb_engine(std::string_view hash_fn,
240 std::span<const uint8_t> common_prefix,
241 std::string_view provider) {
242#if defined(BOTAN_HASH_ENGINE_KECCAK_HAS_IMPL)
243 size_t output_length = 0;
244 size_t rate = 0;
245 uint8_t suffix = 0;
246 std::string name;
247
248 const AlgorithmSpec req(hash_fn);
249 if(auto shake = req.match("SHAKE-128|SHAKE-256({bits:int})")) {
250 const size_t bits = shake->integer("bits");
251 if(bits == 0 || bits % 8 != 0) {
252 return nullptr;
253 }
254 output_length = bits / 8;
255 rate = (shake->head() == "SHAKE-128") ? 168 : 136;
256 suffix = 0x1F;
257 name = fmt("{}({})", shake->head(), bits);
258 } else if(auto sha3 = req.match("SHA-3({bits:int=512})")) {
259 const size_t bits = sha3->integer("bits");
260 if(bits != 224 && bits != 256 && bits != 384 && bits != 512) {
261 return nullptr;
262 }
263 output_length = bits / 8;
264 rate = 200 - 2 * output_length;
265 suffix = 0x06;
266 name = fmt("SHA-3({})", bits);
267 } else {
268 return nullptr;
269 }
270
271 #if defined(BOTAN_HAS_HASH_ENGINE_KECCAK_AVX512)
272 if(auto feat = CPUID::check(CPUID::Feature::AVX512)) {
273 if(provider.empty() || provider == *feat) {
274 return std::make_unique<Keccak_MB_Engine>(
275 name, output_length, rate, suffix, common_prefix, *feat, 8, keccak_mb_permute_x8, keccak_mb_absorb_x8);
276 }
277 }
278 #endif
279
280 #if defined(BOTAN_HAS_HASH_ENGINE_KECCAK_AVX2)
281 if(auto feat = CPUID::check(CPUID::Feature::AVX2)) {
282 if(provider.empty() || provider == *feat) {
283 return std::make_unique<Keccak_MB_Engine>(
284 name, output_length, rate, suffix, common_prefix, *feat, 4, keccak_mb_permute_x4, keccak_mb_absorb_x4);
285 }
286 }
287 #endif
288
289 return nullptr;
290#else
291 BOTAN_UNUSED(hash_fn, common_prefix, provider);
292 return nullptr;
293#endif
294}
295
296} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:151
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
std::optional< AlgorithmMatch > match(const AlgorithmPattern &pattern) const &
static std::optional< std::string > check(CPUID::Feature feat)
Definition cpuid.h:66
const char * name
Definition ffi_tls.h:59
constexpr std::optional< T > checked_add(T a, T b)
Definition int_utils.h:19
std::string fmt(std::string_view format, const T &... args)
Definition fmt.h:53
BOTAN_FN_ISA_SIMD_8X64 void keccak_mb_absorb_x8(uint64_t *states, const uint8_t *const *blocks, size_t rate_words, size_t nblocks)
BOTAN_FN_ISA_SIMD_4X64 void keccak_mb_absorb_x4(uint64_t *states, const uint8_t *const *blocks, size_t rate_words, size_t nblocks)
constexpr void copy_mem(T *out, const T *in, size_t n)
Definition mem_ops.h:144
std::unique_ptr< Hash_Engine > create_keccak_mb_engine(std::string_view hash_fn, std::span< const uint8_t > common_prefix, std::string_view provider)
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
constexpr size_t KECCAK_MB_ABSORB_BLOCKS
BOTAN_FN_ISA_SIMD_4X64 void keccak_mb_permute_x4(uint64_t *states)
BOTAN_FN_ISA_SIMD_8X64 void keccak_mb_permute_x8(uint64_t *states)
constexpr void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:118