CODEWITHSUNDEEP
pythonbrute-force
Chaker
Chaker

Reputation: 1207

Key Bruteforcing

I need to find a password key. The length of the key is 10 characters and the order of the letters in the key is 3,7,2,1,4,5,6,10,8,9. I also know the md5 of the key.

So I wrote

mystring = "abcdefghijklmnopqrstuvwxyz"
for letter3 in mystring:
    for letter7 in mystring[mystring.index(letter3):]:
        for letter2 in mystring[:mystring.index(letter7)]:
            for letter1 in mystring[:mystring.index(letter2)]:
                for letter4 in mystring[mystring.index(letter1):]:
                    for letter5 in mystring[mystring.index(letter4):]:
                        for letter6 in mystring[mystring.index(letter4):]:
                            for letter10 in mystring[mystring.index(leter6):]:  
                                for letter8 in mystring[:mystring.index(letter10)]:
                                    for letter9 in mystring[mystring.index(letter8):]:
                                        strr = "".join([letter1,letter2,letter3,letter4,letter5,letter6,letter7,letter8,letter9,letter10])
                                        if hashlib.md5(strr).hexdigest() == md5:
                                            print "key = " ,strr
                                            break

The order of characters:

The key:

|letter1|letter2|letter3|letter4|letter5|letter6|letter7|letter8|letter9|letter10|

The key sorted alphabetically:

|letter3|letter7|letter2|letter1|letter4|letter5|letter6|letter10|letter8|letter9|

The problem is the time (It take ~ 6 hours for one iteration in the outside loop ). Any suggestions to optimize the range of for loops?

Upvotes: 4

Views: 239

Answers (2)

QuestionC
QuestionC

Reputation: 10064

The solution is at the bottom

You're very close. What you want is this...

mystring = "abcdefghijklmnopqrstuvwxyz"
for letter1 in mystring:
    for letter2 in mystring[mystring.index(letter1):]:
        for letter3 in mystring[mystring.index(letter2):]:
            for letter4 in mystring[mystring.index(letter3):]:
                for letter5 in mystring[mystring.index(letter4):]:
                    for letter6 in mystring[mystring.index(letter5):]:
                        for letter7 in mystring[mystring.index(letter6):]:
                            for letter8 in mystring[mystring.index(leter7):]:  
                                for letter9 in mystring[mystring.index(letter8):]:
                                    for letter10 in mystring[mystring.index(letter9):]:
                                        strr = "".join([letter3,letter7,letter2,letter1,letter4,letter5,letter6,letter10,letter8,letter9])
                                        if hashlib.md5(strr).hexdigest() == md5:
                                            print "key = " ,strr
                                            break

That loop seriously cuts down on the number of iterations because you're searching many fewer characters. Each loop searches fewer characters than its outer loop. Note how it's much more organized with each loop searching in the same direction.

But it is also very slow because mystring.index() is a slow operation. We can make it faster by not using mystring.index()...

mystring = "abcdefghijklmnopqrstuvwxyz"

for i1 in range(len(mystring)):
    for i2 in range(i1, len(mystring)):
        for i3 in range(i2, len(mystring)):
            for i4 in range(i3, len(mystring)):
                for i5 in range(i4, len(mystring)):
                    for i6 in range(i5, len(mystring)):
                        for i7 in range (i6, len(mystring)):
                            for i8 in range (i7, len(mystring)):
                                for i9 in range (i8, len(mystring)):
                                    for i10 in range (i9, len(mystring)):
                                        strr = "".join([mystring[i3], mystring[i7], mystring[i2], mystring[i1], mystring[i4], mystring[i5], mystring[i6], mystring[i10], mystring[i8], mystring[i9]])
                                        if hashlib.md5(strr).hexdigest() == md5:
                                            print "key = " ,strr
                                            break

This is still super slow though, just because it's a huge number of iterations.

The trick here is itertools...

mystring = "abcdefghijklmnopqrstuvwxyz"

import itertools

for L1, L2, L3, L4, L5, L6, L7, L8, L9, L10 in itertools.combinations_with_replacement(mystring, 10):
    strr = "".join([L3, L7, L2, L1, L4, L5, L6, L10, L8, L9])
    if hashlib.md5(strr).hexdigest() == 'a50e38475041f76219748ee22c4377d4':
        print ('key = {}'.format(strr))
        break

itertools.combinations_with_replacement() is how you handle these sorts of nested loops where A >= B >= C >= &ct in python and it's quite fast. This is the fastest possible solution afaik.

Upvotes: 6

Flying_Banana
Flying_Banana

Reputation: 2910

If you compile it down to machine code, you find that for loop amounts to four parts. First the current iteration integer is loaded from memory, and the letter from the given array is loaded. Then whatever is within your for loop executes, and finally the index is incremented and a conditional jump is performed back to the beginning of the for loop if the condition still holds.

The only way to optimise the process (although I cannot claim about python; I've tried to optimise C's for loops) is to get rid of the increment part and use constants instead. That is, manually layout the iteration of letters. That is, get rid of the for loop and copy and paste thousand of lines of code instead. This is obviously not very ideal and not reusable, and the for loop we set out to optimise is, well, gone.

I guess what I'm trying to say is that for loop is very optimised already, being something very fundamental in assembly. You are trying to brute force it after all.

Upvotes: -1

Related Questions