Nesting a function inside itself (i'm desperate)

Question

Mentally exhausted.

An explanation just for context, dont actually need help with hashes:

I'm trying to make a python script that can bruteforce a hashed string or password (learning only, i'm sure there are tenter code herehousands out there). The goal is making a function that can try all the possible combinations of different letters, starting from one character (a, b... y, z) and then start trying with one more character (aa, ab... zy, zz then aaa, aab... zzy, zzz) indefinetly until it finds a match.

First, it asks you for a string (aaaa for example) then it hashes the string, and then try to bruteforce that hash with the function, and finally the function returns the string again when it finds a match.

PASSWORD_INPUT = input("Password string input: ")
PASSWORD_HASH = encrypt_password(PASSWORD_INPUT)  # This returns the clean hash
found_password = old_decrypt()  # This is the function below
print(found_password)

I managed to do this chunk of ugly ass code:

built_password = ['', '', '', '', '', '', '', '', '', '', '', '', '', '', '', '']

def old_decrypt():
    global built_password

    # First letter
    for a in range(len(characters)):  # Characters is a list with the abecedary
        built_password[0] = characters[a]
        if test_password(pretty(built_password)):  # This returns True if it matches
            return pretty(built_password)

        # Second letter
        for b in range(len(characters)):
            built_password[1] = characters[b]
            if test_password(pretty(built_password)):
                return pretty(built_password)

            # Third letter
            for c in range(len(characters)):
                built_password[2] = characters[c]
                if test_password(pretty(built_password)):
                    return pretty(built_password)

                # Fourth letter
                for d in range(len(characters)):
                    built_password[3] = characters[d]
                    if test_password(pretty(built_password)):
                        return pretty(built_password)

The problem of this is that it only works with 4 letters strings.

As you can see, it's almost the exact same loop for every letter, so i thought "Hey i can make this a single function"... After obsessively trying everything that came to my mind for 3 whole days i came with this:

# THIS WORKS
def decrypt(letters_amount_int):
    global built_password

    for function_num in range(letters_amount_int):
        for letter in range(len(characters)):

            built_password[function_num] = characters[letter]
            if letters_amount_int >= 1:
                decrypt(letters_amount_int - 1)

            if test_password(pretty(built_password)):
                return pretty(built_password)

# START
n = 1
while True:
    returned = decrypt(n)

# If it returns a string it gets printed, else trying to print None raises TypeError
    try:
        print("Found hash for: " + returned)
        break
    except TypeError:
        n += 1

Function gets a "1", tries with 1 letter and if it doesnt return anything it gets a "2" and then tries with 2. It works, but for some reason it makes a ridiculous number of unnecessary loops that takes exponentially more and more time, i've been smashing my head and came to the conclussion that i'm not understanding something about python's internal functioning.

Can someone please drop some light on this? Thanks

In case of needed these are the other functions:

def encrypt_password(password_str):
    return hashlib.sha256(password_str.encode()).hexdigest()

def test_password(password_to_test_str):
    global PASSWORD_HASH
    if PASSWORD_HASH == encrypt_password(password_to_test_str):
        return True

characters = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
              'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j',
              'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't',
              'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D',
              'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
              'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
              'Y', 'Z']

Answer 1

Maybe you could try something like this. Inspired by Multiple permutations, including duplicates

Itertools has a cartesian product generator, which is related to permutation.

import itertools

def decrypt(characters, num_chars):
    for test_list in itertools.product(characters, repeat=num_chars):
        test_str = ''.join(test_list)
        if test_password(test_str):
            return test_str
        
    return None


for i in range(min_chars, max_chars+1):
    result = decrypt(characters, i)
    if result:
        print(f'Match found: {result}')

If you run this code with characters, min_chars, max_chars = (characters, 1, 3) and print test_str at each step, you'll get:

0
1
2
00
01
02
10
11
12
20
21
22

or will stop earlier if a match is found. I recommend you look up a recursive, pure python implementation of the the cartesian product function if you want to learn more. However, I'd suspect the cartesian product generator will be faster than a recursive solution.

Note that itertools.product() is a generator, so it's generating each value on demand, and writing it this way allows you to find a match for shorter strings faster than longer ones. But the time it takes this brute force algorithm should indeed increase exponentially with the length of the true password.

Hope this helps.

Answer 2

Recursion in this case gives a very elegant solution:

def add_char(s, limit):
    if len(s) == limit:
        yield s
    else:
        for c in characters:
            yield from add_char(s + c, limit)


def generate_all_passwords_up_to_length(maxlen):
    for i in range(1, maxlen + 1):
        yield from add_char("", i)


for password in generate_all_passwords_up_to_length(5):
    test_password(password)