2 * Check a SQLite database for a password within edit distance one.
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
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.
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
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.
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>
34 * The Board of Trustees of the Leland Stanford Junior University
36 * SPDX-License-Identifier: MIT
40 #include <portable/kadmin.h>
41 #include <portable/krb5.h>
42 #include <portable/system.h>
48 #include <plugin/internal.h>
49 #include <util/macros.h>
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.
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 ?;"
66 * Stub for strength_init_sqlite if not built with SQLite support.
70 strength_init_sqlite(krb5_context ctx, krb5_pwqual_moddata data UNUSED)
74 /* Get CDB dictionary path from krb5.conf. */
75 strength_config_string(ctx, "password_dictionary_sqlite", &path);
77 /* If it was set, report an error, since we don't have SQLite support. */
81 krb5_set_error_message(ctx, KADM5_BAD_SERVER_PARAMS,
82 "SQLite dictionary requested but not built with"
84 return KADM5_BAD_SERVER_PARAMS;
89 /* Skip the rest of this file if SQLite is not available. */
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.
98 static krb5_error_code __attribute__((__format__(printf, 3, 4)))
99 error_sqlite(krb5_context ctx, krb5_pwqual_moddata data, const char *format,
107 errmsg = sqlite3_errmsg(data->sqlite);
108 va_start(args, format);
109 length = vasprintf(&message, format, args);
112 return strength_error_system(ctx, "cannot allocate memory");
113 krb5_set_error_message(ctx, KADM5_FAILURE, "%s: %s", message, errmsg);
115 return KADM5_FAILURE;
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.
125 reverse_string(const char *string)
130 length = strlen(string);
131 reversed = malloc(length + 1);
132 if (reversed == NULL)
134 reversed[length] = '\0';
135 for (i = 0; i < length; i++)
136 reversed[length - i - 1] = string[i];
142 * Given two strings, return the length of their common prefix, not counting
143 * the nul character that terminates either string.
146 common_prefix_length(const char *a, const char *b)
150 for (i = 0; a[i] == b[i] && a[i] != '\0'; i++)
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.
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.
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
175 match(size_t length, const char *password, const char *drowssap,
178 const char *word, *drow;
179 size_t prefix_length, suffix_length, match_length, word_length;
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)
188 * Get the common prefix length and check if the password is an exact
191 prefix_length = common_prefix_length(password, word);
192 if (prefix_length == length)
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.
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);
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).
217 strength_init_sqlite(krb5_context ctx, krb5_pwqual_moddata data)
222 /* Get SQLite dictionary path from krb5.conf. */
223 strength_config_string(ctx, "password_dictionary_sqlite", &path);
225 /* If there is no configured dictionary, nothing to do. */
229 /* Open the database. */
230 status = sqlite3_open_v2(path, &data->sqlite, SQLITE_OPEN_READONLY, NULL);
232 return error_sqlite(ctx, data, "cannot open dictionary %s", path);
234 /* Precompile the queries we'll use. */
235 status = sqlite3_prepare_v2(data->sqlite, PREFIX_QUERY, -1,
236 &data->prefix_query, NULL);
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);
242 return error_sqlite(ctx, data, "cannot prepare suffix query");
244 /* Finished. Return success. */
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.
257 strength_check_sqlite(krb5_context ctx, krb5_pwqual_moddata data,
258 const char *password)
260 krb5_error_code code;
262 int prefix_length, suffix_length;
264 char *drowssap = NULL;
268 /* If we have no dictionary, there is nothing to do. */
269 if (data->sqlite == NULL)
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
279 length = strlen(password);
280 if (length < 2 || length > INT_MAX)
282 prefix_length = (int) length / 2;
283 suffix_length = (int) length - prefix_length;
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");
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");
296 status = sqlite3_bind_text(data->prefix_query, 1, password, prefix_length,
298 if (status != SQLITE_OK) {
299 code = error_sqlite(ctx, data, "cannot bind prefix start");
302 prefix[prefix_length - 1]++;
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");
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.
315 while ((status = sqlite3_step(data->prefix_query)) == SQLITE_ROW)
316 if (match(length, password, drowssap, data->prefix_query)) {
320 if (status != SQLITE_DONE && status != SQLITE_ROW) {
321 code = error_sqlite(ctx, data, "error searching by password prefix");
324 status = sqlite3_reset(data->prefix_query);
325 if (status != SQLITE_OK) {
326 code = error_sqlite(ctx, data, "error resetting prefix query");
332 /* Set up the query for suffix matching. */
333 status = sqlite3_bind_text(data->suffix_query, 1, drowssap, suffix_length,
335 if (status != SQLITE_OK) {
336 code = error_sqlite(ctx, data, "cannot bind suffix start");
339 drowssap[prefix_length - 1]++;
340 status = sqlite3_bind_text(data->suffix_query, 2, drowssap, suffix_length,
342 drowssap[prefix_length - 1]--;
343 if (status != SQLITE_OK) {
344 code = error_sqlite(ctx, data, "cannot bind suffix end");
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.
353 while ((status = sqlite3_step(data->suffix_query)) == SQLITE_ROW)
354 if (match(length, password, drowssap, data->suffix_query)) {
358 if (status != SQLITE_DONE && status != SQLITE_ROW) {
359 code = error_sqlite(ctx, data, "error searching by password suffix");
362 status = sqlite3_reset(data->suffix_query);
363 if (status != SQLITE_OK) {
364 code = error_sqlite(ctx, data, "error resetting suffix query");
370 /* No match. Clean up and return success. */
371 explicit_bzero(prefix, length);
372 explicit_bzero(drowssap, length);
378 /* We found the password in the dictionary. */
379 code = strength_error_dict(ctx, ERROR_DICT);
383 explicit_bzero(prefix, length);
384 explicit_bzero(drowssap, length);
392 * Free internal SQLite state and close the SQLite database.
395 strength_close_sqlite(krb5_context ctx UNUSED, krb5_pwqual_moddata data)
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);
405 #endif /* HAVE_SQLITE3 */