1 /* $OpenBSD: ssh-mldsa-eddsa.c,v 1.1 2026/06/14 03:59:34 djm Exp $ */
2 /*
3 * Copyright (c) 2026 Damien Miller <djm@mindrot.org>
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18 /* draft-miller-sshm-mldsa44-ed25519-composite-sigs-00 */
19
20 #include "includes.h"
21
22 #ifdef USE_MLDSA
23
24 #include <sys/types.h>
25 #include <stdint.h>
26 #include <string.h>
27 #include <stdlib.h>
28
29 #include "crypto_api.h"
30 #include "sshbuf.h"
31 #include "ssherr.h"
32 #include "digest.h"
33 #define SSHKEY_INTERNAL
34 #include "sshkey.h"
35 #include "log.h"
36
37 #define COMPOSITE_PREFIX "CompositeAlgorithmSignatures2025"
38 #define COMPOSITE_LABEL "COMPSIG-MLDSA44-Ed25519-SHA512"
39 #define SSH_MLDSA44_ED25519_ALG_NAME "ssh-mldsa44-ed25519@openssh.com"
40
41 /*
42 * raw_* functions implement the draft-ietf-lamps-pq-composite-sigs-18
43 * composite signature scheme. These are exposed (i.e. not static) so
44 * we can test them separately in unittests/crypto.
45 */
46
47 int
crypto_sign_mldsa44_ed25519_keygen(uint8_t pk[MLDSA44_ED25519_PK_SZ],uint8_t sk[MLDSA44_ED25519_SK_SZ])48 crypto_sign_mldsa44_ed25519_keygen(uint8_t pk[MLDSA44_ED25519_PK_SZ],
49 uint8_t sk[MLDSA44_ED25519_SK_SZ])
50 {
51 uint8_t mldsa_seed[32], ed25519_seed[32];
52 int r;
53
54 arc4random_buf(mldsa_seed, sizeof(mldsa_seed));
55 arc4random_buf(ed25519_seed, sizeof(ed25519_seed));
56
57 r = crypto_sign_mldsa44_ed25519_keygen_seeded(pk, sk, mldsa_seed,
58 ed25519_seed);
59 explicit_bzero(mldsa_seed, sizeof(mldsa_seed));
60 explicit_bzero(ed25519_seed, sizeof(ed25519_seed));
61 return r;
62 }
63
64 int
crypto_sign_mldsa44_ed25519_keygen_seeded(uint8_t pk[MLDSA44_ED25519_PK_SZ],uint8_t sk[MLDSA44_ED25519_SK_SZ],const uint8_t mldsa_seed[32],const uint8_t ed25519_seed[32])65 crypto_sign_mldsa44_ed25519_keygen_seeded(uint8_t pk[MLDSA44_ED25519_PK_SZ],
66 uint8_t sk[MLDSA44_ED25519_SK_SZ], const uint8_t mldsa_seed[32],
67 const uint8_t ed25519_seed[32])
68 {
69 uint8_t ed25519_pk[32], ed25519_sk[64];
70 uint8_t mldsa_sk[MLDSA44_SECRETKEYBYTES];
71 int ret = -1;
72
73 if (crypto_sign_mldsa44_keypair_seeded(pk, mldsa_sk, mldsa_seed) != 0)
74 goto out;
75 if (crypto_sign_ed25519_keypair_from_seed(ed25519_pk, ed25519_sk,
76 ed25519_seed) != 0)
77 goto out;
78
79 /* Serialize PK: mldsaPK || ed25519PK */
80 memcpy(pk + MLDSA44_PUBLICKEYBYTES, ed25519_pk, 32);
81
82 /* Serialize SK: mldsaSeed || ed25519Seed */
83 memcpy(sk, mldsa_seed, 32);
84 memcpy(sk + 32, ed25519_seed, 32);
85
86 /* success */
87 ret = 0;
88 out:
89 explicit_bzero(mldsa_sk, sizeof(mldsa_sk));
90 explicit_bzero(ed25519_sk, sizeof(ed25519_sk));
91 return ret;
92 }
93
94 static int
construct_m_prime(uint8_t ** m_primep,size_t * m_prime_lenp,const uint8_t * msg,size_t msglen,const uint8_t * ctx,size_t ctxlen)95 construct_m_prime(uint8_t **m_primep, size_t *m_prime_lenp,
96 const uint8_t *msg, size_t msglen,
97 const uint8_t *ctx, size_t ctxlen)
98 {
99 int r;
100 uint8_t hash[64];
101 struct sshbuf *m_prime;
102
103 *m_primep = NULL;
104 *m_prime_lenp = 0;
105
106 if (ctxlen > 255)
107 return SSH_ERR_INVALID_ARGUMENT;
108 if ((r = ssh_digest_memory(SSH_DIGEST_SHA512, msg, msglen,
109 hash, sizeof(hash))) != 0)
110 return r;
111 if ((m_prime = sshbuf_new()) == NULL)
112 return SSH_ERR_ALLOC_FAIL;
113 if ((r = sshbuf_put(m_prime, COMPOSITE_PREFIX,
114 sizeof(COMPOSITE_PREFIX) - 1)) != 0 ||
115 (r = sshbuf_put(m_prime, COMPOSITE_LABEL,
116 sizeof(COMPOSITE_LABEL) - 1)) != 0 ||
117 (r = sshbuf_put_u8(m_prime, (uint8_t)ctxlen)) != 0 ||
118 (r = sshbuf_put(m_prime, ctx, ctxlen)) != 0 ||
119 (r = sshbuf_put(m_prime, hash, sizeof(hash))) != 0) {
120 sshbuf_free(m_prime);
121 return r;
122 }
123 if ((*m_primep = malloc(sshbuf_len(m_prime))) == NULL) {
124 sshbuf_free(m_prime);
125 return SSH_ERR_ALLOC_FAIL;
126 }
127 memcpy(*m_primep, sshbuf_ptr(m_prime), sshbuf_len(m_prime));
128 *m_prime_lenp = sshbuf_len(m_prime);
129 /* success */
130 sshbuf_free(m_prime);
131 return 0;
132 }
133
134 int
crypto_sign_mldsa44_ed25519_sign(uint8_t sig[MLDSA44_ED25519_SIG_SZ],const uint8_t * msg,size_t msglen,const uint8_t * ctx,size_t ctxlen,const uint8_t sk[MLDSA44_ED25519_SK_SZ])135 crypto_sign_mldsa44_ed25519_sign(uint8_t sig[MLDSA44_ED25519_SIG_SZ],
136 const uint8_t *msg, size_t msglen,
137 const uint8_t *ctx, size_t ctxlen,
138 const uint8_t sk[MLDSA44_ED25519_SK_SZ])
139 {
140 uint8_t *m_prime = NULL;
141 size_t m_prime_len = 0;
142 uint8_t mldsa_sk[MLDSA44_SECRETKEYBYTES];
143 uint8_t mldsa_pk_dummy[MLDSA44_PUBLICKEYBYTES];
144 uint8_t ed25519_pk[32], ed25519_sk[64];
145 uint8_t mldsa_rnd[32];
146 unsigned long long smlen;
147 int r = -1;
148
149 if (construct_m_prime(&m_prime, &m_prime_len, msg, msglen,
150 ctx, ctxlen) != 0)
151 return -1;
152
153 /* Expand ML-DSA key from seed */
154 if (crypto_sign_mldsa44_keypair_seeded(mldsa_pk_dummy, mldsa_sk, sk) != 0)
155 goto out;
156
157 /* Sign with ML-DSA */
158 arc4random_buf(mldsa_rnd, sizeof(mldsa_rnd));
159 if (crypto_sign_mldsa44_seeded(sig, m_prime, m_prime_len,
160 (const uint8_t *)COMPOSITE_LABEL, sizeof(COMPOSITE_LABEL) - 1,
161 mldsa_sk, mldsa_rnd) != 0)
162 goto out;
163
164 /* Expand Ed25519 key from seed */
165 if (crypto_sign_ed25519_keypair_from_seed(ed25519_pk, ed25519_sk,
166 sk + 32) != 0)
167 goto out;
168
169 /* Sign with Ed25519 */
170 uint8_t *sm = malloc(m_prime_len + 64);
171 if (sm == NULL)
172 goto out;
173
174 if (crypto_sign_ed25519(sm, &smlen, m_prime, m_prime_len,
175 ed25519_sk) != 0) {
176 free(sm);
177 goto out;
178 }
179 memcpy(sig + MLDSA44_SIGBYTES, sm, 64);
180 free(sm);
181
182 r = 0;
183 out:
184 free(m_prime);
185 explicit_bzero(mldsa_rnd, sizeof(mldsa_rnd));
186 explicit_bzero(mldsa_sk, sizeof(mldsa_sk));
187 explicit_bzero(ed25519_sk, sizeof(ed25519_sk));
188 return r;
189 }
190
191 int
crypto_sign_mldsa44_ed25519_verify(const uint8_t sig[MLDSA44_ED25519_SIG_SZ],const uint8_t * msg,size_t msglen,const uint8_t * ctx,size_t ctxlen,const uint8_t pk[MLDSA44_ED25519_PK_SZ])192 crypto_sign_mldsa44_ed25519_verify(const uint8_t sig[MLDSA44_ED25519_SIG_SZ],
193 const uint8_t *msg, size_t msglen,
194 const uint8_t *ctx, size_t ctxlen,
195 const uint8_t pk[MLDSA44_ED25519_PK_SZ])
196 {
197 uint8_t *m_prime = NULL;
198 size_t m_prime_len = 0;
199 uint8_t *sm = NULL, *m = NULL;
200 unsigned long long smlen, mlen;
201 int r = -1;
202
203 if (construct_m_prime(&m_prime, &m_prime_len, msg, msglen,
204 ctx, ctxlen) != 0)
205 return -1;
206
207 /* Verify ML-DSA */
208 if (crypto_sign_mldsa44_verify(sig, m_prime, m_prime_len,
209 (const uint8_t *)COMPOSITE_LABEL, sizeof(COMPOSITE_LABEL) - 1,
210 pk) != 0)
211 goto out;
212
213 /* Verify Ed25519 */
214 smlen = m_prime_len + 64;
215 mlen = smlen;
216 if ((sm = malloc(smlen)) == NULL || (m = malloc(mlen)) == NULL)
217 goto out;
218 memcpy(sm, sig + MLDSA44_SIGBYTES, 64);
219 memcpy(sm + 64, m_prime, m_prime_len);
220
221 if (crypto_sign_ed25519_open(m, &mlen, sm, smlen,
222 pk + MLDSA44_PUBLICKEYBYTES) != 0)
223 goto out;
224 if (mlen != m_prime_len)
225 goto out;
226
227 r = 0;
228 out:
229 free(m_prime);
230 free(sm);
231 free(m);
232 return r;
233 }
234
235 /* sshkey integration */
236
237 static void
ssh_mldsa44_ed25519_cleanup(struct sshkey * k)238 ssh_mldsa44_ed25519_cleanup(struct sshkey *k)
239 {
240 freezero(k->mldsa_ed25519_pk, MLDSA44_ED25519_PK_SZ);
241 freezero(k->mldsa_ed25519_sk, MLDSA44_ED25519_SK_SZ);
242 k->mldsa_ed25519_pk = NULL;
243 k->mldsa_ed25519_sk = NULL;
244 }
245
246 static int
ssh_mldsa44_ed25519_equal(const struct sshkey * a,const struct sshkey * b)247 ssh_mldsa44_ed25519_equal(const struct sshkey *a, const struct sshkey *b)
248 {
249 if (a->mldsa_ed25519_pk == NULL || b->mldsa_ed25519_pk == NULL)
250 return 0;
251 if (memcmp(a->mldsa_ed25519_pk, b->mldsa_ed25519_pk,
252 MLDSA44_ED25519_PK_SZ) != 0)
253 return 0;
254 return 1;
255 }
256
257 static int
ssh_mldsa44_ed25519_serialize_public(const struct sshkey * key,struct sshbuf * b,enum sshkey_serialize_rep opts)258 ssh_mldsa44_ed25519_serialize_public(const struct sshkey *key, struct sshbuf *b,
259 enum sshkey_serialize_rep opts)
260 {
261 int r;
262
263 if (key->mldsa_ed25519_pk == NULL)
264 return SSH_ERR_INVALID_ARGUMENT;
265 if ((r = sshbuf_put_string(b, key->mldsa_ed25519_pk,
266 MLDSA44_ED25519_PK_SZ)) != 0)
267 return r;
268
269 return 0;
270 }
271
272 static int
ssh_mldsa44_ed25519_serialize_private(const struct sshkey * key,struct sshbuf * b,enum sshkey_serialize_rep opts)273 ssh_mldsa44_ed25519_serialize_private(const struct sshkey *key, struct sshbuf *b,
274 enum sshkey_serialize_rep opts)
275 {
276 int r;
277
278 if (key->mldsa_ed25519_sk == NULL)
279 return SSH_ERR_INVALID_ARGUMENT;
280 if (!sshkey_is_cert(key)) {
281 if ((r = ssh_mldsa44_ed25519_serialize_public(key,
282 b, opts)) != 0)
283 return r;
284 }
285 if ((r = sshbuf_put_string(b, key->mldsa_ed25519_sk,
286 MLDSA44_ED25519_SK_SZ)) != 0)
287 return r;
288
289 return 0;
290 }
291
292 static int
ssh_mldsa44_ed25519_deserialize_public(const char * ktype,struct sshbuf * b,struct sshkey * key)293 ssh_mldsa44_ed25519_deserialize_public(const char *ktype, struct sshbuf *b,
294 struct sshkey *key)
295 {
296 u_char *pk = NULL;
297 size_t len = 0;
298 int r;
299
300 if ((r = sshbuf_get_string(b, &pk, &len)) != 0)
301 return r;
302 if (len != MLDSA44_ED25519_PK_SZ) {
303 freezero(pk, len);
304 return SSH_ERR_INVALID_FORMAT;
305 }
306 key->mldsa_ed25519_pk = pk;
307 return 0;
308 }
309
310 static int
ssh_mldsa44_ed25519_deserialize_private(const char * ktype,struct sshbuf * b,struct sshkey * key)311 ssh_mldsa44_ed25519_deserialize_private(const char *ktype, struct sshbuf *b,
312 struct sshkey *key)
313 {
314 int r;
315 size_t sklen = 0;
316 u_char *sk = NULL;
317
318 if (!sshkey_is_cert(key)) {
319 if ((r = ssh_mldsa44_ed25519_deserialize_public(ktype,
320 b, key)) != 0)
321 return r;
322 }
323 if ((r = sshbuf_get_string(b, &sk, &sklen)) != 0)
324 goto out;
325 if (sklen != MLDSA44_ED25519_SK_SZ) {
326 r = SSH_ERR_INVALID_FORMAT;
327 goto out;
328 }
329 key->mldsa_ed25519_sk = sk;
330 sk = NULL; /* transferred */
331 r = 0;
332 out:
333 freezero(sk, sklen);
334 return r;
335 }
336
337 static int
ssh_mldsa44_ed25519_generate(struct sshkey * k,int bits)338 ssh_mldsa44_ed25519_generate(struct sshkey *k, int bits)
339 {
340 free(k->mldsa_ed25519_pk);
341 free(k->mldsa_ed25519_sk);
342 k->mldsa_ed25519_pk = NULL;
343 k->mldsa_ed25519_sk = NULL;
344 if ((k->mldsa_ed25519_pk = malloc(MLDSA44_ED25519_PK_SZ)) == NULL ||
345 (k->mldsa_ed25519_sk = malloc(MLDSA44_ED25519_SK_SZ)) == NULL) {
346 free(k->mldsa_ed25519_pk);
347 return SSH_ERR_ALLOC_FAIL;
348 }
349 if (crypto_sign_mldsa44_ed25519_keygen(k->mldsa_ed25519_pk,
350 k->mldsa_ed25519_sk) != 0) {
351 free(k->mldsa_ed25519_pk);
352 free(k->mldsa_ed25519_sk);
353 return SSH_ERR_CRYPTO_ERROR;
354 }
355 return 0;
356 }
357
358 static int
ssh_mldsa44_ed25519_copy_public(const struct sshkey * from,struct sshkey * to)359 ssh_mldsa44_ed25519_copy_public(const struct sshkey *from, struct sshkey *to)
360 {
361 if (from->mldsa_ed25519_pk == NULL)
362 return SSH_ERR_INVALID_ARGUMENT;
363 if ((to->mldsa_ed25519_pk = malloc(MLDSA44_ED25519_PK_SZ)) == NULL)
364 return SSH_ERR_ALLOC_FAIL;
365 memcpy(to->mldsa_ed25519_pk, from->mldsa_ed25519_pk,
366 MLDSA44_ED25519_PK_SZ);
367 return 0;
368 }
369
370 static int
ssh_mldsa44_ed25519_sign(struct sshkey * key,u_char ** sigp,size_t * lenp,const u_char * data,size_t datalen,const char * alg,const char * sk_provider,const char * sk_pin,u_int compat)371 ssh_mldsa44_ed25519_sign(struct sshkey *key,
372 u_char **sigp, size_t *lenp, const u_char *data, size_t datalen,
373 const char *alg, const char *sk_provider, const char *sk_pin,
374 u_int compat)
375 {
376 u_char sig[MLDSA44_ED25519_SIG_SZ];
377 struct sshbuf *b = NULL;
378 int r = SSH_ERR_INTERNAL_ERROR;
379
380 if (lenp != NULL)
381 *lenp = 0;
382 if (sigp != NULL)
383 *sigp = NULL;
384
385 if (key == NULL ||
386 sshkey_type_plain(key->type) != KEY_MLDSA44_ED25519 ||
387 key->mldsa_ed25519_sk == NULL)
388 return SSH_ERR_INVALID_ARGUMENT;
389
390 if (crypto_sign_mldsa44_ed25519_sign(sig, data, datalen, NULL, 0,
391 key->mldsa_ed25519_sk) != 0) {
392 r = SSH_ERR_CRYPTO_ERROR;
393 goto out;
394 }
395
396 if ((b = sshbuf_new()) == NULL) {
397 r = SSH_ERR_ALLOC_FAIL;
398 goto out;
399 }
400 if ((r = sshbuf_put_cstring(b, SSH_MLDSA44_ED25519_ALG_NAME)) != 0 ||
401 (r = sshbuf_put_string(b, sig, sizeof(sig))) != 0)
402 goto out;
403
404 if (sigp != NULL) {
405 if ((*sigp = malloc(sshbuf_len(b))) == NULL) {
406 r = SSH_ERR_ALLOC_FAIL;
407 goto out;
408 }
409 memcpy(*sigp, sshbuf_ptr(b), sshbuf_len(b));
410 }
411 if (lenp != NULL)
412 *lenp = sshbuf_len(b);
413 r = 0;
414 out:
415 sshbuf_free(b);
416 explicit_bzero(sig, sizeof(sig));
417 return r;
418 }
419
420 static int
ssh_mldsa44_ed25519_verify(const struct sshkey * key,const u_char * sig,size_t siglen,const u_char * data,size_t dlen,const char * alg,u_int compat,struct sshkey_sig_details ** detailsp)421 ssh_mldsa44_ed25519_verify(const struct sshkey *key,
422 const u_char *sig, size_t siglen, const u_char *data, size_t dlen,
423 const char *alg, u_int compat, struct sshkey_sig_details **detailsp)
424 {
425 struct sshbuf *b = NULL;
426 char *ktype = NULL;
427 const u_char *sigblob;
428 size_t len;
429 int r;
430
431 if (key == NULL ||
432 sshkey_type_plain(key->type) != KEY_MLDSA44_ED25519 ||
433 key->mldsa_ed25519_pk == NULL ||
434 sig == NULL || siglen == 0)
435 return SSH_ERR_INVALID_ARGUMENT;
436
437 if ((b = sshbuf_from(sig, siglen)) == NULL)
438 return SSH_ERR_ALLOC_FAIL;
439 if ((r = sshbuf_get_cstring(b, &ktype, NULL)) != 0 ||
440 (r = sshbuf_get_string_direct(b, &sigblob, &len)) != 0)
441 goto out;
442 if (strcmp(SSH_MLDSA44_ED25519_ALG_NAME, ktype) != 0) {
443 r = SSH_ERR_KEY_TYPE_MISMATCH;
444 goto out;
445 }
446 if (sshbuf_len(b) != 0) {
447 r = SSH_ERR_UNEXPECTED_TRAILING_DATA;
448 goto out;
449 }
450 if (len != MLDSA44_ED25519_SIG_SZ) {
451 r = SSH_ERR_INVALID_FORMAT;
452 goto out;
453 }
454
455 if (crypto_sign_mldsa44_ed25519_verify(sigblob, data, dlen, NULL, 0,
456 key->mldsa_ed25519_pk) != 0) {
457 r = SSH_ERR_SIGNATURE_INVALID;
458 goto out;
459 }
460
461 r = 0;
462 out:
463 sshbuf_free(b);
464 free(ktype);
465 return r;
466 }
467
468 const struct sshkey_impl_funcs sshkey_mldsa44_ed25519_funcs = {
469 /* .size = */ NULL,
470 /* .alloc = */ NULL,
471 /* .cleanup = */ ssh_mldsa44_ed25519_cleanup,
472 /* .equal = */ ssh_mldsa44_ed25519_equal,
473 /* .ssh_serialize_public = */ ssh_mldsa44_ed25519_serialize_public,
474 /* .ssh_deserialize_public = */ ssh_mldsa44_ed25519_deserialize_public,
475 /* .ssh_serialize_private = */ ssh_mldsa44_ed25519_serialize_private,
476 /* .ssh_deserialize_private = */ ssh_mldsa44_ed25519_deserialize_private,
477 /* .generate = */ ssh_mldsa44_ed25519_generate,
478 /* .copy_public = */ ssh_mldsa44_ed25519_copy_public,
479 /* .sign = */ ssh_mldsa44_ed25519_sign,
480 /* .verify = */ ssh_mldsa44_ed25519_verify,
481 };
482
483 const struct sshkey_impl sshkey_mldsa44_ed25519_impl = {
484 /* .name = */ "ssh-mldsa44-ed25519@openssh.com",
485 /* .shortname = */ "MLDSA44-ED25519",
486 /* .sigalg = */ NULL,
487 /* .type = */ KEY_MLDSA44_ED25519,
488 /* .nid = */ 0,
489 /* .cert = */ 0,
490 /* .sigonly = */ 0,
491 /* .keybits = */ 256,
492 /* .funcs = */ &sshkey_mldsa44_ed25519_funcs,
493 };
494
495 const struct sshkey_impl sshkey_mldsa44_ed25519_cert_impl = {
496 /* .name = */ "ssh-mldsa44-ed25519-cert-v01@openssh.com",
497 /* .shortname = */ "MLDSA44-ED25519-CERT",
498 /* .sigalg = */ NULL,
499 /* .type = */ KEY_MLDSA44_ED25519_CERT,
500 /* .nid = */ 0,
501 /* .cert = */ 1,
502 /* .sigonly = */ 0,
503 /* .keybits = */ 256,
504 /* .funcs = */ &sshkey_mldsa44_ed25519_funcs,
505 };
506 #endif /* USE_MLDSA */
507