plugin/sqlite.c

   1 /*
   2  * Check a SQLite database for a password within edit distance one.
   3  *
   4  * This file implements yet another variation on dictionary lookups.
   5  * Passwords are checked against a SQLite database (generally created with the
   6  * krb5-strength-wordlist utility) that holds words and reversed words, and
   7  * all passwords within edit distance one of a word in the database are
   8  * rejected.
   9  *
  10  * To find passwords within edit distance one, this algorithm checks, for each
  11  * dictionary word, whether the length of longest common prefix plus the
  12  * length of the longest common suffix between that word and the password is
  13  * within 1 of the length of the password.  It will be one less if a letter
  14  * has been removed or replaced, and equal if the password is an exact match.
  15  *
  16  * To do this, the SQLite database contains one row for each dictionary word,
  17  * containing both the word and the reversed version of the word.  The
  18  * password is divided into two components, a prefix and a suffix.  It is
  19  * checked against all dictionary words that fall lexicographically between
  20  * the prefix and the prefix with its last character incremented, and then
  21  * against all words where the word reversed falls lexicographically between
  22  * the suffix reversed and the suffix reversed with its last character
  23  * incremented.
  24  *
  25  * If the password matches a dictionary word, the edit must either be in the
  26  * first half of the password or the last half of the password.  If in the
  27  * first half, the word it will match will fall in the prefix range.  If in
  28  * the last half, the word it will match will fall in the suffix range.
  29  *
  30  * Written by Russ Allbery <eagle@eyrie.org>
  31  * Based on work by David Mazières
  32  * Copyright 2016, 2020, 2023 Russ Allbery <eagle@eyrie.org>
  33  * Copyright 2014
  34  *     The Board of Trustees of the Leland Stanford Junior University
  35  *
  36  * SPDX-License-Identifier: MIT
  37  */
  38
  39 #include <config.h>
  40 #include <portable/kadmin.h>
  41 #include <portable/krb5.h>
  42 #include <portable/system.h>
  43
  44 #ifdef HAVE_SQLITE3_H
  45 #    include <sqlite3.h>
  46 #endif
  47
  48 #include <plugin/internal.h>
  49 #include <util/macros.h>
  50
  51 /*
  52  * The prefix and suffix SQLite query.  Finds all candidate words in range of
  53  * the prefix or suffix.  The prefix query should get bind variables for the
  54  * prefix and the prefix with the last character incremented; the suffix query
  55  * gets the same, but the suffix should be reversed.
  56  */
  57 /* clang-format off */
  58 #define PREFIX_QUERY \
  59     "SELECT password, drowssap FROM passwords WHERE password BETWEEN ? AND ?;"
  60 #define SUFFIX_QUERY \
  61     "SELECT password, drowssap FROM passwords WHERE drowssap BETWEEN ? AND ?;"
  62 /* clang-format on */
  63
  64
  65 /*
  66  * Stub for strength_init_sqlite if not built with SQLite support.
  67  */
  68 #ifndef HAVE_SQLITE3
  69 krb5_error_code
  70 strength_init_sqlite(krb5_context ctx, krb5_pwqual_moddata data UNUSED)
  71 {
  72     char *path = NULL;
  73
  74     /* Get CDB dictionary path from krb5.conf. */
  75     strength_config_string(ctx, "password_dictionary_sqlite", &path);
  76
  77     /* If it was set, report an error, since we don't have SQLite support. */
  78     if (path == NULL)
  79         return 0;
  80     free(path);
  81     krb5_set_error_message(ctx, KADM5_BAD_SERVER_PARAMS,
  82                            "SQLite dictionary requested but not built with"
  83                            " SQLite support");
  84     return KADM5_BAD_SERVER_PARAMS;
  85 }
  86 #endif
  87
  88
  89 /* Skip the rest of this file if SQLite is not available. */
  90 #ifdef HAVE_SQLITE3
  91
  92 /*
  93  * Report a SQLite error.  Takes the module data (used to access the SQLite
  94  * object) and the Kerberos context, stores the SQLite error in the Kerberos
  95  * context, and returns the generic KADM5_FAILURE code, since there doesn't
  96  * appear to be anything better.
  97  */
  98 static krb5_error_code __attribute__((__format__(printf, 3, 4)))
  99 error_sqlite(krb5_context ctx, krb5_pwqual_moddata data, const char *format,
 100              ...)
 101 {
 102     va_list args;
 103     ssize_t length;
 104     char *message;
 105     const char *errmsg;
 106
 107     errmsg = sqlite3_errmsg(data->sqlite);
 108     va_start(args, format);
 109     length = vasprintf(&message, format, args);
 110     va_end(args);
 111     if (length < 0)
 112         return strength_error_system(ctx, "cannot allocate memory");
 113     krb5_set_error_message(ctx, KADM5_FAILURE, "%s: %s", message, errmsg);
 114     free(message);
 115     return KADM5_FAILURE;
 116 }
 117
 118
 119 /*
 120  * Given a string, returns a reversed version of that string in newly
 121  * allocated memory.  The caller is responsible for freeing.  Returns NULL on
 122  * memory allocation failure.
 123  */
 124 static char *
 125 reverse_string(const char *string)
 126 {
 127     size_t length, i;
 128     char *reversed;
 129
 130     length = strlen(string);
 131     reversed = malloc(length + 1);
 132     if (reversed == NULL)
 133         return NULL;
 134     reversed[length] = '\0';
 135     for (i = 0; i < length; i++)
 136         reversed[length - i - 1] = string[i];
 137     return reversed;
 138 }
 139
 140
 141 /*
 142  * Given two strings, return the length of their common prefix, not counting
 143  * the nul character that terminates either string.
 144  */
 145 static size_t
 146 common_prefix_length(const char *a, const char *b)
 147 {
 148     size_t i;
 149
 150     for (i = 0; a[i] == b[i] && a[i] != '\0'; i++)
 151         ;
 152     return i;
 153 }
 154
 155
 156 /*
 157  * Given the length of the password, the password, the reversed password, and
 158  * an executed SQLite statement that contains the word and reversed word as
 159  * the first two column texts, determine whether this password is a match
 160  * within edit distance one.
 161  *
 162  * It will be a match if the length of the common prefix of the password and
 163  * word plus the length of the common prefix of the reversed password and the
 164  * reversed word (which is the length of the common suffix) is greater than or
 165  * equal to the length of the password minus one.
 166  *
 167  * To see why the sum of the prefix and suffix length can be longer than the
 168  * length of the password when the password doesn't match the word, consider
 169  * the password "aaaa" and the word "aaaaaaaaa".  The prefix length plus the
 170  * suffix length may be greater than the length of the password if the
 171  * password is an exact match for the word or an initial or final substring of
 172  * the word.
 173  */
 174 static bool
 175 match(size_t length, const char *password, const char *drowssap,
 176       sqlite3_stmt *query)
 177 {
 178     const char *word, *drow;
 179     size_t prefix_length, suffix_length, match_length, word_length;
 180
 181     /* Discard all words whose length is too different. */
 182     word = (const char *) sqlite3_column_text(query, 0);
 183     word_length = strlen(word);
 184     if (length > word_length + 1 || length + 1 < word_length)
 185         return false;
 186
 187     /*
 188      * Get the common prefix length and check if the password is an exact
 189      * match.
 190      */
 191     prefix_length = common_prefix_length(password, word);
 192     if (prefix_length == length)
 193         return true;
 194
 195     /*
 196      * Ensure there aren't too many different characters for this to be a
 197      * match.  If the common prefix and the common suffix together have a
 198      * length that's more than one character shorter than the password length,
 199      * this is different by at least edit distance two.  The sum of the
 200      * lengths of the common prefix and suffix can be greater than length in
 201      * cases of an edit in the middle of repeated passwords, such as the
 202      * password "baaab" and the word "baab", but those are all matches.
 203      */
 204     drow = (const char *) sqlite3_column_text(query, 1);
 205     suffix_length = common_prefix_length(drowssap, drow);
 206     match_length = prefix_length + suffix_length;
 207     return (match_length > length || length - match_length <= 1);
 208 }
 209
 210
 211 /*
 212  * Initialize the SQLite dictionary.  Opens the database and compiles the two
 213  * queries that we'll use.  Returns 0 on success, non-zero on failure (and
 214  * sets the error in the Kerberos context).
 215  */
 216 krb5_error_code
 217 strength_init_sqlite(krb5_context ctx, krb5_pwqual_moddata data)
 218 {
 219     char *path = NULL;
 220     int status;
 221
 222     /* Get SQLite dictionary path from krb5.conf. */
 223     strength_config_string(ctx, "password_dictionary_sqlite", &path);
 224
 225     /* If there is no configured dictionary, nothing to do. */
 226     if (path == NULL)
 227         return 0;
 228
 229     /* Open the database. */
 230     status = sqlite3_open_v2(path, &data->sqlite, SQLITE_OPEN_READONLY, NULL);
 231     if (status != 0)
 232         return error_sqlite(ctx, data, "cannot open dictionary %s", path);
 233
 234     /* Precompile the queries we'll use. */
 235     status = sqlite3_prepare_v2(data->sqlite, PREFIX_QUERY, -1,
 236                                 &data->prefix_query, NULL);
 237     if (status != 0)
 238         return error_sqlite(ctx, data, "cannot prepare prefix query");
 239     status = sqlite3_prepare_v2(data->sqlite, SUFFIX_QUERY, -1,
 240                                 &data->suffix_query, NULL);
 241     if (status != 0)
 242         return error_sqlite(ctx, data, "cannot prepare suffix query");
 243
 244     /* Finished.  Return success. */
 245     free(path);
 246     return 0;
 247 }
 248
 249
 250 /*
 251  * Given a password, look for a word in the database within edit distance one.
 252  * The full algorithm used here is described in the comment at the start of
 253  * this file.  Returns a Kerberos status code, which will be KADM5_PASS_Q_DICT
 254  * if the password was found in the dictionary.
 255  */
 256 krb5_error_code
 257 strength_check_sqlite(krb5_context ctx, krb5_pwqual_moddata data,
 258                       const char *password)
 259 {
 260     krb5_error_code code;
 261     size_t length;
 262     int prefix_length, suffix_length;
 263     char *prefix = NULL;
 264     char *drowssap = NULL;
 265     bool found = false;
 266     int status;
 267
 268     /* If we have no dictionary, there is nothing to do. */
 269     if (data->sqlite == NULL)
 270         return 0;
 271
 272     /*
 273      * Determine the length of the prefix and suffix into which we'll divide
 274      * the string.  Passwords shorter than two characters cannot be
 275      * meaningfully checked using this method and cause boundary condition
 276      * problems.  Passwords longer than INT_MAX cannot be passed to the SQLite
 277      * library.
 278      */
 279     length = strlen(password);
 280     if (length < 2 || length > INT_MAX)
 281         return 0;
 282     prefix_length = (int) length / 2;
 283     suffix_length = (int) length - prefix_length;
 284
 285     /* Obtain the reversed password, used for suffix checks. */
 286     drowssap = reverse_string(password);
 287     if (drowssap == NULL)
 288         return strength_error_system(ctx, "cannot allocate memory");
 289
 290     /* Set up the query for prefix matching. */
 291     prefix = strdup(password);
 292     if (prefix == NULL) {
 293         code = strength_error_system(ctx, "cannot allocate memory");
 294         goto fail;
 295     }
 296     status = sqlite3_bind_text(data->prefix_query, 1, password, prefix_length,
 297                                NULL);
 298     if (status != SQLITE_OK) {
 299         code = error_sqlite(ctx, data, "cannot bind prefix start");
 300         goto fail;
 301     }
 302     prefix[prefix_length - 1]++;
 303     status =
 304         sqlite3_bind_text(data->prefix_query, 2, prefix, prefix_length, NULL);
 305     if (status != SQLITE_OK) {
 306         code = error_sqlite(ctx, data, "cannot bind prefix end");
 307         goto fail;
 308     }
 309
 310     /*
 311      * Do prefix matching.  Get the set of all database entries starting with
 312      * the same prefix and, for each, check whether our password matches that
 313      * entry within edit distance one.
 314      */
 315     while ((status = sqlite3_step(data->prefix_query)) == SQLITE_ROW)
 316         if (match(length, password, drowssap, data->prefix_query)) {
 317             found = true;
 318             break;
 319         }
 320     if (status != SQLITE_DONE && status != SQLITE_ROW) {
 321         code = error_sqlite(ctx, data, "error searching by password prefix");
 322         goto fail;
 323     }
 324     status = sqlite3_reset(data->prefix_query);
 325     if (status != SQLITE_OK) {
 326         code = error_sqlite(ctx, data, "error resetting prefix query");
 327         goto fail;
 328     }
 329     if (found)
 330         goto found;
 331
 332     /* Set up the query for suffix matching. */
 333     status = sqlite3_bind_text(data->suffix_query, 1, drowssap, suffix_length,
 334                                SQLITE_TRANSIENT);
 335     if (status != SQLITE_OK) {
 336         code = error_sqlite(ctx, data, "cannot bind suffix start");
 337         goto fail;
 338     }
 339     drowssap[prefix_length - 1]++;
 340     status = sqlite3_bind_text(data->suffix_query, 2, drowssap, suffix_length,
 341                                SQLITE_TRANSIENT);
 342     drowssap[prefix_length - 1]--;
 343     if (status != SQLITE_OK) {
 344         code = error_sqlite(ctx, data, "cannot bind suffix end");
 345         goto fail;
 346     }
 347
 348     /*
 349      * Do suffix matching.  Get the set of all database entries starting with
 350      * the same prefix and, for each, check whether our password matches that
 351      * entry within edit distance one.
 352      */
 353     while ((status = sqlite3_step(data->suffix_query)) == SQLITE_ROW)
 354         if (match(length, password, drowssap, data->suffix_query)) {
 355             found = true;
 356             break;
 357         }
 358     if (status != SQLITE_DONE && status != SQLITE_ROW) {
 359         code = error_sqlite(ctx, data, "error searching by password suffix");
 360         goto fail;
 361     }
 362     status = sqlite3_reset(data->suffix_query);
 363     if (status != SQLITE_OK) {
 364         code = error_sqlite(ctx, data, "error resetting suffix query");
 365         goto fail;
 366     }
 367     if (found)
 368         goto found;
 369
 370     /* No match.  Clean up and return success. */
 371     explicit_bzero(prefix, length);
 372     explicit_bzero(drowssap, length);
 373     free(prefix);
 374     free(drowssap);
 375     return 0;
 376
 377 found:
 378     /* We found the password in the dictionary. */
 379     code = strength_error_dict(ctx, ERROR_DICT);
 380
 381 fail:
 382     if (prefix != NULL)
 383         explicit_bzero(prefix, length);
 384     explicit_bzero(drowssap, length);
 385     free(prefix);
 386     free(drowssap);
 387     return code;
 388 }
 389
 390
 391 /*
 392  * Free internal SQLite state and close the SQLite database.
 393  */
 394 void
 395 strength_close_sqlite(krb5_context ctx UNUSED, krb5_pwqual_moddata data)
 396 {
 397     if (data->prefix_query != NULL)
 398         sqlite3_finalize(data->prefix_query);
 399     if (data->suffix_query != NULL)
 400         sqlite3_finalize(data->suffix_query);
 401     if (data->sqlite != NULL)
 402         sqlite3_close(data->sqlite);
 403 }
 404
 405 #endif /* HAVE_SQLITE3 */