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/src/lib/libssl/ssl_ciph.c b/src/lib/libssl/ssl_ciph.c
index 37417efc08..4afbcf9896 100644
--- a/src/lib/libssl/ssl_ciph.c
+++ b/src/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/src/lib/libssl/ssl_ciphers.c b/src/lib/libssl/ssl_ciphers.c
index d13ce7a9c5..478238bd10 100644
--- a/src/lib/libssl/ssl_ciphers.c
+++ b/src/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/src/lib/libssl/ssl_clnt.c b/src/lib/libssl/ssl_clnt.c
index b6dcb8888d..68c7a83595 100644
--- a/src/lib/libssl/ssl_clnt.c
+++ b/src/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/src/lib/libssl/ssl_lib.c b/src/lib/libssl/ssl_lib.c
index 34ea6154a4..5bc759d483 100644
--- a/src/lib/libssl/ssl_lib.c
+++ b/src/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/src/lib/libssl/ssl_locl.h b/src/lib/libssl/ssl_locl.h
index bfd0ea6733..df07ca68a6 100644
--- a/src/lib/libssl/ssl_locl.h
+++ b/src/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/src/lib/libssl/ssl_srvr.c b/src/lib/libssl/ssl_srvr.c
index 745b15aad0..cbf7c180b5 100644
--- a/src/lib/libssl/ssl_srvr.c
+++ b/src/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/src/lib/libssl/tls13_client.c b/src/lib/libssl/tls13_client.c
index bd72db8be0..35409d92bd 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.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;
         }