Botan 3.14.1
Crypto and TLS for C&
kyber_keys.cpp
Go to the documentation of this file.
1/*
2 * Crystals Kyber Internal Key Types
3 *
4 * (C) 2021-2024 Jack Lloyd
5 * (C) 2021-2022 Manuel Glaser and Michael Boric, Rohde & Schwarz Cybersecurity
6 * (C) 2021-2022 René Meusel and Hannes Rantzsch, neXenio GmbH
7 * (C) 2024 René Meusel, Fabian Albert, Rohde & Schwarz Cybersecurity
8 *
9 * Botan is released under the Simplified BSD License (see license.txt)
10 */
11
12#include <botan/internal/kyber_keys.h>
13
14#include <botan/asn1_obj.h>
15#include <botan/ber_dec.h>
16#include <botan/der_enc.h>
17#include <botan/exceptn.h>
18#include <botan/mem_ops.h>
19#include <botan/internal/buffer_slicer.h>
20#include <botan/internal/concat_util.h>
21#include <botan/internal/kyber_symmetric_primitives.h>
22
23namespace Botan {
24
25namespace {
26
27KyberSerializedPublicKey validate_public_key_length(KyberSerializedPublicKey public_key, size_t expected_length) {
28 if(public_key.size() != expected_length) {
29 throw Decoding_Error("Public key does not have the correct byte count");
30 }
31 return public_key;
32}
33
34} // namespace
35
36/**
37 * Key decoding as specified in Crystals Kyber (Version 3.01),
38 * Algorithms 4 (CPAPKE.KeyGen()), and 7 (CCAKEM.KeyGen())
39 *
40 * Public Key: pk := (encode(t) || rho)
41 * Secret Key: sk' := encode(s)
42 *
43 * Expanded Secret Key: sk := (sk' || pk || H(pk) || z)
44 */
46 const auto scope = CT::scoped_poison(sk);
47 BufferSlicer s(sk);
48
50 auto pub_key = s.copy<KyberSerializedPublicKey>(mode.public_key_bytes());
53
55
56 CT::unpoison_all(pub_key, puk_key_hash, skpv, z);
57
59 std::make_shared<Kyber_PublicKeyInternal>(mode, std::move(pub_key)),
60 std::make_shared<Kyber_PrivateKeyInternal>(
61 std::move(mode),
62 std::move(skpv),
63 KyberPrivateKeySeed{std::nullopt, // Reading from an expanded and encoded
64 // private key cannot reconstruct the
65 // original seed from key generation.
66 std::move(z)}),
67 };
68
69 BOTAN_ASSERT(keypair.first && keypair.second, "reading private key encoding");
70
71 const auto& computed_hash = keypair.first->H_public_key_bits_raw();
72 if(computed_hash.size() != puk_key_hash.size() ||
73 !std::equal(computed_hash.begin(), computed_hash.end(), puk_key_hash.begin())) {
74 throw Decoding_Error("Public key hash does not match the hash stored in the private key");
75 }
76
77 {
78 // Pairwise consistency check: the hash check above does not detect a
79 // secret vector s that does not belong to the public key (see RFC 9935,
80 // Appendix C.4, example 2). A deterministic K-PKE encryption of an
81 // arbitrary message with the public key must decrypt correctly with s.
82 //
83 // TODO(Botan4): reuse the ML_KEM_Encryptor/Decryptor helpers for this
84 // roundtrip check. The encryptor might need an additional
85 // interface to accept a fixed randomness value.
86 // See: https://github.com/randombit/botan/pull/5934#discussion_r4454849589
87 const auto& pk = *keypair.first;
88 const auto& priv = *keypair.second;
89 const auto& sym = pk.mode().symmetric_primitives();
90 const auto& pk_hash = pk.H_public_key_bits_raw();
91 const KyberMessage m(pk_hash.begin(), pk_hash.end());
92 const auto [K, r] = sym.G(m, pk_hash);
93 BOTAN_UNUSED(K);
94 const auto At = Kyber_Algos::sample_matrix(pk.rho(), true /* transposed */, pk.mode());
95 const auto ct = pk.indcpa_encrypt(m, r, At, pk.mode());
96 const auto m_prime = priv.indcpa_decrypt(ct);
97 if(m_prime.size() != m.size() || !constant_time_compare(m_prime, m)) {
98 throw Decoding_Error("ML-KEM expanded private key is inconsistent with its public key");
99 }
100 }
101
102 return keypair;
103}
104
106 BOTAN_ASSERT_NONNULL(keypair.first);
107 BOTAN_ASSERT_NONNULL(keypair.second);
108 const auto& mode = keypair.first->mode();
109 const auto scope = CT::scoped_poison(*keypair.second);
110 auto result = concat(Kyber_Algos::encode_polynomial_vector(keypair.second->s(), mode),
111 keypair.first->public_key_bits_raw(),
112 keypair.first->H_public_key_bits_raw(),
113 keypair.second->z());
114 CT::unpoison(result);
115 return result;
116}
117
119 KyberConstants mode) const {
120 BufferSlicer s(private_key);
121 auto seed = KyberPrivateKeySeed{
124 };
126 return Kyber_Algos::expand_keypair(std::move(seed), std::move(mode));
127}
128
130 BOTAN_ASSERT_NONNULL(keypair.second);
131 const auto& seed = keypair.second->seed();
132 BOTAN_ARG_CHECK(seed.d.has_value(), "Cannot encode keypair without the full private seed");
133 return concat<secure_vector<uint8_t>>(seed.d.value(), seed.z);
134}
135
136namespace {
137
138KyberInternalKeypair decode_ml_kem_seed(std::span<const uint8_t> seed, KyberConstants mode) {
139 if(seed.size() != mode.seed_private_key_bytes()) {
140 throw Decoding_Error("invalid length of ML-KEM private key seed");
141 }
142 return Seed_Expanding_Keypair_Codec().decode_keypair(seed, std::move(mode));
143}
144
145KyberInternalKeypair decode_ml_kem_expanded(std::span<const uint8_t> expanded, KyberConstants mode) {
146 if(expanded.size() != mode.expanded_private_key_bytes()) {
147 throw Decoding_Error("invalid length of ML-KEM expanded private key");
148 }
149 return Expanded_Keypair_Codec().decode_keypair(expanded, std::move(mode));
150}
151
152} // namespace
153
154KyberDecodedKeypair decode_ml_kem_private_key(std::span<const uint8_t> private_key, KyberConstants mode) {
155 BOTAN_ARG_CHECK(mode.mode().is_ml_kem(), "RFC 9935 private key encodings are only defined for ML-KEM");
156
157 if(private_key.size() == mode.seed_private_key_bytes()) {
158 // backwards compatibility (not RFC 9935 conforming) to the raw seed d || z
159 return {
160 .keypair = decode_ml_kem_seed(private_key, std::move(mode)),
161 .format = MlPrivateKeyFormat::Seed,
162 };
163 }
164 if(private_key.size() == mode.expanded_private_key_bytes()) {
165 // raw expanded key in the FIPS 203 dk encoding without ASN.1 wrapping (not RFC 9935
166 // conforming), as used e.g. by the NIST ACVP and Wycheproof test vectors. The length
167 // cannot collide with any of the RFC 9935 encodings.
168 return {
169 .keypair = decode_ml_kem_expanded(private_key, std::move(mode)),
171 };
172 }
173
174 auto dec = BER_Decoder(private_key, BER_Decoder::Limits::DER());
175
176 // RFC 9935, Section 6: the ASN.1 tag identifies the CHOICE alternative
177 const auto obj = [&]() {
178 try {
179 return dec.peek_next_object();
180 } catch(const Decoding_Error&) {
181 throw Decoding_Error("Invalid ML-KEM private key encoding");
182 }
183 }();
184
185 if(obj.type() == ASN1_Type(0) && obj.class_tag() == ASN1_Class::ContextSpecific) {
186 // "seed" alternative: [0] IMPLICIT OCTET STRING
188 dec.decode(seed, ASN1_Type::OctetString, ASN1_Type(0), ASN1_Class::ContextSpecific).verify_end();
189
190 return {
191 .keypair = decode_ml_kem_seed(seed, std::move(mode)),
192 .format = MlPrivateKeyFormat::Seed,
193 };
194 }
195
196 if(obj.type() == ASN1_Type::OctetString && obj.class_tag() == ASN1_Class::Universal) {
197 // "expandedKey" alternative: OCTET STRING
198 secure_vector<uint8_t> expanded;
199 dec.decode(expanded, ASN1_Type::OctetString).verify_end();
200
201 return {
202 .keypair = decode_ml_kem_expanded(expanded, std::move(mode)),
204 };
205 }
206
207 if(obj.type() == ASN1_Type::Sequence && obj.class_tag() == ASN1_Class::Constructed) {
208 // "both" alternative: SEQUENCE { seed OCTET STRING, expandedKey OCTET STRING }
210 secure_vector<uint8_t> expanded;
211 dec.start_sequence()
212 .decode(seed, ASN1_Type::OctetString)
213 .decode(expanded, ASN1_Type::OctetString)
214 .end_cons()
215 .verify_end();
216
217 if(expanded.size() != mode.expanded_private_key_bytes()) {
218 throw Decoding_Error("invalid length of ML-KEM expanded private key");
219 }
220
221 // RFC 9935, Section 8: the expanded key must be the expansion of the seed
222 auto keypair = decode_ml_kem_seed(seed, std::move(mode));
223 const auto expanded_from_seed = Expanded_Keypair_Codec().encode_keypair(keypair);
224 if(expanded_from_seed.size() != expanded.size() || !constant_time_compare(expanded_from_seed, expanded)) {
225 throw Decoding_Error("seed and expanded key in ML-KEM private key do not match");
226 }
227
228 return {
229 .keypair = std::move(keypair),
230 .format = MlPrivateKeyFormat::Both,
231 };
232 }
233
234 throw Decoding_Error("Invalid ML-KEM private key encoding");
235}
236
238 BOTAN_ASSERT_NONNULL(keypair.second);
239 BOTAN_ARG_CHECK(keypair.second->mode().mode().is_ml_kem(),
240 "RFC 9935 private key encodings are only defined for ML-KEM");
241 if(format != MlPrivateKeyFormat::Expanded && !keypair.second->seed().d.has_value()) {
242 throw Encoding_Error("ML-KEM private key does not contain the seed, cannot encode it in the requested format");
243 }
244
245 DER_Encoder der_enc;
246 switch(format) {
248 // RFC 9935 "seed" CHOICE alternative: [0] IMPLICIT OCTET STRING
249 der_enc.encode(Seed_Expanding_Keypair_Codec().encode_keypair(keypair),
251 ASN1_Type(0),
253 break;
255 // RFC 9935 "expandedKey" CHOICE alternative: OCTET STRING
256 der_enc.encode(Expanded_Keypair_Codec().encode_keypair(keypair), ASN1_Type::OctetString);
257 break;
259 // RFC 9935 "both" CHOICE alternative:
260 // SEQUENCE { seed OCTET STRING, expandedKey OCTET STRING }
261 der_enc.start_sequence()
263 .encode(Expanded_Keypair_Codec().encode_keypair(keypair), ASN1_Type::OctetString)
264 .end_cons();
265 break;
266 }
267
268 return der_enc.get_contents();
269}
270
272 m_mode(std::move(mode)),
273 m_public_key_bits_raw(validate_public_key_length(std::move(public_key), m_mode.public_key_bytes())),
274 m_H_public_key_bits_raw(m_mode.symmetric_primitives().H(m_public_key_bits_raw)),
275 m_t(Kyber_Algos::decode_polynomial_vector(
276 std::span{m_public_key_bits_raw}.first(m_mode.polynomial_vector_bytes()), m_mode)),
277 m_rho(std::span{m_public_key_bits_raw}.last(Botan::KyberConstants::SEED_BYTES)) {}
278
280 m_mode(std::move(mode)),
281 m_public_key_bits_raw(concat(Kyber_Algos::encode_polynomial_vector<std::vector<uint8_t>>(t, m_mode), rho)),
282 m_H_public_key_bits_raw(m_mode.symmetric_primitives().H(m_public_key_bits_raw)),
283 m_t(std::move(t)),
284 m_rho(std::move(rho)) {}
285
286/**
287 * NIST FIPS 203, Algorithm 14 (K-PKE.Encrypt)
288 *
289 * In contrast to FIPS 203, the matrix @p At is not sampled for every invocation,
290 * instead it is precomputed and passed in as a parameter. Similarly, the t^T is
291 * already decoded and available as a member variable. This allows to reuse these
292 * structures for multiple encryptions.
293 *
294 * The sampling loops spelled out in FIPS 203 are hidden in the sample_* functions.
295 */
299 const KyberPolyMat& At,
300 const KyberConstants& mode) const {
301 // The nonce N is handled internally by the PolynomialSampler
303 const auto y = ntt(ps.sample_polynomial_vector_cbd_eta1());
304 const auto [e1, e2] = ps.sample_polynomial_vector_and_poly_cbd_eta2();
305
306 auto u = inverse_ntt(At * y);
307 u += e1;
308 u.reduce();
309
310 const auto mu = Kyber_Algos::polynomial_from_message(m);
311 auto v = inverse_ntt(m_t * y);
312 v += e2;
313 v += mu;
314 v.reduce();
315
316 Kyber_Algos::compress_ciphertext(out_ct, u, v, m_mode);
317}
318
319/**
320 * NIST FIPS 203, Algorithm 15 (K-PKE.Decrypt)
321 *
322 * s^T is already decoded and available as a member variable. This allows to reuse
323 * the structure for multiple decryptions.
324 */
326 auto [u, v] = Kyber_Algos::decompress_ciphertext(ct, m_mode);
327 v -= inverse_ntt(m_s * ntt(std::move(u)));
328 v.reduce();
330}
331
332} // namespace Botan
#define BOTAN_UNUSED
Definition assert.h:151
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:82
#define BOTAN_ASSERT_NONNULL(ptr)
Definition assert.h:121
#define BOTAN_ARG_CHECK(expr, msg)
Definition assert.h:33
#define BOTAN_ASSERT(expr, assertion_made)
Definition assert.h:69
static Limits DER()
Definition ber_dec.h:44
auto copy(const size_t count)
std::span< const uint8_t > take(const size_t count)
secure_vector< uint8_t > get_contents()
Definition der_enc.cpp:161
DER_Encoder & start_sequence()
Definition der_enc.h:86
DER_Encoder & end_cons()
Definition der_enc.cpp:208
DER_Encoder & encode(bool b)
Definition der_enc.cpp:313
Codec for expanded private keys (as specified in FIPS 203).
Definition kyber_keys.h:31
secure_vector< uint8_t > encode_keypair(KyberInternalKeypair private_key) const override
KyberInternalKeypair decode_keypair(std::span< const uint8_t > buffer, KyberConstants mode) const override
static constexpr size_t SEED_BYTES
size_t public_key_bytes() const
byte length of an encoded public key
size_t seed_private_key_bytes() const
byte length of an private key encoded as the seed: d || z
size_t polynomial_vector_bytes() const
byte length of an encoded polynomial vector
size_t expanded_private_key_bytes() const
byte length of a private key with expanded encoding as defined
KyberMode mode() const
static constexpr size_t PUBLIC_KEY_HASH_BYTES
bool is_ml_kem() const
Definition kyber.cpp:128
KyberPolyVec sample_polynomial_vector_cbd_eta1()
Definition kyber_algos.h:70
std::pair< KyberPolyVec, KyberPoly > sample_polynomial_vector_and_poly_cbd_eta2()
Samples a polynomial vector and a single polynomial in one PRF batch.
Definition kyber_algos.h:86
KyberMessage indcpa_decrypt(StrongSpan< const KyberCompressedCiphertext > ct) const
const KyberPolyVecNTT & t() const
Definition kyber_keys.h:85
const KyberSeedRho & rho() const
Definition kyber_keys.h:87
void indcpa_encrypt(StrongSpan< KyberCompressedCiphertext > out_ct, StrongSpan< const KyberMessage > m, StrongSpan< const KyberEncryptionRandomness > r, const KyberPolyMat &At, const KyberConstants &mode) const
const KyberConstants & mode() const
Definition kyber_keys.h:89
Codec for private keys as 64-byte seeds: d || z.
Definition kyber_keys.h:38
KyberInternalKeypair decode_keypair(std::span< const uint8_t > buffer, KyberConstants mode) const override
secure_vector< uint8_t > encode_keypair(KyberInternalKeypair keypair) const override
size_type size() const noexcept(noexcept(this->get().size()))
constexpr auto scoped_poison(const Ts &... xs)
Definition ct_utils.h:222
constexpr void unpoison_all(const Ts &... ts)
Definition ct_utils.h:207
constexpr void unpoison(const T *p, size_t n)
Definition ct_utils.h:67
void encode_polynomial_vector(std::span< uint8_t > out, const KyberPolyVecNTT &vec)
KyberMessage polynomial_to_message(const KyberPoly &p)
KyberPolyMat sample_matrix(StrongSpan< const KyberSeedRho > seed, bool transposed, const KyberConstants &mode)
void compress_ciphertext(StrongSpan< KyberCompressedCiphertext > out, const KyberPolyVec &u, const KyberPoly &v, const KyberConstants &m_mode)
KyberInternalKeypair expand_keypair(KyberPrivateKeySeed seed, KyberConstants mode)
KyberPoly polynomial_from_message(StrongSpan< const KyberMessage > msg)
std::pair< KyberPolyVec, KyberPoly > decompress_ciphertext(StrongSpan< const KyberCompressedCiphertext > ct, const KyberConstants &mode)
KyberPolyVecNTT decode_polynomial_vector(std::span< const uint8_t > a, const 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
KyberDecodedKeypair decode_ml_kem_private_key(std::span< const uint8_t > private_key, KyberConstants mode)
Strong< secure_vector< uint8_t >, struct KyberMessage_ > KyberMessage
Random message value to be encrypted by the CPA-secure Kyber encryption scheme.
Definition kyber_types.h:45
ASN1_Type
Definition asn1_obj.h:47
secure_vector< uint8_t > encode_ml_kem_private_key(const KyberInternalKeypair &keypair, MlPrivateKeyFormat format)
Botan::CRYSTALS::PolynomialVector< KyberPolyTraits, Botan::CRYSTALS::Domain::NTT > KyberPolyVecNTT
Definition kyber_types.h:26
Strong< secure_vector< uint8_t >, struct KyberSeedRandomness_ > KyberSeedRandomness
Principal seed used to generate Kyber key pairs.
Definition kyber_types.h:33
Strong< std::vector< uint8_t >, struct KyberSeedRho_ > KyberSeedRho
Public seed value to generate the Kyber matrix A.
Definition kyber_types.h:36
constexpr auto concat(Rs &&... ranges)
Definition concat_util.h:95
std::vector< T, secure_allocator< T > > secure_vector
Definition secmem.h:128
std::pair< std::shared_ptr< const Kyber_PublicKeyInternal >, std::shared_ptr< const Kyber_PrivateKeyInternal > > KyberInternalKeypair
Definition kyber_types.h:73
bool constant_time_compare(std::span< const uint8_t > x, std::span< const uint8_t > y)
Definition mem_ops.cpp:17
Botan::CRYSTALS::PolynomialMatrix< KyberPolyTraits > KyberPolyMat
Definition kyber_types.h:27
Strong< std::vector< uint8_t >, struct KyberHashedPublicKey_ > KyberHashedPublicKey
Hash value of the serialized public key.
Definition kyber_types.h:60
Strong< std::vector< uint8_t >, struct KyberSerializedPublicKey_ > KyberSerializedPublicKey
Public key in serialized form (t || rho).
Definition kyber_types.h:57
A decoded private key together with the encoding format it was found in.
Definition kyber_keys.h:45