StackOverFlowException thrown only when multi-threading

Question

I'm writing a program to help me gather statistics for a research report I'm writing on password security. I decided to make the application run on multiple threads when attempted to brute-force an MD5 hashed password for the obvious performance increase. The application runs fine on a single thread, but the moment 2 threads are running, a StackOverFlowException is throwing at "using (MD5 md5Hash = MD5.Create())" in the TryPass function.

    // Microsoft's GetMd5Hash function.
    static string GetMd5Hash(MD5 md5Hash, string input)
    {
        // Convert the input string to a byte array and compute the hash. 
        byte[] data = md5Hash.ComputeHash(Encoding.UTF8.GetBytes(input));

        // Create a new Stringbuilder to collect the bytes 
        // and create a string.
        StringBuilder sBuilder = new StringBuilder();

        // Loop through each byte of the hashed data  
        // and format each one as a hexadecimal string. 
        for (int i = 0; i < data.Length; i++)
        {
            sBuilder.Append(data[i].ToString("x2"));
        }

        // Return the hexadecimal string. 
        return sBuilder.ToString();
    }

    static bool TryPass(string attempt, string password)
    {
        using (MD5 md5Hash = MD5.Create())
        {
            if (GetMd5Hash(md5Hash, attempt) == password)
                return true;
            else
                return false;
        }
    }



    static bool BruteForce(BruteOptions bruteOptions)
    {
        if (bruteOptions.prefix.Length == 1 && TryPass(bruteOptions.prefix, bruteOptions.password)) // If it's the first in a series, try it.
            return true;

        for (int i = 0; i < bruteOptions.chars.Length; i++)
        {
            if (TryPass(bruteOptions.prefix + bruteOptions.chars[i], bruteOptions.password))
            {
                Console.WriteLine("The password is: " + bruteOptions.prefix + bruteOptions.chars[i]);
                return true;
            }

            if (bruteOptions.prefix.Length + 1 < bruteOptions.maxLength)
                if (BruteForce(bruteOptions))
                    return true;

            //Console.WriteLine(prefix + chars[i]);
        }

        return false;
    }



    public struct BruteOptions
    {
        public string password, prefix;
        public char[] chars;
        public int maxLength;
    }

    static void OptionBruteForce()
    {
        Console.WriteLine("-----------------------");
        Console.WriteLine("----- Brute-Force -----");
        Console.WriteLine("-----------------------");

        BruteOptions bruteOptions = new BruteOptions();
        bruteOptions.password = ReadString("Enter the MD5 password hash to brute-force: ");
        bruteOptions.chars = ReadString("Enter the characters to use: ").ToCharArray();
        bruteOptions.maxLength = ReadIntegerRange("Max length of password: ", 1, 16);
        bruteOptions.prefix = "";

        Stopwatch myStopWatch = Stopwatch.StartNew();

        int NUM_THREADS = bruteOptions.chars.Length;
        Thread[] workers = new Thread[NUM_THREADS]; // Run a thread for each char.
        var countdownEvent = new CountdownEvent(NUM_THREADS);
        bool result = false;

        // Start workers.
        for (int i = 0; i < NUM_THREADS; i++)
        {
            int index = i;
            BruteOptions newBruteOptions = bruteOptions;
            newBruteOptions.prefix = bruteOptions.chars[index].ToString();

            workers[index] = new Thread(delegate()
            {
                // Also check single char.
                if (BruteForce(bruteOptions))
                {
                    result = true;

                    // End all other threads.
                    for (int ii = 0; ii < NUM_THREADS; ii++)
                    {
                        if (workers[ii].ThreadState == System.Threading.ThreadState.Running && index != ii) // Ensures we don't prematurely abort this thread.
                        {
                            workers[ii].Abort();
                            countdownEvent.Signal(); // Signal so we can zero it and continue on the UI thread.
                        }
                    }
                }

                // Signal the CountdownEvent.
                countdownEvent.Signal();
            });

            workers[index].Start();
        }

        // Wait for workers.
        countdownEvent.Wait();

        if (!result)
            Console.WriteLine("No Match.");

        Console.WriteLine("Took " + myStopWatch.ElapsedMilliseconds + " Milliseconds");
    }

That's all the relevant code. Any insight onto why this is happening would be greatly appreciated! I'm completely stumped. I attempted to specify a greater stack size when initialising each thread, to no avail.

Thanks in advance!

Answer 1

Your static bool BruteForce(BruteOptions bruteOptions) is infinitely recursive: it calls itself if the length allows, with the same parameters:

if (bruteOptions.prefix.Length + 1 < bruteOptions.maxLength)
    if (BruteForce(bruteOptions))

bruteOptions remain the same as it was on the entry to the function.

As a solution you may use this code:

if (bruteOptions.prefix.Length + 1 < bruteOptions.maxLength)
{
    BruteOptions newOptions = bruteOptions;
    newOptions.prefix += bruteOptions.chars[i];
    if (BruteForce(newOptions))
        return true;
}

Plus, you pass bruteOptions, not newBruteOptions to the delegate you use in main function. Thus, your multithreading is not used, in fact. All your threads test the same passwords. Change it to newBruteOptions.

Additionally, don't assume anything about threads execution order. You assume that all workers are filled by the moment one finds a proper password, which can be wrong. You will then get a NullReferenceException in this line:

if (workers[ii].ThreadState == System.Threading.ThreadState.Running && index != ii) // Ensures we don't prematurely abort this thread.