Hook up X25519MKLEM768 to the TLS 1.3 handshake

This does the following:

1) Adds a second key share prediction to the TLS 1.3 handshake.
   We only add one as we are unlikely to want to send more than
   one PQ one, and one classical one and are unlikely to waste
   bytes on a second PQ algorithm (anything that wants something
   else that we support can HRR to get it)

2) Adds X25519MLKEM768 (4588) to our list of supported groups.
   We add this to our preferred client and server key shares for TLS 1.3
   and we now have a separate list for TLS 1.2 which does not do this,
   cleaning up the old "full list" from the comments.

3) Updates the golden magic numbers in the regression tests to allow
   for the above two things changing the handshake, so the regress
   tests pass.

With this you can successfully hybrid PQ with servers and clients
that support it.

ok tb@ kenjiro@

5 files changed, 100 insertions, 39 deletions

diff --git a/src/lib/libssl/s3_lib.c b/src/lib/libssl/s3_lib.c
index 86b32aec15..bcf26bec40 100644
--- a/src/lib/libssl/s3_lib.c
+++ b/src/lib/libssl/s3_lib.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: s3_lib.c,v 1.257 2024/07/23 14:40:53 jsing Exp $ */
+/* $OpenBSD: s3_lib.c,v 1.258 2025/12/04 21:16:17 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -1286,6 +1286,7 @@ ssl3_free(SSL *s)
         sk_X509_pop_free(s->s3->hs.peer_certs_no_leaf, X509_free);
         sk_X509_pop_free(s->s3->hs.verified_chain, X509_free);
         tls_key_share_free(s->s3->hs.key_share);
+        tls_key_share_free(s->s3->hs.tls13.key_share);
 
         tls13_secrets_destroy(s->s3->hs.tls13.secrets);
         freezero(s->s3->hs.tls13.cookie, s->s3->hs.tls13.cookie_len);
@@ -1337,6 +1338,8 @@ ssl3_clear(SSL *s)
 
         tls_key_share_free(s->s3->hs.key_share);
         s->s3->hs.key_share = NULL;
+        tls_key_share_free(s->s3->hs.tls13.key_share);
+        s->s3->hs.tls13.key_share = NULL;
 
         tls13_secrets_destroy(s->s3->hs.tls13.secrets);
         s->s3->hs.tls13.secrets = NULL;
diff --git a/src/lib/libssl/ssl_local.h b/src/lib/libssl/ssl_local.h
index 9921c3a730..7942c36dbd 100644
--- a/src/lib/libssl/ssl_local.h
+++ b/src/lib/libssl/ssl_local.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_local.h,v 1.34 2025/10/24 09:23:06 tb Exp $ */
+/* $OpenBSD: ssl_local.h,v 1.35 2025/12/04 21:16:17 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -490,6 +490,9 @@ typedef struct ssl_handshake_tls13_st {
         /* Certificate selected for use (static pointer). */
         const SSL_CERT_PKEY *cpk;
 
+        /* Client's extra predicted key share */
+        struct tls_key_share *key_share;
+
         /* Version proposed by peer server. */
         uint16_t server_version;
 
diff --git a/src/lib/libssl/ssl_tlsext.c b/src/lib/libssl/ssl_tlsext.c
index dcd9a31205..d879b3304e 100644
--- a/src/lib/libssl/ssl_tlsext.c
+++ b/src/lib/libssl/ssl_tlsext.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_tlsext.c,v 1.158 2025/12/04 21:03:42 beck Exp $ */
+/* $OpenBSD: ssl_tlsext.c,v 1.159 2025/12/04 21:16:17 beck Exp $ */
 /*
  * Copyright (c) 2016, 2017, 2019 Joel Sing <jsing@openbsd.org>
  * Copyright (c) 2017 Doug Hogan <doug@openbsd.org>
@@ -1445,7 +1445,7 @@ tlsext_keyshare_client_needs(SSL *s, uint16_t msg_type)
 static int
 tlsext_keyshare_client_build(SSL *s, uint16_t msg_type, CBB *cbb)
 {
-        CBB client_shares, key_exchange;
+        CBB client_shares, key_exchange, key_exchange2;
 
         if (!CBB_add_u16_length_prefixed(cbb, &client_shares))
                 return 0;
@@ -1458,6 +1458,31 @@ tlsext_keyshare_client_build(SSL *s, uint16_t msg_type, CBB *cbb)
         if (!tls_key_share_public(s->s3->hs.key_share, &key_exchange))
                 return 0;
 
+        /*
+         * We wish to include a second key share prediction in a TLS 1.3 client
+         * hello if we have more than one preferred group. We never wish to do
+         * this in response to a server selected group (Either from a TLS 1.2
+         * server, or from a hello retry request after having negotiated TLS
+         * 1.3).
+         *
+         * Therefore we only do this if we have not yet negotiated
+         * a version, and our max version could negotiate TLS 1.3.
+         */
+        if (s->s3->hs.negotiated_tls_version == 0 &&
+            s->s3->hs.our_max_tls_version >= TLS1_3_VERSION) {
+                if (s->s3->hs.tls13.key_share != NULL) {
+                        if (!CBB_add_u16(&client_shares,
+                            tls_key_share_group(s->s3->hs.tls13.key_share)))
+                                return 0;
+                        if (!CBB_add_u16_length_prefixed(&client_shares,
+                            &key_exchange2))
+                                return 0;
+                        if (!tls_key_share_public(s->s3->hs.tls13.key_share,
+                            &key_exchange2))
+                                return 0;
+                }
+        }
+
         if (!CBB_flush(cbb))
                 return 0;
 
@@ -1687,10 +1712,32 @@ tlsext_keyshare_client_process(SSL *s, uint16_t msg_type, CBS *cbs, int *alert)
                 *alert = SSL_AD_INTERNAL_ERROR;
                 return 0;
         }
+
+        if (s->s3->hs.tls13.server_version >= TLS1_3_VERSION &&
+            tls_key_share_group(s->s3->hs.key_share) != group &&
+            s->s3->hs.tls13.key_share != NULL &&
+            tls_key_share_group(s->s3->hs.tls13.key_share) == group) {
+                /*
+                 * Server chose our second key share prediction, switch to it,
+                 * and discard the first one.
+                 */
+                tls_key_share_free(s->s3->hs.key_share);
+                s->s3->hs.key_share = s->s3->hs.tls13.key_share;
+                s->s3->hs.tls13.key_share = NULL;
+        }
+
         if (tls_key_share_group(s->s3->hs.key_share) != group) {
                 *alert = SSL_AD_INTERNAL_ERROR;
                 return 0;
         }
+
+        /*
+         * Discard our now unused second key share prediction if we had made one
+         * with our initial 1.3 client hello
+         */
+        tls_key_share_free(s->s3->hs.tls13.key_share);
+        s->s3->hs.tls13.key_share = NULL;
+
         if (!tls_key_share_client_peer_public(s->s3->hs.key_share,
             &key_exchange, &decode_error, NULL)) {
                 if (!decode_error)
diff --git a/src/lib/libssl/t1_lib.c b/src/lib/libssl/t1_lib.c
index 57cd180d09..912bea592a 100644
--- a/src/lib/libssl/t1_lib.c
+++ b/src/lib/libssl/t1_lib.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: t1_lib.c,v 1.206 2025/05/31 15:17:11 tb Exp $ */
+/* $OpenBSD: t1_lib.c,v 1.207 2025/12/04 21:16:17 beck Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -306,6 +306,11 @@ static const struct supported_group nid_list[] = {
                 .nid = NID_X25519,
                 .bits = 128,
         },
+        {
+                .group_id = 4588,
+                .nid = NID_X25519MLKEM768,
+                .bits = 128,
+        },
 };
 
 #define NID_LIST_LEN (sizeof(nid_list) / sizeof(nid_list[0]))
@@ -322,41 +327,21 @@ static const uint8_t ecformats_default[] = {
         TLSEXT_ECPOINTFORMAT_uncompressed,
 };
 
-#if 0
-static const uint16_t ecgroups_list[] = {
+static const uint16_t ecgroups_tls12_client_default[] = {
         29,                     /* X25519 (29) */
-        14,                     /* sect571r1 (14) */
-        13,                     /* sect571k1 (13) */
-        25,                     /* secp521r1 (25) */
-        28,                     /* brainpoolP512r1 (28) */
-        11,                     /* sect409k1 (11) */
-        12,                     /* sect409r1 (12) */
-        27,                     /* brainpoolP384r1 (27) */
+        23,                     /* secp256r1 (23) */
         24,                     /* secp384r1 (24) */
-        9,                      /* sect283k1 (9) */
-        10,                     /* sect283r1 (10) */
-        26,                     /* brainpoolP256r1 (26) */
-        22,                     /* secp256k1 (22) */
+        25,                     /* secp521r1 (25) */
+};
+
+static const uint16_t ecgroups_tls12_server_default[] = {
+        29,                     /* X25519 (29) */
         23,                     /* secp256r1 (23) */
-        8,                      /* sect239k1 (8) */
-        6,                      /* sect233k1 (6) */
-        7,                      /* sect233r1 (7) */
-        20,                     /* secp224k1 (20) */
-        21,                     /* secp224r1 (21) */
-        4,                      /* sect193r1 (4) */
-        5,                      /* sect193r2 (5) */
-        18,                     /* secp192k1 (18) */
-        19,                     /* secp192r1 (19) */
-        1,                      /* sect163k1 (1) */
-        2,                      /* sect163r1 (2) */
-        3,                      /* sect163r2 (3) */
-        15,                     /* secp160k1 (15) */
-        16,                     /* secp160r1 (16) */
-        17,                     /* secp160r2 (17) */
+        24,                     /* secp384r1 (24) */
 };
-#endif
 
 static const uint16_t ecgroups_client_default[] = {
+        4588,                   /* X25519MLKEM768 (4588) */
         29,                     /* X25519 (29) */
         23,                     /* secp256r1 (23) */
         24,                     /* secp384r1 (24) */
@@ -364,6 +349,7 @@ static const uint16_t ecgroups_client_default[] = {
 };
 
 static const uint16_t ecgroups_server_default[] = {
+        4588,                   /* X25519MLKEM768 (4588) */
         29,                     /* X25519 (29) */
         23,                     /* secp256r1 (23) */
         24,                     /* secp384r1 (24) */
@@ -478,11 +464,21 @@ tls1_get_group_list(const SSL *s, int client_groups, const uint16_t **pgroups,
                 return;
 
         if (!s->server) {
-                *pgroups = ecgroups_client_default;
-                *pgroupslen = sizeof(ecgroups_client_default) / 2;
+                if (s->s3->hs.our_max_tls_version >= TLS1_3_VERSION) {
+                        *pgroups = ecgroups_client_default;
+                        *pgroupslen = sizeof(ecgroups_client_default) / 2;
+                } else {
+                        *pgroups = ecgroups_tls12_client_default;
+                        *pgroupslen = sizeof(ecgroups_tls12_client_default) / 2;
+                }
         } else {
-                *pgroups = ecgroups_server_default;
-                *pgroupslen = sizeof(ecgroups_server_default) / 2;
+                if (s->s3->hs.our_max_tls_version >= TLS1_3_VERSION) {
+                        *pgroups = ecgroups_server_default;
+                        *pgroupslen = sizeof(ecgroups_server_default) / 2;
+                } else {
+                        *pgroups = ecgroups_tls12_server_default;
+                        *pgroupslen = sizeof(ecgroups_tls12_server_default) / 2;
+                }
         }
 }
 
diff --git a/src/lib/libssl/tls13_client.c b/src/lib/libssl/tls13_client.c
index b0a285694d..21d3960796 100644
--- a/src/lib/libssl/tls13_client.c
+++ b/src/lib/libssl/tls13_client.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: tls13_client.c,v 1.105 2025/12/04 21:03:42 beck Exp $ */
+/* $OpenBSD: tls13_client.c,v 1.106 2025/12/04 21:16:17 beck Exp $ */
 /*
  * Copyright (c) 2018, 2019 Joel Sing <jsing@openbsd.org>
  *
@@ -56,6 +56,18 @@ tls13_client_init(struct tls13_ctx *ctx)
         if (!tls_key_share_client_generate(ctx->hs->key_share))
                 return 0;
 
+        /*
+         * Generate a second key share prediction if we have another
+         * supported group
+         */
+        if (groups_len > 1) {
+                if ((ctx->hs->tls13.key_share = tls_key_share_new(groups[1])) ==
+                    NULL)
+                        return 0;
+                if (!tls_key_share_client_generate(ctx->hs->tls13.key_share))
+                        return 0;
+        }
+
         arc4random_buf(s->s3->client_random, SSL3_RANDOM_SIZE);
 
         /*