<s> import math <EOL> import re <EOL> from zxcvbn . matching import ( KEYBOARD_STARTING_POSITIONS , KEYBOARD_AVERAGE_DEGREE , <EOL> KEYPAD_STARTING_POSITIONS , KEYPAD_AVERAGE_DEGREE ) <EOL> def binom ( n , k ) : <EOL> """<STR_LIT>""" <EOL> if k > n : <EOL> return <NUM_LIT:0> <EOL> if k == <NUM_LIT:0> : <EOL> return <NUM_LIT:1> <EOL> result = <NUM_LIT:1> <EOL> for denom in range ( <NUM_LIT:1> , k + <NUM_LIT:1> ) : <EOL> result *= n <EOL> result /= denom <EOL> n -= <NUM_LIT:1> <EOL> return result <EOL> def lg ( n ) : <EOL> """<STR_LIT>""" <EOL> return math . log ( n , <NUM_LIT:2> ) <EOL> def get ( a , i ) : <EOL> if i < <NUM_LIT:0> or i >= len ( a ) : <EOL> return <NUM_LIT:0> <EOL> return a [ i ] <EOL> def minimum_entropy_match_sequence ( password , matches ) : <EOL> """<STR_LIT>""" <EOL> bruteforce_cardinality = calc_bruteforce_cardinality ( password ) <EOL> up_to_k = [ <NUM_LIT:0> ] * len ( password ) <EOL> backpointers = [ ] <EOL> for k in range ( <NUM_LIT:0> , len ( password ) ) : <EOL> up_to_k [ k ] = get ( up_to_k , k - <NUM_LIT:1> ) + lg ( bruteforce_cardinality ) <EOL> backpointers . append ( None ) <EOL> for match in matches : <EOL> if match [ '<STR_LIT>' ] != k : <EOL> continue <EOL> i , j = match [ '<STR_LIT:i>' ] , match [ '<STR_LIT>' ] <EOL> up_to = get ( up_to_k , i - <NUM_LIT:1> ) <EOL> candidate_entropy = up_to + calc_entropy ( match ) <EOL> if candidate_entropy < up_to_k [ j ] : <EOL> up_to_k [ j ] = candidate_entropy <EOL> backpointers [ j ] = match <EOL> match_sequence = [ ] <EOL> k = len ( password ) - <NUM_LIT:1> <EOL> while k >= <NUM_LIT:0> : <EOL> match = backpointers [ k ] <EOL> if match : <EOL> match_sequence . append ( match ) <EOL> k = match [ '<STR_LIT:i>' ] - <NUM_LIT:1> <EOL> else : <EOL> k -= <NUM_LIT:1> <EOL> match_sequence . reverse ( ) <EOL> def make_bruteforce_match ( i , j ) : <EOL> return { <EOL> '<STR_LIT>' : '<STR_LIT>' , <EOL> '<STR_LIT:i>' : i , <EOL> '<STR_LIT>' : j , <EOL> '<STR_LIT>' : password [ i : j + <NUM_LIT:1> ] , <EOL> '<STR_LIT>' : lg ( math . pow ( bruteforce_cardinality , j - i + <NUM_LIT:1> ) ) , <EOL> '<STR_LIT>' : bruteforce_cardinality , <EOL> } <EOL> k = <NUM_LIT:0> <EOL> match_sequence_copy = [ ] <EOL> for match in match_sequence : <EOL> i , j = match [ '<STR_LIT:i>' ] , match [ '<STR_LIT>' ] <EOL> if i - k > <NUM_LIT:0> : <EOL> match_sequence_copy . append ( make_bruteforce_match ( k , i - <NUM_LIT:1> ) ) <EOL> k = j + <NUM_LIT:1> <EOL> match_sequence_copy . append ( match ) <EOL> if k < len ( password ) : <EOL> match_sequence_copy . append ( make_bruteforce_match ( k , len ( password ) - <NUM_LIT:1> ) ) <EOL> match_sequence = match_sequence_copy <EOL> min_entropy = <NUM_LIT:0> if len ( password ) == <NUM_LIT:0> else up_to_k [ len ( password ) - <NUM_LIT:1> ] <EOL> crack_time = entropy_to_crack_time ( min_entropy ) <EOL> return { <EOL> '<STR_LIT:password>' : password , <EOL> '<STR_LIT>' : round_to_x_digits ( min_entropy , <NUM_LIT:3> ) , <EOL> '<STR_LIT>' : match_sequence , <EOL> '<STR_LIT>' : round_to_x_digits ( crack_time , <NUM_LIT:3> ) , <EOL> '<STR_LIT>' : display_time ( crack_time ) , <EOL> '<STR_LIT>' : crack_time_to_score ( crack_time ) , <EOL> } <EOL> def round_to_x_digits ( number , digits ) : <EOL> """<STR_LIT>""" <EOL> return round ( number * math . pow ( <NUM_LIT:10> , digits ) ) / math . pow ( <NUM_LIT:10> , digits ) <EOL> SINGLE_GUESS = <NUM_LIT> <EOL> NUM_ATTACKERS = <NUM_LIT:100> <EOL> SECONDS_PER_GUESS = SINGLE_GUESS / NUM_ATTACKERS <EOL> def entropy_to_crack_time ( entropy ) : <EOL> return ( <NUM_LIT:0.5> * math . pow ( <NUM_LIT:2> , entropy ) ) * SECONDS_PER_GUESS <EOL> def crack_time_to_score ( seconds ) : <EOL> if seconds < math . pow ( <NUM_LIT:10> , <NUM_LIT:2> ) : <EOL> return <NUM_LIT:0> <EOL> if seconds < math . pow ( <NUM_LIT:10> , <NUM_LIT:4> ) : <EOL> return <NUM_LIT:1> <EOL> if seconds < math . pow ( <NUM_LIT:10> , <NUM_LIT:6> ) : <EOL> return <NUM_LIT:2> <EOL> if seconds < math . pow ( <NUM_LIT:10> , <NUM_LIT:8> ) : <EOL> return <NUM_LIT:3> <EOL> return <NUM_LIT:4> <EOL> def calc_entropy ( match ) : <EOL> if '<STR_LIT>' in match : return match [ '<STR_LIT>' ] <EOL> if match [ '<STR_LIT>' ] == '<STR_LIT>' : <EOL> entropy_func = repeat_entropy <EOL> elif match [ '<STR_LIT>' ] == '<STR_LIT>' : <EOL> entropy_func = sequence_entropy <EOL> elif match [ '<STR_LIT>' ] == '<STR_LIT>' : <EOL> entropy_func = digits_entropy <EOL> elif match [ '<STR_LIT>' ] == '<STR_LIT>' : <EOL> entropy_func = year_entropy <EOL> elif match [ '<STR_LIT>' ] == '<STR_LIT:date>' : <EOL> entropy_func = date_entropy <EOL> elif match [ '<STR_LIT>' ] == '<STR_LIT>' : <EOL> entropy_func = spatial_entropy <EOL> elif match [ '<STR_LIT>' ] == '<STR_LIT>' : <EOL> entropy_func = dictionary_entropy <EOL> match [ '<STR_LIT>' ] = entropy_func ( match ) <EOL> return match [ '<STR_LIT>' ] <EOL> def repeat_entropy ( match ) : <EOL> cardinality = calc_bruteforce_cardinality ( match [ '<STR_LIT>' ] ) <EOL> return lg ( cardinality * len ( match [ '<STR_LIT>' ] ) ) <EOL> def sequence_entropy ( match ) : <EOL> first_chr = match [ '<STR_LIT>' ] [ <NUM_LIT:0> ] <EOL> if first_chr in [ '<STR_LIT:a>' , '<STR_LIT:1>' ] : <EOL> base_entropy = <NUM_LIT:1> <EOL> else : <EOL> if first_chr . isdigit ( ) : <EOL> base_entropy = lg ( <NUM_LIT:10> ) <EOL> elif first_chr . isalpha ( ) : <EOL> base_entropy = lg ( <NUM_LIT> ) <EOL> else : <EOL> base_entropy = lg ( <NUM_LIT> ) + <NUM_LIT:1> <EOL> if not match [ '<STR_LIT>' ] : <EOL> base_entropy += <NUM_LIT:1> <EOL> return base_entropy + lg ( len ( match [ '<STR_LIT>' ] ) ) <EOL> def digits_entropy ( match ) : <EOL> return lg ( math . pow ( <NUM_LIT:10> , len ( match [ '<STR_LIT>' ] ) ) ) <EOL> NUM_YEARS = <NUM_LIT> <EOL> NUM_MONTHS = <NUM_LIT:12> <EOL> NUM_DAYS = <NUM_LIT> <EOL> def year_entropy ( match ) : <EOL> return lg ( NUM_YEARS ) <EOL> def date_entropy ( match ) : <EOL> if match [ '<STR_LIT>' ] < <NUM_LIT:100> : <EOL> entropy = lg ( NUM_DAYS * NUM_MONTHS * <NUM_LIT:100> ) <EOL> else : <EOL> entropy = lg ( NUM_DAYS * NUM_MONTHS * NUM_YEARS ) <EOL> if match [ '<STR_LIT>' ] : <EOL> entropy += <NUM_LIT:2> <EOL> return entropy <EOL> def spatial_entropy ( match ) : <EOL> if match [ '<STR_LIT>' ] in [ '<STR_LIT>' , '<STR_LIT>' ] : <EOL> s = KEYBOARD_STARTING_POSITIONS <EOL> d = KEYBOARD_AVERAGE_DEGREE <EOL> else : <EOL> s = KEYPAD_STARTING_POSITIONS <EOL> d = KEYPAD_AVERAGE_DEGREE <EOL> possibilities = <NUM_LIT:0> <EOL> L = len ( match [ '<STR_LIT>' ] ) <EOL> t = match [ '<STR_LIT>' ] <EOL> for i in range ( <NUM_LIT:2> , L + <NUM_LIT:1> ) : <EOL> possible_turns = min ( t , i - <NUM_LIT:1> ) <EOL> for j in range ( <NUM_LIT:1> , possible_turns + <NUM_LIT:1> ) : <EOL> x = binom ( i - <NUM_LIT:1> , j - <NUM_LIT:1> ) * s * math . pow ( d , j ) <EOL> possibilities += x <EOL> entropy = lg ( possibilities ) <EOL> if '<STR_LIT>' in match : <EOL> S = match [ '<STR_LIT>' ] <EOL> U = L - S <EOL> possibilities = sum ( binom ( S + U , i ) for i in xrange ( <NUM_LIT:0> , min ( S , U ) + <NUM_LIT:1> ) ) <EOL> entropy += lg ( possibilities ) <EOL> return entropy <EOL> def dictionary_entropy ( match ) : <EOL> match [ '<STR_LIT>' ] = lg ( match [ '<STR_LIT>' ] ) <EOL> match [ '<STR_LIT>' ] = extra_uppercase_entropy ( match ) <EOL> match [ '<STR_LIT>' ] = extra_l33t_entropy ( match ) <EOL> ret = match [ '<STR_LIT>' ] + match [ '<STR_LIT>' ] + match [ '<STR_LIT>' ] <EOL> return ret <EOL> START_UPPER = re . compile ( '<STR_LIT>' ) <EOL> END_UPPER = re . compile ( '<STR_LIT>' ) <EOL> ALL_UPPER = re . compile ( '<STR_LIT>' ) <EOL> def extra_uppercase_entropy ( match ) : <EOL> word = match [ '<STR_LIT>' ] <EOL> if word . islower ( ) : <EOL> return <NUM_LIT:0> <EOL> for regex in [ START_UPPER , END_UPPER , ALL_UPPER ] : <EOL> if regex . match ( word ) : <EOL> return <NUM_LIT:1> <EOL> upp_len = len ( [ x for x in word if x . isupper ( ) ] ) <EOL> low_len = len ( [ x for x in word if x . islower ( ) ] ) <EOL> possibilities = sum ( binom ( upp_len + low_len , i ) for i in range ( <NUM_LIT:0> , min ( upp_len , low_len ) + <NUM_LIT:1> ) ) <EOL> return lg ( possibilities ) <EOL> def extra_l33t_entropy ( match ) : <EOL> if '<STR_LIT>' not in match or not match [ '<STR_LIT>' ] : <EOL> return <NUM_LIT:0> <EOL> possibilities = <NUM_LIT:0> <EOL> for subbed , unsubbed in match [ '<STR_LIT>' ] . items ( ) : <EOL> sub_len = len ( [ x for x in match [ '<STR_LIT>' ] if x == subbed ] ) <EOL> unsub_len = len ( [ x for x in match [ '<STR_LIT>' ] if x == unsubbed ] ) <EOL> possibilities += sum ( binom ( unsub_len + sub_len , i ) for i in range ( <NUM_LIT:0> , min ( unsub_len , sub_len ) + <NUM_LIT:1> ) ) <EOL> if possibilities <= <NUM_LIT:1> : <EOL> return <NUM_LIT:1> <EOL> return lg ( possibilities ) <EOL> def calc_bruteforce_cardinality ( password ) : <EOL> lower , upper , digits , symbols = <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> , <NUM_LIT:0> <EOL> for char in password : <EOL> if char . islower ( ) : <EOL> lower = <NUM_LIT> <EOL> elif char . isdigit ( ) : <EOL> digits = <NUM_LIT:10> <EOL> elif char . isupper ( ) : <EOL> upper = <NUM_LIT> <EOL> else : <EOL> symbols = <NUM_LIT> <EOL> cardinality = lower + digits + upper + symbols <EOL> return cardinality <EOL> def display_time ( seconds ) : <EOL> minute = <NUM_LIT> <EOL> hour = minute * <NUM_LIT> <EOL> day = hour * <NUM_LIT> <EOL> month = day * <NUM_LIT> <EOL> year = month * <NUM_LIT:12> <EOL> century = year * <NUM_LIT:100> <EOL> if seconds < minute : <EOL> return '<STR_LIT>' <EOL> elif seconds < hour : <EOL> return str ( <NUM_LIT:1> + math . ceil ( seconds / minute ) ) + "<STR_LIT>" <EOL> elif seconds < day : <EOL> return str ( <NUM_LIT:1> + math . ceil ( seconds / hour ) ) + "<STR_LIT>" <EOL> elif seconds < month : <EOL> return str ( <NUM_LIT:1> + math . ceil ( seconds / day ) ) + "<STR_LIT>" <EOL> elif seconds < year : <EOL> return str ( <NUM_LIT:1> + math . ceil ( seconds / month ) ) + "<STR_LIT>" <EOL> elif seconds < century : <EOL> return str ( <NUM_LIT:1> + math . ceil ( seconds / year ) ) + "<STR_LIT>" <EOL> else : <EOL> return '<STR_LIT>' </s>
