Botan 3.9.0
Crypto and TLS for C&
kuznyechik.cpp
Go to the documentation of this file.
1/*
2* GOST R 34.12-2015: Block Cipher "Kuznyechik" (RFC 7801)
3* (C) 2023 Richard Huveneers
4* 2024 Jack Lloyd
5*
6* This code is written by kerukuro for cppcrypto library (http://cppcrypto.sourceforge.net/)
7* and released into public domain.
8*
9* Botan is released under the Simplified BSD License (see license.txt)
10*/
11
12#include <botan/internal/kuznyechik.h>
13
14#include <botan/mem_ops.h>
15#include <botan/internal/loadstor.h>
16#include <algorithm>
17
18namespace Botan {
19
20namespace {
21
22namespace Kuznyechik_F {
23
24alignas(256) const constexpr uint8_t S[256] = {
25 252, 238, 221, 17, 207, 110, 49, 22, 251, 196, 250, 218, 35, 197, 4, 77, 233, 119, 240, 219, 147, 46,
26 153, 186, 23, 54, 241, 187, 20, 205, 95, 193, 249, 24, 101, 90, 226, 92, 239, 33, 129, 28, 60, 66,
27 139, 1, 142, 79, 5, 132, 2, 174, 227, 106, 143, 160, 6, 11, 237, 152, 127, 212, 211, 31, 235, 52,
28 44, 81, 234, 200, 72, 171, 242, 42, 104, 162, 253, 58, 206, 204, 181, 112, 14, 86, 8, 12, 118, 18,
29 191, 114, 19, 71, 156, 183, 93, 135, 21, 161, 150, 41, 16, 123, 154, 199, 243, 145, 120, 111, 157, 158,
30 178, 177, 50, 117, 25, 61, 255, 53, 138, 126, 109, 84, 198, 128, 195, 189, 13, 87, 223, 245, 36, 169,
31 62, 168, 67, 201, 215, 121, 214, 246, 124, 34, 185, 3, 224, 15, 236, 222, 122, 148, 176, 188, 220, 232,
32 40, 80, 78, 51, 10, 74, 167, 151, 96, 115, 30, 0, 98, 68, 26, 184, 56, 130, 100, 159, 38, 65,
33 173, 69, 70, 146, 39, 94, 85, 47, 140, 163, 165, 125, 105, 213, 149, 59, 7, 88, 179, 64, 134, 172,
34 29, 247, 48, 55, 107, 228, 136, 217, 231, 137, 225, 27, 131, 73, 76, 63, 248, 254, 141, 83, 170, 144,
35 202, 216, 133, 97, 32, 113, 103, 164, 45, 43, 9, 91, 203, 155, 37, 208, 190, 229, 108, 82, 89, 166,
36 116, 210, 230, 244, 180, 192, 209, 102, 175, 194, 57, 75, 99, 182};
37
38alignas(256) const constexpr uint8_t IS[256] = {
39 165, 45, 50, 143, 14, 48, 56, 192, 84, 230, 158, 57, 85, 126, 82, 145, 100, 3, 87, 90, 28, 96,
40 7, 24, 33, 114, 168, 209, 41, 198, 164, 63, 224, 39, 141, 12, 130, 234, 174, 180, 154, 99, 73, 229,
41 66, 228, 21, 183, 200, 6, 112, 157, 65, 117, 25, 201, 170, 252, 77, 191, 42, 115, 132, 213, 195, 175,
42 43, 134, 167, 177, 178, 91, 70, 211, 159, 253, 212, 15, 156, 47, 155, 67, 239, 217, 121, 182, 83, 127,
43 193, 240, 35, 231, 37, 94, 181, 30, 162, 223, 166, 254, 172, 34, 249, 226, 74, 188, 53, 202, 238, 120,
44 5, 107, 81, 225, 89, 163, 242, 113, 86, 17, 106, 137, 148, 101, 140, 187, 119, 60, 123, 40, 171, 210,
45 49, 222, 196, 95, 204, 207, 118, 44, 184, 216, 46, 54, 219, 105, 179, 20, 149, 190, 98, 161, 59, 22,
46 102, 233, 92, 108, 109, 173, 55, 97, 75, 185, 227, 186, 241, 160, 133, 131, 218, 71, 197, 176, 51, 250,
47 150, 111, 110, 194, 246, 80, 255, 93, 169, 142, 23, 27, 151, 125, 236, 88, 247, 31, 251, 124, 9, 13,
48 122, 103, 69, 135, 220, 232, 79, 29, 78, 4, 235, 248, 243, 62, 61, 189, 138, 136, 221, 205, 11, 19,
49 152, 2, 147, 128, 144, 208, 36, 52, 203, 237, 244, 206, 153, 16, 68, 64, 146, 58, 1, 38, 18, 26,
50 72, 104, 245, 129, 139, 199, 214, 32, 10, 8, 0, 76, 215, 116};
51
52namespace Kuznyechik_T {
53
54const constexpr uint8_t LINEAR[16] = {
55 0x94, 0x20, 0x85, 0x10, 0xC2, 0xC0, 0x01, 0xFB, 0x01, 0xC0, 0xC2, 0x10, 0x85, 0x20, 0x94, 0x01};
56
57constexpr uint8_t poly_mul(uint8_t x, uint8_t y) {
58 const uint8_t poly = 0xC3;
59
60 uint8_t r = 0;
61 while(x > 0 && y > 0) {
62 if((y & 1) != 0) {
63 r ^= x;
64 }
65 x = (x << 1) ^ ((x >> 7) * poly);
66 y >>= 1;
67 }
68 return r;
69}
70
71constexpr uint64_t poly_mul(uint64_t x, uint8_t y) {
72 const uint64_t lo_bit = 0x0101010101010101;
73 const uint64_t mask = 0x7F7F7F7F7F7F7F7F;
74 const uint64_t poly = 0xC3;
75
76 uint64_t r = 0;
77 while(x > 0 && y > 0) {
78 if((y & 1) != 0) {
79 r ^= x;
80 }
81 x = ((x & mask) << 1) ^ (((x >> 7) & lo_bit) * poly);
82 y >>= 1;
83 }
84 return r;
85}
86
87consteval std::array<uint8_t, 256> L_table(bool forward) noexcept {
88 std::array<uint8_t, 256> L = {};
89
90 for(size_t i = 0; i != 16; ++i) {
91 L[i] = LINEAR[i];
92 if(i > 0) {
93 L[17 * i - 1] = 1;
94 }
95 }
96
97 if(!forward) {
98 std::reverse(L.begin(), L.end());
99 }
100
101 auto sqr_matrix = [](std::span<const uint8_t, 256> mat) {
102 std::array<uint8_t, 256> res = {};
103 for(size_t i = 0; i != 16; ++i) {
104 for(size_t j = 0; j != 16; ++j) {
105 for(size_t k = 0; k != 16; ++k) {
106 res[16 * i + j] ^= poly_mul(mat[16 * i + k], mat[16 * k + j]);
107 }
108 }
109 }
110 return res;
111 };
112
113 for(size_t i = 0; i != 4; ++i) {
114 L = sqr_matrix(L);
115 }
116
117 return L;
118}
119
120consteval std::array<uint64_t, 16 * 256 * 2> T_table(std::span<const uint8_t> L,
121 std::span<const uint8_t, 256> SB) noexcept {
122 std::array<uint64_t, 16 * 256 * 2> T = {};
123
124 for(size_t i = 0; i != 16; ++i) {
125 uint64_t L_stride_0 = 0;
126 uint64_t L_stride_1 = 0;
127 for(size_t j = 0; j != 8; ++j) {
128 L_stride_0 |= static_cast<uint64_t>(L[i + 16 * j]) << (8 * (j % 8));
129 L_stride_1 |= static_cast<uint64_t>(L[i + 16 * (j + 8)]) << (8 * (j % 8));
130 }
131
132 for(size_t j = 0; j != 256; ++j) {
133 const uint8_t Sj = SB[j];
134 T[512 * i + 2 * j] = poly_mul(L_stride_0, Sj);
135 T[512 * i + 2 * j + 1] = poly_mul(L_stride_1, Sj);
136 }
137 }
138
139 return T;
140}
141
142} // namespace Kuznyechik_T
143
144// TODO(Botan4) this indirection with L/IL is required to work around a problem
145// with Clang 19, where suddenly T_table became too much for it to handle as constexpr.
146// Check if it's possible to remove this.
147constexpr auto L = Kuznyechik_T::L_table(true);
148constexpr auto IL = Kuznyechik_T::L_table(false);
149const constinit auto T = Kuznyechik_T::T_table(L, S);
150const constinit auto IT = Kuznyechik_T::T_table(IL, IS);
151
152const uint64_t C[32][2] = {{0xb87a486c7276a26e, 0x019484dd10bd275d}, {0xb3f490d8e4ec87dc, 0x02ebcb7920b94eba},
153 {0x0b8ed8b4969a25b2, 0x037f4fa4300469e7}, {0xa52be3730b1bcd7b, 0x041555f240b19cb7},
154 {0x1d51ab1f796d6f15, 0x0581d12f500cbbea}, {0x16df73abeff74aa7, 0x06fe9e8b6008d20d},
155 {0xaea53bc79d81e8c9, 0x076a1a5670b5f550}, {0x895605e6163659f6, 0x082aaa2780a1fbad},
156 {0x312c4d8a6440fb98, 0x09be2efa901cdcf0}, {0x3aa2953ef2dade2a, 0x0ac1615ea018b517},
157 {0x82d8dd5280ac7c44, 0x0b55e583b0a5924a}, {0x2c7de6951d2d948d, 0x0c3fffd5c010671a},
158 {0x9407aef96f5b36e3, 0x0dab7b08d0ad4047}, {0x9f89764df9c11351, 0x0ed434ace0a929a0},
159 {0x27f33e218bb7b13f, 0x0f40b071f0140efd}, {0xd1ac0a0f2c6cb22f, 0x1054974ec3813599},
160 {0x69d642635e1a1041, 0x11c01393d33c12c4}, {0x62589ad7c88035f3, 0x12bf5c37e3387b23},
161 {0xda22d2bbbaf6979d, 0x132bd8eaf3855c7e}, {0x7487e97c27777f54, 0x1441c2bc8330a92e},
162 {0xccfda1105501dd3a, 0x15d54661938d8e73}, {0xc77379a4c39bf888, 0x16aa09c5a389e794},
163 {0x7f0931c8b1ed5ae6, 0x173e8d18b334c0c9}, {0x58fa0fe93a5aebd9, 0x187e3d694320ce34},
164 {0xe0804785482c49b7, 0x19eab9b4539de969}, {0xeb0e9f31deb66c05, 0x1a95f6106399808e},
165 {0x5374d75dacc0ce6b, 0x1b0172cd7324a7d3}, {0xfdd1ec9a314126a2, 0x1c6b689b03915283},
166 {0x45aba4f6433784cc, 0x1dffec46132c75de}, {0x4e257c42d5ada17e, 0x1e80a3e223281c39},
167 {0xf65f342ea7db0310, 0x1f14273f33953b64}, {0x619b141e58d8a75e, 0x20a8ed9c45c16af1}};
168
169inline void LS(uint64_t& x1, uint64_t& x2) {
170 uint64_t t1 = 0;
171 uint64_t t2 = 0;
172 for(size_t i = 0; i != 16; ++i) {
173 const uint8_t x = get_byte_var(7 - (i % 8), (i < 8) ? x1 : x2);
174 t1 ^= T[512 * i + 2 * x + 0];
175 t2 ^= T[512 * i + 2 * x + 1];
176 }
177
178 x1 = t1;
179 x2 = t2;
180}
181
182inline void ILS(uint64_t& x1, uint64_t& x2) {
183 uint64_t t1 = 0;
184 uint64_t t2 = 0;
185 for(size_t i = 0; i != 16; ++i) {
186 const uint8_t x = get_byte_var(7 - (i % 8), (i < 8) ? x1 : x2);
187 t1 ^= IT[512 * i + 2 * x + 0];
188 t2 ^= IT[512 * i + 2 * x + 1];
189 }
190 x1 = t1;
191 x2 = t2;
192}
193
194inline void ILSS(uint64_t& x1, uint64_t& x2) {
195 uint64_t t1 = 0;
196 uint64_t t2 = 0;
197 for(size_t i = 0; i != 16; ++i) {
198 const uint8_t x = S[get_byte_var(7 - (i % 8), (i < 8) ? x1 : x2)];
199 t1 ^= IT[512 * i + 2 * x + 0];
200 t2 ^= IT[512 * i + 2 * x + 1];
201 }
202 x1 = t1;
203 x2 = t2;
204}
205
206inline uint64_t ISI(uint64_t val) {
207 uint64_t out = 0;
208 for(size_t i = 0; i != 8; ++i) {
209 out <<= 8;
210 out |= IS[get_byte_var(i, val)];
211 }
212 return out;
213}
214
215} // namespace Kuznyechik_F
216
217} // namespace
218
220 zap(m_rke);
221 zap(m_rkd);
222}
223
225 return !m_rke.empty();
226}
227
228void Kuznyechik::key_schedule(std::span<const uint8_t> key) {
229 using namespace Kuznyechik_F;
230
231 BOTAN_ASSERT_NOMSG(key.size() == 32);
232
233 uint64_t k0 = load_le<uint64_t>(key.data(), 0);
234 uint64_t k1 = load_le<uint64_t>(key.data(), 1);
235 uint64_t k2 = load_le<uint64_t>(key.data(), 2);
236 uint64_t k3 = load_le<uint64_t>(key.data(), 3);
237
238 m_rke.resize(20);
239
240 m_rke[0] = k0;
241 m_rke[1] = k1;
242 m_rke[2] = k2;
243 m_rke[3] = k3;
244
245 for(size_t i = 0; i != 4; ++i) {
246 for(size_t r = 0; r != 8; r += 2) {
247 uint64_t t0 = k0 ^ C[8 * i + r][0];
248 uint64_t t1 = k1 ^ C[8 * i + r][1];
249 uint64_t t2 = k0;
250 uint64_t t3 = k1;
251 LS(t0, t1);
252 t0 ^= k2;
253 t1 ^= k3;
254
255 k0 = t0 ^ C[8 * i + r + 1][0];
256 k1 = t1 ^ C[8 * i + r + 1][1];
257 k2 = t0;
258 k3 = t1;
259 LS(k0, k1);
260 k0 ^= t2;
261 k1 ^= t3;
262 }
263
264 m_rke[4 * (i + 1) + 0] = k0;
265 m_rke[4 * (i + 1) + 1] = k1;
266 m_rke[4 * (i + 1) + 2] = k2;
267 m_rke[4 * (i + 1) + 3] = k3;
268 }
269
270 m_rkd.resize(20);
271
272 for(size_t i = 0; i != 10; i++) {
273 uint64_t t0 = m_rke[2 * i + 0];
274 uint64_t t1 = m_rke[2 * i + 1];
275
276 if(i > 0) {
277 Kuznyechik_F::ILSS(t0, t1);
278 }
279
280 const size_t dest = 9 - i;
281
282 m_rkd[2 * dest + 0] = t0;
283 m_rkd[2 * dest + 1] = t1;
284 }
285}
286
287void Kuznyechik::encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {
289 while(blocks > 0) {
290 uint64_t x1 = load_le<uint64_t>(in, 0);
291 uint64_t x2 = load_le<uint64_t>(in, 1);
292
293 x1 ^= m_rke[0];
294 x2 ^= m_rke[1];
295 Kuznyechik_F::LS(x1, x2);
296
297 x1 ^= m_rke[2];
298 x2 ^= m_rke[3];
299 Kuznyechik_F::LS(x1, x2);
300
301 x1 ^= m_rke[4];
302 x2 ^= m_rke[5];
303 Kuznyechik_F::LS(x1, x2);
304
305 x1 ^= m_rke[6];
306 x2 ^= m_rke[7];
307 Kuznyechik_F::LS(x1, x2);
308
309 x1 ^= m_rke[8];
310 x2 ^= m_rke[9];
311 Kuznyechik_F::LS(x1, x2);
312
313 x1 ^= m_rke[10];
314 x2 ^= m_rke[11];
315 Kuznyechik_F::LS(x1, x2);
316
317 x1 ^= m_rke[12];
318 x2 ^= m_rke[13];
319 Kuznyechik_F::LS(x1, x2);
320
321 x1 ^= m_rke[14];
322 x2 ^= m_rke[15];
323 Kuznyechik_F::LS(x1, x2);
324
325 x1 ^= m_rke[16];
326 x2 ^= m_rke[17];
327 Kuznyechik_F::LS(x1, x2);
328
329 x1 ^= m_rke[18];
330 x2 ^= m_rke[19];
331
332 store_le(out, x1, x2);
333
334 in += 16;
335 out += 16;
336 blocks--;
337 }
338}
339
340void Kuznyechik::decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const {
342 while(blocks > 0) {
343 uint64_t x1 = load_le<uint64_t>(in, 0);
344 uint64_t x2 = load_le<uint64_t>(in, 1);
345
346 Kuznyechik_F::ILSS(x1, x2);
347
348 x1 ^= m_rkd[0];
349 x2 ^= m_rkd[1];
350 Kuznyechik_F::ILS(x1, x2);
351
352 x1 ^= m_rkd[2];
353 x2 ^= m_rkd[3];
354 Kuznyechik_F::ILS(x1, x2);
355
356 x1 ^= m_rkd[4];
357 x2 ^= m_rkd[5];
358 Kuznyechik_F::ILS(x1, x2);
359
360 x1 ^= m_rkd[6];
361 x2 ^= m_rkd[7];
362 Kuznyechik_F::ILS(x1, x2);
363
364 x1 ^= m_rkd[8];
365 x2 ^= m_rkd[9];
366 Kuznyechik_F::ILS(x1, x2);
367
368 x1 ^= m_rkd[10];
369 x2 ^= m_rkd[11];
370 Kuznyechik_F::ILS(x1, x2);
371
372 x1 ^= m_rkd[12];
373 x2 ^= m_rkd[13];
374 Kuznyechik_F::ILS(x1, x2);
375
376 x1 ^= m_rkd[14];
377 x2 ^= m_rkd[15];
378 Kuznyechik_F::ILS(x1, x2);
379
380 x1 ^= m_rkd[16];
381 x2 ^= m_rkd[17];
382 x1 = Kuznyechik_F::ISI(x1);
383 x2 = Kuznyechik_F::ISI(x2);
384
385 x1 ^= m_rkd[18];
386 x2 ^= m_rkd[19];
387
388 store_le(out, x1, x2);
389
390 in += 16;
391 out += 16;
392 blocks--;
393 }
394}
395
396} // namespace Botan
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:75
void encrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
void clear() override
void decrypt_n(const uint8_t in[], uint8_t out[], size_t blocks) const override
bool has_keying_material() const override
void zap(std::vector< T, Alloc > &vec)
Definition secmem.h:134
constexpr auto store_le(ParamTs &&... params)
Definition loadstor.h:736
constexpr auto load_le(ParamTs &&... params)
Definition loadstor.h:495
constexpr uint8_t get_byte_var(size_t byte_num, T input)
Definition loadstor.h:69