MD5 Brute Force Algorithm

I am coding an Objective-C MD5 hash "decrypter". Since you cannot decrypt such a hash function, I am approaching it with a brute force algorithm, that tries every single password combination until it found the correct one or not.

I would highly appreciate any help to improve the algorithm to make it even faster. I am currently computing approx. 28,000 guesses per second on my iMac and 7,000 on an iPhone 6. I know that 7,000 guesses are quite ridiculous compared to the performance a tool like hashcat has (2.2 billion guesses per second on my iMac), nonetheless I want a mobile MD5 decryption tool on my iPhone.

-(void)brute_sequentialWithMaxLength:(int)length
{
   iterateFurther = YES;

   char * buf = malloc(length + 1);

   for (int i=1; i <= length; i++)
   {
     memset(buf, 0, length+1);
     [self brute_implWithChar:buf andIndex:0 andDepth:i];
   }

  free(buf);
}

-(void)brute_implWithChar:(char*)str andIndex:(int)index andDepth:(int)max_depth
{ 

 for (int i=0; i < [pm_maskArray count] && iterateFurther == YES;i++)
 {
    alph = [[pm_maskArray objectAtIndex:i] characterAtIndex:0];

    str[index] = alph;

    if (index == max_depth - 1)
    {

         if ([[self makeMD5StringFromString:[NSString stringWithFormat:@"%s",str]] isEqualToString:pm_hashString])
         {
           NSLog(@"Found");
           iterateFurther = NO;
         }

    }
    else
    {
      [self brute_implWithChar:str andIndex:index+1 andDepth:max_depth];
    }

 }   
}

rolfl's answer pretty well explains why this isn't really a realistically reasonable approach to cracking passwords. I'm going to set that answer aside, ignore it, and address some of the specific ways in which this code could be improved if it were part of a more realistic program.

As a start, this code has one massive, massive problem: What happens when we actually find a match?

NSLog("Found");

And that's it.

We don't log the password. We don't post a notification, return it, tell a delegate. We don't save it as a local variable. We just post a borderline useless log statement claiming we found it.

And what's worse? WE KEEP CALCULATING!

We're done with this call to brute_implWithChar, but as soon as it returns, the loop in brute_sequentialWithMaxLength: is on another iteration and we jump right back in brute_implWithChar..., and go through all of that, and then return and do it all again, etc.

This is a major problem which should be addressed.

We can speed this up by using fast enumeration in brute_implWithChar...

But to do that, let's first talk about: pm_maskArray. You don't show this anywhere, but I can only assume it's an array of NSString objects. I'm going to recommend instead that we use an array of NSNumber objects.

And why NSNumber? Because NSNumber can also hold characters:

NSNumber *theCapitalLetterC = @'C';
char theCStyleCapicalCChar = [theCapitalLetterC characterValue];

So... presuming we've built pm_maskArray into an appropriate array of NSNumber objects, our loop is now going to look something more like this:

for (NSNumber *aChar in pm_maskArray) {
    char alph = [aChar characterValue];

    // all your checking stuff
    // when/if a match is found, we can:
    break;
    // to stop the loop and return executing at the first line after the loop
    // or in this case we can also:
    return;
    // to exit the method entirely.
}

As it stands, this forin loop will already allow you SEVERAL more guesses per second, as it will send a message to the pm_maskArray about once for every 16 times your version of the code was sending the message (approximately).

And looking back to my first point, we probably want to change this method to return an NSString object, rather than void. Then, if we find a match, we return it, otherwise, we return nil.

I'm also going to rename this method to strip the "and"s out of it, as they're inappropriate.

So if our method looks like this:

-(NSString *)brute_implWithChar:(char*)str index:(int)index depth:(int)depth
// returns matching password or nil

Then the loop in which we call it can look like this:

NSString *crackedPassword = nil;
while ((crackedPassword = [self brute_implWithChar:but index:0 depth:i]) == nil 
    && i <= length) {
    ++i;
}
return crackedPassword;

Now, on every unsuccessful call of brute_implWithChar:index:depth: for which we don't find a password, nil is returned and assigned to crackedPassword. If crackedPassword == nil evaluates to true AND i is still not larger than length, the loop will iterate again.

Meanwhile, the loop will stop iterating as soon as crackedPassword evaluates to anything non-nil. And since we're returning the password from the inner method, the outer method can return it to its caller as well. If the password isn't found before i <= length evaluates false, then nil will be returned, indicating that the password wasn't found--otherwise, the password is returned.

StackExchange Code Review Q#71250, answer score: 6