657 lines
21 KiB
Python
657 lines
21 KiB
Python
from zxcvbn import scoring
|
|
from . import adjacency_graphs
|
|
from zxcvbn.frequency_lists import FREQUENCY_LISTS
|
|
import re
|
|
|
|
from zxcvbn.scoring import most_guessable_match_sequence
|
|
|
|
|
|
def build_ranked_dict(ordered_list):
|
|
return {word: idx for idx, word in enumerate(ordered_list, 1)}
|
|
|
|
RANKED_DICTIONARIES = {}
|
|
|
|
|
|
def add_frequency_lists(frequency_lists_):
|
|
for name, lst in frequency_lists_.items():
|
|
RANKED_DICTIONARIES[name] = build_ranked_dict(lst)
|
|
|
|
|
|
add_frequency_lists(FREQUENCY_LISTS)
|
|
|
|
GRAPHS = {
|
|
'qwerty': adjacency_graphs.ADJACENCY_GRAPHS['qwerty'],
|
|
'dvorak': adjacency_graphs.ADJACENCY_GRAPHS['dvorak'],
|
|
'keypad': adjacency_graphs.ADJACENCY_GRAPHS['keypad'],
|
|
'mac_keypad': adjacency_graphs.ADJACENCY_GRAPHS['mac_keypad'],
|
|
}
|
|
|
|
L33T_TABLE = {
|
|
'a': ['4', '@'],
|
|
'b': ['8'],
|
|
'c': ['(', '{', '[', '<'],
|
|
'e': ['3'],
|
|
'g': ['6', '9'],
|
|
'i': ['1', '!', '|'],
|
|
'l': ['1', '|', '7'],
|
|
'o': ['0'],
|
|
's': ['$', '5'],
|
|
't': ['+', '7'],
|
|
'x': ['%'],
|
|
'z': ['2'],
|
|
}
|
|
|
|
REGEXEN = {
|
|
'recent_year': re.compile(r'19\d\d|200\d|201\d'),
|
|
}
|
|
|
|
DATE_MAX_YEAR = 2050
|
|
DATE_MIN_YEAR = 1000
|
|
DATE_SPLITS = {
|
|
4: [ # for length-4 strings, eg 1191 or 9111, two ways to split:
|
|
[1, 2], # 1 1 91 (2nd split starts at index 1, 3rd at index 2)
|
|
[2, 3], # 91 1 1
|
|
],
|
|
5: [
|
|
[1, 3], # 1 11 91
|
|
[2, 3], # 11 1 91
|
|
],
|
|
6: [
|
|
[1, 2], # 1 1 1991
|
|
[2, 4], # 11 11 91
|
|
[4, 5], # 1991 1 1
|
|
],
|
|
7: [
|
|
[1, 3], # 1 11 1991
|
|
[2, 3], # 11 1 1991
|
|
[4, 5], # 1991 1 11
|
|
[4, 6], # 1991 11 1
|
|
],
|
|
8: [
|
|
[2, 4], # 11 11 1991
|
|
[4, 6], # 1991 11 11
|
|
],
|
|
}
|
|
|
|
|
|
# omnimatch -- perform all matches
|
|
def omnimatch(password, _ranked_dictionaries=RANKED_DICTIONARIES):
|
|
matches = []
|
|
for matcher in [
|
|
dictionary_match,
|
|
reverse_dictionary_match,
|
|
l33t_match,
|
|
spatial_match,
|
|
repeat_match,
|
|
sequence_match,
|
|
regex_match,
|
|
date_match,
|
|
]:
|
|
matches.extend(matcher(password, _ranked_dictionaries=_ranked_dictionaries))
|
|
|
|
return sorted(matches, key=lambda x: (x['i'], x['j']))
|
|
|
|
|
|
# dictionary match (common passwords, english, last names, etc)
|
|
def dictionary_match(password, _ranked_dictionaries=RANKED_DICTIONARIES):
|
|
matches = []
|
|
length = len(password)
|
|
password_lower = password.lower()
|
|
for dictionary_name, ranked_dict in _ranked_dictionaries.items():
|
|
for i in range(length):
|
|
for j in range(i, length):
|
|
if password_lower[i:j + 1] in ranked_dict:
|
|
word = password_lower[i:j + 1]
|
|
rank = ranked_dict[word]
|
|
matches.append({
|
|
'pattern': 'dictionary',
|
|
'i': i,
|
|
'j': j,
|
|
'token': password[i:j + 1],
|
|
'matched_word': word,
|
|
'rank': rank,
|
|
'dictionary_name': dictionary_name,
|
|
'reversed': False,
|
|
'l33t': False,
|
|
})
|
|
|
|
return sorted(matches, key=lambda x: (x['i'], x['j']))
|
|
|
|
|
|
def reverse_dictionary_match(password,
|
|
_ranked_dictionaries=RANKED_DICTIONARIES):
|
|
reversed_password = ''.join(reversed(password))
|
|
matches = dictionary_match(reversed_password, _ranked_dictionaries)
|
|
for match in matches:
|
|
match['token'] = ''.join(reversed(match['token']))
|
|
match['reversed'] = True
|
|
match['i'], match['j'] = len(password) - 1 - match['j'], \
|
|
len(password) - 1 - match['i']
|
|
|
|
return sorted(matches, key=lambda x: (x['i'], x['j']))
|
|
|
|
|
|
def relevant_l33t_subtable(password, table):
|
|
password_chars = {}
|
|
for char in list(password):
|
|
password_chars[char] = True
|
|
|
|
subtable = {}
|
|
for letter, subs in table.items():
|
|
relevant_subs = [sub for sub in subs if sub in password_chars]
|
|
if len(relevant_subs) > 0:
|
|
subtable[letter] = relevant_subs
|
|
|
|
return subtable
|
|
|
|
|
|
def enumerate_l33t_subs(table):
|
|
keys = list(table.keys())
|
|
subs = [[]]
|
|
|
|
def dedup(subs):
|
|
deduped = []
|
|
members = {}
|
|
for sub in subs:
|
|
assoc = [(k, v) for v, k in sub]
|
|
assoc.sort()
|
|
label = '-'.join([k + ',' + str(v) for k, v in assoc])
|
|
if label not in members:
|
|
members[label] = True
|
|
deduped.append(sub)
|
|
|
|
return deduped
|
|
|
|
def helper(keys, subs):
|
|
if not len(keys):
|
|
return subs
|
|
|
|
first_key = keys[0]
|
|
rest_keys = keys[1:]
|
|
next_subs = []
|
|
for l33t_chr in table[first_key]:
|
|
for sub in subs:
|
|
dup_l33t_index = -1
|
|
for i in range(len(sub)):
|
|
if sub[i][0] == l33t_chr:
|
|
dup_l33t_index = i
|
|
break
|
|
if dup_l33t_index == -1:
|
|
sub_extension = list(sub)
|
|
sub_extension.append([l33t_chr, first_key])
|
|
next_subs.append(sub_extension)
|
|
else:
|
|
sub_alternative = list(sub)
|
|
sub_alternative.pop(dup_l33t_index)
|
|
sub_alternative.append([l33t_chr, first_key])
|
|
next_subs.append(sub)
|
|
next_subs.append(sub_alternative)
|
|
|
|
subs = dedup(next_subs)
|
|
return helper(rest_keys, subs)
|
|
|
|
subs = helper(keys, subs)
|
|
sub_dicts = [] # convert from assoc lists to dicts
|
|
for sub in subs:
|
|
sub_dict = {}
|
|
for l33t_chr, chr in sub:
|
|
sub_dict[l33t_chr] = chr
|
|
sub_dicts.append(sub_dict)
|
|
|
|
return sub_dicts
|
|
|
|
|
|
def translate(string, chr_map):
|
|
chars = []
|
|
for char in list(string):
|
|
if chr_map.get(char, False):
|
|
chars.append(chr_map[char])
|
|
else:
|
|
chars.append(char)
|
|
|
|
return ''.join(chars)
|
|
|
|
|
|
def l33t_match(password, _ranked_dictionaries=RANKED_DICTIONARIES,
|
|
_l33t_table=L33T_TABLE):
|
|
matches = []
|
|
|
|
for sub in enumerate_l33t_subs(
|
|
relevant_l33t_subtable(password, _l33t_table)):
|
|
if not len(sub):
|
|
break
|
|
|
|
subbed_password = translate(password, sub)
|
|
for match in dictionary_match(subbed_password, _ranked_dictionaries):
|
|
token = password[match['i']:match['j'] + 1]
|
|
if token.lower() == match['matched_word']:
|
|
# only return the matches that contain an actual substitution
|
|
continue
|
|
|
|
# subset of mappings in sub that are in use for this match
|
|
match_sub = {}
|
|
for subbed_chr, chr in sub.items():
|
|
if subbed_chr in token:
|
|
match_sub[subbed_chr] = chr
|
|
match['l33t'] = True
|
|
match['token'] = token
|
|
match['sub'] = match_sub
|
|
match['sub_display'] = ', '.join(
|
|
["%s -> %s" % (k, v) for k, v in match_sub.items()]
|
|
)
|
|
matches.append(match)
|
|
|
|
matches = [match for match in matches if len(match['token']) > 1]
|
|
|
|
return sorted(matches, key=lambda x: (x['i'], x['j']))
|
|
|
|
|
|
# repeats (aaa, abcabcabc) and sequences (abcdef)
|
|
def repeat_match(password, _ranked_dictionaries=RANKED_DICTIONARIES):
|
|
matches = []
|
|
greedy = re.compile(r'(.+)\1+')
|
|
lazy = re.compile(r'(.+?)\1+')
|
|
lazy_anchored = re.compile(r'^(.+?)\1+$')
|
|
last_index = 0
|
|
while last_index < len(password):
|
|
greedy_match = greedy.search(password, pos=last_index)
|
|
lazy_match = lazy.search(password, pos=last_index)
|
|
|
|
if not greedy_match:
|
|
break
|
|
|
|
if len(greedy_match.group(0)) > len(lazy_match.group(0)):
|
|
# greedy beats lazy for 'aabaab'
|
|
# greedy: [aabaab, aab]
|
|
# lazy: [aa, a]
|
|
match = greedy_match
|
|
# greedy's repeated string might itself be repeated, eg.
|
|
# aabaab in aabaabaabaab.
|
|
# run an anchored lazy match on greedy's repeated string
|
|
# to find the shortest repeated string
|
|
base_token = lazy_anchored.search(match.group(0)).group(1)
|
|
else:
|
|
match = lazy_match
|
|
base_token = match.group(1)
|
|
|
|
i, j = match.span()[0], match.span()[1] - 1
|
|
|
|
# recursively match and score the base string
|
|
base_analysis = most_guessable_match_sequence(
|
|
base_token,
|
|
omnimatch(base_token)
|
|
)
|
|
base_matches = base_analysis['sequence']
|
|
base_guesses = base_analysis['guesses']
|
|
matches.append({
|
|
'pattern': 'repeat',
|
|
'i': i,
|
|
'j': j,
|
|
'token': match.group(0),
|
|
'base_token': base_token,
|
|
'base_guesses': base_guesses,
|
|
'base_matches': base_matches,
|
|
'repeat_count': len(match.group(0)) / len(base_token),
|
|
})
|
|
last_index = j + 1
|
|
|
|
return matches
|
|
|
|
|
|
def spatial_match(password, _graphs=GRAPHS, _ranked_dictionaries=RANKED_DICTIONARIES):
|
|
matches = []
|
|
for graph_name, graph in _graphs.items():
|
|
matches.extend(spatial_match_helper(password, graph, graph_name))
|
|
|
|
return sorted(matches, key=lambda x: (x['i'], x['j']))
|
|
|
|
|
|
SHIFTED_RX = re.compile(r'[~!@#$%^&*()_+QWERTYUIOP{}|ASDFGHJKL:"ZXCVBNM<>?]')
|
|
|
|
|
|
def spatial_match_helper(password, graph, graph_name):
|
|
matches = []
|
|
i = 0
|
|
while i < len(password) - 1:
|
|
j = i + 1
|
|
last_direction = None
|
|
turns = 0
|
|
if graph_name in ['qwerty', 'dvorak', ] and \
|
|
SHIFTED_RX.search(password[i]):
|
|
# initial character is shifted
|
|
shifted_count = 1
|
|
else:
|
|
shifted_count = 0
|
|
|
|
while True:
|
|
prev_char = password[j - 1]
|
|
found = False
|
|
found_direction = -1
|
|
cur_direction = -1
|
|
try:
|
|
adjacents = graph[prev_char] or []
|
|
except KeyError:
|
|
adjacents = []
|
|
# consider growing pattern by one character if j hasn't gone
|
|
# over the edge.
|
|
if j < len(password):
|
|
cur_char = password[j]
|
|
for adj in adjacents:
|
|
cur_direction += 1
|
|
if adj and cur_char in adj:
|
|
found = True
|
|
found_direction = cur_direction
|
|
if adj.index(cur_char) == 1:
|
|
# index 1 in the adjacency means the key is shifted,
|
|
# 0 means unshifted: A vs a, % vs 5, etc.
|
|
# for example, 'q' is adjacent to the entry '2@'.
|
|
# @ is shifted w/ index 1, 2 is unshifted.
|
|
shifted_count += 1
|
|
if last_direction != found_direction:
|
|
# adding a turn is correct even in the initial case
|
|
# when last_direction is null:
|
|
# every spatial pattern starts with a turn.
|
|
turns += 1
|
|
last_direction = found_direction
|
|
break
|
|
# if the current pattern continued, extend j and try to grow again
|
|
if found:
|
|
j += 1
|
|
# otherwise push the pattern discovered so far, if any...
|
|
else:
|
|
if j - i > 2: # don't consider length 1 or 2 chains.
|
|
matches.append({
|
|
'pattern': 'spatial',
|
|
'i': i,
|
|
'j': j - 1,
|
|
'token': password[i:j],
|
|
'graph': graph_name,
|
|
'turns': turns,
|
|
'shifted_count': shifted_count,
|
|
})
|
|
# ...and then start a new search for the rest of the password.
|
|
i = j
|
|
break
|
|
|
|
return matches
|
|
|
|
|
|
MAX_DELTA = 5
|
|
|
|
|
|
def sequence_match(password, _ranked_dictionaries=RANKED_DICTIONARIES):
|
|
# Identifies sequences by looking for repeated differences in unicode codepoint.
|
|
# this allows skipping, such as 9753, and also matches some extended unicode sequences
|
|
# such as Greek and Cyrillic alphabets.
|
|
#
|
|
# for example, consider the input 'abcdb975zy'
|
|
#
|
|
# password: a b c d b 9 7 5 z y
|
|
# index: 0 1 2 3 4 5 6 7 8 9
|
|
# delta: 1 1 1 -2 -41 -2 -2 69 1
|
|
#
|
|
# expected result:
|
|
# [(i, j, delta), ...] = [(0, 3, 1), (5, 7, -2), (8, 9, 1)]
|
|
if len(password) == 1:
|
|
return []
|
|
|
|
def update(i, j, delta):
|
|
if j - i > 1 or (delta and abs(delta) == 1):
|
|
if 0 < abs(delta) <= MAX_DELTA:
|
|
token = password[i:j + 1]
|
|
if re.compile(r'^[a-z]+$').match(token):
|
|
sequence_name = 'lower'
|
|
sequence_space = 26
|
|
elif re.compile(r'^[A-Z]+$').match(token):
|
|
sequence_name = 'upper'
|
|
sequence_space = 26
|
|
elif re.compile(r'^\d+$').match(token):
|
|
sequence_name = 'digits'
|
|
sequence_space = 10
|
|
else:
|
|
sequence_name = 'unicode'
|
|
sequence_space = 26
|
|
result.append({
|
|
'pattern': 'sequence',
|
|
'i': i,
|
|
'j': j,
|
|
'token': password[i:j + 1],
|
|
'sequence_name': sequence_name,
|
|
'sequence_space': sequence_space,
|
|
'ascending': delta > 0
|
|
})
|
|
|
|
result = []
|
|
i = 0
|
|
last_delta = None
|
|
|
|
for k in range(1, len(password)):
|
|
delta = ord(password[k]) - ord(password[k - 1])
|
|
if last_delta is None:
|
|
last_delta = delta
|
|
if delta == last_delta:
|
|
continue
|
|
j = k - 1
|
|
update(i, j, last_delta)
|
|
i = j
|
|
last_delta = delta
|
|
update(i, len(password) - 1, last_delta)
|
|
|
|
return result
|
|
|
|
|
|
def regex_match(password, _regexen=REGEXEN, _ranked_dictionaries=RANKED_DICTIONARIES):
|
|
matches = []
|
|
for name, regex in _regexen.items():
|
|
for rx_match in regex.finditer(password):
|
|
matches.append({
|
|
'pattern': 'regex',
|
|
'token': rx_match.group(0),
|
|
'i': rx_match.start(),
|
|
'j': rx_match.end()-1,
|
|
'regex_name': name,
|
|
'regex_match': rx_match,
|
|
})
|
|
|
|
return sorted(matches, key=lambda x: (x['i'], x['j']))
|
|
|
|
|
|
def date_match(password, _ranked_dictionaries=RANKED_DICTIONARIES):
|
|
# a "date" is recognized as:
|
|
# any 3-tuple that starts or ends with a 2- or 4-digit year,
|
|
# with 2 or 0 separator chars (1.1.91 or 1191),
|
|
# maybe zero-padded (01-01-91 vs 1-1-91),
|
|
# a month between 1 and 12,
|
|
# a day between 1 and 31.
|
|
#
|
|
# note: this isn't true date parsing in that "feb 31st" is allowed,
|
|
# this doesn't check for leap years, etc.
|
|
#
|
|
# recipe:
|
|
# start with regex to find maybe-dates, then attempt to map the integers
|
|
# onto month-day-year to filter the maybe-dates into dates.
|
|
# finally, remove matches that are substrings of other matches to reduce noise.
|
|
#
|
|
# note: instead of using a lazy or greedy regex to find many dates over the full string,
|
|
# this uses a ^...$ regex against every substring of the password -- less performant but leads
|
|
# to every possible date match.
|
|
matches = []
|
|
maybe_date_no_separator = re.compile(r'^\d{4,8}$')
|
|
maybe_date_with_separator = re.compile(
|
|
r'^(\d{1,4})([\s/\\_.-])(\d{1,2})\2(\d{1,4})$'
|
|
)
|
|
|
|
# dates without separators are between length 4 '1191' and 8 '11111991'
|
|
for i in range(len(password) - 3):
|
|
for j in range(i + 3, i + 8):
|
|
if j >= len(password):
|
|
break
|
|
|
|
token = password[i:j + 1]
|
|
if not maybe_date_no_separator.match(token):
|
|
continue
|
|
candidates = []
|
|
for k, l in DATE_SPLITS[len(token)]:
|
|
dmy = map_ints_to_dmy([
|
|
int(token[0:k]),
|
|
int(token[k:l]),
|
|
int(token[l:])
|
|
])
|
|
if dmy:
|
|
candidates.append(dmy)
|
|
if not len(candidates) > 0:
|
|
continue
|
|
# at this point: different possible dmy mappings for the same i,j
|
|
# substring. match the candidate date that likely takes the fewest
|
|
# guesses: a year closest to 2000. (scoring.REFERENCE_YEAR).
|
|
#
|
|
# ie, considering '111504', prefer 11-15-04 to 1-1-1504
|
|
# (interpreting '04' as 2004)
|
|
best_candidate = candidates[0]
|
|
|
|
def metric(candidate_):
|
|
return abs(candidate_['year'] - scoring.REFERENCE_YEAR)
|
|
|
|
min_distance = metric(candidates[0])
|
|
for candidate in candidates[1:]:
|
|
distance = metric(candidate)
|
|
if distance < min_distance:
|
|
best_candidate, min_distance = candidate, distance
|
|
matches.append({
|
|
'pattern': 'date',
|
|
'token': token,
|
|
'i': i,
|
|
'j': j,
|
|
'separator': '',
|
|
'year': best_candidate['year'],
|
|
'month': best_candidate['month'],
|
|
'day': best_candidate['day'],
|
|
})
|
|
|
|
# dates with separators are between length 6 '1/1/91' and 10 '11/11/1991'
|
|
for i in range(len(password) - 5):
|
|
for j in range(i + 5, i + 10):
|
|
if j >= len(password):
|
|
break
|
|
token = password[i:j + 1]
|
|
rx_match = maybe_date_with_separator.match(token)
|
|
if not rx_match:
|
|
continue
|
|
dmy = map_ints_to_dmy([
|
|
int(rx_match.group(1)),
|
|
int(rx_match.group(3)),
|
|
int(rx_match.group(4)),
|
|
])
|
|
if not dmy:
|
|
continue
|
|
matches.append({
|
|
'pattern': 'date',
|
|
'token': token,
|
|
'i': i,
|
|
'j': j,
|
|
'separator': rx_match.group(2),
|
|
'year': dmy['year'],
|
|
'month': dmy['month'],
|
|
'day': dmy['day'],
|
|
})
|
|
|
|
# matches now contains all valid date strings in a way that is tricky to
|
|
# capture with regexes only. while thorough, it will contain some
|
|
# unintuitive noise:
|
|
#
|
|
# '2015_06_04', in addition to matching 2015_06_04, will also contain
|
|
# 5(!) other date matches: 15_06_04, 5_06_04, ..., even 2015
|
|
# (matched as 5/1/2020)
|
|
#
|
|
# to reduce noise, remove date matches that are strict substrings of others
|
|
def filter_fun(match):
|
|
is_submatch = False
|
|
for other in matches:
|
|
if match == other:
|
|
continue
|
|
if other['i'] <= match['i'] and other['j'] >= match['j']:
|
|
is_submatch = True
|
|
break
|
|
return not is_submatch
|
|
|
|
return sorted(filter(filter_fun, matches), key=lambda x: (x['i'], x['j']))
|
|
|
|
|
|
def map_ints_to_dmy(ints):
|
|
# given a 3-tuple, discard if:
|
|
# middle int is over 31 (for all dmy formats, years are never allowed in
|
|
# the middle)
|
|
# middle int is zero
|
|
# any int is over the max allowable year
|
|
# any int is over two digits but under the min allowable year
|
|
# 2 ints are over 31, the max allowable day
|
|
# 2 ints are zero
|
|
# all ints are over 12, the max allowable month
|
|
if ints[1] > 31 or ints[1] <= 0:
|
|
return
|
|
over_12 = 0
|
|
over_31 = 0
|
|
under_1 = 0
|
|
for int in ints:
|
|
if 99 < int < DATE_MIN_YEAR or int > DATE_MAX_YEAR:
|
|
return
|
|
if int > 31:
|
|
over_31 += 1
|
|
if int > 12:
|
|
over_12 += 1
|
|
if int <= 0:
|
|
under_1 += 1
|
|
if over_31 >= 2 or over_12 == 3 or under_1 >= 2:
|
|
return
|
|
|
|
# first look for a four digit year: yyyy + daymonth or daymonth + yyyy
|
|
possible_four_digit_splits = [
|
|
(ints[2], ints[0:2]),
|
|
(ints[0], ints[1:3]),
|
|
]
|
|
for y, rest in possible_four_digit_splits:
|
|
if DATE_MIN_YEAR <= y <= DATE_MAX_YEAR:
|
|
dm = map_ints_to_dm(rest)
|
|
if dm:
|
|
return {
|
|
'year': y,
|
|
'month': dm['month'],
|
|
'day': dm['day'],
|
|
}
|
|
else:
|
|
# for a candidate that includes a four-digit year,
|
|
# when the remaining ints don't match to a day and month,
|
|
# it is not a date.
|
|
return
|
|
|
|
# given no four-digit year, two digit years are the most flexible int to
|
|
# match, so try to parse a day-month out of ints[0..1] or ints[1..0]
|
|
for y, rest in possible_four_digit_splits:
|
|
dm = map_ints_to_dm(rest)
|
|
if dm:
|
|
y = two_to_four_digit_year(y)
|
|
return {
|
|
'year': y,
|
|
'month': dm['month'],
|
|
'day': dm['day'],
|
|
}
|
|
|
|
|
|
def map_ints_to_dm(ints):
|
|
for d, m in [ints, reversed(ints)]:
|
|
if 1 <= d <= 31 and 1 <= m <= 12:
|
|
return {
|
|
'day': d,
|
|
'month': m,
|
|
}
|
|
|
|
|
|
def two_to_four_digit_year(year):
|
|
if year > 99:
|
|
return year
|
|
elif year > 50:
|
|
# 87 -> 1987
|
|
return year + 1900
|
|
else:
|
|
# 15 -> 2015
|
|
return year + 2000
|