STRLCPY/btcrecover

improve --min-typos performance for #112
Christopher Gurnee committed 7 years ago

f774485f

1 parent 8c9a5447

Revision indexing in progress... (symbol navigation in revisions will be accurate after indexed)

■ ■ ■ ■ ■ ■

btcrecover/btcrpass.py

		skipped 28 lines
29	29		# (all optional futures for 2.7)
30	30		from __future__ import print_function, absolute_import, division, unicode_literals
31	31
32		-	__version__ = "0.17.6"
	32	+	__version__ = "0.17.7"
33	33		__ordering_version__ = b"0.6.4" # must be updated whenever password ordering changes
34	34
35	35		import sys, argparse, itertools, string, re, multiprocessing, signal, os, cPickle, gc, \
		skipped 4062 lines
4098	4098		global password_dups, token_combination_dups, passwordlist_warnings
4099	4099		password_dups = token_combination_dups = None
4100	4100		passwordlist_warnings = 0
	4101	+	# (re)set the min_typos argument default values to 0
	4102	+	capslock_typos_generator.func_defaults = (0,)
	4103	+	swap_typos_generator .func_defaults = (0,)
	4104	+	simple_typos_generator .func_defaults = (0,)
	4105	+	insert_typos_generator .func_defaults = (0,)
4101	4106		#
4102	4107		def password_generator(chunksize = 1, only_yield_count = False):
4103	4108		assert chunksize > 0, "password_generator: chunksize > 0"
4104	4109		# Used to communicate between typo generators the number of typos that have been
4105	4110		# created so far during each password generated so that later generators know how
4106		-	# many additional typos, at most, they are permitted to add
	4111	+	# many additional typos, at most, they are permitted to add, and also if it is
	4112	+	# the last typo generator that will run, how many, at least, it must add
4107	4113		global typos_sofar
4108	4114		typos_sofar = 0
4109	4115
		skipped 10 lines
4120	4126
4121	4127		# Copy a few globals into local for a small speed boost
4122	4128		l_generator_product = generator_product
4123		-	l_args_min_typos = args.min_typos
4124	4129		l_regex_only = regex_only
4125	4130		l_regex_never = regex_never
4126	4131		l_password_dups = password_dups
		skipped 11 lines
4138	4143		if args.typos_insert: modification_generators.append( insert_typos_generator )
4139	4144		modification_generators_len = len(modification_generators)
4140	4145
	4146	+	# Only the last typo generator needs to enforce a min-typos requirement
	4147	+	if args.min_typos:
	4148	+	assert modification_generators[-1] != expand_wildcards_generator
	4149	+	# set the min_typos argument default value
	4150	+	modification_generators[-1].func_defaults = (args.min_typos,)
	4151	+
4141	4152		# The base password generator is set in parse_arguments(); it's either an iterable
4142	4153		# or a generator function (which returns an iterator) that produces base passwords
4143	4154		# usually based on either a tokenlist file (as parsed above) or a passwordlist file.
		skipped 21 lines
4165	4176		modification_iterator = (password_base,)
4166	4177
4167	4178		for password in modification_iterator:
4168		-
4169		-	if typos_sofar < l_args_min_typos: continue
4170	4179
4171	4180		# Check the password against the --regex-only and --regex-never options
4172	4181		if l_regex_only and not l_regex_only .search(password): continue
		skipped 636 lines
4809	4818		# capslock_typos_generator() is a generator function which tries swapping the case of
4810	4819		# the entire password (producing just one variation of the password_base in addition
4811	4820		# to the password_base itself)
4812		-	def capslock_typos_generator(password_base):
	4821	+	def capslock_typos_generator(password_base, min_typos = 0):
4813	4822		global typos_sofar
4814	4823
	4824	+	min_typos -= typos_sofar
	4825	+	if min_typos > 1: return # this generator can't ever generate more than 1 typo
	4826	+
4815	4827		# Start with the unmodified password itself, and end if there's nothing left to do
4816		-	yield password_base
	4828	+	if min_typos <= 0: yield password_base
4817	4829		if typos_sofar >= args.typos: return
4818	4830
4819	4831		password_swapped = password_base.swapcase()
		skipped 7 lines
4827	4839		# of the password_base where zero or more pairs of adjacent characters are swapped. Even
4828	4840		# when multiple swapping typos are requested, any single character is never swapped more
4829	4841		# than once per generated password.
4830		-	def swap_typos_generator(password_base):
	4842	+	def swap_typos_generator(password_base, min_typos = 0):
4831	4843		global typos_sofar
4832	4844		# Copy a few globals into local for a small speed boost
4833	4845		l_xrange = xrange
		skipped 1 lines
4835	4847		l_args_nodupchecks = args.no_dupchecks
4836	4848
4837	4849		# Start with the unmodified password itself
4838		-	yield password_base
	4850	+	min_typos -= typos_sofar
	4851	+	if min_typos <= 0: yield password_base
4839	4852
4840	4853		# First swap one pair of characters, then all combinations of 2 pairs, then of 3,
4841	4854		# up to the max requested or up to the max number swappable (whichever's less). The
4842	4855		# max number swappable is len // 2 because we never swap any single character twice.
4843	4856		password_base_len = len(password_base)
4844	4857		max_swaps = min(args.max_typos_swap, args.typos - typos_sofar, password_base_len // 2)
4845		-	for swap_count in l_xrange(1, max_swaps + 1):
	4858	+	for swap_count in l_xrange(max(1, min_typos), max_swaps + 1):
4846	4859		typos_sofar += swap_count
4847	4860
4848	4861		# Generate all possible combinations of swapping exactly swap_count characters;
		skipped 47 lines
4896	4909		# itself isn't very simple... it's called "simple" because the functions in the Configurables
4897	4910		# section which simple_typos_generator() calls are simple; they are collectively called
4898	4911		# simple typo generators)
4899		-	def simple_typos_generator(password_base):
	4912	+	def simple_typos_generator(password_base, min_typos = 0):
4900	4913		global typos_sofar
4901	4914		# Copy a few globals into local for a small speed boost
4902	4915		l_xrange = xrange
		skipped 4 lines
4907	4920		assert len(enabled_simple_typos) > 0, "simple_typos_generator: at least one simple typo enabled"
4908	4921
4909	4922		# Start with the unmodified password itself
4910		-	yield password_base
	4923	+	min_typos -= typos_sofar
	4924	+	if min_typos <= 0: yield password_base
4911	4925
4912	4926		# First change all single characters, then all combinations of 2 characters, then of 3, etc.
4913	4927		password_base_len = len(password_base)
4914	4928		max_typos = min(sum_max_simple_typos, args.typos - typos_sofar, password_base_len)
4915		-	for typos_count in l_xrange(1, max_typos + 1):
	4929	+	for typos_count in l_xrange(max(1, min_typos), max_typos + 1):
4916	4930		typos_sofar += typos_count
4917	4931
4918	4932		# Pre-calculate all possible permutations of the chosen simple_typos_choices
		skipped 84 lines
5003	5017		# insert_typos_generator() is a generator function which inserts one or more strings
5004	5018		# from the typos_insert_expanded list between every pair of characters in password_base,
5005	5019		# as well as at its beginning and its end.
5006		-	def insert_typos_generator(password_base):
	5020	+	def insert_typos_generator(password_base, min_typos = 0):
5007	5021		global typos_sofar
5008	5022		# Copy a few globals into local for a small speed boost
5009	5023		l_max_adjacent_inserts = args.max_adjacent_inserts
		skipped 1 lines
5011	5025		l_itertools_product = itertools.product
5012	5026
5013	5027		# Start with the unmodified password itself
5014		-	yield password_base
	5028	+	min_typos -= typos_sofar
	5029	+	if min_typos <= 0: yield password_base
5015	5030
5016	5031		password_base_len = len(password_base)
5017	5032		assert l_max_adjacent_inserts > 0
		skipped 7 lines
5025	5040		max_inserts = min(args.max_typos_insert, args.typos - typos_sofar, password_base_len + 1)
5026	5041
5027	5042		# First insert a single string, then all combinations of 2 strings, then of 3, etc.
5028		-	for inserts_count in l_xrange(1, max_inserts + 1):
	5043	+	for inserts_count in l_xrange(max(1, min_typos), max_inserts + 1):
5029	5044		typos_sofar += inserts_count
5030	5045
5031	5046		# Select the indexes (some possibly the same) of exactly inserts_count characters
		skipped 539 lines

■ ■ ■ ■ ■ ■

btcrecover/test/test_passwords.py

		skipped 468 lines
469	469		if tstr != unicode: self.skipTest("Unicode mode only")
470	470		self.do_generator_test(["Один2Три"], ["Один2Три", "оДИН2тРИ"],
471	471		"--typos-capslock --typos 2 -d", True)
	472	+	def test_capslock_min_1(self):
	473	+	self.do_generator_test(["One2Three"], ["oNE2tHREE"],
	474	+	"--typos-capslock --typos 2 -d --min-typos 1", True)
	475	+	def test_capslock_min_2(self):
	476	+	self.do_generator_test(["One2Three"], [],
	477	+	"--typos-capslock --typos 2 -d --min-typos 2", True)
472	478
473	479		def test_swap(self):
474	480		self.do_generator_test(["abcdd"], ["abcdd", "bacdd", "acbdd", "abdcd", "badcd"],
		skipped 1 lines
476	482		def test_swap_max(self):
477	483		self.do_generator_test(["abcdd"], ["abcdd", "bacdd", "acbdd", "abdcd"],
478	484		"--typos-swap --max-typos-swap 1 --typos 2 -d", True)
	485	+	def test_swap_min_1(self):
	486	+	self.do_generator_test(["abcdd"], ["bacdd", "acbdd", "abdcd", "badcd"],
	487	+	"--typos-swap --typos 2 -d --min-typos 1", True)
	488	+	def test_swap_min_2(self):
	489	+	self.do_generator_test(["abcdd"], ["badcd"],
	490	+	"--typos-swap --typos 2 -d --min-typos 2", True)
	491	+	def test_swap_min_3(self):
	492	+	self.do_generator_test(["abcdd"], [],
	493	+	"--typos-swap --typos 3 -d --min-typos 3", True)
479	494
480	495		def test_repeat(self):
481	496		self.do_generator_test(["abc"], ["abc", "aabc", "abbc", "abcc", "aabbc", "aabcc", "abbcc"],
		skipped 1 lines
483	498		def test_repeat_max(self):
484	499		self.do_generator_test(["abc"], ["abc", "aabc", "abbc", "abcc"],
485	500		"--typos-repeat --max-typos-repeat 1 --typos 2 -d", True)
	501	+	def test_repeat_min_1(self):
	502	+	self.do_generator_test(["abc"], ["aabc", "abbc", "abcc", "aabbc", "aabcc", "abbcc"],
	503	+	"--typos-repeat --typos 2 -d --min-typos 1", True)
	504	+	def test_repeat_min_2(self):
	505	+	self.do_generator_test(["abc"], ["aabbc", "aabcc", "abbcc"],
	506	+	"--typos-repeat --typos 2 -d --min-typos 2", True)
	507	+	def test_repeat_min_4(self):
	508	+	self.do_generator_test(["abc"], [],
	509	+	"--typos-repeat --typos 4 -d --min-typos 4", True)
486	510
487	511		def test_delete(self):
488	512		self.do_generator_test(["abc"], ["abc", "bc", "ac", "ab", "c", "b", "a"],
		skipped 27 lines
516	540		self.do_generator_test(["abc"],
517	541		["abc", "Xabc", "aXbc", "abXc", "abcX"],
518	542		"--typos-insert X --max-typos-insert 1 --typos 2 -d", True)
	543	+	def test_insert_min_1(self):
	544	+	self.do_generator_test(["abc"],
	545	+	["Xabc", "aXbc", "abXc", "abcX", "XaXbc", "XabXc", "XabcX", "aXbXc", "aXbcX", "abXcX"],
	546	+	"--typos-insert X --typos 2 -d --min-typos 1", True)
	547	+	def test_insert_min_2(self):
	548	+	self.do_generator_test(["abc"],
	549	+	["XaXbc", "XabXc", "XabcX", "aXbXc", "aXbcX", "abXcX"],
	550	+	"--typos-insert X --typos 2 -d --min-typos 2", True)
	551	+	def test_insert_min_5(self):
	552	+	self.do_generator_test(["abc"], [],
	553	+	"--typos-insert X --typos 5 -d --min-typos 5", True)
519	554		def test_insert_adjacent_1(self):
520	555		self.do_generator_test(["ab"], ["ab", "Xab", "aXb", "abX", "XXab", "XaXb", "XabX", "aXXb", "aXbX", "abXX"],
521	556		"--typos-insert X --typos 2 --max-adjacent-inserts 2 -d", True)
		skipped 1365 lines

improve --min-typos performance for #112