How to make all of the permutations of a password for brute force?

Question

So I was trying to make a program that brute forces passwords.

Firstly, I made a program for a password of length 1:

password = input('What is your password?\n')
chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'

def brute_force():
    for char in chars:
        if char == password:
            return char

print(brute_force())

Then I edited it for a password of length 2:

def brute_force():
    guess = [None, None]
    for char in chars:
        guess[0] = char
        for char2 in chars:
            guess[1] = char2
            if ''.join(guess) == password:
                return ''.join(guess)

Finally I did the same for a password of length 3:

def brute_force():
    guess = [None, None, None]
    for char in chars:
        guess[0] = char
        for char2 in chars:
            guess[1] = char2
            for char3 in chars:
                guess[2] = char3
                if ''.join(guess) == password:
                    return ''.join(guess)

How could I generalize this for a variable called length which contains the integer value of the lenght of the password?

Coltun

Use recursion – Chaddy

Have you thought about using itertools.product? – Sayce

Answer 1

You can use the following recursive function:

def brute_force(string, length, goal):
    if not length:
        if string == goal:
            return string
        return False
    for c in chars:
         s = brute_force(string + c, length - 1, goal)
         if s:
             return s
    return False

which you can call with syntax like:

>>> brute_force('', 3, 'bob')
'bob'
>>> brute_force('', 2, 'yo')
'yo'

---

Why does this work?

We always call each function with the three variables: string, length and goal. The variable string holds the current guess up to this point, so in the first example, string will be everything up to bob such as ab, bo etc.

The next variable length holds how many characters there are to go till the string is the right length.

The next variable goal is the correct password which we just pass through and is compare against.

In the main body of the function, we need to first check the case where length is 0 (done by checking not length as 0 evaluates to False). This is the case when we already have a string that is the length of the goal and we just want to check whether it is correct.

If it matches, then we return the string, otherwise we return False. We return either the solution or False to indicate to the function which called us (the call above in the stack) that we found the right password (or not).

We have now finished the case where length = 0 and now need to handle the other cases.

In these cases, the aim is to take the string that we have been called with and loop through all of the characters in chars, each time calling the brute_force function (recursive) with the result of the concatenation of the string we were called with and that character (c).

This will create a tree like affect where every string up to the original length is checked.

We also need to know what to do with the length and goal variables when calling the next function.

Well, to handle these, we just need to think what the next function needs to know. It already has the string (as this was the result of concatenating the next character in the chars string) and the length is just going to be one less as we just added one to the string through the concatenation and the goal is clearly going to be the same - we are still searching for the same password.

Now that we have called this function, it will run through subtracting one from the length at each of the subsequent calls it makes until it eventually reaches the case where length == 0. And we are at the easy case again and already know what to do!

So, after calling it, the function will return one of two things, either False indicating that the last node did not find the password (so this would occur in the case where something like ab reached the end in our search for bob so returned False after no solution was found), or, the call could return the actual solution.

Handling these cases is simple, if we got the actual solution, we just want to return that up the chain and if we got a fail (False), we just want to return False And that will indicate to the node above us that we did not succeed and tell it to continue its search.

So now, we just need to know how to call the function. We just need to send in an empty string and a target length and goal value and let the recursion take place.

---

Note one last thing is that if you wanted this to be even neater, you could modify the function definition to:

def brute_force(length, goal, string=''):
    ...

and change the recursive call within. This way, you could call the function with something just like: brute_force(3, 'bob') and wouldn't need to specify what string should start at. This is just something that you can add in if you want, but isn't necessary for the function to work.

Pushcart

Exactly what I meant, for completeness I would define chars within the function and you are good. – Polyvinyl

Could you explain a bit more please? (I am new to recursive functions) Thanks. – Coltun

@MilanTom Ended up writing a fairly long explanation! Hope it makes sense now – Pushcart

Presented like this, the function is almost useless and very inefficient. If you have the goal, all you'd need is to check that it has the correct length and that every character is in chars. – Vanbuskirk

@EricDuminil Well obviously! If they are asked to input their password, there is no need for any algorithm! Clearly if this were to be used in a real circumstance, the check would not simply be == goal, it would probably be another function of sorts that goes and does some hashing / encryption etc. – Pushcart

Why do you stop at length == 1 instead of length == 0? – Loathe

@StefanPochmann Of course! Missed that entirely, it only makes the code one line shorter but definitely makes sense :) – Pushcart

@MilanTom Well when you add an extra length, you will do all the searches below many (the length of chars) times so I think you should just call this function in a for-loop, starting at length 1 and working the way up until you find the password or reach a pre-defined limit (max length of the password). – Pushcart

Thanks, @JoeIddon! I deleted the comment because I figured out how to do it. – Coltun

Answer 2

In addition to the answer that shows you how this works, I'd like to draw attention to the fact that the standard library has a function for just this, in the shape of itertools.product—not itertools.permutations because that does not allow repetitions and therefore would only generate guesses with all unique characters:

from itertools import product

def brute_force():
    for length in range(min_length, max_length + 1):
        for p in product(chars, repeat=length):
            guess = ''.join(p)
            if guess == password:
                return guess

Position

Functional one-liner: return next(filter(password.__eq__, map(''.join, itertools.chain.from_iterable(map(functools.partial(itertools.permutations, chars), range(min_length, max_length+1))))), None) – Berke

You need itertools.product; permutations don't include duplicate characters. – Gunwale

@MilanTom Please note this answer has changed. – Position

Answer 3

Here's one solution:

password = input('What is your password? ')
chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'

def brute_force(length, check_callback, guess = ""):
    if check_callback(guess):
        return guess
    elif len(guess) == length: #Reached maximum length and didn't find the password
        return None
    for char in chars:
        retval = brute_force(length, check_callback, guess = guess + char)
        if retval is not None:
            return retval
    return None #Couldn't find anything

print(brute_force(len(password), lambda guess: (guess == password))) #len(password) => cheating just for this example

length is the maximum guess length the function will go up to. check_callback should take a guess and return a truthy value if it worked. The function returns the first successful guess, or None if it couldn't find anything.

I will admit I forgot about the guess length and was reminded by @Joe Iddon's answer.

---

Now, that function checks for a correct answer even if the guess isn't the right length yet, which is wasteful in some circumstances. Here's a function that doesn't do that:

def brute_force(length, check_callback, guess = ""):
    if len(guess) == length: #Reached maximum length
        return (guess if check_callback(guess) else None)
    for char in chars:
        retval = brute_force(length, check_callback, guess = guess + char)
        if retval is not None:
            return retval
    return None #Couldn't find anything
print(brute_force(len(password), lambda guess: guess == password)) #len(password) => cheating just for this example

Treasure

Upvote for check_callback, which could be a hash calculation for example. – Vanbuskirk

Answer 4

Try this:

password = input('What is your password?\n')
chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'

answer = ''
for i in range(len(password)):
    for char in chars:
        if char==password[i]:
            answer += char

print(answer)

Instead of using nested loops it guesses each character in turn.

Pueblo

This is ok but in application, you will only know if you got the password correct when you submit the whole password - even one character wrong will mean the password will be rejected. – Coltun