Time Complexity Python Script

Question

I am writing a small script that guesses numeric passwords (including ones with leading zeros). The script works fine but I am having trouble understanding what the worst case time complexity would be for this algorithm. Any insight on the complexity of this implementation would be great, thanks.

def bruteforce(cipherText):
    for pLen in itertools.count():
        for password in itertools.product("0123456789", repeat=pLen):
            if hashlib.sha256("".join(password)).hexdigest() == cipherText:
                return "".join(password)

Answer 1

First, it's always possible that you're going to find a hash collision before you find the right password. And, for a long-enough input string, this is guaranteed. So, really, the algorithm is constant time: it will complete in about 2^256 steps no matter what the input is.

But this isn't very helpful when you're asking about how it scales with more reasonable N, so let's assume we had some upper limit that was low enough where hash collisions weren't relevant.

Now, if the password is length N, the outer loop will run N times.*

_{* I'm assuming here that the password really will be purely numeric. Otherwise, of course, it'll fail to find the right answer at N and keep going until it finds a hash collision.}

How long does the inner loop take? Well, the main thing it does is iterate each element in product("0123456789", repeat=pLen). That just iterates the cartesian product of the 10-element list pLen times—in other words, there are 10^pLen elements in the product.

Since 10**pLen is greater than sum(10**i for i in range(pLen)) (e.g., 100000 > 11111), we can ignore all but the last time through the outer loop, so that 10**pLen is the total number of inner loops.

The stuff that it does inside each inner loop is all linear on pLen (joining a string, hashing a string) or constant (comparing two hashes), so there are (10^pLen)*pLen total steps.

So, the worst-case complexity is exponential: O(10^N). Because that's the same as multiplying N by a constant and then doing 2^cN, that's the same complexity class as O(2^N).

If you want to combine the two together, you could call this O(2^min(log2(10)*N, 256)). Which, again, is constant-time (since the asymptote is still 2^256), but shows how it's practically exponential if you only care about smaller N.