How to decrease runtime for generating permutations of a string?

Question

I have written a function that takes in a MD5 hashvalue and finds its input/original value by permuting all possible combinations of a string. As per BIT_CHEETAH's answer on a SO question:

... you cannot decrypt MD5 without attempting something like brute force hacking which is extremely resource intensive, not practical, and unethical.

(Source: encrypt and decrypt md5)

I'm well aware of this, however, I am using this scenario to implement a string permutation function. I would also like to stick to the recursive methodology as opposed to others. The best summary of doing this is probably summarised by Mark Byers post:

 - Try each of the letters in turn as the first letter and then find all
   the permutations of the remaining letters using a recursive call.
 - The base case is when the input is an empty string the only permutation is the empty string.

(Generating all permutations of a given string)

Anyway, so I implemented this and got the following:

function matchMD5($possibleChars, $md5, $concat, $length) {
    for($i = 0; $i < strlen($possibleChars); $i++) {
        $ch = $possibleChars[$i];
        $concatSubstr = $concat.$ch;
        if(strlen($concatSubstr) != $length) {
            matchMD5($possibleChars, $md5, $concatSubstr, $length);
        }
        else if(strlen($concatSubstr) == $length) {
            $tryHash = hash('md5', $concatSubstr);
            if ($tryHash == $md5) {
                echo "Match! $concatSubstr ";
                return $concatSubstr;
            }
        }
    }
}

Works 100%, however when I pass in a four character array, my server runs 10.7 seconds to generate a match where the match lies approximately 1/10th of the way of all possible permutations. My valid characters in which the functions permutes, called, $possibleChars, contains all alphanumeric characters plus a few selected punctionations:

0123456789.,;:abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

Question: Can the above code be written to run faster somehow?

Answer 1

When doing brute-force, you have to run through all the possibilities, there is not way of cutting a corner there. So you are left with profiling your code to find out what the application spends the most time doing and then trying to optimize that.