/
test_cmce.cpp
338 lines (262 loc) · 14.2 KB
/
test_cmce.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
/*
* Tests for Classic McEliece
*
* (C) 2023 Jack Lloyd
* 2023,2024 Fabian Albert, Amos Treiber - Rohde & Schwarz Cybersecurity
*
* Botan is released under the Simplified BSD License (see license.txt)
*/
#include "test_pubkey.h"
#include "test_pubkey_pqc.h"
#include "test_rng.h"
#include "tests.h"
#if defined(BOTAN_HAS_CLASSICMCELIECE)
#include <botan/cmce.h>
#include <botan/hash.h>
#include <botan/pk_algs.h>
#include <botan/pubkey.h>
#include <botan/internal/cmce_decaps.h>
#include <botan/internal/cmce_encaps.h>
#include <botan/internal/cmce_field_ordering.h>
#include <botan/internal/cmce_gf.h>
#include <botan/internal/cmce_keys_internal.h>
#include <botan/internal/cmce_parameters.h>
#include <botan/internal/cmce_poly.h>
namespace Botan_Tests {
namespace {
Botan::Classic_McEliece_Polynomial create_element_from_bytes(std::span<const uint8_t> bytes,
const Botan::Classic_McEliece_Polynomial_Ring& ring) {
BOTAN_ARG_CHECK(bytes.size() == ring.degree() * 2, "Correct input size");
std::vector<uint16_t> coef(ring.degree());
Botan::load_le<uint16_t>(coef.data(), bytes.data(), ring.degree());
std::vector<Botan::Classic_McEliece_GF> coeff_vec_gf;
std::transform(coef.begin(), coef.end(), std::back_inserter(coeff_vec_gf), [&](auto& coeff) {
return Botan::Classic_McEliece_GF(Botan::CmceGfElem(coeff), ring.poly_f());
});
return Botan::Classic_McEliece_Polynomial(coeff_vec_gf);
}
std::vector<Botan::Classic_McEliece_Parameter_Set> get_test_instances_all() {
return {// All instances
Botan::Classic_McEliece_Parameter_Set::mceliece348864,
Botan::Classic_McEliece_Parameter_Set::mceliece348864f,
Botan::Classic_McEliece_Parameter_Set::mceliece460896,
Botan::Classic_McEliece_Parameter_Set::mceliece460896f,
Botan::Classic_McEliece_Parameter_Set::mceliece6688128,
Botan::Classic_McEliece_Parameter_Set::mceliece6688128f,
Botan::Classic_McEliece_Parameter_Set::mceliece6688128pc,
Botan::Classic_McEliece_Parameter_Set::mceliece6688128pcf,
Botan::Classic_McEliece_Parameter_Set::mceliece6960119,
Botan::Classic_McEliece_Parameter_Set::mceliece6960119f,
Botan::Classic_McEliece_Parameter_Set::mceliece6960119pc,
Botan::Classic_McEliece_Parameter_Set::mceliece6960119pcf,
Botan::Classic_McEliece_Parameter_Set::mceliece8192128,
Botan::Classic_McEliece_Parameter_Set::mceliece8192128f,
Botan::Classic_McEliece_Parameter_Set::mceliece8192128pc,
Botan::Classic_McEliece_Parameter_Set::mceliece8192128pcf};
}
std::vector<Botan::Classic_McEliece_Parameter_Set> get_test_instances_min() {
return {// Testing with and without pc and f. Also testing 6960119 with m*t mod 8 != 0.
Botan::Classic_McEliece_Parameter_Set::mceliece348864,
Botan::Classic_McEliece_Parameter_Set::mceliece6960119pcf};
}
std::vector<Botan::Classic_McEliece_Parameter_Set> instances_to_test() {
if(Test::run_long_tests()) {
return get_test_instances_all();
} else {
return get_test_instances_min();
}
}
bool skip_cmce_test(const std::string& params_str) {
auto params = Botan::Classic_McEliece_Parameters::create(params_str);
auto to_test = instances_to_test();
return std::find(to_test.begin(), to_test.end(), params.parameter_set()) == to_test.end();
}
} // namespace
class CMCE_Utility_Tests final : public Test {
public:
Test::Result expand_seed_test() {
Test::Result result("Seed expansion");
auto params =
Botan::Classic_McEliece_Parameters::create(Botan::Classic_McEliece_Parameter_Set::mceliece348864);
// Created using the reference implementation
auto seed = Botan::hex_decode_locked("0102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f20");
auto exp_first_and_last_bytes = Botan::hex_decode(
"543e2791fd98dbc1" // first 8 bytes
"d332a7c40776ca01"); // last 8 bytes
size_t byte_length =
(params.n() + params.sigma2() * params.q() + params.sigma1() * params.t() + params.ell()) / 8;
auto rand = params.prg(seed)->output_stdvec(byte_length);
rand.erase(rand.begin() + 8, rand.end() - 8);
result.test_is_eq("Seed expansion", rand, exp_first_and_last_bytes);
return result;
}
Test::Result irreducible_poly_gen_test() {
Test::Result result("Irreducible Polynomial Generation");
auto params =
Botan::Classic_McEliece_Parameters::create(Botan::Classic_McEliece_Parameter_Set::mceliece348864);
// Created using the reference implementation
auto random_bits = Botan::CmceIrreducibleBits(Botan::hex_decode(
"d9b8bb962a3f9dac0f832d243def581e7d26f4028de1ff9cd168460e5050ab095a32a372b40d720bd5d75389a6b3f08fa1d13cec60a4b716d4d6c240f2f80cd3"
"cbc76ae0dddca164c1130da185bd04e890f2256fb9f4754864811e14ea5a43b8b3612d59cecde1b2fdb6362659a0193d2b7d4b9d79aa1801dde3ca90dc300773"));
auto exp_g = Botan::Classic_McEliece_Minimal_Polynomial::from_bytes(
Botan::hex_decode(
"8d00a50f520a0307b8007c06cb04b9073b0f4a0f800fb706a60f2a05910a670b460375091209fc060a09ab036c09e5085a0df90d3506b404a30fda041d09970f"
"1206d000e00aac01c00dc80f490cd80b4108330c0208cf00d602450ec00a21079806eb093f00de015f052905560917081b09270c820af002000c34094504cd03"),
params.poly_f());
auto g = params.poly_ring().compute_minimal_polynomial(random_bits);
result.confirm("Minimize polynomial successful", g.has_value());
result.test_is_eq("Minimize polynomial", g.value().coef(), exp_g.coef());
return result;
}
Test::Result gf_inv_test() {
Test::Result result("GF inv test");
auto params =
Botan::Classic_McEliece_Parameters::create(Botan::Classic_McEliece_Parameter_Set::mceliece348864);
auto v = params.gf(Botan::CmceGfElem(42));
auto v_inv = v.inv();
result.test_is_eq("Control bits creation", (v * v_inv).elem(), Botan::CmceGfElem(1));
return result;
}
Test::Result gf_poly_mul_test() {
Test::Result result("GF Poly Mul");
auto params =
Botan::Classic_McEliece_Parameters::create(Botan::Classic_McEliece_Parameter_Set::mceliece348864);
const auto& field = params.poly_ring();
auto val1 = create_element_from_bytes(
Botan::hex_decode(
"bb02d40437094c0ae4034c00b10fed090a04850f660c3b0e110eb409810a86015b0f5804ca0e78089806e20b5b03aa0bc2020b05ea03710da902340c390f630b"
"bc07a70db20b9e0ee4038905a00a09090a0521045e0a0706370b5a00050a4100480c4d0e8f00730692093701fe04650dbe0fd00702011a04910360023f04fb0a"),
field);
auto val2 = create_element_from_bytes(
Botan::hex_decode(
"060c630b170abb00020fef03e501020e89098108bf01f30dd30900000e0d3d0ca404ec01190760021f088c09b90b0a06a702d104500f0f02f00a580287010a09"
"4e01490d270c73051800bc0af303b901b202b50321002802b903ce0ab40806083f0a2d06d002df0f260811005c02a10b300e5c0ba20d14045003c50f2f02de02"),
field);
auto exp_mul = create_element_from_bytes(
Botan::hex_decode(
"370d090b19008f0efb01f5011b04f9054b0d1f071d0457011e09cd0dfa093c004f08500e670abb0567090000f603770a3905bf044408b8025805930b25012201"
"8d0a560e840d960d9d0a280d1d06fc08d5078c06fe0cb406d0061e02c6090507d20eb10cb90146085c042e030c0e1a07910fcd0c5f0fda066c0cee061d01f40f"),
field);
auto mul = field.multiply(val1, val2); // val1 * val2;
result.test_is_eq("GF multiplication", mul.coef(), exp_mul.coef());
return result;
}
Test::Result rigged_rng_encryption_test() {
// RNG that always returns zero bytes
class All_Zero_RNG : public Botan::RandomNumberGenerator {
public:
void fill_bytes_with_input(std::span<uint8_t> output, std::span<const uint8_t> /* ignored */) override {
std::fill(output.begin(), output.end(), 0);
}
std::string name() const override { return "All_Zero_RNG"; }
bool accepts_input() const override { return false; }
void clear() override {}
bool is_seeded() const override { return true; }
} rigged_rng;
Test::Result result("No endless loop with rigged RNG");
// Key creation should work even with a rigged RNG (PRNG is not used for key creation)
auto private_key = Botan::create_private_key("ClassicMcEliece", rigged_rng, "mceliece348864f");
if(!private_key) {
result.test_failure("Key generation failed");
return result;
}
auto enc = Botan::PK_KEM_Encryptor(*private_key, "Raw");
result.test_throws("Many failed encryption attempts throws exception", [&] { enc.encrypt(rigged_rng); });
return result;
}
std::vector<Test::Result> run() override {
return {expand_seed_test(),
irreducible_poly_gen_test(),
gf_inv_test(),
gf_poly_mul_test(),
rigged_rng_encryption_test()};
}
};
#if defined(BOTAN_HAS_AES)
class CMCE_Invalid_Test : public Text_Based_Test {
public:
CMCE_Invalid_Test() :
Text_Based_Test("pubkey/cmce_negative.vec", "seed,ct_invalid,ss_invalid", "ct_invalid_c1,ss_invalid_c1") {}
Test::Result run_one_test(const std::string& params_str, const VarMap& vars) override {
Test::Result result("CMCE Invalid Ciphertext Test");
auto params = Botan::Classic_McEliece_Parameters::create(params_str);
const auto kat_seed = Botan::lock(vars.get_req_bin("seed"));
const auto ct_invalid = vars.get_req_bin("ct_invalid");
const auto ref_ss_invalid = Botan::lock(vars.get_req_bin("ss_invalid"));
const auto test_rng = std::make_unique<CTR_DRBG_AES256>(kat_seed);
auto private_key = Botan::create_private_key("ClassicMcEliece", *test_rng, params_str);
// Decaps an invalid ciphertext
auto dec = Botan::PK_KEM_Decryptor(*private_key, *test_rng, "Raw");
auto decaps_ct_invalid = dec.decrypt(ct_invalid);
result.test_is_eq("Decaps an invalid encapsulated key", decaps_ct_invalid, ref_ss_invalid);
if(params.is_pc()) {
// For pc variants, additionally check the plaintext confirmation (pc) logic by
// flipping a bit in the second part of the ciphertext (C_1 in pc). In this case
// C_0 is decoded correctly, but pc will change the shared secret, since C_1' != C_1.
const auto ct_invalid_c1 = vars.get_opt_bin("ct_invalid_c1");
const auto ref_ss_invalid_c1 = Botan::lock(vars.get_opt_bin("ss_invalid_c1"));
auto decaps_ct_invalid_c1 = dec.decrypt(ct_invalid_c1);
result.test_is_eq("Decaps with invalid C_1 in pc", decaps_ct_invalid_c1, ref_ss_invalid_c1);
}
return result;
}
};
#endif // BOTAN_HAS_AES
class CMCE_Generic_Keygen_Tests final : public PK_Key_Generation_Test {
public:
std::vector<std::string> keygen_params() const override {
auto to_test = get_test_instances_min();
std::vector<std::string> res;
std::transform(to_test.begin(), to_test.end(), std::back_inserter(res), [](auto& param_set) {
return param_set.to_string();
});
return res;
}
std::string algo_name() const override { return "ClassicMcEliece"; }
};
class Classic_McEliece_KAT_Tests final : public Botan_Tests::PK_PQC_KEM_KAT_Test {
public:
Classic_McEliece_KAT_Tests() : PK_PQC_KEM_KAT_Test("ClassicMcEliece", "pubkey/cmce_kat_hashed.vec") {}
private:
Botan::Classic_McEliece_Parameters get_params(const std::string& header) const {
return Botan::Classic_McEliece_Parameters::create(Botan::Classic_McEliece_Parameter_Set::from_string(header));
}
bool is_available(const std::string& alg_name) const final { return !skip_cmce_test(alg_name); }
std::vector<uint8_t> map_value(const std::string&, std::span<const uint8_t> value, VarType var_type) const final {
if(var_type == VarType::Ciphertext || var_type == VarType::SharedSecret) {
return {value.begin(), value.end()};
}
auto hash = Botan::HashFunction::create_or_throw("SHAKE-256(512)");
return hash->process<std::vector<uint8_t>>(value);
}
Fixed_Output_RNG rng_for_keygen(const std::string&, Botan::RandomNumberGenerator& rng) const final {
const auto seed = rng.random_vec(Botan::Classic_McEliece_Parameters::seed_len());
return Fixed_Output_RNG(seed);
}
Fixed_Output_RNG rng_for_encapsulation(const std::string& alg_name,
Botan::RandomNumberGenerator& rng) const final {
// There is no way to tell exacly how much randomness is
// needed for encapsulation (rejection sampling)
// For testing we use a number that fits for all test cases
auto params = get_params(alg_name);
const size_t max_attempts = 100;
const size_t bits_per_attempt = (params.sigma1() / 8) * params.tau();
std::vector<uint8_t> rand_buffer;
for(size_t attempt = 0; attempt < max_attempts; ++attempt) {
auto random_bytes = rng.random_vec(bits_per_attempt);
rand_buffer.insert(rand_buffer.end(), random_bytes.begin(), random_bytes.end());
}
return Fixed_Output_RNG(rand_buffer);
}
void inspect_rng_after_encaps(const std::string&, const Fixed_Output_RNG&, Test::Result&) const final {
// Encaps uses any number of random bytes, so we cannot check the RNG
}
};
BOTAN_REGISTER_TEST("cmce", "cmce_utility", CMCE_Utility_Tests);
BOTAN_REGISTER_TEST("cmce", "cmce_generic_keygen", CMCE_Generic_Keygen_Tests);
BOTAN_REGISTER_TEST("cmce", "cmce_generic_kat", Classic_McEliece_KAT_Tests);
#if defined(BOTAN_HAS_AES)
BOTAN_REGISTER_TEST("cmce", "cmce_invalid", CMCE_Invalid_Test);
#endif
} // namespace Botan_Tests
#endif // BOTAN_HAS_CLASSICMCELIECE