Botan 3.14.1
Crypto and TLS for C&
twofish.cpp
Go to the documentation of this file.
1/*
2* Twofish
3* (C) 1999-2007,2017,2026 Jack Lloyd
4*
5* Botan is released under the Simplified BSD License (see license.txt)
6*/
7
8#include <botan/internal/twofish.h>
9
10#include <botan/internal/ct_utils.h>
11#include <botan/internal/loadstor.h>
12#include <botan/internal/rotate.h>
13
14#if defined(BOTAN_HAS_CPUID)
15 #include <botan/internal/cpuid.h>
16#endif
17
18namespace Botan {
19
20namespace {
21
22namespace Twofish_KS {
23
24// Twofish q-permutation derived from four 4-bit sboxes
25// ("Twofish: A 128-Bit Block Cipher", section 4.3.5)
26consteval std::array<uint8_t, 256> twofish_q_perm(std::array<uint8_t, 16> t0,
27 std::array<uint8_t, 16> t1,
28 std::array<uint8_t, 16> t2,
29 std::array<uint8_t, 16> t3) noexcept {
30 std::array<uint8_t, 256> Q = {};
31 for(size_t x = 0; x != 256; ++x) {
32 const uint8_t a0 = static_cast<uint8_t>((x >> 4) & 0x0F);
33 const uint8_t b0 = static_cast<uint8_t>(x & 0x0F);
34
35 const uint8_t a1 = a0 ^ b0;
36 const uint8_t b1 = a0 ^ ((b0 >> 1) | ((b0 & 1) << 3)) ^ ((8 * a0) & 0x0F);
37
38 const uint8_t a2 = t0[a1];
39 const uint8_t b2 = t1[b1];
40
41 const uint8_t a3 = a2 ^ b2;
42 const uint8_t b3 = a2 ^ ((b2 >> 1) | ((b2 & 1) << 3)) ^ ((8 * a2) & 0x0F);
43
44 const uint8_t a4 = t2[a3];
45 const uint8_t b4 = t3[b3];
46
47 Q[x] = static_cast<uint8_t>((b4 << 4) | a4);
48 }
49 return Q;
50}
51
52// clang-format off
53alignas(256) constexpr auto Q0 = twofish_q_perm(
54 {8, 1, 7, 13, 6, 15, 3, 2, 0, 11, 5, 9, 14, 12, 10, 4},
55 {14, 12, 11, 8, 1, 2, 3, 5, 15, 4, 10, 6, 7, 0, 9, 13},
56 {11, 10, 5, 14, 6, 13, 9, 0, 12, 8, 15, 3, 2, 4, 7, 1},
57 {13, 7, 15, 4, 1, 2, 6, 14, 9, 11, 3, 0, 8, 5, 12, 10});
58
59alignas(256) constexpr auto Q1 = twofish_q_perm(
60 {2, 8, 11, 13, 15, 7, 6, 14, 3, 1, 9, 4, 0, 10, 12, 5},
61 {1, 14, 2, 11, 4, 12, 3, 7, 6, 13, 10, 5, 15, 9, 0, 8},
62 {4, 12, 7, 5, 1, 6, 9, 10, 0, 14, 13, 8, 2, 11, 3, 15},
63 {11, 9, 5, 1, 12, 3, 13, 14, 6, 4, 7, 15, 2, 0, 8, 10});
64
65// clang-format on
66
67/*
68* MDS matrix multiplication (Twofish paper Section 4.2)
69*
70* MDS = [01, EF, 5B, 5B]
71* [5B, EF, EF, 01]
72* [EF, 5B, 01, EF]
73* [EF, 01, EF, 5B]
74*
75* The MDS coefficients are 01, 5B, and EF. These were chosen so that
76*
77* 5B = 1 + 1/x^2
78* EF = 1 + 1/x + 1/x^2
79*
80* in GF(2^8) mod x^8+x^6+x^5+x^3+1, where 1/x is computed by shifting
81* right and conditionally XORing with 0xB4 (which is itself just the
82* irreducible polynomial 0x169 shifted right by 1).
83*
84* This property of the MDS constants is described (briefly) in Section 7.3
85* of the Twofish paper.
86*/
87
88inline uint8_t mds_div_x(uint8_t q) {
89 return (q >> 1) ^ (CT::value_barrier<uint8_t>(q & 1) * 0xB4);
90}
91
92inline uint32_t mds0(uint8_t q) {
93 const uint8_t q_div_x = mds_div_x(q);
94 const uint8_t q5b = q ^ mds_div_x(q_div_x);
95 const uint8_t qef = q5b ^ q_div_x;
96 return make_uint32(qef, qef, q5b, q);
97}
98
99inline uint32_t mds1(uint8_t q) {
100 const uint8_t q_div_x = mds_div_x(q);
101 const uint8_t q5b = q ^ mds_div_x(q_div_x);
102 const uint8_t qef = q5b ^ q_div_x;
103 return make_uint32(q, q5b, qef, qef);
104}
105
106inline uint32_t mds2(uint8_t q) {
107 const uint8_t q_div_x = mds_div_x(q);
108 const uint8_t q5b = q ^ mds_div_x(q_div_x);
109 const uint8_t qef = q5b ^ q_div_x;
110 return make_uint32(qef, q, qef, q5b);
111}
112
113inline uint32_t mds3(uint8_t q) {
114 const uint8_t q_div_x = mds_div_x(q);
115 const uint8_t q5b = q ^ mds_div_x(q_div_x);
116 const uint8_t qef = q5b ^ q_div_x;
117 return make_uint32(q5b, qef, q, q5b);
118}
119
120// Constant-time GF(2^8) multiply in the RS field (irreducible polynomial 0x14D)
121inline uint32_t gf_mul_rs32(uint32_t rs, uint8_t k) {
122 constexpr uint32_t lo_bit = 0x01010101;
123 constexpr uint32_t mask = 0x7F7F7F7F;
124 constexpr uint32_t poly = 0x4D;
125
126 uint32_t r = 0;
127 for(size_t i = 0; i != 8; ++i) {
128 const auto k_lo = CT::Mask<uint32_t>::expand(k & 1);
129 r ^= k_lo.if_set_return(rs);
130 rs = ((rs & mask) << 1) ^ (((rs >> 7) & lo_bit) * poly);
131 k >>= 1;
132 }
133 return r;
134}
135
136} // namespace Twofish_KS
137
138inline void TF_E(
139 uint32_t A, uint32_t B, uint32_t& C, uint32_t& D, uint32_t RK1, uint32_t RK2, const secure_vector<uint32_t>& SB) {
140 uint32_t X = SB[get_byte<3>(A)] ^ SB[256 + get_byte<2>(A)] ^ SB[512 + get_byte<1>(A)] ^ SB[768 + get_byte<0>(A)];
141 uint32_t Y = SB[get_byte<0>(B)] ^ SB[256 + get_byte<3>(B)] ^ SB[512 + get_byte<2>(B)] ^ SB[768 + get_byte<1>(B)];
142
143 X += Y;
144 Y += X;
145
146 X += RK1;
147 Y += RK2;
148
149 C = rotr<1>(C ^ X);
150 D = rotl<1>(D) ^ Y;
151}
152
153inline void TF_D(
154 uint32_t A, uint32_t B, uint32_t& C, uint32_t& D, uint32_t RK1, uint32_t RK2, const secure_vector<uint32_t>& SB) {
155 uint32_t X = SB[get_byte<3>(A)] ^ SB[256 + get_byte<2>(A)] ^ SB[512 + get_byte<1>(A)] ^ SB[768 + get_byte<0>(A)];
156 uint32_t Y = SB[get_byte<0>(B)] ^ SB[256 + get_byte<3>(B)] ^ SB[512 + get_byte<2>(B)] ^ SB[768 + get_byte<1>(B)];
157
158 X += Y;
159 Y += X;
160
161 X += RK1;
162 Y += RK2;
163
164 C = rotl<1>(C) ^ X;
165 D = rotr<1>(D ^ Y);
166}
167
168} // namespace
169
170/*
171* Twofish Encryption
172*/
173void Twofish::encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {
175
176#if defined(BOTAN_HAS_TWOFISH_AVX512)
177 if(!m_QS.empty()) {
178 return avx512_encrypt(in, out, blocks);
179 }
180#endif
181
182 BOTAN_ASSERT_NOMSG(!m_SB.empty());
183
184 while(blocks >= 2) {
185 uint32_t A0 = 0;
186 uint32_t B0 = 0;
187 uint32_t C0 = 0;
188 uint32_t D0 = 0;
189 uint32_t A1 = 0;
190 uint32_t B1 = 0;
191 uint32_t C1 = 0;
192 uint32_t D1 = 0;
193 load_le(in, A0, B0, C0, D0, A1, B1, C1, D1);
194
195 A0 ^= m_RK[0];
196 A1 ^= m_RK[0];
197 B0 ^= m_RK[1];
198 B1 ^= m_RK[1];
199 C0 ^= m_RK[2];
200 C1 ^= m_RK[2];
201 D0 ^= m_RK[3];
202 D1 ^= m_RK[3];
203
204 for(size_t k = 8; k != 40; k += 4) {
205 TF_E(A0, B0, C0, D0, m_RK[k + 0], m_RK[k + 1], m_SB);
206 TF_E(A1, B1, C1, D1, m_RK[k + 0], m_RK[k + 1], m_SB);
207
208 TF_E(C0, D0, A0, B0, m_RK[k + 2], m_RK[k + 3], m_SB);
209 TF_E(C1, D1, A1, B1, m_RK[k + 2], m_RK[k + 3], m_SB);
210 }
211
212 C0 ^= m_RK[4];
213 C1 ^= m_RK[4];
214 D0 ^= m_RK[5];
215 D1 ^= m_RK[5];
216 A0 ^= m_RK[6];
217 A1 ^= m_RK[6];
218 B0 ^= m_RK[7];
219 B1 ^= m_RK[7];
220
221 store_le(out, C0, D0, A0, B0, C1, D1, A1, B1);
222
223 blocks -= 2;
224 out += 2 * BLOCK_SIZE;
225 in += 2 * BLOCK_SIZE;
226 }
227
228 if(blocks > 0) {
229 uint32_t A = 0;
230 uint32_t B = 0;
231 uint32_t C = 0;
232 uint32_t D = 0;
233 load_le(in, A, B, C, D);
234
235 A ^= m_RK[0];
236 B ^= m_RK[1];
237 C ^= m_RK[2];
238 D ^= m_RK[3];
239
240 for(size_t k = 8; k != 40; k += 4) {
241 TF_E(A, B, C, D, m_RK[k], m_RK[k + 1], m_SB);
242 TF_E(C, D, A, B, m_RK[k + 2], m_RK[k + 3], m_SB);
243 }
244
245 C ^= m_RK[4];
246 D ^= m_RK[5];
247 A ^= m_RK[6];
248 B ^= m_RK[7];
249
250 store_le(out, C, D, A, B);
251 }
252}
253
254/*
255* Twofish Decryption
256*/
257void Twofish::decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {
259
260#if defined(BOTAN_HAS_TWOFISH_AVX512)
261 if(!m_QS.empty()) {
262 return avx512_decrypt(in, out, blocks);
263 }
264#endif
265
266 BOTAN_ASSERT_NOMSG(!m_SB.empty());
267
268 while(blocks >= 2) {
269 uint32_t A0 = 0;
270 uint32_t B0 = 0;
271 uint32_t C0 = 0;
272 uint32_t D0 = 0;
273 uint32_t A1 = 0;
274 uint32_t B1 = 0;
275 uint32_t C1 = 0;
276 uint32_t D1 = 0;
277 load_le(in, A0, B0, C0, D0, A1, B1, C1, D1);
278
279 A0 ^= m_RK[4];
280 A1 ^= m_RK[4];
281 B0 ^= m_RK[5];
282 B1 ^= m_RK[5];
283 C0 ^= m_RK[6];
284 C1 ^= m_RK[6];
285 D0 ^= m_RK[7];
286 D1 ^= m_RK[7];
287
288 for(size_t k = 40; k != 8; k -= 4) {
289 TF_D(A0, B0, C0, D0, m_RK[k - 2], m_RK[k - 1], m_SB);
290 TF_D(A1, B1, C1, D1, m_RK[k - 2], m_RK[k - 1], m_SB);
291
292 TF_D(C0, D0, A0, B0, m_RK[k - 4], m_RK[k - 3], m_SB);
293 TF_D(C1, D1, A1, B1, m_RK[k - 4], m_RK[k - 3], m_SB);
294 }
295
296 C0 ^= m_RK[0];
297 C1 ^= m_RK[0];
298 D0 ^= m_RK[1];
299 D1 ^= m_RK[1];
300 A0 ^= m_RK[2];
301 A1 ^= m_RK[2];
302 B0 ^= m_RK[3];
303 B1 ^= m_RK[3];
304
305 store_le(out, C0, D0, A0, B0, C1, D1, A1, B1);
306
307 blocks -= 2;
308 out += 2 * BLOCK_SIZE;
309 in += 2 * BLOCK_SIZE;
310 }
311
312 if(blocks > 0) {
313 uint32_t A = 0;
314 uint32_t B = 0;
315 uint32_t C = 0;
316 uint32_t D = 0;
317 load_le(in, A, B, C, D);
318
319 A ^= m_RK[4];
320 B ^= m_RK[5];
321 C ^= m_RK[6];
322 D ^= m_RK[7];
323
324 for(size_t k = 40; k != 8; k -= 4) {
325 TF_D(A, B, C, D, m_RK[k - 2], m_RK[k - 1], m_SB);
326 TF_D(C, D, A, B, m_RK[k - 4], m_RK[k - 3], m_SB);
327 }
328
329 C ^= m_RK[0];
330 D ^= m_RK[1];
331 A ^= m_RK[2];
332 B ^= m_RK[3];
333
334 store_le(out, C, D, A, B);
335 }
336}
337
339 return !m_RK.empty();
340}
341
342std::string Twofish::provider() const {
343#if defined(BOTAN_HAS_TWOFISH_AVX512)
345 return "avx512";
346 }
347#endif
348 return "base";
349}
350
351size_t Twofish::parallelism() const {
352#if defined(BOTAN_HAS_TWOFISH_AVX512)
354 return 16;
355 }
356#endif
357 return 1;
358}
359
360/*
361* Twofish Key Schedule
362*/
363void Twofish::key_schedule(std::span<const uint8_t> key) {
364 using namespace Twofish_KS;
365
366 // Reed-Solomon matrix for key schedule (Twofish paper Section 4.3)
367 // in column-major form
368
369 // clang-format off
370 constexpr uint32_t RS32[8] = {
371 0x01A402A4,
372 0xA456A155,
373 0x5582FC87,
374 0x87F3C15A,
375 0x5A1E4758,
376 0x58C6AEDB,
377 0xDB683D9E,
378 0x9EE51903
379 };
380 // clang-format on
381
382 m_RK.resize(40);
383
385
386 for(size_t i = 0; i != key.size(); ++i) {
387 const uint8_t ki = key[i];
388 const size_t s_off = 4 * (i / 8);
389
390 const uint32_t p = gf_mul_rs32(RS32[i % 8], ki);
391
392 S[s_off + 0] ^= get_byte<0>(p);
393 S[s_off + 1] ^= get_byte<1>(p);
394 S[s_off + 2] ^= get_byte<2>(p);
395 S[s_off + 3] ^= get_byte<3>(p);
396 }
397
398 secure_vector<uint8_t> QS(1024);
399
400 if(key.size() == 16) {
401 for(size_t i = 0; i != 256; ++i) {
402 QS[i] = Q1[Q0[Q0[i] ^ S[0]] ^ S[4]];
403 QS[256 + i] = Q0[Q0[Q1[i] ^ S[1]] ^ S[5]];
404 QS[512 + i] = Q1[Q1[Q0[i] ^ S[2]] ^ S[6]];
405 QS[768 + i] = Q0[Q1[Q1[i] ^ S[3]] ^ S[7]];
406 }
407
408 for(size_t i = 0; i < 40; i += 2) {
409 uint32_t X = mds0(Q1[Q0[Q0[i] ^ key[8]] ^ key[0]]) ^ mds1(Q0[Q0[Q1[i] ^ key[9]] ^ key[1]]) ^
410 mds2(Q1[Q1[Q0[i] ^ key[10]] ^ key[2]]) ^ mds3(Q0[Q1[Q1[i] ^ key[11]] ^ key[3]]);
411 uint32_t Y = mds0(Q1[Q0[Q0[i + 1] ^ key[12]] ^ key[4]]) ^ mds1(Q0[Q0[Q1[i + 1] ^ key[13]] ^ key[5]]) ^
412 mds2(Q1[Q1[Q0[i + 1] ^ key[14]] ^ key[6]]) ^ mds3(Q0[Q1[Q1[i + 1] ^ key[15]] ^ key[7]]);
413 Y = rotl<8>(Y);
414 X += Y;
415 Y += X;
416
417 m_RK[i] = X;
418 m_RK[i + 1] = rotl<9>(Y);
419 }
420 } else if(key.size() == 24) {
421 for(size_t i = 0; i != 256; ++i) {
422 QS[i] = Q1[Q0[Q0[Q1[i] ^ S[0]] ^ S[4]] ^ S[8]];
423 QS[256 + i] = Q0[Q0[Q1[Q1[i] ^ S[1]] ^ S[5]] ^ S[9]];
424 QS[512 + i] = Q1[Q1[Q0[Q0[i] ^ S[2]] ^ S[6]] ^ S[10]];
425 QS[768 + i] = Q0[Q1[Q1[Q0[i] ^ S[3]] ^ S[7]] ^ S[11]];
426 }
427
428 for(size_t i = 0; i < 40; i += 2) {
429 uint32_t X =
430 mds0(Q1[Q0[Q0[Q1[i] ^ key[16]] ^ key[8]] ^ key[0]]) ^ mds1(Q0[Q0[Q1[Q1[i] ^ key[17]] ^ key[9]] ^ key[1]]) ^
431 mds2(Q1[Q1[Q0[Q0[i] ^ key[18]] ^ key[10]] ^ key[2]]) ^ mds3(Q0[Q1[Q1[Q0[i] ^ key[19]] ^ key[11]] ^ key[3]]);
432 uint32_t Y = mds0(Q1[Q0[Q0[Q1[i + 1] ^ key[20]] ^ key[12]] ^ key[4]]) ^
433 mds1(Q0[Q0[Q1[Q1[i + 1] ^ key[21]] ^ key[13]] ^ key[5]]) ^
434 mds2(Q1[Q1[Q0[Q0[i + 1] ^ key[22]] ^ key[14]] ^ key[6]]) ^
435 mds3(Q0[Q1[Q1[Q0[i + 1] ^ key[23]] ^ key[15]] ^ key[7]]);
436 Y = rotl<8>(Y);
437 X += Y;
438 Y += X;
439
440 m_RK[i] = X;
441 m_RK[i + 1] = rotl<9>(Y);
442 }
443 } else if(key.size() == 32) {
444 for(size_t i = 0; i != 256; ++i) {
445 QS[i] = Q1[Q0[Q0[Q1[Q1[i] ^ S[0]] ^ S[4]] ^ S[8]] ^ S[12]];
446 QS[256 + i] = Q0[Q0[Q1[Q1[Q0[i] ^ S[1]] ^ S[5]] ^ S[9]] ^ S[13]];
447 QS[512 + i] = Q1[Q1[Q0[Q0[Q0[i] ^ S[2]] ^ S[6]] ^ S[10]] ^ S[14]];
448 QS[768 + i] = Q0[Q1[Q1[Q0[Q1[i] ^ S[3]] ^ S[7]] ^ S[11]] ^ S[15]];
449 }
450
451 for(size_t i = 0; i < 40; i += 2) {
452 uint32_t X = mds0(Q1[Q0[Q0[Q1[Q1[i] ^ key[24]] ^ key[16]] ^ key[8]] ^ key[0]]) ^
453 mds1(Q0[Q0[Q1[Q1[Q0[i] ^ key[25]] ^ key[17]] ^ key[9]] ^ key[1]]) ^
454 mds2(Q1[Q1[Q0[Q0[Q0[i] ^ key[26]] ^ key[18]] ^ key[10]] ^ key[2]]) ^
455 mds3(Q0[Q1[Q1[Q0[Q1[i] ^ key[27]] ^ key[19]] ^ key[11]] ^ key[3]]);
456 uint32_t Y = mds0(Q1[Q0[Q0[Q1[Q1[i + 1] ^ key[28]] ^ key[20]] ^ key[12]] ^ key[4]]) ^
457 mds1(Q0[Q0[Q1[Q1[Q0[i + 1] ^ key[29]] ^ key[21]] ^ key[13]] ^ key[5]]) ^
458 mds2(Q1[Q1[Q0[Q0[Q0[i + 1] ^ key[30]] ^ key[22]] ^ key[14]] ^ key[6]]) ^
459 mds3(Q0[Q1[Q1[Q0[Q1[i + 1] ^ key[31]] ^ key[23]] ^ key[15]] ^ key[7]]);
460 Y = rotl<8>(Y);
461 X += Y;
462 Y += X;
463
464 m_RK[i] = X;
465 m_RK[i + 1] = rotl<9>(Y);
466 }
467 }
468
469#if defined(BOTAN_HAS_TWOFISH_AVX512)
471 m_QS = std::move(QS);
472 // AVX512 needs QS but not the expanded sbox values in SB
473 return;
474 }
475#endif
476
477 // m_SB is unused in the AVX-512 path so don't bother computing it
478 m_SB.resize(1024);
479 for(size_t i = 0; i != 256; ++i) {
480 m_SB[i] = mds0(QS[i]);
481 m_SB[256 + i] = mds1(QS[256 + i]);
482 m_SB[512 + i] = mds2(QS[512 + i]);
483 m_SB[768 + i] = mds3(QS[768 + i]);
484 }
485}
486
487/*
488* Clear memory of sensitive data
489*/
491 zap(m_SB);
492 zap(m_RK);
493 zap(m_QS);
494}
495
496} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
static bool has(CPUID::Feature feat)
Definition cpuid.h:93
static constexpr Mask< T > expand(T v)
Definition ct_utils.h:397
std::string provider() const override
Definition twofish.cpp:342
bool has_keying_material() const override
Definition twofish.cpp:338
void clear() override
Definition twofish.cpp:490
void encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition twofish.cpp:173
void decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
Definition twofish.cpp:257
size_t parallelism() const override
Definition twofish.cpp:351
constexpr T value_barrier(T x)
constexpr uint8_t get_byte(T input)
Definition loadstor.h:79
void zap(std::vector< T, Alloc > &vec)
Definition secmem.h:261
BOTAN_FORCE_INLINE constexpr T rotr(T input)
Definition rotate.h:35
constexpr uint32_t make_uint32(uint8_t i0, uint8_t i1, uint8_t i2, uint8_t i3)
Definition loadstor.h:104
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
BOTAN_FORCE_INLINE constexpr T rotl(T input)
Definition rotate.h:23
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128