Remove cipher_list_by_id.

When parsing a cipher string, a cipher list is created, before being
duplicated and sorted - the second copy being stored as cipher_list_by_id.
This is done only so that a client can ensure that the cipher selected by
a server is in the cipher list. This is pretty pointless given that most
clients are short-lived and that we already had to iterate over the cipher
list in order to build the client hello. Additionally, any update to the
cipher list requires that cipher_list_by_id also be updated and kept in
sync.

Remove all of this and replace it with a simple linear scan - the overhead
of duplicating and sorting the cipher list likely exceeds that of a simple
linear scan over the cipher list (64 maximum, more typically ~9 or so).

ok beck@ tb@

7 files changed, 32 insertions, 89 deletions

diff --git a/lib/libssl/ssl_ciph.c b/lib/libssl/ssl_ciph.c
index 37417efc08d..4afbcf98963 100644
--- a/lib/libssl/ssl_ciph.c
+++ b/lib/libssl/ssl_ciph.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_ciph.c,v 1.117 2020/04/19 14:54:14 jsing Exp $ */
+/* $OpenBSD: ssl_ciph.c,v 1.118 2020/09/11 17:36:27 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -1184,12 +1184,11 @@ ssl_aes_is_accelerated(void)
 STACK_OF(SSL_CIPHER) *
 ssl_create_cipher_list(const SSL_METHOD *ssl_method,
     STACK_OF(SSL_CIPHER) **cipher_list,
-    STACK_OF(SSL_CIPHER) **cipher_list_by_id,
     const char *rule_str)
 {
 	int ok, num_of_ciphers, num_of_alias_max, num_of_group_aliases;
 	unsigned long disabled_mkey, disabled_auth, disabled_enc, disabled_mac, disabled_ssl;
-	STACK_OF(SSL_CIPHER) *cipherstack, *tmp_cipher_list;
+	STACK_OF(SSL_CIPHER) *cipherstack;
 	const char *rule_p;
 	CIPHER_ORDER *co_list = NULL, *head = NULL, *tail = NULL, *curr;
 	const SSL_CIPHER **ca_list = NULL;
@@ -1199,7 +1198,7 @@ ssl_create_cipher_list(const SSL_METHOD *ssl_method,
 	/*
 	 * Return with error if nothing to do.
 	 */
-	if (rule_str == NULL || cipher_list == NULL || cipher_list_by_id == NULL)
+	if (rule_str == NULL || cipher_list == NULL)
 		return NULL;
 
 	/*
@@ -1358,19 +1357,9 @@ ssl_create_cipher_list(const SSL_METHOD *ssl_method,
 
 	free(co_list);	/* Not needed any longer */
 
-	tmp_cipher_list = sk_SSL_CIPHER_dup(cipherstack);
-	if (tmp_cipher_list == NULL) {
-		sk_SSL_CIPHER_free(cipherstack);
-		return NULL;
-	}
 	sk_SSL_CIPHER_free(*cipher_list);
 	*cipher_list = cipherstack;
-	sk_SSL_CIPHER_free(*cipher_list_by_id);
-	*cipher_list_by_id = tmp_cipher_list;
-	(void)sk_SSL_CIPHER_set_cmp_func(*cipher_list_by_id,
-	    ssl_cipher_ptr_id_cmp);
 
-	sk_SSL_CIPHER_sort(*cipher_list_by_id);
 	return (cipherstack);
 }
 
diff --git a/lib/libssl/ssl_ciphers.c b/lib/libssl/ssl_ciphers.c
index d13ce7a9c5c..478238bd103 100644
--- a/lib/libssl/ssl_ciphers.c
+++ b/lib/libssl/ssl_ciphers.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: ssl_ciphers.c,v 1.5 2020/09/11 15:28:07 jsing Exp $ */
+/*	$OpenBSD: ssl_ciphers.c,v 1.6 2020/09/11 17:36:27 jsing Exp $ */
 /*
  * Copyright (c) 2015-2017 Doug Hogan <doug@openbsd.org>
  * Copyright (c) 2015-2018 Joel Sing <jsing@openbsd.org>
@@ -23,6 +23,19 @@
 #include "ssl_locl.h"
 
 int
+ssl_cipher_in_list(STACK_OF(SSL_CIPHER) *ciphers, const SSL_CIPHER *cipher)
+{
+	int i;
+
+	for (i = 0; i < sk_SSL_CIPHER_num(ciphers); i++) {
+		if (sk_SSL_CIPHER_value(ciphers, i)->id == cipher->id)
+			return 1;
+	}
+
+	return 0;
+}
+
+int
 ssl_cipher_allowed_in_version_range(const SSL_CIPHER *cipher, uint16_t min_ver,
     uint16_t max_ver)
 {
diff --git a/lib/libssl/ssl_clnt.c b/lib/libssl/ssl_clnt.c
index b6dcb8888db..68c7a835959 100644
--- a/lib/libssl/ssl_clnt.c
+++ b/lib/libssl/ssl_clnt.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_clnt.c,v 1.70 2020/07/03 04:12:50 tb Exp $ */
+/* $OpenBSD: ssl_clnt.c,v 1.71 2020/09/11 17:36:27 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -802,12 +802,11 @@ ssl3_get_server_hello(SSL *s)
 	uint16_t server_version, cipher_suite;
 	uint16_t min_version, max_version;
 	uint8_t compression_method;
-	STACK_OF(SSL_CIPHER) *sk;
 	const SSL_CIPHER *cipher;
 	const SSL_METHOD *method;
 	unsigned long alg_k;
 	size_t outlen;
-	int i, al, ok;
+	int al, ok;
 	long n;
 
 	s->internal->first_packet = 1;
@@ -981,9 +980,7 @@ ssl3_get_server_hello(SSL *s)
 		goto f_err;
 	}
 
-	sk = ssl_get_ciphers_by_id(s);
-	i = sk_SSL_CIPHER_find(sk, cipher);
-	if (i < 0) {
+	if (!ssl_cipher_in_list(SSL_get_ciphers(s), cipher)) {
 		/* we did not say we would use this cipher */
 		al = SSL_AD_ILLEGAL_PARAMETER;
 		SSLerror(s, SSL_R_WRONG_CIPHER_RETURNED);
diff --git a/lib/libssl/ssl_lib.c b/lib/libssl/ssl_lib.c
index 34ea6154a42..5bc759d483c 100644
--- a/lib/libssl/ssl_lib.c
+++ b/lib/libssl/ssl_lib.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_lib.c,v 1.224 2020/09/11 17:23:44 jsing Exp $ */
+/* $OpenBSD: ssl_lib.c,v 1.225 2020/09/11 17:36:27 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -230,7 +230,7 @@ SSL_CTX_set_ssl_version(SSL_CTX *ctx, const SSL_METHOD *meth)
 	ctx->method = meth;
 
 	ciphers = ssl_create_cipher_list(ctx->method, &ctx->cipher_list,
-	    &ctx->internal->cipher_list_by_id, SSL_DEFAULT_CIPHER_LIST);
+	    SSL_DEFAULT_CIPHER_LIST);
 	if (ciphers == NULL || sk_SSL_CIPHER_num(ciphers) <= 0) {
 		SSLerrorx(SSL_R_SSL_LIBRARY_HAS_NO_CIPHERS);
 		return (0);
@@ -529,9 +529,7 @@ SSL_free(SSL *s)
 
 	BUF_MEM_free(s->internal->init_buf);
 
-	/* add extra stuff */
 	sk_SSL_CIPHER_free(s->cipher_list);
-	sk_SSL_CIPHER_free(s->internal->cipher_list_by_id);
 
 	/* Make the next call work :-) */
 	if (s->session != NULL) {
@@ -1240,19 +1238,6 @@ ssl_cipher_id_cmp(const SSL_CIPHER *a, const SSL_CIPHER *b)
 		return ((l > 0) ? 1:-1);
 }
 
-int
-ssl_cipher_ptr_id_cmp(const SSL_CIPHER * const *ap,
-    const SSL_CIPHER * const *bp)
-{
-	long	l;
-
-	l = (*ap)->id - (*bp)->id;
-	if (l == 0L)
-		return (0);
-	else
-		return ((l > 0) ? 1:-1);
-}
-
 STACK_OF(SSL_CIPHER) *
 SSL_get_ciphers(const SSL *s)
 {
@@ -1307,24 +1292,6 @@ SSL_get1_supported_ciphers(SSL *s)
 	return NULL;
 }
 
-/*
- * Return a STACK of the ciphers available for the SSL and in order of
- * algorithm id.
- */
-STACK_OF(SSL_CIPHER) *
-ssl_get_ciphers_by_id(SSL *s)
-{
-	if (s != NULL) {
-		if (s->internal->cipher_list_by_id != NULL) {
-			return (s->internal->cipher_list_by_id);
-		} else if ((s->ctx != NULL) &&
-		    (s->ctx->internal->cipher_list_by_id != NULL)) {
-			return (s->ctx->internal->cipher_list_by_id);
-		}
-	}
-	return (NULL);
-}
-
 /* See if we have any ECC cipher suites. */
 int
 ssl_has_ecc_ciphers(SSL *s)
@@ -1384,11 +1351,9 @@ SSL_CTX_set_cipher_list(SSL_CTX *ctx, const char *str)
 	 * find a cipher matching the given rule string (for example if the
 	 * rule string specifies a cipher which has been disabled). This is not
 	 * an error as far as ssl_create_cipher_list is concerned, and hence
-	 * ctx->cipher_list and ctx->internal->cipher_list_by_id has been
-	 * updated.
+	 * ctx->cipher_list has been updated.
 	 */
-	ciphers = ssl_create_cipher_list(ctx->method, &ctx->cipher_list,
-	    &ctx->internal->cipher_list_by_id, str);
+	ciphers = ssl_create_cipher_list(ctx->method, &ctx->cipher_list, str);
 	if (ciphers == NULL) {
 		return (0);
 	} else if (sk_SSL_CIPHER_num(ciphers) == 0) {
@@ -1405,8 +1370,7 @@ SSL_set_cipher_list(SSL *s, const char *str)
 	STACK_OF(SSL_CIPHER) *ciphers;
 
 	/* See comment in SSL_CTX_set_cipher_list. */
-	ciphers = ssl_create_cipher_list(s->ctx->method, &s->cipher_list,
-	    &s->internal->cipher_list_by_id, str);
+	ciphers = ssl_create_cipher_list(s->ctx->method, &s->cipher_list, str);
 	if (ciphers == NULL) {
 		return (0);
 	} else if (sk_SSL_CIPHER_num(ciphers) == 0) {
@@ -1794,7 +1758,7 @@ SSL_CTX_new(const SSL_METHOD *meth)
 		goto err;
 
 	ssl_create_cipher_list(ret->method, &ret->cipher_list,
-	    &ret->internal->cipher_list_by_id, SSL_DEFAULT_CIPHER_LIST);
+	    SSL_DEFAULT_CIPHER_LIST);
 	if (ret->cipher_list == NULL ||
 	    sk_SSL_CIPHER_num(ret->cipher_list) <= 0) {
 		SSLerrorx(SSL_R_LIBRARY_HAS_NO_CIPHERS);
@@ -1891,7 +1855,6 @@ SSL_CTX_free(SSL_CTX *ctx)
 
 	X509_STORE_free(ctx->cert_store);
 	sk_SSL_CIPHER_free(ctx->cipher_list);
-	sk_SSL_CIPHER_free(ctx->internal->cipher_list_by_id);
 	ssl_cert_free(ctx->internal->cert);
 	sk_X509_NAME_pop_free(ctx->internal->client_CA, X509_NAME_free);
 	sk_X509_pop_free(ctx->extra_certs, X509_free);
@@ -2483,17 +2446,11 @@ SSL_dup(SSL *s)
 
 	X509_VERIFY_PARAM_inherit(ret->param, s->param);
 
-	/* dup the cipher_list and cipher_list_by_id stacks */
 	if (s->cipher_list != NULL) {
 		if ((ret->cipher_list =
 		    sk_SSL_CIPHER_dup(s->cipher_list)) == NULL)
 			goto err;
 	}
-	if (s->internal->cipher_list_by_id != NULL) {
-		if ((ret->internal->cipher_list_by_id =
-		    sk_SSL_CIPHER_dup(s->internal->cipher_list_by_id)) == NULL)
-			goto err;
-	}
 
 	/* Dup the client_CA list */
 	if (s->internal->client_CA != NULL) {
diff --git a/lib/libssl/ssl_locl.h b/lib/libssl/ssl_locl.h
index bfd0ea67337..df07ca68a67 100644
--- a/lib/libssl/ssl_locl.h
+++ b/lib/libssl/ssl_locl.h
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_locl.h,v 1.289 2020/09/11 15:28:08 jsing Exp $ */
+/* $OpenBSD: ssl_locl.h,v 1.290 2020/09/11 17:36:27 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -599,9 +599,6 @@ typedef struct ssl_ctx_internal_st {
 
 	CRYPTO_EX_DATA ex_data;
 
-	/* same cipher_list but sorted for lookup */
-	STACK_OF(SSL_CIPHER) *cipher_list_by_id;
-
 	struct cert_st /* CERT */ *cert;
 
 	/* Default values used when no per-SSL value is defined follow */
@@ -746,9 +743,6 @@ typedef struct ssl_internal_st {
 
 	int hit;		/* reusing a previous session */
 
-	/* crypto */
-	STACK_OF(SSL_CIPHER) *cipher_list_by_id;
-
 	/* These are the ones being used, the ones in SSL_SESSION are
 	 * the ones to be 'copied' into these ones */
 	int mac_flags;
@@ -1127,6 +1121,7 @@ int ssl_version_set_min(const SSL_METHOD *meth, uint16_t ver, uint16_t max_ver,
 int ssl_version_set_max(const SSL_METHOD *meth, uint16_t ver, uint16_t min_ver,
     uint16_t *out_ver);
 int ssl_downgrade_max_version(SSL *s, uint16_t *max_ver);
+int ssl_cipher_in_list(STACK_OF(SSL_CIPHER) *ciphers, const SSL_CIPHER *cipher);
 int ssl_cipher_allowed_in_version_range(const SSL_CIPHER *cipher,
     uint16_t min_ver, uint16_t max_ver);
 
@@ -1166,13 +1161,10 @@ int ssl_get_prev_session(SSL *s, CBS *session_id, CBS *ext_block,
 int ssl_cipher_id_cmp(const SSL_CIPHER *a, const SSL_CIPHER *b);
 SSL_CIPHER *OBJ_bsearch_ssl_cipher_id(SSL_CIPHER *key, SSL_CIPHER const *base,
     int num);
-int ssl_cipher_ptr_id_cmp(const SSL_CIPHER * const *ap,
-    const SSL_CIPHER * const *bp);
 int ssl_cipher_list_to_bytes(SSL *s, STACK_OF(SSL_CIPHER) *ciphers, CBB *cbb);
 STACK_OF(SSL_CIPHER) *ssl_bytes_to_cipher_list(SSL *s, CBS *cbs);
 STACK_OF(SSL_CIPHER) *ssl_create_cipher_list(const SSL_METHOD *meth,
-    STACK_OF(SSL_CIPHER) **pref, STACK_OF(SSL_CIPHER) **sorted,
-    const char *rule_str);
+    STACK_OF(SSL_CIPHER) **pref, const char *rule_str);
 void ssl_update_cache(SSL *s, int mode);
 int ssl_cipher_get_evp(const SSL_SESSION *s, const EVP_CIPHER **enc,
     const EVP_MD **md, int *mac_pkey_type, int *mac_secret_size);
diff --git a/lib/libssl/ssl_srvr.c b/lib/libssl/ssl_srvr.c
index 745b15aad05..cbf7c180b5d 100644
--- a/lib/libssl/ssl_srvr.c
+++ b/lib/libssl/ssl_srvr.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: ssl_srvr.c,v 1.81 2020/08/31 14:04:51 tb Exp $ */
+/* $OpenBSD: ssl_srvr.c,v 1.82 2020/09/11 17:36:27 jsing Exp $ */
 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
  * All rights reserved.
  *
@@ -1096,11 +1096,7 @@ ssl3_get_client_hello(SSL *s)
 			s->session->cipher = pref_cipher;
 
 			sk_SSL_CIPHER_free(s->cipher_list);
-			sk_SSL_CIPHER_free(s->internal->cipher_list_by_id);
-
 			s->cipher_list = sk_SSL_CIPHER_dup(s->session->ciphers);
-			s->internal->cipher_list_by_id =
-			    sk_SSL_CIPHER_dup(s->session->ciphers);
 		}
 	}
 
diff --git a/lib/libssl/tls13_client.c b/lib/libssl/tls13_client.c
index bd72db8be0c..35409d92bdc 100644
--- a/lib/libssl/tls13_client.c
+++ b/lib/libssl/tls13_client.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: tls13_client.c,v 1.66 2020/07/03 04:12:51 tb Exp $ */
+/* $OpenBSD: tls13_client.c,v 1.67 2020/09/11 17:36:27 jsing Exp $ */
 /*
  * Copyright (c) 2018, 2019 Joel Sing <jsing@openbsd.org>
  *
@@ -304,8 +304,7 @@ tls13_server_hello_process(struct tls13_ctx *ctx, CBS *cbs)
 	 * hello and that it matches the TLS version selected.
 	 */
 	cipher = ssl3_get_cipher_by_value(cipher_suite);
-	if (cipher == NULL ||
-	    sk_SSL_CIPHER_find(ssl_get_ciphers_by_id(s), cipher) < 0) {
+	if (cipher == NULL || !ssl_cipher_in_list(SSL_get_ciphers(s), cipher)) {
 		ctx->alert = TLS13_ALERT_ILLEGAL_PARAMETER;
 		goto err;
 	}