Botan 3.5.0
Crypto and TLS for C&
frodokem.cpp
Go to the documentation of this file.
1/*
2 * FrodoKEM implemenation
3 * Based on the MIT licensed reference implementation by the designers
4 * (https://github.com/microsoft/PQCrypto-LWEKE/tree/master/src)
5 *
6 * The Fellowship of the FrodoKEM:
7 * (C) 2023 Jack Lloyd
8 * 2023 René Meusel, Amos Treiber - Rohde & Schwarz Cybersecurity
9 *
10 * Botan is released under the Simplified BSD License (see license.txt)
11 */
12
13#include <botan/frodokem.h>
14
15#include <botan/assert.h>
16#include <botan/hex.h>
17#include <botan/rng.h>
18#include <botan/xof.h>
19#include <botan/internal/ct_utils.h>
20#include <botan/internal/frodo_constants.h>
21#include <botan/internal/frodo_matrix.h>
22#include <botan/internal/frodo_types.h>
23#include <botan/internal/loadstor.h>
24#include <botan/internal/pk_ops_impl.h>
25#include <botan/internal/stl_util.h>
26
27#include <algorithm>
28#include <memory>
29#include <tuple>
30#include <vector>
31
32namespace Botan {
33
34class FrodoKEM_PublicKeyInternal {
35 public:
36 FrodoKEM_PublicKeyInternal(FrodoKEMConstants constants, FrodoSeedA seed_a, FrodoMatrix b) :
37 m_constants(std::move(constants)), m_seed_a(std::move(seed_a)), m_b(std::move(b)) {
38 auto& shake = m_constants.SHAKE_XOF();
39 shake.update(serialize());
40 m_hash = shake.output<FrodoPublicKeyHash>(m_constants.len_sec_bytes());
41 }
42
43 const FrodoKEMConstants& constants() const { return m_constants; }
44
45 const FrodoSeedA& seed_a() const { return m_seed_a; }
46
47 const FrodoMatrix& b() const { return m_b; }
48
49 const FrodoPublicKeyHash& hash() const { return m_hash; }
50
51 std::vector<uint8_t> serialize() const { return concat<std::vector<uint8_t>>(seed_a(), b().pack(m_constants)); }
52
53 private:
54 FrodoKEMConstants m_constants;
55 FrodoSeedA m_seed_a;
56 FrodoMatrix m_b;
57 FrodoPublicKeyHash m_hash;
58};
59
60class FrodoKEM_PrivateKeyInternal {
61 public:
62 FrodoKEM_PrivateKeyInternal(FrodoSeedS s, FrodoMatrix s_trans) :
63 m_s(std::move(s)), m_s_trans(std::move(s_trans)) {}
64
65 const FrodoSeedS& s() const { return m_s; }
66
67 const FrodoMatrix& s_trans() const { return m_s_trans; }
68
69 private:
70 FrodoSeedS m_s;
71 FrodoMatrix m_s_trans;
72};
73
74//
75// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
76//
77
78class Frodo_KEM_Encryptor final : public PK_Ops::KEM_Encryption_with_KDF {
79 public:
80 Frodo_KEM_Encryptor(std::shared_ptr<FrodoKEM_PublicKeyInternal> key, std::string_view kdf) :
81 KEM_Encryption_with_KDF(kdf), m_public_key(std::move(key)) {}
82
83 size_t raw_kem_shared_key_length() const override { return m_public_key->constants().len_sec_bytes(); }
84
85 size_t encapsulated_key_length() const override { return m_public_key->constants().len_ct_bytes(); }
86
87 void raw_kem_encrypt(std::span<uint8_t> out_encapsulated_key,
88 std::span<uint8_t> out_shared_key,
89 RandomNumberGenerator& rng) override {
90 const auto& consts = m_public_key->constants();
91 auto& shake = consts.SHAKE_XOF();
92 auto sample_generator = FrodoMatrix::make_sample_generator(consts, shake);
93
94 BufferStuffer out_ct_bs(out_encapsulated_key);
95
96 auto c_1 = out_ct_bs.next<FrodoPackedMatrix>(consts.len_packed_b_bytes());
97 auto c_2 = out_ct_bs.next<FrodoPackedMatrix>(consts.len_packed_c_bytes());
98 auto salt = out_ct_bs.next<FrodoSalt>(consts.len_salt_bytes());
99
100 BOTAN_ASSERT_NOMSG(out_ct_bs.full());
101
102 const auto u = rng.random_vec<FrodoPlaintext>(consts.len_sec_bytes());
103 rng.randomize(salt);
104
105 shake.update(m_public_key->hash());
106 shake.update(u);
107 shake.update(salt);
108 const auto seed_se = shake.output<FrodoSeedSE>(consts.len_se_bytes());
109 const auto k = shake.output<FrodoIntermediateSharedSecret>(consts.len_sec_bytes());
110 shake.clear();
111
112 shake.update(consts.encapsulation_domain_separator());
113 shake.update(seed_se);
114
115 const auto s_p = sample_generator(std::tuple(consts.n_bar(), consts.n()));
116
117 const auto e_p = sample_generator(std::tuple(consts.n_bar(), consts.n()));
118
119 const auto b_p = FrodoMatrix::mul_add_sa_plus_e(consts, s_p, e_p, m_public_key->seed_a());
120
121 b_p.pack(consts, c_1);
122
123 const auto e_pp = sample_generator(std::tuple(consts.n_bar(), consts.n_bar()));
124 shake.clear();
125
126 const auto v = FrodoMatrix::mul_add_sb_plus_e(consts, m_public_key->b(), s_p, e_pp);
127
128 const auto encoded = FrodoMatrix::encode(consts, u);
129
130 const auto c = FrodoMatrix::add(consts, v, encoded);
131
132 c.pack(consts, c_2);
133
134 shake.update(out_encapsulated_key);
135 shake.update(k);
136 shake.output(out_shared_key);
137 }
138
139 private:
140 std::shared_ptr<FrodoKEM_PublicKeyInternal> m_public_key;
141};
142
143class Frodo_KEM_Decryptor final : public PK_Ops::KEM_Decryption_with_KDF {
144 public:
145 Frodo_KEM_Decryptor(std::shared_ptr<FrodoKEM_PublicKeyInternal> public_key,
146 std::shared_ptr<FrodoKEM_PrivateKeyInternal> private_key,
147 std::string_view kdf) :
148 KEM_Decryption_with_KDF(kdf), m_public_key(std::move(public_key)), m_private_key(std::move(private_key)) {}
149
150 size_t raw_kem_shared_key_length() const override { return m_public_key->constants().len_sec_bytes(); }
151
152 size_t encapsulated_key_length() const override { return m_public_key->constants().len_ct_bytes(); }
153
154 void raw_kem_decrypt(std::span<uint8_t> out_shared_key, std::span<const uint8_t> encapsulated_key) override {
155 const auto& consts = m_public_key->constants();
156 auto& shake = consts.SHAKE_XOF();
157 auto sample_generator = FrodoMatrix::make_sample_generator(consts, shake);
158
159 if(encapsulated_key.size() != consts.len_ct_bytes()) {
160 throw Invalid_Argument("FrodoKEM ciphertext does not have the correct byte count");
161 }
162
163 BufferSlicer ct_bs(encapsulated_key);
164 auto c_1 = ct_bs.take<FrodoPackedMatrix>(consts.len_packed_b_bytes());
165 auto c_2 = ct_bs.take<FrodoPackedMatrix>(consts.len_packed_c_bytes());
166 auto salt = ct_bs.take<FrodoSalt>(consts.len_salt_bytes());
167 BOTAN_ASSERT_NOMSG(ct_bs.empty());
168
169 const auto b_p = FrodoMatrix::unpack(consts, {consts.n_bar(), consts.n()}, c_1);
170 const auto c = FrodoMatrix::unpack(consts, {consts.n_bar(), consts.n_bar()}, c_2);
171
172 const auto w = FrodoMatrix::mul_bs(consts, b_p, m_private_key->s_trans());
173 const auto m = FrodoMatrix::sub(consts, c, w);
174
175 const auto seed_u_p = m.decode(consts);
176
177 shake.update(m_public_key->hash());
178 shake.update(seed_u_p);
179 shake.update(salt);
180
181 const auto seed_se_p = shake.output<FrodoSeedSE>(consts.len_se_bytes());
182 const auto k_p = shake.output<FrodoIntermediateSharedSecret>(consts.len_sec_bytes());
183 shake.clear();
184
185 shake.update(consts.encapsulation_domain_separator());
186 shake.update(seed_se_p);
187 const auto s_p = sample_generator(std::tuple(consts.n_bar(), consts.n()));
188
189 const auto e_p = sample_generator(std::tuple(consts.n_bar(), consts.n()));
190
191 auto b_pp = FrodoMatrix::mul_add_sa_plus_e(consts, s_p, e_p, m_public_key->seed_a());
192
193 const auto e_pp = sample_generator(std::tuple(consts.n_bar(), consts.n_bar()));
194 shake.clear();
195
196 const auto v = FrodoMatrix::mul_add_sb_plus_e(consts, m_public_key->b(), s_p, e_pp);
197
198 const auto encoded = FrodoMatrix::encode(consts, seed_u_p);
199 auto c_p = FrodoMatrix::add(consts, v, encoded);
200
201 // b_p and c are unpacked values that are reduced by definition.
202 // b_pp and c_p are calculated values that need the reduction for
203 // an unambiguous comparison that is required next.
204 b_pp.reduce(consts);
205 c_p.reduce(consts);
206
207 // The spec concats the matrices b_p and c (b_pp and c_p respectively)
208 // and performs a single CT comparison. For convenience we compare the
209 // matrices individually in CT and CT-&& the resulting masks.
210 const auto cmp = b_p.constant_time_compare(b_pp) & c.constant_time_compare(c_p);
211
212 std::vector<uint8_t> k_bar(consts.len_sec_bytes(), 0);
213 CT::conditional_copy_mem(cmp, k_bar.data(), k_p.data(), m_private_key->s().data(), consts.len_sec_bytes());
214
215 shake.update(encapsulated_key);
216 shake.update(k_bar);
217 shake.output(out_shared_key);
218 }
219
220 private:
221 std::shared_ptr<FrodoKEM_PublicKeyInternal> m_public_key;
222 std::shared_ptr<FrodoKEM_PrivateKeyInternal> m_private_key;
223};
224
225//
226// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
227//
228
229FrodoKEM_PublicKey::FrodoKEM_PublicKey(std::span<const uint8_t> pub_key, FrodoKEMMode mode) {
230 FrodoKEMConstants consts(mode);
231 if(pub_key.size() != consts.len_public_key_bytes()) {
232 throw Invalid_Argument("FrodoKEM public key does not have the correct byte count");
233 }
234
235 BufferSlicer pk_bs(pub_key);
236 auto seed_a = pk_bs.copy<FrodoSeedA>(consts.len_a_bytes());
237 const auto packed_b = pk_bs.take<FrodoPackedMatrix>(consts.d() * consts.n() * consts.n_bar() / 8);
238 BOTAN_ASSERT_NOMSG(pk_bs.empty());
239
240 auto b = FrodoMatrix::unpack(consts, std::tuple(consts.n(), consts.n_bar()), packed_b);
241
242 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(std::move(consts), std::move(seed_a), std::move(b));
243}
244
245FrodoKEM_PublicKey::FrodoKEM_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) :
246 FrodoKEM_PublicKey(key_bits, FrodoKEMMode(alg_id.oid())) {}
247
249 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(
250 other.m_public->constants(), other.m_public->seed_a(), other.m_public->b());
251}
252
254 if(this != &other) {
255 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(
256 other.m_public->constants(), other.m_public->seed_a(), other.m_public->b());
257 }
258 return *this;
259}
260
264
266 return m_public->constants().mode().object_identifier();
267}
268
270 return m_public->constants().n();
271}
272
274 return m_public->constants().estimated_strength();
275}
276
277std::vector<uint8_t> FrodoKEM_PublicKey::raw_public_key_bits() const {
278 return concat<std::vector<uint8_t>>(m_public->seed_a(), m_public->b().pack(m_public->constants()));
279}
280
281std::vector<uint8_t> FrodoKEM_PublicKey::public_key_bits() const {
282 // Currently, there isn't a finalized definition of an ASN.1 structure for
283 // FrodoKEM public keys. Therefore, we return the raw public key bits.
284 return raw_public_key_bits();
285}
286
288 return true;
289}
290
291std::unique_ptr<Private_Key> FrodoKEM_PublicKey::generate_another(RandomNumberGenerator& rng) const {
292 return std::make_unique<FrodoKEM_PrivateKey>(rng, m_public->constants().mode());
293}
294
295std::unique_ptr<PK_Ops::KEM_Encryption> FrodoKEM_PublicKey::create_kem_encryption_op(std::string_view params,
296 std::string_view provider) const {
297 if(provider.empty() || provider == "base") {
298 return std::make_unique<Frodo_KEM_Encryptor>(m_public, params);
299 }
300 throw Provider_Not_Found(algo_name(), provider);
301}
302
303//
304// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
305//
306
308 FrodoKEMConstants consts(mode);
309 auto& shake = consts.SHAKE_XOF();
310 auto sample_generator = FrodoMatrix::make_sample_generator(consts, shake);
311
312 auto s = rng.random_vec<FrodoSeedS>(consts.len_sec_bytes());
313 const auto seed_se = rng.random_vec<FrodoSeedSE>(consts.len_se_bytes());
314 const auto z = rng.random_vec<FrodoSeedZ>(consts.len_a_bytes());
315
316 shake.update(z);
317 auto seed_a = shake.output<FrodoSeedA>(consts.len_a_bytes());
318 shake.clear();
319
320 shake.update(consts.keygen_domain_separator());
321 shake.update(seed_se);
322
323 auto s_trans = sample_generator(std::tuple(consts.n_bar(), consts.n()));
324 auto e = sample_generator(std::tuple(consts.n(), consts.n_bar()));
325
326 auto b = FrodoMatrix::mul_add_as_plus_e(consts, s_trans, e, seed_a);
327
328 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(std::move(consts), std::move(seed_a), std::move(b));
329 m_private = std::make_shared<FrodoKEM_PrivateKeyInternal>(std::move(s), std::move(s_trans));
330}
331
332FrodoKEM_PrivateKey::FrodoKEM_PrivateKey(std::span<const uint8_t> sk, FrodoKEMMode mode) {
333 FrodoKEMConstants consts(mode);
334
335 if(sk.size() != consts.len_private_key_bytes()) {
336 throw Invalid_Argument("FrodoKEM private key does not have the correct byte count");
337 }
338
339 BufferSlicer sk_bs(sk);
340 auto s = sk_bs.copy<FrodoSeedS>(consts.len_sec_bytes());
341 auto seed_a = sk_bs.copy<FrodoSeedA>(consts.len_a_bytes());
342 const auto packed_b = sk_bs.take<FrodoPackedMatrix>(consts.d() * consts.n() * consts.n_bar() / 8);
343 const auto s_trans_bytes = sk_bs.take<FrodoSerializedMatrix>(consts.n_bar() * consts.n() * 2);
344 const auto pkh = sk_bs.copy<FrodoPublicKeyHash>(consts.len_sec_bytes());
345 BOTAN_ASSERT_NOMSG(sk_bs.empty());
346
347 auto b = FrodoMatrix::unpack(consts, std::tuple(consts.n(), consts.n_bar()), packed_b);
348 auto s_trans = FrodoMatrix::deserialize({consts.n_bar(), consts.n()}, s_trans_bytes);
349
350 m_public = std::make_shared<FrodoKEM_PublicKeyInternal>(std::move(consts), std::move(seed_a), std::move(b));
351 m_private = std::make_shared<FrodoKEM_PrivateKeyInternal>(std::move(s), std::move(s_trans));
352
353 BOTAN_STATE_CHECK(pkh == m_public->hash());
354}
355
356FrodoKEM_PrivateKey::FrodoKEM_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) :
357 FrodoKEM_PrivateKey(key_bits, FrodoKEMMode(alg_id.oid())) {}
358
359std::unique_ptr<Public_Key> FrodoKEM_PrivateKey::public_key() const {
360 return std::make_unique<FrodoKEM_PublicKey>(*this);
361}
362
364 return raw_private_key_bits(); // TODO: check if we need to do something else here
365}
366
368 return concat<secure_vector<uint8_t>>(m_private->s(),
369 m_public->seed_a(),
370 m_public->b().pack(m_public->constants()),
371 m_private->s_trans().serialize(),
372 m_public->hash());
373}
374
375std::unique_ptr<PK_Ops::KEM_Decryption> FrodoKEM_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& rng,
376 std::string_view params,
377 std::string_view provider) const {
378 BOTAN_UNUSED(rng);
379 if(provider.empty() || provider == "base") {
380 return std::make_unique<Frodo_KEM_Decryptor>(m_public, m_private, params);
381 }
382 throw Provider_Not_Found(algo_name(), provider);
383}
384
385} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:118
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:59
#define BOTAN_STATE_CHECK(expr)
Definition assert.h:41
auto copy(const size_t count)
Definition stl_util.h:89
bool empty() const
Definition stl_util.h:129
std::span< const uint8_t > take(const size_t count)
Definition stl_util.h:98
FrodoDomainSeparator keygen_domain_separator() const
size_t len_private_key_bytes() const
size_t len_public_key_bytes() const
FrodoKEM_PrivateKey(RandomNumberGenerator &rng, FrodoKEMMode mode)
Definition frodokem.cpp:307
std::unique_ptr< PK_Ops::KEM_Decryption > create_kem_decryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
Definition frodokem.cpp:375
secure_vector< uint8_t > raw_private_key_bits() const override
Definition frodokem.cpp:367
secure_vector< uint8_t > private_key_bits() const override
Definition frodokem.cpp:363
std::unique_ptr< Public_Key > public_key() const override
Definition frodokem.cpp:359
size_t estimated_strength() const override
Definition frodokem.cpp:273
AlgorithmIdentifier algorithm_identifier() const override
Definition frodokem.cpp:261
std::unique_ptr< PK_Ops::KEM_Encryption > create_kem_encryption_op(std::string_view params, std::string_view provider) const override
Definition frodokem.cpp:295
size_t key_length() const override
Definition frodokem.cpp:269
std::shared_ptr< FrodoKEM_PublicKeyInternal > m_public
Definition frodokem.h:76
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
Definition frodokem.cpp:291
std::vector< uint8_t > public_key_bits() const override
Definition frodokem.cpp:281
FrodoKEM_PublicKey & operator=(const FrodoKEM_PublicKey &other)
Definition frodokem.cpp:253
std::string algo_name() const override
Definition frodokem.h:47
std::vector< uint8_t > raw_public_key_bits() const override
Definition frodokem.cpp:277
bool check_key(RandomNumberGenerator &, bool) const override
Definition frodokem.cpp:287
OID object_identifier() const override
Definition frodokem.cpp:265
static FrodoMatrix mul_add_sa_plus_e(const FrodoKEMConstants &constants, const FrodoMatrix &s, const FrodoMatrix &e, StrongSpan< const FrodoSeedA > seed_a)
static std::function< FrodoMatrix(const Dimensions &dimensions)> make_sample_generator(const FrodoKEMConstants &constants, Botan::XOF &shake)
static FrodoMatrix mul_add_sb_plus_e(const FrodoKEMConstants &constants, const FrodoMatrix &b, const FrodoMatrix &s, const FrodoMatrix &e)
static FrodoMatrix mul_add_as_plus_e(const FrodoKEMConstants &constants, const FrodoMatrix &s, const FrodoMatrix &e, StrongSpan< const FrodoSeedA > seed_a)
static FrodoMatrix sub(const FrodoKEMConstants &constants, const FrodoMatrix &a, const FrodoMatrix &b)
static FrodoMatrix add(const FrodoKEMConstants &constants, const FrodoMatrix &a, const FrodoMatrix &b)
static FrodoMatrix encode(const FrodoKEMConstants &constants, StrongSpan< const FrodoPlaintext > in)
static FrodoMatrix unpack(const FrodoKEMConstants &constants, const Dimensions &dimensions, StrongSpan< const FrodoPackedMatrix > packed_bytes)
static FrodoMatrix mul_bs(const FrodoKEMConstants &constants, const FrodoMatrix &b_p, const FrodoMatrix &s)
static FrodoMatrix deserialize(const Dimensions &dimensions, StrongSpan< const FrodoSerializedMatrix > bytes)
KEM_Decryption_with_KDF(std::string_view kdf)
Definition pk_ops.cpp:223
KEM_Encryption_with_KDF(std::string_view kdf)
Definition pk_ops.cpp:190
void random_vec(std::span< uint8_t > v)
Definition rng.h:179
void update(std::span< const uint8_t > input)
Definition xof.h:142
int(* final)(unsigned char *, CTX *)
constexpr Mask< T > conditional_copy_mem(Mask< T > mask, T *to, const T *from0, const T *from1, size_t elems)
Definition ct_utils.h:426
Strong< secure_vector< uint8_t >, struct FrodoSeedSE_ > FrodoSeedSE
Definition frodo_types.h:29
Strong< secure_vector< uint8_t >, struct FrodoIntermediateSharedSecret_ > FrodoIntermediateSharedSecret
Definition frodo_types.h:56
Strong< std::vector< uint8_t >, struct FrodoPublicKeyHash_ > FrodoPublicKeyHash
Definition frodo_types.h:38
constexpr auto concat(Rs &&... ranges)
Definition stl_util.h:262
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:61
Strong< std::vector< uint8_t >, struct FrodoSeedA_ > FrodoSeedA
Definition frodo_types.h:23
Strong< secure_vector< uint8_t >, struct FrodoPlaintext_ > FrodoPlaintext
Definition frodo_types.h:50
Strong< std::vector< uint8_t >, struct FrodoSalt_ > FrodoSalt
Definition frodo_types.h:53
Strong< std::vector< uint8_t >, struct FrodoPackedMatrix_ > FrodoPackedMatrix
Definition frodo_types.h:41
Strong< secure_vector< uint8_t >, struct FrodoSeedS_ > FrodoSeedS
Definition frodo_types.h:26