[Tutor] Suggestions for more efficient and optimized coding technique,
Michael Langford
michael.langford at rowdylabs.com
Thu Jan 8 21:20:12 CET 2009
I understand that each response is unique Robert and no caching is
required to solve the problem at hand. However in a real program, the
chance you're brute forcing just one password is small (usually you
would brute force many); additionally, the question posted
specifically asked that the trials be cached, which is why I suggest
you do so, not out of any real need for just testing on the "loner"
testcase.
Additionally, the reason the aaaaa->zzzzz method is suggested is that
it a much faster algorithm to test every available combination than
the random method. The random method may never find the data.
I've created a frame work for you to play around with on this problem.
It shows how long different methods take in a more realistic scenario.
Try some other methods if you want, as well play around with password
length, the aaaaa->zzzzz method, etc. I've shorted then password
length to 3 to make it run faster as well. Enough procrastination,
back to google app engine stuff.
--Michael
#!/usr/bin/env python
import string
import random
# test code to simulate a computer system under
# attack, no need to understand now
class Computer(object):
def __init__(self):
self.reset_password()
def reset_password(self,length=3):
self.secret_password=''.join(random.sample(string.ascii_lowercase,length))
print('The new password is: ' + self.secret_password)
def enter_password(self,teststr):
"""returns true if the password was correct"""
return teststr==self.secret_password
# end test code
def rand_string(length = 3):
"""generates a random string of the given length"""
return ''.join(random.sample(string.ascii_lowercase,length))
passcache = list()
def crack_password(comp):
"""repeatedly tries passwords on the given computer"""
tries = 0
while True:
tries += 1
if comp.enter_password(rand_string()):
print( 'Password found in ' + str(tries) + ' tries.')
return
def crack_password_cached(comp):
"""repeatedly tries passwords on the given computer"""
for password in passcache:
if comp.enter_password(password):
print 'Password found in cache'
return
tries = 0
while True:
tries += 1
s = rand_string()
passcache.append(s)
if comp.enter_password(s):
print( 'Password found in ' + str(tries) + ' tries.')
return
def hack():
"""hacks a computer via a brute force method"""
my_computer = Computer()
crack_password(my_computer)
def hack_cached():
"""hacks a computer via a brute force method with cached results"""
my_computer = Computer()
crack_password_cached(my_computer)
def mean(ls):
"""finds the mean of a list of numbers"""
return sum(ls)/len(ls)
def test_case(funcname, repeats):
"""
timeit is a python library for timing code. No need to
understand how this works, just that its repeating the
command given the number times specified by repeats. It's
returning a list of the execution times of each of the trials
"""
import timeit
timer = timeit.Timer("%s()"%funcname,"from __main__ import %s"%funcname)
return timer.repeat(number=repeats)
if __name__ == '__main__':
times_to_repeat = 100
uc_results = test_case("hack",times_to_repeat)
c_results = test_case("hack_cached", times_to_repeat)
print( "Cached mean time: " + repr(mean(c_results)) )
print( "Cached min. time: " + repr(min(c_results)) )
print( "Uncached mean time: " + repr(mean(uc_results)) )
print( "Uncached min. time: " + repr(min(uc_results)) )
On Thu, Jan 8, 2009 at 1:31 PM, Robert Berman <bermanrl at cfl.rr.com> wrote:
> Michael,
>
> Thank you for your code and your commentary. The code tells me this is
> really an ongoing learning process; almost as convoluted as linguistics and
> certainly every bit as interesting.
>
> Your concept of brute force in this example is intriguing. It is as if I
> have five cogs spinning, 'a' the slowest and 'e' flying as fast as its
> spokes can engage, and every click of every wheel produces a viable but
> possibly wrong response. However, each response is unique and in the nth
> iteration where password is found, all previous iterations are unique so
> there is certainly no need to carry the previous responses in either a list
> or a dictionary. They do not duplicate since they cannot repeat. Other than
> to include extraneous code, why include repetitive checking at all?
>
> In spite of that, your code and your remarks are most appreciated.
>
> Robert
>
> Michael Langford wrote:
>
> Here is your algorithm made more pythonic. Notice the use of default
> parameters, doc strings, not abbreviated variable names, unix C style
> capitolization (very subjective, but often the one found in python
> libs), the avoidance of control variables when possible, the use of
> ascii_lowercase instead of your own string and the not calling
> functions main that aren't __main__.
>
> #!/usr/bin/env python
> import string
> import random
>
> def rand_string(length = 5):
> """returns a random string of numbers"""
> return ''.join(random.sample(string.ascii_lowercase,length))
>
> def try_password(match="loner"):
> """randomly tries 5 letter long passwords until the user finds the
> correct one"""
> tries = 0
> while True:
> tries += 1
> if rand_string() == match:
> print 'Password found in ' + str(tries) + ' tries.'
> return
>
> if __name__ == '__main__':
> try_password()
>
>
> Note: I do not think you're doing the problem the way the author
> intended. As it wants you to try all combinations, and it's about
> brute force, not finding it quickly, you most likely should start at
> "aaaaa" and move to "zzzzz", and cache the results in a list like they
> ask you too. At the very least, you should be saving these
> combinations you are generating randomly in a list (as it asks you to)
> and not testing the password if the generated string was already in
> the list (as in a real application, that is the time consuming or
> dangerous operation).
>
> --Michael
>
> PS: If you wish to assure direct replies reach me
>
> On Thu, Jan 8, 2009 at 10:49 AM, Robert Berman <bermanrl at cfl.rr.com> wrote:
>
>
> Hi,
>
> One of the challenges on the challenge you web page appropriately titled
> 'Brute force' reads as follows:
>
> "The password you have to guess is 'loner' . Try all combinations of
> lowercase letters until you guess it. Try not to loop much for example,
> save all used combinations in an array so you don't repeat."
>
> My code is as follows:
>
> #!/usr/bin/env python
>
> import random
>
> def GetString():
> alphabet='abcdefghijklmnopqrstuvwxyz'
> return ''.join(random.sample(alphabet,5))
> def main():
> password='loner'
> errknt = 0
> control = True
> while control is True:
> if GetString() != password:
> errknt +=1
> else:
> print 'Password found in ',errknt,' tries.'
> control = False
>
> if __name__ == '__main__': main()
> The code does work. I am looking for suggestions to learn more about both
> efficiency and optimization of code.
>
> Since the challenge revolves around the use of randomized retrieval, I'm not
> too sure how to optimize the process. The authors concept of using arrays
> seem a bit superfluous as I think it takes longer to add an item to a
> dictionary and retrieve an item from a dictionary than it does to do an if
> compare of two 5 character strings. So, I left that code out of the program
> entirely. If that was wrong, or there is a better way to avoid duplication,
> please point me in the right direction.
>
> I think, perhaps, I could make it a tad more efficient if I changed
> 'alphabet' from a string to a list as I remember reading that lists are
> significantly faster to manipulate than are strings. Is that true and is it
> a viable change.
>
> I realize my code looks like modified C++ structured code. I am trying to
> become more Python concise but I think that is a matter of writing more and
> more python code.
>
> All suggestions, ideas, critiques are most welcome.
>
> Thank you,
>
> Robert
> _______________________________________________
> Tutor maillist - Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>
>
>
>
--
Michael Langford
Phone: 404-386-0495
Web: http://www.RowdyLabs.com
More information about the Tutor
mailing list