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