1 /*
2 * Copyright 2024-2025 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License"). You may not use
5 * this file except in compliance with the License. You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10 #include <openssl/core_dispatch.h>
11 #include <openssl/core_names.h>
12 #include <openssl/err.h>
13 #include <openssl/params.h>
14 #include <openssl/proverr.h>
15 #include <openssl/rand.h>
16 #include "ml_dsa_key.h"
17 #include "ml_dsa_matrix.h"
18 #include "ml_dsa_hash.h"
19 #include "internal/encoder.h"
20
ossl_ml_dsa_key_params(const ML_DSA_KEY * key)21 const ML_DSA_PARAMS *ossl_ml_dsa_key_params(const ML_DSA_KEY *key)
22 {
23 return key->params;
24 }
25
26 /* Returns the seed data or NULL if there is no seed */
ossl_ml_dsa_key_get_seed(const ML_DSA_KEY * key)27 const uint8_t *ossl_ml_dsa_key_get_seed(const ML_DSA_KEY *key)
28 {
29 return key->seed;
30 }
31
ossl_ml_dsa_key_get_prov_flags(const ML_DSA_KEY * key)32 int ossl_ml_dsa_key_get_prov_flags(const ML_DSA_KEY *key)
33 {
34 return key->prov_flags;
35 }
36
ossl_ml_dsa_set_prekey(ML_DSA_KEY * key,int flags_set,int flags_clr,const uint8_t * seed,size_t seed_len,const uint8_t * sk,size_t sk_len)37 int ossl_ml_dsa_set_prekey(ML_DSA_KEY *key, int flags_set, int flags_clr,
38 const uint8_t *seed, size_t seed_len,
39 const uint8_t *sk, size_t sk_len)
40 {
41 int ret = 0;
42
43 if (key == NULL
44 || key->pub_encoding != NULL
45 || key->priv_encoding != NULL
46 || (sk != NULL && sk_len != key->params->sk_len)
47 || (seed != NULL && seed_len != ML_DSA_SEED_BYTES)
48 || key->seed != NULL)
49 return 0;
50
51 if (sk != NULL
52 && (key->priv_encoding = OPENSSL_memdup(sk, sk_len)) == NULL)
53 goto end;
54 if (seed != NULL
55 && (key->seed = OPENSSL_memdup(seed, seed_len)) == NULL)
56 goto end;
57 key->prov_flags |= flags_set;
58 key->prov_flags &= ~flags_clr;
59 ret = 1;
60
61 end:
62 if (!ret) {
63 OPENSSL_free(key->priv_encoding);
64 OPENSSL_free(key->seed);
65 key->priv_encoding = key->seed = NULL;
66 }
67 return ret;
68 }
69
70 /**
71 * @brief Create a new ML_DSA_KEY object
72 *
73 * @param libctx A OSSL_LIB_CTX object used for fetching algorithms.
74 * @param propq The property query used for fetching algorithms
75 * @param alg The algorithm name associated with the key type
76 * @returns The new ML_DSA_KEY object on success, or NULL on malloc failure
77 */
ossl_ml_dsa_key_new(OSSL_LIB_CTX * libctx,const char * propq,int evp_type)78 ML_DSA_KEY *ossl_ml_dsa_key_new(OSSL_LIB_CTX *libctx, const char *propq,
79 int evp_type)
80 {
81 ML_DSA_KEY *ret;
82 const ML_DSA_PARAMS *params = ossl_ml_dsa_params_get(evp_type);
83
84 if (params == NULL)
85 return NULL;
86
87 ret = OPENSSL_zalloc(sizeof(*ret));
88 if (ret != NULL) {
89 ret->libctx = libctx;
90 ret->params = params;
91 ret->prov_flags = ML_DSA_KEY_PROV_FLAGS_DEFAULT;
92 ret->shake128_md = EVP_MD_fetch(libctx, "SHAKE-128", propq);
93 ret->shake256_md = EVP_MD_fetch(libctx, "SHAKE-256", propq);
94 if (ret->shake128_md == NULL || ret->shake256_md == NULL)
95 goto err;
96 }
97 return ret;
98 err:
99 ossl_ml_dsa_key_free(ret);
100 return NULL;
101 }
102
ossl_ml_dsa_key_pub_alloc(ML_DSA_KEY * key)103 int ossl_ml_dsa_key_pub_alloc(ML_DSA_KEY *key)
104 {
105 if (key->t1.poly != NULL)
106 return 0;
107 return vector_alloc(&key->t1, key->params->k);
108 }
109
ossl_ml_dsa_key_priv_alloc(ML_DSA_KEY * key)110 int ossl_ml_dsa_key_priv_alloc(ML_DSA_KEY *key)
111 {
112 size_t k = key->params->k, l = key->params->l;
113 POLY *poly;
114
115 if (key->s1.poly != NULL)
116 return 0;
117 if (!vector_alloc(&key->s1, l + 2 * k))
118 return 0;
119
120 poly = key->s1.poly;
121 key->s1.num_poly = l;
122 vector_init(&key->s2, poly + l, k);
123 vector_init(&key->t0, poly + l + k, k);
124 return 1;
125 }
126
127 /**
128 * @brief Destroy an ML_DSA_KEY object
129 */
ossl_ml_dsa_key_free(ML_DSA_KEY * key)130 void ossl_ml_dsa_key_free(ML_DSA_KEY *key)
131 {
132 if (key == NULL)
133 return;
134
135 EVP_MD_free(key->shake128_md);
136 EVP_MD_free(key->shake256_md);
137 ossl_ml_dsa_key_reset(key);
138 OPENSSL_free(key);
139 }
140
141 /**
142 * @brief Factory reset an ML_DSA_KEY object
143 */
ossl_ml_dsa_key_reset(ML_DSA_KEY * key)144 void ossl_ml_dsa_key_reset(ML_DSA_KEY *key)
145 {
146 /*
147 * The allocation for |s1.poly| subsumes those for |s2| and |t0|, which we
148 * must not access after |s1|'s poly is freed.
149 */
150 if (key->s1.poly != NULL) {
151 vector_zero(&key->s1);
152 vector_zero(&key->s2);
153 vector_zero(&key->t0);
154 vector_free(&key->s1);
155 key->s2.poly = NULL;
156 key->t0.poly = NULL;
157 }
158 /* The |t1| vector is public and allocated separately */
159 vector_free(&key->t1);
160 OPENSSL_cleanse(key->K, sizeof(key->K));
161 OPENSSL_free(key->pub_encoding);
162 key->pub_encoding = NULL;
163 if (key->priv_encoding != NULL)
164 OPENSSL_clear_free(key->priv_encoding, key->params->sk_len);
165 key->priv_encoding = NULL;
166 if (key->seed != NULL)
167 OPENSSL_clear_free(key->seed, ML_DSA_SEED_BYTES);
168 key->seed = NULL;
169 }
170
171 /**
172 * @brief Duplicate a key
173 *
174 * @param src A ML_DSA_KEY object to copy
175 * @param selection to select public and/or private components. Selecting the
176 * private key will also select the public key
177 * @returns The duplicated key, or NULL on failure.
178 */
ossl_ml_dsa_key_dup(const ML_DSA_KEY * src,int selection)179 ML_DSA_KEY *ossl_ml_dsa_key_dup(const ML_DSA_KEY *src, int selection)
180 {
181 ML_DSA_KEY *ret = NULL;
182
183 if (src == NULL)
184 return NULL;
185
186 /* Prekeys with just a seed or private key are not dupable */
187 if (src->pub_encoding == NULL
188 && (src->priv_encoding != NULL || src->seed != NULL))
189 return NULL;
190
191 ret = OPENSSL_zalloc(sizeof(*ret));
192 if (ret != NULL) {
193 ret->libctx = src->libctx;
194 ret->params = src->params;
195 ret->prov_flags = src->prov_flags;
196 if ((selection & OSSL_KEYMGMT_SELECT_KEYPAIR) != 0) {
197 if (src->pub_encoding != NULL) {
198 /* The public components are present if the private key is present */
199 memcpy(ret->rho, src->rho, sizeof(src->rho));
200 memcpy(ret->tr, src->tr, sizeof(src->tr));
201 if (src->t1.poly != NULL) {
202 if (!ossl_ml_dsa_key_pub_alloc(ret))
203 goto err;
204 vector_copy(&ret->t1, &src->t1);
205 }
206 if ((ret->pub_encoding = OPENSSL_memdup(src->pub_encoding,
207 src->params->pk_len))
208 == NULL)
209 goto err;
210 }
211 if ((selection & OSSL_KEYMGMT_SELECT_PRIVATE_KEY) != 0) {
212 if (src->priv_encoding != NULL) {
213 memcpy(ret->K, src->K, sizeof(src->K));
214 if (src->s1.poly != NULL) {
215 if (!ossl_ml_dsa_key_priv_alloc(ret))
216 goto err;
217 vector_copy(&ret->s1, &src->s1);
218 vector_copy(&ret->s2, &src->s2);
219 vector_copy(&ret->t0, &src->t0);
220 }
221 if ((ret->priv_encoding = OPENSSL_memdup(src->priv_encoding,
222 src->params->sk_len))
223 == NULL)
224 goto err;
225 }
226 if (src->seed != NULL
227 && (ret->seed = OPENSSL_memdup(src->seed,
228 ML_DSA_SEED_BYTES))
229 == NULL)
230 goto err;
231 }
232 }
233 EVP_MD_up_ref(src->shake128_md);
234 EVP_MD_up_ref(src->shake256_md);
235 ret->shake128_md = src->shake128_md;
236 ret->shake256_md = src->shake256_md;
237 }
238 return ret;
239 err:
240 ossl_ml_dsa_key_free(ret);
241 return NULL;
242 }
243
244 /**
245 * @brief Are 2 keys equal?
246 *
247 * To be equal the keys must have matching public or private key data and
248 * contain the same parameters.
249 * (Note that in OpenSSL that the private key always has a public key component).
250 *
251 * @param key1 A ML_DSA_KEY object
252 * @param key2 A ML_DSA_KEY object
253 * @param selection to select public and/or private component comparison.
254 * @returns 1 if the keys are equal otherwise it returns 0.
255 */
ossl_ml_dsa_key_equal(const ML_DSA_KEY * key1,const ML_DSA_KEY * key2,int selection)256 int ossl_ml_dsa_key_equal(const ML_DSA_KEY *key1, const ML_DSA_KEY *key2,
257 int selection)
258 {
259 int key_checked = 0;
260
261 if (key1->params != key2->params)
262 return 0;
263
264 if ((selection & OSSL_KEYMGMT_SELECT_KEYPAIR) != 0) {
265 if ((selection & OSSL_KEYMGMT_SELECT_PUBLIC_KEY) != 0) {
266 if (key1->pub_encoding != NULL && key2->pub_encoding != NULL) {
267 if (memcmp(key1->pub_encoding, key2->pub_encoding,
268 key1->params->pk_len)
269 != 0)
270 return 0;
271 key_checked = 1;
272 }
273 }
274 if (!key_checked
275 && (selection & OSSL_KEYMGMT_SELECT_PRIVATE_KEY) != 0) {
276 if (key1->priv_encoding != NULL && key2->priv_encoding != NULL) {
277 if (memcmp(key1->priv_encoding, key2->priv_encoding,
278 key1->params->sk_len)
279 != 0)
280 return 0;
281 key_checked = 1;
282 }
283 }
284 return key_checked;
285 }
286 return 1;
287 }
288
ossl_ml_dsa_key_has(const ML_DSA_KEY * key,int selection)289 int ossl_ml_dsa_key_has(const ML_DSA_KEY *key, int selection)
290 {
291 if ((selection & OSSL_KEYMGMT_SELECT_KEYPAIR) != 0) {
292 /* Note that the public key always exists if there is a private key */
293 if (ossl_ml_dsa_key_get_pub(key) == NULL)
294 return 0; /* No public key */
295 if ((selection & OSSL_KEYMGMT_SELECT_PRIVATE_KEY) != 0
296 && ossl_ml_dsa_key_get_priv(key) == NULL)
297 return 0; /* No private key */
298 return 1;
299 }
300 return 0;
301 }
302
303 /*
304 * @brief Given a key containing private key values for rho, s1 & s2
305 * generate the public value t and return the compressed values t1, t0.
306 *
307 * @param key A private key containing params, rh0, s1 & s2.
308 * @param md_ctx A EVP_MD_CTX used for sampling.
309 * @param t1 The returned polynomial encoding of the 10 MSB of each coefficient
310 * of the uncompressed public key polynomial t.
311 * @param t0 The returned polynomial encoding of the 13 LSB of each coefficient
312 * of the uncompressed public key polynomial t.
313 * @returns 1 on success, or 0 on failure.
314 */
public_from_private(const ML_DSA_KEY * key,EVP_MD_CTX * md_ctx,VECTOR * t1,VECTOR * t0)315 static int public_from_private(const ML_DSA_KEY *key, EVP_MD_CTX *md_ctx,
316 VECTOR *t1, VECTOR *t0)
317 {
318 int ret = 0;
319 const ML_DSA_PARAMS *params = key->params;
320 uint32_t k = params->k, l = params->l;
321 POLY *polys;
322 MATRIX a_ntt;
323 VECTOR s1_ntt;
324 VECTOR t;
325
326 polys = OPENSSL_malloc(sizeof(*polys) * (k + l + k * l));
327 if (polys == NULL)
328 return 0;
329
330 vector_init(&t, polys, k);
331 vector_init(&s1_ntt, t.poly + k, l);
332 matrix_init(&a_ntt, s1_ntt.poly + l, k, l);
333
334 /* Using rho generate A' = A in NTT form */
335 if (!matrix_expand_A(md_ctx, key->shake128_md, key->rho, &a_ntt))
336 goto err;
337
338 /* t = NTT_inv(A' * NTT(s1)) + s2 */
339 vector_copy(&s1_ntt, &key->s1);
340 vector_ntt(&s1_ntt);
341
342 matrix_mult_vector(&a_ntt, &s1_ntt, &t);
343 vector_ntt_inverse(&t);
344 vector_add(&t, &key->s2, &t);
345
346 /* Compress t */
347 vector_power2_round(&t, t1, t0);
348
349 /* Zeroize secret */
350 vector_zero(&s1_ntt);
351 ret = 1;
352 err:
353 OPENSSL_free(polys);
354 return ret;
355 }
356
ossl_ml_dsa_key_public_from_private(ML_DSA_KEY * key)357 int ossl_ml_dsa_key_public_from_private(ML_DSA_KEY *key)
358 {
359 int ret = 0;
360 VECTOR t0;
361 EVP_MD_CTX *md_ctx = NULL;
362
363 if (!vector_alloc(&t0, key->params->k)) /* t0 is already in the private key */
364 return 0;
365 ret = ((md_ctx = EVP_MD_CTX_new()) != NULL)
366 && ossl_ml_dsa_key_pub_alloc(key) /* allocate space for t1 */
367 && public_from_private(key, md_ctx, &key->t1, &t0)
368 && vector_equal(&t0, &key->t0) /* compare the generated t0 to the expected */
369 && ossl_ml_dsa_pk_encode(key)
370 && shake_xof(md_ctx, key->shake256_md,
371 key->pub_encoding, key->params->pk_len,
372 key->tr, sizeof(key->tr));
373 vector_free(&t0);
374 EVP_MD_CTX_free(md_ctx);
375 return ret;
376 }
377
ossl_ml_dsa_key_pairwise_check(const ML_DSA_KEY * key)378 int ossl_ml_dsa_key_pairwise_check(const ML_DSA_KEY *key)
379 {
380 int ret = 0;
381 VECTOR t1, t0;
382 POLY *polys = NULL;
383 uint32_t k = key->params->k;
384 EVP_MD_CTX *md_ctx = NULL;
385
386 if (key->pub_encoding == NULL || key->priv_encoding == 0)
387 return 0;
388
389 polys = OPENSSL_malloc(sizeof(*polys) * (2 * k));
390 if (polys == NULL)
391 return 0;
392 md_ctx = EVP_MD_CTX_new();
393 if (md_ctx == NULL)
394 goto err;
395
396 vector_init(&t1, polys, k);
397 vector_init(&t0, polys + k, k);
398 if (!public_from_private(key, md_ctx, &t1, &t0))
399 goto err;
400
401 ret = vector_equal(&t1, &key->t1) && vector_equal(&t0, &key->t0);
402 err:
403 EVP_MD_CTX_free(md_ctx);
404 OPENSSL_free(polys);
405 return ret;
406 }
407
408 /*
409 * @brief Generate a public-private key pair from a seed.
410 * See FIPS 204, Algorithm 6 ML-DSA.KeyGen_internal().
411 *
412 * @param out The generated key (which contains params on input)
413 *
414 * @returns 1 on success or 0 on failure.
415 */
keygen_internal(ML_DSA_KEY * out)416 static int keygen_internal(ML_DSA_KEY *out)
417 {
418 int ret = 0;
419 uint8_t augmented_seed[ML_DSA_SEED_BYTES + 2];
420 uint8_t expanded_seed[ML_DSA_RHO_BYTES + ML_DSA_PRIV_SEED_BYTES + ML_DSA_K_BYTES];
421 const uint8_t *const rho = expanded_seed; /* p = Public Random Seed */
422 const uint8_t *const priv_seed = expanded_seed + ML_DSA_RHO_BYTES;
423 const uint8_t *const K = priv_seed + ML_DSA_PRIV_SEED_BYTES;
424 const ML_DSA_PARAMS *params = out->params;
425 EVP_MD_CTX *md_ctx = NULL;
426
427 if (out->seed == NULL
428 || (md_ctx = EVP_MD_CTX_new()) == NULL
429 || !ossl_ml_dsa_key_pub_alloc(out)
430 || !ossl_ml_dsa_key_priv_alloc(out))
431 goto err;
432
433 /* augmented_seed = seed || k || l */
434 memcpy(augmented_seed, out->seed, ML_DSA_SEED_BYTES);
435 augmented_seed[ML_DSA_SEED_BYTES] = (uint8_t)params->k;
436 augmented_seed[ML_DSA_SEED_BYTES + 1] = (uint8_t)params->l;
437 /* Expand the seed into p[32], p'[64], K[32] */
438 if (!shake_xof(md_ctx, out->shake256_md, augmented_seed, sizeof(augmented_seed),
439 expanded_seed, sizeof(expanded_seed)))
440 goto err;
441
442 memcpy(out->rho, rho, sizeof(out->rho));
443 memcpy(out->K, K, sizeof(out->K));
444
445 ret = vector_expand_S(md_ctx, out->shake256_md, params->eta, priv_seed, &out->s1, &out->s2)
446 && public_from_private(out, md_ctx, &out->t1, &out->t0)
447 && ossl_ml_dsa_pk_encode(out)
448 && shake_xof(md_ctx, out->shake256_md, out->pub_encoding, out->params->pk_len,
449 out->tr, sizeof(out->tr))
450 && ossl_ml_dsa_sk_encode(out);
451
452 err:
453 if (out->seed != NULL && (out->prov_flags & ML_DSA_KEY_RETAIN_SEED) == 0) {
454 OPENSSL_clear_free(out->seed, ML_DSA_SEED_BYTES);
455 out->seed = NULL;
456 }
457 EVP_MD_CTX_free(md_ctx);
458 OPENSSL_cleanse(augmented_seed, sizeof(augmented_seed));
459 OPENSSL_cleanse(expanded_seed, sizeof(expanded_seed));
460 return ret;
461 }
462
ossl_ml_dsa_generate_key(ML_DSA_KEY * out)463 int ossl_ml_dsa_generate_key(ML_DSA_KEY *out)
464 {
465 size_t seed_len = ML_DSA_SEED_BYTES;
466 uint8_t *sk;
467 int ret;
468
469 if (out->seed == NULL) {
470 if ((out->seed = OPENSSL_malloc(seed_len)) == NULL)
471 return 0;
472 if (RAND_priv_bytes_ex(out->libctx, out->seed, seed_len, 0) <= 0) {
473 OPENSSL_free(out->seed);
474 out->seed = NULL;
475 return 0;
476 }
477 }
478 /* We're generating from a seed, drop private prekey encoding */
479 sk = out->priv_encoding;
480 out->priv_encoding = NULL;
481 if (sk == NULL) {
482 ret = keygen_internal(out);
483 } else {
484 if ((ret = keygen_internal(out)) != 0
485 && memcmp(out->priv_encoding, sk, out->params->sk_len) != 0) {
486 ret = 0;
487 ossl_ml_dsa_key_reset(out);
488 ERR_raise_data(ERR_LIB_PROV, PROV_R_INVALID_KEY,
489 "explicit %s private key does not match seed",
490 out->params->alg);
491 }
492 OPENSSL_free(sk);
493 }
494 return ret;
495 }
496
497 /**
498 * @brief This is used when a ML DSA key is used for an operation.
499 * This checks that the algorithm is the same (i.e. uses the same parameters)
500 *
501 * @param key A ML_DSA key to use for an operation.
502 * @param evp_type The algorithm nid associated with an operation
503 *
504 * @returns 1 if the algorithm matches, or 0 otherwise.
505 */
506
ossl_ml_dsa_key_matches(const ML_DSA_KEY * key,int evp_type)507 int ossl_ml_dsa_key_matches(const ML_DSA_KEY *key, int evp_type)
508 {
509 return (key->params->evp_type == evp_type);
510 }
511
512 /* Returns the public key data or NULL if there is no public key */
ossl_ml_dsa_key_get_pub(const ML_DSA_KEY * key)513 const uint8_t *ossl_ml_dsa_key_get_pub(const ML_DSA_KEY *key)
514 {
515 return key->pub_encoding;
516 }
517
518 /* Returns the encoded public key size */
ossl_ml_dsa_key_get_pub_len(const ML_DSA_KEY * key)519 size_t ossl_ml_dsa_key_get_pub_len(const ML_DSA_KEY *key)
520 {
521 return key->params->pk_len;
522 }
523
ossl_ml_dsa_key_get_collision_strength_bits(const ML_DSA_KEY * key)524 size_t ossl_ml_dsa_key_get_collision_strength_bits(const ML_DSA_KEY *key)
525 {
526 return key->params->bit_strength;
527 }
528
529 /* Returns the private key data or NULL if there is no private key */
ossl_ml_dsa_key_get_priv(const ML_DSA_KEY * key)530 const uint8_t *ossl_ml_dsa_key_get_priv(const ML_DSA_KEY *key)
531 {
532 return key->priv_encoding;
533 }
534
ossl_ml_dsa_key_get_priv_len(const ML_DSA_KEY * key)535 size_t ossl_ml_dsa_key_get_priv_len(const ML_DSA_KEY *key)
536 {
537 return key->params->sk_len;
538 }
539
ossl_ml_dsa_key_get_sig_len(const ML_DSA_KEY * key)540 size_t ossl_ml_dsa_key_get_sig_len(const ML_DSA_KEY *key)
541 {
542 return key->params->sig_len;
543 }
544
ossl_ml_dsa_key_get0_libctx(const ML_DSA_KEY * key)545 OSSL_LIB_CTX *ossl_ml_dsa_key_get0_libctx(const ML_DSA_KEY *key)
546 {
547 return key != NULL ? key->libctx : NULL;
548 }
549
ossl_ml_dsa_key_get_name(const ML_DSA_KEY * key)550 const char *ossl_ml_dsa_key_get_name(const ML_DSA_KEY *key)
551 {
552 return key->params->alg;
553 }
554