kex: Do not ignore keys in known_hosts files

Previously, if the SSH_OPTIONS_HOSTKEYS option was set by any mean,
including the client configuration file, the keys in known_hosts files
wouldn't be considered before advertising the list of wanted host keys.

This could result in the client requesting the server to provide a
signature using a key not present in the known_hosts files (e.g. when
the first wanted algorithm in SSH_OPTIONS_HOSTKEYS is not present in the
known_hosts files), causing a host key mismatch and possible key
rejection.

Now, the keys present in the known_hosts files are prioritized over the
other wanted keys.  This do not change the fact that only keys of types
present in the list set in SSH_OPTIONS_HOSTKEYS will be accepted and
prioritized following the order defined by such list.

The new wanted list of hostkeys is given by:
 - The keys present in known_hosts files, ordered by preference defined
   in SSH_OPTIONS_HOSTKEYS.  If the option is not set, a default order
   of preference is used.
 - The other keys present in the same option are appended without adding
   duplicates.  If the option is not set, the default list of keys is
   used.

Fixes: T156

Signed-off-by: Anderson Toshiyuki Sasaki <ansasaki@redhat.com>
Reviewed-by: Jakub Jelen <jjelen@redhat.com>

2 files changed, 223 insertions, 90 deletions

diff --git a/src/kex.c b/src/kex.c
index 6ea5e8ba..0d4cad6d 100644
--- a/src/kex.c
+++ b/src/kex.c
@@ -561,103 +561,94 @@ void ssh_list_kex(struct ssh_kex_struct *kex) {
 
 /**
  * @internal
+ *
  * @brief selects the hostkey mechanisms to be chosen for the key exchange,
- * as some hostkey mechanisms may be present in known_hosts file and preferred
+ * as some hostkey mechanisms may be present in known_hosts files.
+ *
  * @returns a cstring containing a comma-separated list of hostkey methods.
  *          NULL if no method matches
  */
 char *ssh_client_select_hostkeys(ssh_session session)
 {
-    char methods_buffer[128]={0};
-    char tail_buffer[128]={0};
+    const char *wanted = NULL;
+    char *wanted_without_certs = NULL;
+    char *known_hosts_algorithms = NULL;
+    char *known_hosts_ordered = NULL;
     char *new_hostkeys = NULL;
-    static const char *preferred_hostkeys[] = {
-        "ssh-ed25519",
-        "ecdsa-sha2-nistp521",
-        "ecdsa-sha2-nistp384",
-        "ecdsa-sha2-nistp256",
-        "rsa-sha2-512",
-        "rsa-sha2-256",
-        "ssh-rsa",
-#ifdef HAVE_DSA
-        "ssh-dss",
-#endif
-        NULL
-    };
-    struct ssh_list *algo_list = NULL;
-    struct ssh_iterator *it = NULL;
-    size_t algo_count;
-    int needcomma = 0;
-    size_t i, len;
-
-    algo_list = ssh_known_hosts_get_algorithms(session);
-    if (algo_list == NULL) {
-        return NULL;
+    char *fips_hostkeys = NULL;
+
+    wanted = session->opts.wanted_methods[SSH_HOSTKEYS];
+    if (wanted == NULL) {
+        if (ssh_fips_mode()) {
+            wanted = ssh_kex_get_fips_methods(SSH_HOSTKEYS);
+        } else {
+            wanted = ssh_kex_get_default_methods(SSH_HOSTKEYS);
+        }
     }
 
-    algo_count = ssh_list_count(algo_list);
-    if (algo_count == 0) {
-        ssh_list_free(algo_list);
+    /* This removes the certificate types, unsupported for now */
+    wanted_without_certs = ssh_find_all_matching(HOSTKEYS, wanted);
+    if (wanted_without_certs == NULL) {
+        SSH_LOG(SSH_LOG_WARNING,
+                "List of allowed host key algorithms is empty or contains only "
+                "unsupported algorithms");
         return NULL;
     }
 
-    for (i = 0; preferred_hostkeys[i] != NULL; ++i) {
-        bool found = false;
-        /* This is a signature type: We list also the SHA2 extensions */
-        enum ssh_keytypes_e base_preferred =
-            ssh_key_type_from_signature_name(preferred_hostkeys[i]);
-
-        for (it = ssh_list_get_iterator(algo_list);
-             it != NULL;
-             it = it->next) {
-            const char *algo = ssh_iterator_value(const char *, it);
-            /* This is always key type so we do not have to care for the
-             * SHA2 extension */
-            enum ssh_keytypes_e base_algo = ssh_key_type_from_name(algo);
-
-            if (base_preferred == base_algo) {
-                /* Matching the keys already verified it is a known type */
-                if (needcomma) {
-                    strncat(methods_buffer,
-                            ",",
-                            sizeof(methods_buffer) - strlen(methods_buffer) - 1);
-                }
-                strncat(methods_buffer,
-                        preferred_hostkeys[i],
-                        sizeof(methods_buffer) - strlen(methods_buffer) - 1);
-                needcomma = 1;
-                found = true;
-            }
-        }
-        /* Collect the rest of the algorithms in other buffer, that will
-         * follow the preferred buffer. This will signalize all the algorithms
-         * we are willing to accept.
-         */
-        if (!found) {
-            snprintf(tail_buffer + strlen(tail_buffer),
-                     sizeof(tail_buffer) - strlen(tail_buffer),
-                     ",%s", preferred_hostkeys[i]);
-        }
+    SSH_LOG(SSH_LOG_DEBUG,
+            "Order of wanted host keys: \"%s\"",
+            wanted_without_certs);
+
+    known_hosts_algorithms = ssh_known_hosts_get_algorithms_names(session);
+    if (known_hosts_algorithms == NULL) {
+        SSH_LOG(SSH_LOG_DEBUG,
+                "No key found in known_hosts; "
+                "changing host key method to \"%s\"",
+                wanted_without_certs);
+
+        return wanted_without_certs;
     }
-    ssh_list_free(algo_list);
 
-    if (strlen(methods_buffer) == 0) {
+    SSH_LOG(SSH_LOG_DEBUG,
+            "Algorithms found in known_hosts files: \"%s\"",
+            known_hosts_algorithms);
+
+    /* Filter and order the keys from known_hosts according to wanted list */
+    known_hosts_ordered = ssh_find_all_matching(known_hosts_algorithms,
+                                                wanted_without_certs);
+    SAFE_FREE(known_hosts_algorithms);
+    if (known_hosts_ordered == NULL) {
         SSH_LOG(SSH_LOG_DEBUG,
-                "No supported kex method for existing key in known_hosts file");
-        return NULL;
+                "No key found in known_hosts is allowed; "
+                "changing host key method to \"%s\"",
+                wanted_without_certs);
+
+        return wanted_without_certs;
     }
 
-    /* Append the supported list to the preferred.
-     * The length is maximum 128 + 128 + 1, which will not overflow
-     */
-    len = strlen(methods_buffer) + strlen(tail_buffer) + 1;
-    new_hostkeys = malloc(len);
+    /* Append the other supported keys after the preferred ones
+     * This function tolerates NULL pointers in parameters */
+    new_hostkeys = ssh_append_without_duplicates(known_hosts_ordered,
+                                                 wanted_without_certs);
+    SAFE_FREE(known_hosts_ordered);
+    SAFE_FREE(wanted_without_certs);
     if (new_hostkeys == NULL) {
         ssh_set_error_oom(session);
         return NULL;
     }
-    snprintf(new_hostkeys, len,
-             "%s%s", methods_buffer, tail_buffer);
+
+    if (ssh_fips_mode()) {
+        /* Filter out algorithms not allowed in FIPS mode */
+        fips_hostkeys = ssh_keep_fips_algos(SSH_HOSTKEYS, new_hostkeys);
+        SAFE_FREE(new_hostkeys);
+        if (fips_hostkeys == NULL) {
+            SSH_LOG(SSH_LOG_WARNING,
+                    "None of the wanted host keys or keys in known_hosts files "
+                    "is allowed in FIPS mode.");
+            return NULL;
+        }
+        new_hostkeys = fips_hostkeys;
+    }
 
     SSH_LOG(SSH_LOG_DEBUG,
             "Changing host key method to \"%s\"",
@@ -672,7 +663,7 @@ char *ssh_client_select_hostkeys(ssh_session session)
  */
 int ssh_set_client_kex(ssh_session session)
 {
-    struct ssh_kex_struct *client= &session->next_crypto->client_kex;
+    struct ssh_kex_struct *client = &session->next_crypto->client_kex;
     const char *wanted;
     char *kex = NULL;
     char *kex_tmp = NULL;
@@ -687,14 +678,22 @@ int ssh_set_client_kex(ssh_session session)
     }
 
     memset(client->methods, 0, KEX_METHODS_SIZE * sizeof(char **));
-    /* first check if we have specific host key methods */
-    if (session->opts.wanted_methods[SSH_HOSTKEYS] == NULL) {
-    	/* Only if no override */
-    	session->opts.wanted_methods[SSH_HOSTKEYS] =
-            ssh_client_select_hostkeys(session);
-    }
 
+    /* Set the list of allowed algorithms in order of preference, if it hadn't
+     * been set yet. */
     for (i = 0; i < KEX_METHODS_SIZE; i++) {
+        if (i == SSH_HOSTKEYS) {
+            /* Set the hostkeys in the following order:
+             * - First: keys present in known_hosts files ordered by preference
+             * - Next: other wanted algorithms ordered by preference */
+            client->methods[i] = ssh_client_select_hostkeys(session);
+            if (client->methods[i] == NULL) {
+                ssh_set_error_oom(session);
+                return SSH_ERROR;
+            }
+            continue;
+        }
+
         wanted = session->opts.wanted_methods[i];
         if (wanted == NULL) {
             if (ssh_fips_mode()) {
diff --git a/tests/unittests/torture_knownhosts_parsing.c b/tests/unittests/torture_knownhosts_parsing.c
index 6952e858..1c2ccc10 100644
--- a/tests/unittests/torture_knownhosts_parsing.c
+++ b/tests/unittests/torture_knownhosts_parsing.c
@@ -28,6 +28,8 @@
 
 #define TMP_FILE_NAME "/tmp/known_hosts_XXXXXX"
 
+const char template[] = "temp_dir_XXXXXX";
+
 static int setup_knownhosts_file(void **state)
 {
     char *tmp_file = NULL;
@@ -394,6 +396,115 @@ static void torture_knownhosts_get_algorithms_names(void **state)
     ssh_free(session);
 }
 
+static void torture_knownhosts_algorithms_wanted(void **state)
+{
+    const char *knownhosts_file = *state;
+    char *algo_list = NULL;
+    ssh_session session;
+    bool process_config = false;
+    const char *wanted = "ecdsa-sha2-nistp384,ecdsa-sha2-nistp256,"
+                         "rsa-sha2-256,ecdsa-sha2-nistp521";
+    const char *expect = "rsa-sha2-256,ecdsa-sha2-nistp384,"
+                         "ecdsa-sha2-nistp256,ecdsa-sha2-nistp521";
+    int verbose = 4;
+
+    session = ssh_new();
+    assert_non_null(session);
+
+    ssh_options_set(session, SSH_OPTIONS_LOG_VERBOSITY, &verbose);
+
+    /* This makes sure the global configuration file is not processed */
+    ssh_options_set(session, SSH_OPTIONS_PROCESS_CONFIG, &process_config);
+
+    /* Set the wanted list of hostkeys, ordered by preference */
+    ssh_options_set(session, SSH_OPTIONS_HOSTKEYS, wanted);
+
+    ssh_options_set(session, SSH_OPTIONS_HOST, "localhost");
+    ssh_options_set(session, SSH_OPTIONS_KNOWNHOSTS, knownhosts_file);
+
+    algo_list = ssh_client_select_hostkeys(session);
+    assert_non_null(algo_list);
+    assert_string_equal(algo_list, expect);
+    free(algo_list);
+
+    ssh_free(session);
+}
+
+static void torture_knownhosts_algorithms_negative(UNUSED_PARAM(void **state))
+{
+    const char *wanted = NULL;
+    const char *expect = NULL;
+
+    char *algo_list = NULL;
+
+    char *cwd = NULL;
+    char *tmp_dir = NULL;
+
+    bool process_config = false;
+    int verbose = 4;
+    int rc = 0;
+
+    ssh_session session;
+    /* Create temporary directory */
+    cwd = torture_get_current_working_dir();
+    assert_non_null(cwd);
+
+    tmp_dir = torture_make_temp_dir(template);
+    assert_non_null(tmp_dir);
+
+    rc = torture_change_dir(tmp_dir);
+    assert_int_equal(rc, 0);
+
+    session = ssh_new();
+    assert_non_null(session);
+
+    ssh_options_set(session, SSH_OPTIONS_LOG_VERBOSITY, &verbose);
+    ssh_options_set(session, SSH_OPTIONS_PROCESS_CONFIG, &process_config);
+    ssh_options_set(session, SSH_OPTIONS_HOST, "localhost");
+
+    /* Test with unknown key type in known_hosts */
+    wanted = "rsa-sha2-256";
+    ssh_options_set(session, SSH_OPTIONS_HOSTKEYS, wanted);
+    torture_write_file("unknown_key_type", "localhost unknown AAAABBBBCCCC");
+    ssh_options_set(session, SSH_OPTIONS_KNOWNHOSTS, "unknown_key_type");
+    algo_list = ssh_client_select_hostkeys(session);
+    assert_non_null(algo_list);
+    assert_string_equal(algo_list, wanted);
+    SAFE_FREE(algo_list);
+
+    /* Test with unsupported, but existing types */
+    wanted = "rsa-sha2-256-cert-v01@openssh.com,"
+             "rsa-sha2-512-cert-v01@openssh.com";
+    ssh_options_set(session, SSH_OPTIONS_HOSTKEYS, wanted);
+    algo_list = ssh_client_select_hostkeys(session);
+    assert_null(algo_list);
+
+    /* In FIPS mode, test filtering keys not allowed */
+    if (ssh_fips_mode()) {
+        wanted = "ssh-ed25519,rsa-sha2-256,ssh-rsa";
+        expect = "rsa-sha2-256";
+        ssh_options_set(session, SSH_OPTIONS_HOSTKEYS, wanted);
+        torture_write_file("no_fips", LOCALHOST_DEFAULT_ED25519);
+        ssh_options_set(session, SSH_OPTIONS_KNOWNHOSTS, "no_fips");
+        algo_list = ssh_client_select_hostkeys(session);
+        assert_non_null(algo_list);
+        assert_string_equal(algo_list, expect);
+        SAFE_FREE(algo_list);
+    }
+
+    ssh_free(session);
+
+    /* Teardown */
+    rc = torture_change_dir(cwd);
+    assert_int_equal(rc, 0);
+
+    rc = torture_rmdirs(tmp_dir);
+    assert_int_equal(rc, 0);
+
+    SAFE_FREE(tmp_dir);
+    SAFE_FREE(cwd);
+}
+
 #ifndef _WIN32 /* There is no /dev/null on Windows */
 static void torture_knownhosts_host_exists(void **state)
 {
@@ -457,12 +568,12 @@ static void torture_knownhosts_host_exists_global(void **state)
     ssh_free(session);
 }
 
-static void
-torture_knownhosts_algorithms(void **state)
+static void torture_knownhosts_algorithms(void **state)
 {
     const char *knownhosts_file = *state;
     char *algo_list = NULL;
     ssh_session session;
+    bool process_config = false;
     const char *expect = "ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa,"
                          "ecdsa-sha2-nistp521,ecdsa-sha2-nistp384,"
                          "ecdsa-sha2-nistp256"
@@ -470,10 +581,15 @@ torture_knownhosts_algorithms(void **state)
                          ",ssh-dss"
 #endif
     ;
+    const char *expect_fips = "rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp521,"
+                              "ecdsa-sha2-nistp384,ecdsa-sha2-nistp256";
 
     session = ssh_new();
     assert_non_null(session);
 
+    /* This makes sure the global configuration file is not processed */
+    ssh_options_set(session, SSH_OPTIONS_PROCESS_CONFIG, &process_config);
+
     ssh_options_set(session, SSH_OPTIONS_HOST, "localhost");
     ssh_options_set(session, SSH_OPTIONS_KNOWNHOSTS, knownhosts_file);
     /* This makes sure the system's known_hosts are not used */
@@ -481,18 +597,22 @@ torture_knownhosts_algorithms(void **state)
 
     algo_list = ssh_client_select_hostkeys(session);
     assert_non_null(algo_list);
-    assert_string_equal(algo_list, expect);
+    if (ssh_fips_mode()) {
+        assert_string_equal(algo_list, expect_fips);
+    } else {
+        assert_string_equal(algo_list, expect);
+    }
     free(algo_list);
 
     ssh_free(session);
 }
 
-static void
-torture_knownhosts_algorithms_global(void **state)
+static void torture_knownhosts_algorithms_global(void **state)
 {
     const char *knownhosts_file = *state;
     char *algo_list = NULL;
     ssh_session session;
+    bool process_config = false;
     const char *expect = "ssh-ed25519,rsa-sha2-512,rsa-sha2-256,ssh-rsa,"
                          "ecdsa-sha2-nistp521,ecdsa-sha2-nistp384,"
                          "ecdsa-sha2-nistp256"
@@ -500,10 +620,15 @@ torture_knownhosts_algorithms_global(void **state)
                          ",ssh-dss"
 #endif
     ;
+    const char *expect_fips = "rsa-sha2-512,rsa-sha2-256,ecdsa-sha2-nistp521,"
+                              "ecdsa-sha2-nistp384,ecdsa-sha2-nistp256";
 
     session = ssh_new();
     assert_non_null(session);
 
+    /* This makes sure the global configuration file is not processed */
+    ssh_options_set(session, SSH_OPTIONS_PROCESS_CONFIG, &process_config);
+
     ssh_options_set(session, SSH_OPTIONS_HOST, "localhost");
     /* This makes sure the current-user's known hosts are not used */
     ssh_options_set(session, SSH_OPTIONS_KNOWNHOSTS, "/dev/null");
@@ -511,12 +636,17 @@ torture_knownhosts_algorithms_global(void **state)
 
     algo_list = ssh_client_select_hostkeys(session);
     assert_non_null(algo_list);
-    assert_string_equal(algo_list, expect);
+    if (ssh_fips_mode()) {
+        assert_string_equal(algo_list, expect_fips);
+    } else {
+        assert_string_equal(algo_list, expect);
+    }
     free(algo_list);
 
     ssh_free(session);
 }
-#endif
+
+#endif /* _WIN32 There is no /dev/null on Windows */
 
 int torture_run_tests(void) {
     int rc;
@@ -538,6 +668,10 @@ int torture_run_tests(void) {
         cmocka_unit_test_setup_teardown(torture_knownhosts_get_algorithms_names,
                                         setup_knownhosts_file,
                                         teardown_knownhosts_file),
+        cmocka_unit_test_setup_teardown(torture_knownhosts_algorithms_wanted,
+                                        setup_knownhosts_file,
+                                        teardown_knownhosts_file),
+        cmocka_unit_test(torture_knownhosts_algorithms_negative),
 #ifndef _WIN32
         cmocka_unit_test_setup_teardown(torture_knownhosts_host_exists,
                                         setup_knownhosts_file,