Why is my brute-force MD5 hack not working?

Question

For class, I was given a password that was run through the md5 hash. I am told that it is a maximum of 6 characters, uppercase and digits only. I am to write a brute force algorithm to reveal the original password. I have been able to get my own hash values, run it through my program, and decode it, but it fails on the one my teacher gave us. I sourced my md5 from a website and checked its results against others so I know that isn't the issue. Is there some error in my code, like I'm not covering all possible combinations, or is there most likely an error in the hash value given to me?

#include <stdlib.h>
#include <string>
#include <iostream>
#include "md5.h"//File was sourced from http://www.zedwood.com/article/cpp-md5-function

using namespace std;

const int numPossibleChar = 36;
const string givenHash = "ad2ad129385e4b2ba3b477378bc1d9b6";
long count=0;//make sure I go through all combinations

const char * charOptions[numPossibleChar]={"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", "1", "2", "3", "4", "5", "6", "7",
                            "8", "9", "0"};



int main()
{   
    for( int i =0; i<numPossibleChar; i++)
    {
         string guess1 = charOptions[i];
        string guessHash = md5(guess1);
        if( md5(guess1)==givenHash)
        {
            cout <<"match, password is: "<< guess1<<endl;
            return 0;
        }
        cout<<guess1<<endl;
        count++;
        for (int j=0; j<numPossibleChar; j++)
        {
            string guess2=guess1+charOptions[j];
            if( md5(guess2)==givenHash)
            {
                cout <<"match, password is: "<< guess2<<endl;
                return 0;
            }
            count++;
            for(int k=0; k<numPossibleChar; k++)
            {
                string guess3=guess2+charOptions[k];
                if( md5(guess3)== givenHash)
                {
                    cout <<"match, password is: "<< guess3<<endl;
                    return 0;
                }
                count++;
                for(int l=0; l<numPossibleChar; l++)
                {
                    string guess4=guess3+charOptions[l];
                    if( md5(guess4)== givenHash)
                    {
                        cout <<"match, password is: "<< guess4<<endl;
                        return 0;
                    }
                    count++;
                    for(int m=0; m<numPossibleChar; m++)
                    {
                        string guess5=guess4+charOptions[m];
                        if( md5(guess4)==givenHash)
                        {
                            cout <<"match, password is: "<< guess5<<endl;
                            return 0;
                        }
                        count++;
                        for(int n=0; n<numPossibleChar; n++)
                        {
                            string guess6=guess5+charOptions[n];
                            if( md5(guess6)==givenHash)
                            {
                                cout <<"match, password is: "<< guess6<<endl;
                                return 0;
                            }
                            count++;
                        }
                    }
                }

            }
        }
    }

    cout << "Count "<<count<<endl;




    return 0;
}

And no, I don't actually have what the final value of count is. I intially has it as an int instead of a long, so after running 9 hours it overflowed. I wanted to check with you guys before I ran it again and got a new number.

Answer 1

Style issues aside,

                string guess4=guess3+charOptions[l];
                if( md5(guess4)== givenHash)
                {
                    cout <<"match, password is: "<< guess4<<endl;
                    return 0;
                }
                count++;
                for(int m=0; m<numPossibleChar; m++)
                {
                    string guess5=guess4+charOptions[m];
                    if( md5(guess4)==givenHash)
                    {
                        cout <<"match, password is: "<< guess5<<endl;
                        return 0;
                    }

I would venture a guess that you did not mean to check md5(guess4) twice.

Edit, to expand on this and style issues: Obviously without checking md5(guess5), one in six potential passwords would be missed.

There are easy ways around this type of bug by refactoring your code for better style. Of particular note, I suggest you read up on the Arrow Anti-pattern. You have a lot of code duplication (eg, conducting the nearly/exact same operations with different variables) which means you could easily refactor into either a recursive function or stacked (push/pop to heap style) loop and achieve easier-to-read (thus generally less-prone to errors) code.

If it took 9 hours for you to overflow your count, I would suggest you've got a bit of a performance problem (assuming you're running on relatively recent hardware). You could further expand on that to reduce the number of string allocations and deallocations by reusing your existing strings for each check. For example, count can be inferred strictly by adding count=1+i+j+k+l+m+n, so it wouldn't be necessary to increment it manually.