token, kex: Add functions to handle tokens lists

The added functions allow splitting chains of tokens separated by a
given character (usually ','), and extracting matching parts between two
chains of tokens.

The previously existing functions in kex.c were replaced by the
introduced ones.

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

3 files changed, 264 insertions, 111 deletions

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt
index db7e74a0..3c7f198c 100644
--- a/src/CMakeLists.txt
+++ b/src/CMakeLists.txt
@@ -164,6 +164,7 @@ set(libssh_SRCS
   external/sc25519.c
   chachapoly.c
   config_parser.c
+  token.c
 )
 
 if (DEFAULT_C_NO_DEPRECATION_FLAGS)
diff --git a/src/kex.c b/src/kex.c
index 63b1d45c..fbb4b8a4 100644
--- a/src/kex.c
+++ b/src/kex.c
@@ -43,6 +43,7 @@
 #include "libssh/misc.h"
 #include "libssh/pki.h"
 #include "libssh/bignum.h"
+#include "libssh/token.h"
 
 #ifdef WITH_BLOWFISH_CIPHER
 # if defined(HAVE_OPENSSL_BLOWFISH_H) || defined(HAVE_LIBGCRYPT) || defined(HAVE_LIBMBEDCRYPTO)
@@ -296,117 +297,6 @@ const char *ssh_kex_get_description(uint32_t algo) {
   return ssh_kex_descriptions[algo];
 }
 
-/* find_matching gets 2 parameters : a list of available objects (available_d), separated by colons,*/
-/* and a list of preferred objects (preferred_d) */
-/* it will return a strduped pointer on the first preferred object found in the available objects list */
-
-char *ssh_find_matching(const char *available_d, const char *preferred_d){
-    char ** tok_available, **tok_preferred;
-    int i_avail, i_pref;
-    char *ret;
-
-    if ((available_d == NULL) || (preferred_d == NULL)) {
-      return NULL; /* don't deal with null args */
-    }
-
-    tok_available = tokenize(available_d);
-    if (tok_available == NULL) {
-      return NULL;
-    }
-
-    tok_preferred = tokenize(preferred_d);
-    if (tok_preferred == NULL) {
-      SAFE_FREE(tok_available[0]);
-      SAFE_FREE(tok_available);
-      return NULL;
-    }
-
-    for(i_pref=0; tok_preferred[i_pref] ; ++i_pref){
-      for(i_avail=0; tok_available[i_avail]; ++i_avail){
-        if(strcmp(tok_available[i_avail],tok_preferred[i_pref]) == 0){
-          /* match */
-          ret=strdup(tok_available[i_avail]);
-          /* free the tokens */
-          SAFE_FREE(tok_available[0]);
-          SAFE_FREE(tok_preferred[0]);
-          SAFE_FREE(tok_available);
-          SAFE_FREE(tok_preferred);
-          return ret;
-        }
-      }
-    }
-    SAFE_FREE(tok_available[0]);
-    SAFE_FREE(tok_preferred[0]);
-    SAFE_FREE(tok_available);
-    SAFE_FREE(tok_preferred);
-    return NULL;
-}
-
-static char *ssh_find_all_matching(const char *available_d,
-                                   const char *preferred_d)
-{
-    char **tok_available, **tok_preferred;
-    int i_avail, i_pref;
-    char *ret;
-    unsigned max, len, pos = 0;
-
-    if ((available_d == NULL) || (preferred_d == NULL)) {
-        return NULL; /* don't deal with null args */
-    }
-
-    max = MAX(strlen(available_d), strlen(preferred_d));
-
-    ret = malloc(max+1);
-    if (ret == NULL) {
-      return NULL;
-    }
-    ret[0] = 0;
-
-    tok_available = tokenize(available_d);
-    if (tok_available == NULL) {
-        SAFE_FREE(ret);
-        return NULL;
-    }
-
-    tok_preferred = tokenize(preferred_d);
-    if (tok_preferred == NULL) {
-        SAFE_FREE(ret);
-        SAFE_FREE(tok_available[0]);
-        SAFE_FREE(tok_available);
-        return NULL;
-    }
-
-    for (i_pref = 0; tok_preferred[i_pref] ; ++i_pref) {
-        for (i_avail = 0; tok_available[i_avail]; ++i_avail) {
-            int cmp = strcmp(tok_available[i_avail],tok_preferred[i_pref]);
-            if (cmp == 0) {
-                /* match */
-                if (pos != 0) {
-                    ret[pos] = ',';
-                    pos++;
-                }
-
-                len = strlen(tok_available[i_avail]);
-                memcpy(&ret[pos], tok_available[i_avail], len);
-                pos += len;
-                ret[pos] = '\0';
-            }
-        }
-    }
-
-    if (ret[0] == '\0') {
-        SAFE_FREE(ret);
-        ret = NULL;
-    }
-
-    SAFE_FREE(tok_available[0]);
-    SAFE_FREE(tok_preferred[0]);
-    SAFE_FREE(tok_available);
-    SAFE_FREE(tok_preferred);
-
-    return ret;
-}
-
 /**
  * @internal
  * @brief returns whether the first client key exchange algorithm or
diff --git a/src/token.c b/src/token.c
new file mode 100644
index 00000000..aee235ac
--- /dev/null
+++ b/src/token.c
@@ -0,0 +1,262 @@
+/*
+ * token.c - Token list handling functions
+ *
+ * This file is part of the SSH Library
+ *
+ * Copyright (c) 2003-2008 by Aris Adamantiadis
+ * Copyright (c) 2019 by Anderson Toshiyuki Sasaki - Red Hat, Inc.
+ *
+ * The SSH Library is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Lesser General Public License as published by
+ * the Free Software Foundation; either version 2.1 of the License, or (at your
+ * option) any later version.
+ *
+ * The SSH Library is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public License
+ * along with the SSH Library; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+#include "config.h"
+
+#include <stdio.h>
+#include <string.h>
+
+#include "libssh/priv.h"
+#include "libssh/token.h"
+
+/**
+ * @internal
+ *
+ * @brief Free the given tokens list structure. The used buffer is overwritten
+ * with zeroes before freed.
+ *
+ * @param[in] tokens    The pointer to a structure to be freed;
+ */
+void ssh_tokens_free(struct ssh_tokens_st *tokens)
+{
+    int i;
+    if (tokens == NULL) {
+        return;
+    }
+
+    if (tokens->tokens != NULL) {
+        for (i = 0; tokens->tokens[i] != NULL; i++) {
+            explicit_bzero(tokens->tokens[i], strlen(tokens->tokens[i]));
+        }
+    }
+
+    SAFE_FREE(tokens->buffer);
+    SAFE_FREE(tokens->tokens);
+    SAFE_FREE(tokens);
+}
+
+/**
+ * @internal
+ *
+ * @brief Split a given string on the given separator character. The returned
+ * structure holds an array of pointers (tokens) pointing to the obtained
+ * parts and a buffer where all the content of the list is stored. The last
+ * element of the array will always be set as NULL.
+ *
+ * @param[in] chain         The string to split
+ * @param[in] separator     The character used to separate the tokens.
+ *
+ * @return  A newly allocated tokens list structure; NULL in case of error.
+ */
+struct ssh_tokens_st *ssh_tokenize(const char *chain, char separator)
+{
+
+    struct ssh_tokens_st *tokens = NULL;
+    size_t num_tokens = 1, i = 1;
+
+    char *found, *c;
+
+    if (chain == NULL) {
+        return NULL;
+    }
+
+    tokens = calloc(1, sizeof(struct ssh_tokens_st));
+    if (tokens == NULL) {
+        return NULL;
+    }
+
+    tokens->buffer= strdup(chain);
+    if (tokens->buffer == NULL) {
+        goto error;
+    }
+
+    c = tokens->buffer;
+    do {
+        found = strchr(c, separator);
+        if (found != NULL) {
+            c = found + 1;
+            num_tokens++;
+        }
+    } while(found != NULL);
+
+    /* Allocate tokens list */
+    tokens->tokens = calloc(num_tokens + 1, sizeof(char *));
+    if (tokens->tokens == NULL) {
+        goto error;
+    }
+
+    /* First token starts in the beginning of the chain */
+    tokens->tokens[0] = tokens->buffer;
+    c = tokens->buffer;
+
+    for (i = 1; i < num_tokens; i++) {
+        /* Find next separator */
+        found = strchr(c, separator);
+        if (found == NULL) {
+            break;
+        }
+
+        /* Replace it with a string terminator */
+        *found = '\0';
+
+        /* The next token starts in the next byte */
+        c = found + 1;
+
+        /* If we did not reach the end of the chain yet, set the next token */
+        if (*c != '\0') {
+            tokens->tokens[i] = c;
+        } else {
+            break;
+        }
+    }
+
+    return tokens;
+
+error:
+    ssh_tokens_free(tokens);
+    return NULL;
+}
+
+/**
+ * @internal
+ *
+ * @brief Given two strings, the first containing a list of available tokens and
+ * the second containing a list of tokens to be searched ordered by preference,
+ * returns a copy of the first preferred token present in the available list.
+ *
+ * @param[in] available_list    The list of available tokens
+ * @param[in] preferred_list    The list of tokens to search, ordered by
+ * preference
+ *
+ * @return  A newly allocated copy of the token if found; NULL otherwise
+ */
+char *ssh_find_matching(const char *available_list,
+                        const char *preferred_list)
+{
+    struct ssh_tokens_st *a_tok = NULL, *p_tok = NULL;
+
+    int i, j;
+    char *ret = NULL;
+
+    if ((available_list == NULL) || (preferred_list == NULL)) {
+        return NULL;
+    }
+
+    a_tok = ssh_tokenize(available_list, ',');
+    if (a_tok == NULL) {
+        return NULL;
+    }
+
+    p_tok = ssh_tokenize(preferred_list, ',');
+    if (p_tok == NULL) {
+        goto out;
+    }
+
+    for (i = 0; p_tok->tokens[i]; i++) {
+        for (j = 0; a_tok->tokens[j]; j++) {
+            if (strcmp(a_tok->tokens[j], p_tok->tokens[i]) == 0){
+                ret = strdup(a_tok->tokens[j]);
+                goto out;
+            }
+        }
+    }
+
+out:
+    ssh_tokens_free(a_tok);
+    ssh_tokens_free(p_tok);
+    return ret;
+}
+
+/**
+ * @internal
+ *
+ * @brief Given two strings, the first containing a list of available tokens and
+ * the second containing a list of tokens to be searched ordered by preference,
+ * returns a list of all matching tokens ordered by preference.
+ *
+ * @param[in] available_list    The list of available tokens
+ * @param[in] preferred_list    The list of tokens to search, ordered by
+ * preference
+ *
+ * @return  A newly allocated string containing the list of all matching tokens;
+ * NULL otherwise
+ */
+char *ssh_find_all_matching(const char *available_list,
+                            const char *preferred_list)
+{
+    struct ssh_tokens_st *a_tok = NULL, *p_tok = NULL;
+    int i, j;
+    char *ret = NULL;
+    size_t max, len, pos = 0;
+    int match;
+
+    if ((available_list == NULL) || (preferred_list == NULL)) {
+        return NULL;
+    }
+
+    max = MAX(strlen(available_list), strlen(preferred_list));
+
+    ret = calloc(1, max + 1);
+    if (ret == NULL) {
+        return NULL;
+    }
+
+    a_tok = ssh_tokenize(available_list, ',');
+    if (a_tok == NULL) {
+        SAFE_FREE(ret);
+        goto out;
+    }
+
+    p_tok = ssh_tokenize(preferred_list, ',');
+    if (p_tok == NULL) {
+        SAFE_FREE(ret);
+        goto out;
+    }
+
+    for (i = 0; p_tok->tokens[i] ; i++) {
+        for (j = 0; a_tok->tokens[j]; j++) {
+            match = !strcmp(a_tok->tokens[j], p_tok->tokens[i]);
+            if (match) {
+                if (pos != 0) {
+                    ret[pos] = ',';
+                    pos++;
+                }
+
+                len = strlen(a_tok->tokens[j]);
+                memcpy(&ret[pos], a_tok->tokens[j], len);
+                pos += len;
+                ret[pos] = '\0';
+            }
+        }
+    }
+
+    if (ret[0] == '\0') {
+        SAFE_FREE(ret);
+    }
+
+out:
+    ssh_tokens_free(a_tok);
+    ssh_tokens_free(p_tok);
+    return ret;
+}