Botan 3.8.1
Crypto and TLS for C&
kyber.cpp
Go to the documentation of this file.
1/*
2 * Crystals Kyber key encapsulation mechanism
3 * Based on the public domain reference implementation by the
4 * designers (https://github.com/pq-crystals/kyber)
5 *
6 * Further changes
7 * (C) 2021-2024 Jack Lloyd
8 * (C) 2021-2022 Manuel Glaser and Michael Boric, Rohde & Schwarz Cybersecurity
9 * (C) 2021-2022 René Meusel and Hannes Rantzsch, neXenio GmbH
10 * (C) 2024 René Meusel, Fabian Albert, Rohde & Schwarz Cybersecurity
11 *
12 * Botan is released under the Simplified BSD License (see license.txt)
13 */
14
15#include <botan/kyber.h>
16
17#include <botan/assert.h>
18#include <botan/mem_ops.h>
19#include <botan/pubkey.h>
20#include <botan/rng.h>
21#include <botan/secmem.h>
22
23#include <botan/internal/ct_utils.h>
24#include <botan/internal/fmt.h>
25#include <botan/internal/kyber_algos.h>
26#include <botan/internal/kyber_constants.h>
27#include <botan/internal/kyber_keys.h>
28#include <botan/internal/kyber_symmetric_primitives.h>
29#include <botan/internal/kyber_types.h>
30#include <botan/internal/stl_util.h>
31
32#if defined(BOTAN_HAS_KYBER)
33 #include <botan/internal/kyber_modern.h>
34#endif
35
36#if defined(BOTAN_HAS_KYBER_90S)
37 #include <botan/internal/kyber_90s.h>
38#endif
39
40#if defined(BOTAN_HAS_KYBER) || defined(BOTAN_HAS_KYBER_90S)
41 #include <botan/internal/kyber_round3_impl.h>
42#endif
43
44#if defined(BOTAN_HAS_ML_KEM)
45 #include <botan/internal/ml_kem_impl.h>
46#endif
47
48#include <memory>
49#include <vector>
50
51namespace Botan {
52
53namespace {
54
55KyberMode::Mode kyber_mode_from_string(std::string_view str) {
56 if(str == "Kyber-512-90s-r3") {
58 }
59 if(str == "Kyber-768-90s-r3") {
61 }
62 if(str == "Kyber-1024-90s-r3") {
64 }
65 if(str == "Kyber-512-r3") {
67 }
68 if(str == "Kyber-768-r3") {
70 }
71 if(str == "Kyber-1024-r3") {
73 }
74 if(str == "ML-KEM-512") {
76 }
77 if(str == "ML-KEM-768") {
79 }
80 if(str == "ML-KEM-1024") {
82 }
83
84 throw Invalid_Argument(fmt("'{}' is not a valid Kyber mode name", str));
85}
86
87} // namespace
88
90
91KyberMode::KyberMode(const OID& oid) : m_mode(kyber_mode_from_string(oid.to_formatted_string())) {}
92
93KyberMode::KyberMode(std::string_view str) : m_mode(kyber_mode_from_string(str)) {}
94
98
99std::string KyberMode::to_string() const {
100 switch(m_mode) {
101 case Kyber512_90s:
102 return "Kyber-512-90s-r3";
103 case Kyber768_90s:
104 return "Kyber-768-90s-r3";
105 case Kyber1024_90s:
106 return "Kyber-1024-90s-r3";
107 case Kyber512_R3:
108 return "Kyber-512-r3";
109 case Kyber768_R3:
110 return "Kyber-768-r3";
111 case Kyber1024_R3:
112 return "Kyber-1024-r3";
113 case ML_KEM_512:
114 return "ML-KEM-512";
115 case ML_KEM_768:
116 return "ML-KEM-768";
117 case ML_KEM_1024:
118 return "ML-KEM-1024";
119 }
120
122}
123
124bool KyberMode::is_90s() const {
125 return m_mode == Kyber512_90s || m_mode == Kyber768_90s || m_mode == Kyber1024_90s;
126}
127
129 return !is_90s();
130}
131
133 return m_mode == KyberMode::ML_KEM_512 || m_mode == KyberMode::ML_KEM_768 || m_mode == KyberMode::ML_KEM_1024;
134}
135
137 return m_mode == KyberMode::Kyber512_R3 || m_mode == KyberMode::Kyber768_R3 || m_mode == KyberMode::Kyber1024_R3 ||
139}
140
142#if defined(BOTAN_HAS_KYBER)
143 if(is_kyber_round3() && is_modern()) {
144 return true;
145 }
146#endif
147
148#if defined(BOTAN_HAS_KYBER_90S)
149 if(is_kyber_round3() && is_90s()) {
150 return true;
151 }
152#endif
153
154#if defined(BOTAN_HAS_ML_KEM)
155 if(is_ml_kem()) {
156 return true;
157 }
158#endif
159
160 return false;
161}
162
164 return m_public->mode().mode();
165}
166
167std::string Kyber_PublicKey::algo_name() const {
168 return mode().is_ml_kem() ? "ML-KEM" : "Kyber";
169}
170
172 // draft-ietf-lamps-kyber-certificates-latest (22 July 2024) The
173 // AlgorithmIdentifier for a ML-KEM public key MUST use one of the
174 // id-alg-ml-kem object identifiers [...]. The parameters field of the
175 // AlgorithmIdentifier for the ML-KEM public key MUST be absent.
177}
178
182
184 return m_public->mode().estimated_strength();
185}
186
187Kyber_PublicKey::Kyber_PublicKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) :
188 Kyber_PublicKey(key_bits, KyberMode(alg_id.oid())) {}
189
190Kyber_PublicKey::Kyber_PublicKey(std::span<const uint8_t> pub_key, KyberMode mode) {
191 m_public = std::make_shared<Kyber_PublicKeyInternal>(mode, KyberSerializedPublicKey(pub_key));
192}
193
195 m_public(std::make_shared<Kyber_PublicKeyInternal>(
196 other.m_public->mode(), other.m_public->t().clone(), other.m_public->rho())) {}
197
198std::vector<uint8_t> Kyber_PublicKey::raw_public_key_bits() const {
199 return m_public->public_key_bits_raw().get();
200}
201
202std::vector<uint8_t> Kyber_PublicKey::public_key_bits() const {
203 // Currently, there isn't a finalized definition of an ASN.1 structure for
204 // Kyber aka ML-KEM public keys. Therefore, we return the raw public key bits.
205 return raw_public_key_bits();
206}
207
209 return m_public->mode().canonical_parameter_set_identifier();
210}
211
213 // The length checks described in FIPS 203, Section 7.2 are already performed
214 // while decoding the public key. See constructor of Kyber_PublicKeyInternal.
215 // The decoding function KyberAlgos::byte_decode() also checks the range of
216 // the decoded values. The check below is added for completeness.
217
218 std::vector<uint8_t> test(m_public->mode().polynomial_vector_bytes());
220
221 const auto& serialized_pubkey = m_public->public_key_bits_raw();
222 return test.size() < serialized_pubkey.size() && std::equal(test.begin(), test.end(), serialized_pubkey.begin());
223}
224
225std::unique_ptr<Private_Key> Kyber_PublicKey::generate_another(RandomNumberGenerator& rng) const {
226 return std::make_unique<Kyber_PrivateKey>(rng, mode());
227}
228
229/**
230 * NIST FIPS 203, Algorithms 19 (ML-KEM.KeyGen)
231 */
238
239Kyber_PrivateKey::Kyber_PrivateKey(const AlgorithmIdentifier& alg_id, std::span<const uint8_t> key_bits) :
240 Kyber_PrivateKey(key_bits, KyberMode(alg_id.oid())) {}
241
242Kyber_PrivateKey::Kyber_PrivateKey(std::span<const uint8_t> sk, KyberMode m) {
244
245 if(mode.mode().is_ml_kem() && sk.size() == mode.seed_private_key_bytes()) {
246 std::tie(m_public, m_private) = Seed_Expanding_Keypair_Codec().decode_keypair(sk, std::move(mode));
247 } else if(sk.size() == mode.expanded_private_key_bytes()) {
248 std::tie(m_public, m_private) = Expanded_Keypair_Codec().decode_keypair(sk, std::move(mode));
249 } else if(!mode.mode().is_ml_kem() && sk.size() == mode.seed_private_key_bytes()) {
250 throw Invalid_Argument("Kyber round 3 private keys do not support the seed format");
251 } else {
252 throw Invalid_Argument("Private key does not have the correct byte count");
253 }
254}
255
256std::unique_ptr<Public_Key> Kyber_PrivateKey::public_key() const {
257 return std::make_unique<Kyber_PublicKey>(*this);
258}
259
263
267
269 // As we do not support loading a private key in extended format but rather
270 // always extract it from a 64-byte seed, these checks (as described in
271 // FIPS 203, Section 7.1) should never fail. Particularly, the length checks
272 // and the hash consistency check described in Section 7.2 and 7.3 are
273 // trivial when the private key is always extracted from a seed. The encaps/
274 // decaps roundtrip test is added for completeness.
275
276 if(!Kyber_PublicKey::check_key(rng, strong)) {
277 return false;
278 }
279
280 PK_KEM_Encryptor enc(*this, "Raw");
281 PK_KEM_Decryptor dec(*this, rng, "Raw");
282
283 const auto [c, K] = KEM_Encapsulation::destructure(enc.encrypt(rng));
284 const auto K_prime = dec.decrypt(c);
285
286 return K == K_prime;
287}
288
289std::unique_ptr<PK_Ops::KEM_Encryption> Kyber_PublicKey::create_kem_encryption_op(std::string_view params,
290 std::string_view provider) const {
291 if(provider.empty() || provider == "base") {
292#if defined(BOTAN_HAS_KYBER) || defined(BOTAN_HAS_KYBER_90S)
293 if(mode().is_kyber_round3()) {
294 return std::make_unique<Kyber_KEM_Encryptor>(m_public, params);
295 }
296#endif
297
298#if defined(BOTAN_HAS_ML_KEM)
299 if(mode().is_ml_kem()) {
300 return std::make_unique<ML_KEM_Encryptor>(m_public, params);
301 }
302#endif
303
305 }
306 throw Provider_Not_Found(algo_name(), provider);
307}
308
309std::unique_ptr<PK_Ops::KEM_Decryption> Kyber_PrivateKey::create_kem_decryption_op(RandomNumberGenerator& rng,
310 std::string_view params,
311 std::string_view provider) const {
312 BOTAN_UNUSED(rng);
313 if(provider.empty() || provider == "base") {
314#if defined(BOTAN_HAS_KYBER) || defined(BOTAN_HAS_KYBER_90S)
315 if(mode().is_kyber_round3()) {
316 return std::make_unique<Kyber_KEM_Decryptor>(m_private, m_public, params);
317 }
318#endif
319
320#if defined(BOTAN_HAS_ML_KEM)
321 if(mode().is_ml_kem()) {
322 return std::make_unique<ML_KEM_Decryptor>(m_private, m_public, params);
323 }
324#endif
325
327 }
328 throw Provider_Not_Found(algo_name(), provider);
329}
330
332 if(mode().is_ml_kem() && m_private->seed().d.has_value()) {
334 }
336}
337
340 throw Encoding_Error("Expanded private keys do not support the seed format");
341 }
342 const auto codec = [&]() -> std::unique_ptr<Kyber_Keypair_Codec> {
343 switch(format) {
345 return std::make_unique<Seed_Expanding_Keypair_Codec>();
347 return std::make_unique<Expanded_Keypair_Codec>();
348 }
350 }();
351 return codec->encode_keypair({m_public, m_private});
352}
353} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:120
#define BOTAN_ASSERT_UNREACHABLE()
Definition assert.h:139
Codec for expanded private keys (as specified in FIPS 203)
Definition kyber_keys.h:30
KyberInternalKeypair decode_keypair(std::span< const uint8_t > buffer, KyberConstants mode) const override
static std::pair< std::vector< uint8_t >, secure_vector< uint8_t > > destructure(KEM_Encapsulation &&kem)
Definition pubkey.h:569
static constexpr size_t SEED_BYTES
bool is_available() const
Definition kyber.cpp:141
bool is_kyber_round3() const
Definition kyber.cpp:136
std::string to_string() const
Definition kyber.cpp:99
bool is_modern() const
Definition kyber.cpp:128
OID object_identifier() const
Definition kyber.cpp:95
KyberMode(Mode mode)
Definition kyber.cpp:89
bool is_90s() const
Definition kyber.cpp:124
bool is_ml_kem() const
Definition kyber.cpp:132
Mode mode() const
Definition kyber.h:60
MlPrivateKeyFormat private_key_format() const
Definition kyber.cpp:331
secure_vector< uint8_t > private_key_bits_with_format(MlPrivateKeyFormat format) const
Definition kyber.cpp:338
std::unique_ptr< PK_Ops::KEM_Decryption > create_kem_decryption_op(RandomNumberGenerator &rng, std::string_view params, std::string_view provider) const override
Definition kyber.cpp:309
std::unique_ptr< Public_Key > public_key() const override
Definition kyber.cpp:256
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition kyber.cpp:268
Kyber_PrivateKey(RandomNumberGenerator &rng, KyberMode mode)
Definition kyber.cpp:232
secure_vector< uint8_t > raw_private_key_bits() const override
Definition kyber.cpp:260
secure_vector< uint8_t > private_key_bits() const override
Definition kyber.cpp:264
std::vector< uint8_t > public_key_bits() const override
Definition kyber.cpp:202
std::vector< uint8_t > raw_public_key_bits() const override
Definition kyber.cpp:198
bool check_key(RandomNumberGenerator &rng, bool strong) const override
Definition kyber.cpp:212
std::string algo_name() const override
Definition kyber.cpp:167
std::shared_ptr< Kyber_PublicKeyInternal > m_public
Definition kyber.h:143
size_t key_length() const override
Definition kyber.cpp:208
AlgorithmIdentifier algorithm_identifier() const override
Definition kyber.cpp:171
std::unique_ptr< PK_Ops::KEM_Encryption > create_kem_encryption_op(std::string_view params, std::string_view provider) const override
Definition kyber.cpp:289
KyberMode mode() const
Definition kyber.cpp:163
OID object_identifier() const override
Definition kyber.cpp:179
std::unique_ptr< Private_Key > generate_another(RandomNumberGenerator &rng) const final
Definition kyber.cpp:225
Kyber_PublicKey(std::span< const uint8_t > pub_key, KyberMode mode)
Definition kyber.cpp:190
size_t estimated_strength() const override
Definition kyber.cpp:183
static OID from_string(std::string_view str)
Definition asn1_oid.cpp:86
void random_vec(std::span< uint8_t > v)
Definition rng.h:196
Codec for private keys as 64-byte seeds: d || z.
Definition kyber_keys.h:37
KyberInternalKeypair decode_keypair(std::span< const uint8_t > buffer, KyberConstants mode) const override
void encode_polynomial_vector(std::span< uint8_t > out, const KyberPolyVecNTT &vec)
KyberInternalKeypair expand_keypair(KyberPrivateKeySeed seed, KyberConstants mode)
Strong< secure_vector< uint8_t >, struct KyberImplicitRejectionValue_ > KyberImplicitRejectionValue
Secret random value (called Z in the spec), used for implicit rejection in the decapsulation.
Definition kyber_types.h:42
constexpr T rho(T x)
Definition rotate.h:51
std::string fmt(std::string_view format, const T &... args)
Definition fmt.h:53
Strong< secure_vector< uint8_t >, struct KyberSeedRandomness_ > KyberSeedRandomness
Principal seed used to generate Kyber key pairs.
Definition kyber_types.h:33
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:65
MlPrivateKeyFormat
Byte encoding format of ML-KEM and ML-DSA the private key.
Definition kyber.h:81
@ Expanded
The expanded format, i.e., the format specified in FIPS-203/204.
Definition kyber.h:88
Strong< std::vector< uint8_t >, struct KyberSerializedPublicKey_ > KyberSerializedPublicKey
Public key in serialized form (t || rho)
Definition kyber_types.h:57