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