From 18cc9d6ab7486675263643555de3e6257b1c2fe6 Mon Sep 17 00:00:00 2001 From: Russ Allbery Date: Tue, 25 Mar 2014 00:42:29 -0700 Subject: [PATCH] Add a full complement of edit distance one SQLite checks Fix one logic error uncovered by the more complete tests, which produced the wrong result when the edit involved a sequence of repeated characters. --- plugin/sqlite.c | 39 +++++- tests/data/passwords/sqlite.json | 203 +++++++++++++++++++++++++++++++ 2 files changed, 236 insertions(+), 6 deletions(-) diff --git a/plugin/sqlite.c b/plugin/sqlite.c index 56f8d2c..c6fd2d6 100644 --- a/plugin/sqlite.c +++ b/plugin/sqlite.c @@ -154,25 +154,52 @@ common_prefix_length(const char *a, const char *b) * the first two column texts, determine whether this password is a match * within edit distance one. * - * It will be a match if the length of the common prefix of the passwod and + * It will be a match if the length of the common prefix of the password and * word plus the length of the common prefix of the reversed password and the - * reversed word (which is the length of the common suffix) is within 1 of the - * length of the password. + * reversed word (which is the length of the common suffix) is greater than or + * equal to the length of the password minus one. + * + * To see why the sum of the prefix and suffix length can be longer than the + * length of the password when the password doesn't match the word, consider + * the password "aaaa" and the word "aaaaaaaaa" + * (The prefix length plus the + * suffix length may be greater than the length of the password if the + * password is an exact match for the word or */ static bool match(size_t length, const char *password, const char *drowssap, sqlite3_stmt *query) { const char *word, *drow; - size_t prefix_length, suffix_length; + size_t prefix_length, suffix_length, match_length, word_length; + /* Discard all words whose length is too different. */ word = (const char *) sqlite3_column_text(query, 0); - drow = (const char *) sqlite3_column_text(query, 1); + word_length = strlen(word); + if (length > word_length + 1 || length + 1 < word_length) + return false; + + /* + * Get the common prefix length and check if the password is an exact + * match. + */ prefix_length = common_prefix_length(password, word); if (prefix_length == length) return true; + + /* + * Ensure there aren't too many different characters for this to be a + * match. If the common prefix and the common suffix together have a + * length that's more than one character shorter than the password length, + * this is different by at least edit distance two. The sum of the + * lengths of the common prefix and suffix can be greater than length in + * cases of an edit in the middle of repeated passwords, such as the + * password "baaab" and the word "baab", but those are all matches. + */ + drow = (const char *) sqlite3_column_text(query, 1); suffix_length = common_prefix_length(drowssap, drow); - return (length - prefix_length - suffix_length <= 1); + match_length = prefix_length + suffix_length; + return (match_length > length || length - match_length <= 1); } diff --git a/tests/data/passwords/sqlite.json b/tests/data/passwords/sqlite.json index f736e02..2b361af 100644 --- a/tests/data/passwords/sqlite.json +++ b/tests/data/passwords/sqlite.json @@ -58,5 +58,208 @@ "principal": "test@EXAMPLE.ORG", "password": "a", "code": 0 + }, + { + "name": "in dictionary (edit: delete 1)", + "principal": "test@EXAMPLE.ORG", + "password": "itterbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: delete 2)", + "principal": "test@EXAMPLE.ORG", + "password": "btterbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: delete 3/4)", + "principal": "test@EXAMPLE.ORG", + "password": "biterbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: delete 5)", + "principal": "test@EXAMPLE.ORG", + "password": "bittrbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: delete 6)", + "principal": "test@EXAMPLE.ORG", + "password": "bittebane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: delete 7)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: delete 8)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterbne", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: delete 9)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterbae", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: delete 10)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterban", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 1)", + "principal": "test@EXAMPLE.ORG", + "password": "Citterbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 2)", + "principal": "test@EXAMPLE.ORG", + "password": "b7tterbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 3)", + "principal": "test@EXAMPLE.ORG", + "password": "bi#terbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 4)", + "principal": "test@EXAMPLE.ORG", + "password": "bit*erbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 5)", + "principal": "test@EXAMPLE.ORG", + "password": "bittgrbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 6)", + "principal": "test@EXAMPLE.ORG", + "password": "bitte.bane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 7)", + "principal": "test@EXAMPLE.ORG", + "password": "bitter ane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 8)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterb-ne", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 9)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterbame", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: modify 10)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterbanq", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 2)", + "principal": "test@EXAMPLE.ORG", + "password": "b7itterbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 3)", + "principal": "test@EXAMPLE.ORG", + "password": "bi#tterbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 4)", + "principal": "test@EXAMPLE.ORG", + "password": "bit*terbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 4)", + "principal": "test@EXAMPLE.ORG", + "password": "bit*terbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 5)", + "principal": "test@EXAMPLE.ORG", + "password": "bittgerbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 6)", + "principal": "test@EXAMPLE.ORG", + "password": "bitte.rbane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 7)", + "principal": "test@EXAMPLE.ORG", + "password": "bitter bane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 8)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterb-ane", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 9)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterbamne", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" + }, + { + "name": "in dictionary (edit: add 10)", + "principal": "test@EXAMPLE.ORG", + "password": "bitterbanqe", + "code": "KADM5_PASS_Q_DICT", + "error": "password found in list of common passwords" } ] -- 2.39.2