Randomize the order of TLS extensions

On creation of an SSL using SSL_new(), randomize the order in which the
extensions will be sent. There are several constraints: the PSK extension
must always come last. The order cannot be randomized on a per-message
basis as the strict interpretation of the standard chosen in the CH hashing
doesn't allow changing the order between first and second ClientHello.

Another constraint is that the current code calls callbacks directly on
parsing an extension, which means that the order callbacks are called
depends on the order in which the peer sent the extensions. This results
in breaking apache-httpd setups using virtual hosts with full ranomization
because virtual hosts don't work if the SNI is unknown at the time the
ALPN callback is called. So for the time being, we ensure that SNI always
precedes ALPN to avoid issues until this issue is fixed.

This is based on an idea by David Benjamin
https://boringssl-review.googlesource.com/c/boringssl/+/48045

Input & ok jsing

4 files changed, 71 insertions, 5 deletions

diff --git a/lib/libssl/ssl_lib.c b/lib/libssl/ssl_lib.c
index de4ef3fb5e7..68e60a54812 100644
--- a/lib/libssl/ssl_lib.c
+++ b/lib/libssl/ssl_lib.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_lib.c,v 1.308 2022/11/26 16:08:55 tb Exp $ */
+/* $OpenBSD: ssl_lib.c,v 1.309 2023/04/23 18:51:53 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -302,6 +302,9 @@ SSL_new(SSL_CTX *ctx)
 	CRYPTO_add(&ctx->references, 1, CRYPTO_LOCK_SSL_CTX);
 	s->initial_ctx = ctx;
 
+	if (!tlsext_randomize_build_order(s))
+		goto err;
+
 	if (ctx->tlsext_ecpointformatlist != NULL) {
 		s->tlsext_ecpointformatlist =
 		    calloc(ctx->tlsext_ecpointformatlist_length,
@@ -550,6 +553,8 @@ SSL_free(SSL *s)
 
 	ssl_cert_free(s->cert);
 
+	free(s->tlsext_build_order);
+
 	free(s->tlsext_hostname);
 	SSL_CTX_free(s->initial_ctx);
 
diff --git a/lib/libssl/ssl_local.h b/lib/libssl/ssl_local.h
index d510f80d8c8..1748eccbfd1 100644
--- a/lib/libssl/ssl_local.h
+++ b/lib/libssl/ssl_local.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_local.h,v 1.3 2022/12/26 07:31:44 jmc Exp $ */
+/* $OpenBSD: ssl_local.h,v 1.4 2023/04/23 18:51:53 tb Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -974,6 +974,7 @@ struct ssl_st {
 
 	unsigned int max_send_fragment;
 
+	const struct tls_extension **tlsext_build_order;
 	char *tlsext_hostname;
 
 	/* certificate status request info */
diff --git a/lib/libssl/ssl_tlsext.c b/lib/libssl/ssl_tlsext.c
index e576384118d..5ff61f39a51 100644
--- a/lib/libssl/ssl_tlsext.c
+++ b/lib/libssl/ssl_tlsext.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_tlsext.c,v 1.131 2022/11/26 16:08:56 tb Exp $ */
+/* $OpenBSD: ssl_tlsext.c,v 1.132 2023/04/23 18:51:53 tb Exp $ */
 /*
  * Copyright (c) 2016, 2017, 2019 Joel Sing <jsing@openbsd.org>
  * Copyright (c) 2017 Doug Hogan <doug@openbsd.org>
@@ -32,6 +32,8 @@
 #include "ssl_sigalgs.h"
 #include "ssl_tlsext.h"
 
+#define TLSEXT_TYPE_alpn TLSEXT_TYPE_application_layer_protocol_negotiation
+
 /*
  * Supported Application-Layer Protocol Negotiation - RFC 7301
  */
@@ -2239,6 +2241,63 @@ tlsext_funcs(const struct tls_extension *tlsext, int is_server)
 	return &tlsext->client;
 }
 
+int
+tlsext_randomize_build_order(SSL *s)
+{
+	size_t idx, new_idx, psk_idx;
+	size_t alpn_idx, sni_idx;
+
+	if ((s->tlsext_build_order = calloc(sizeof(*s->tlsext_build_order),
+	    N_TLS_EXTENSIONS)) == NULL)
+		return 0;
+
+	/* RFC 8446, section 4.2: PSK must be the last extension in the CH. */
+	psk_idx = N_TLS_EXTENSIONS - 1;
+	s->tlsext_build_order[psk_idx] = &tls_extensions[psk_idx];
+
+	/* Fisher-Yates shuffle with PSK fixed. */
+	for (idx = 0; idx < psk_idx; idx++) {
+		new_idx = arc4random_uniform(idx + 1);
+		s->tlsext_build_order[idx] = s->tlsext_build_order[new_idx];
+		s->tlsext_build_order[new_idx] = &tls_extensions[idx];
+	}
+
+	/*
+	 * XXX - Apache2 special until year 2025: ensure that SNI precedes ALPN
+	 * for clients so that virtual host setups work correctly.
+	 */
+
+	if (s->server)
+		return 1;
+
+	for (idx = 0; idx < N_TLS_EXTENSIONS; idx++) {
+		if (s->tlsext_build_order[idx]->type == TLSEXT_TYPE_alpn)
+			alpn_idx = idx;
+		if (s->tlsext_build_order[idx]->type == TLSEXT_TYPE_server_name)
+			sni_idx = idx;
+	}
+	if (alpn_idx < sni_idx) {
+		const struct tls_extension *tmp;
+
+		tmp = s->tlsext_build_order[alpn_idx];
+		s->tlsext_build_order[alpn_idx] = s->tlsext_build_order[sni_idx];
+		s->tlsext_build_order[sni_idx] = tmp;
+	}
+
+	return 1;
+}
+
+int
+tlsext_linearize_build_order(SSL *s)
+{
+	size_t idx;
+
+	for (idx = 0; idx < N_TLS_EXTENSIONS; idx++)
+		s->tlsext_build_order[idx] = &tls_extensions[idx];
+
+	return 1;
+}
+
 static int
 tlsext_build(SSL *s, int is_server, uint16_t msg_type, CBB *cbb)
 {
@@ -2255,7 +2314,7 @@ tlsext_build(SSL *s, int is_server, uint16_t msg_type, CBB *cbb)
 		return 0;
 
 	for (i = 0; i < N_TLS_EXTENSIONS; i++) {
-		tlsext = &tls_extensions[i];
+		tlsext = s->tlsext_build_order[i];
 		ext = tlsext_funcs(tlsext, is_server);
 
 		/* RFC 8446 Section 4.2 */
diff --git a/lib/libssl/ssl_tlsext.h b/lib/libssl/ssl_tlsext.h
index 7a41c8095db..da14f7fa94b 100644
--- a/lib/libssl/ssl_tlsext.h
+++ b/lib/libssl/ssl_tlsext.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_tlsext.h,v 1.32 2022/08/04 09:27:36 tb Exp $ */
+/* $OpenBSD: ssl_tlsext.h,v 1.33 2023/04/23 18:51:53 tb Exp $ */
 /*
  * Copyright (c) 2016, 2017 Joel Sing <jsing@openbsd.org>
  * Copyright (c) 2017 Doug Hogan <doug@openbsd.org>
@@ -41,6 +41,7 @@ int tlsext_server_build(SSL *s, uint16_t msg_type, CBB *cbb);
 int tlsext_server_parse(SSL *s, uint16_t msg_type, CBS *cbs, int *alert);
 
 int tlsext_extension_seen(SSL *s, uint16_t);
+int tlsext_randomize_build_order(SSL *s);
 
 __END_HIDDEN_DECLS