Find MD5-hash whose hexadecimals starts like digits of π

Question

I saw a programming puzzle. Find a string containing letters from a to z such that its MD5-hash starts like 314159265359. I am a junior programmer so I would like to know if I can solve the problem faster that checking firs strings a-z, then aa-zz, then aaa-zzz and so on. As the computation takes time, I save results to the file regularly to be able to continue computation. I put my Mint to autostart the application as desktop is on.

In particular, is there faster way to solve the problem and is there cleaner way to write the code:

//using Datetime;
using System;
using System.IO;
using System.Text;
//using StringBuilder;

// This is an exercise from https://www.ohjelmointiputka.net/postit/tehtava.php?tunnus=ssana2 .
// It tries to find an md5-hash that begins with hexadecimals 314159265...
namespace RandomCS
{
    public class Program
    {
        public static void Main()
        {
            DateTime dt1 = DateTime.Now;
            Console.WriteLine(dt1);
            string md5 = "";
            string last = "a";
            string c = "";
            string file = "md5piresults.txt";
            string path = "/home/jaakko/Desktop/Programming/";
            int limit = 1;
            int cp = 0;
            string bestsa;
            string charstring;
            string[] lines = System.IO.File.ReadAllLines(@path+file);
            Console.WriteLine(lines[0]+"\n" +lines[1]);
            const string pi = "314159265358";
            do {


                last = lines[0].Substring(6,lines[0].Length-6);
                Console.WriteLine("We got: "+last);

                bestsa = lines[1].Substring(6,lines[1].Length-6);
                charstring = last;
                cp = CommonPrefix(CreateMD5(bestsa),pi).Length;
                Console.WriteLine("The best we have found = "+bestsa+", md5="+CreateMD5(bestsa)+ ",n="+cp);
                limit = cp+1;
                TimeSpan aInterval = new System.TimeSpan(0, 0, 0, 3);
                DateTime newTime = dt1.Add(aInterval);
                while (!Console.KeyAvailable) {
//                    Console.WriteLine(DateTime.Now + " " + newTime+ DateTime.Compare(DateTime.Now, newTime));
                    if (DateTime.Compare(DateTime.Now, newTime) == 1)
                    {
//                        Console.WriteLine("Meni aikaa!");
                        newTime = DateTime.Now.Add(aInterval);
                        lines[0] = "last: " + charstring;
//                        lines[1] = "best: " + bestsa;
                        System.IO.File.WriteAllLines(@path + file, lines);
                        Console.WriteLine("We saved to the file " + file + " lines " + lines[0] + " and " + lines[1]);
                    }

                    md5 = CreateMD5(charstring);
                    c = CommonPrefix(md5,pi);
                    if (c.Length >= limit) {
                        Console.WriteLine(charstring+" " +md5+ " " +c.Length);
                        lines[0] = "last: "+charstring;
                        lines[1] = "best: "+charstring;
                        System.IO.File.WriteAllLines(@path +file,lines);
                        Console.WriteLine("We saved to the file " +file + " lines " + lines[0] + " and "+lines[1]);
                        limit = c.Length + 1;
                    }
                    charstring = Increase(charstring);

                    if (charstring == endstring(charstring.Length)) {
                        md5 = CreateMD5(charstring);
                        c = CommonPrefix(md5,pi);
                        if (c.Length >= limit) {
                            Console.WriteLine(charstring+" " +md5+ " "+c.Length);
                            lines[0] = "last: "+charstring;
                            lines[1] = "best: "+charstring;
                            System.IO.File.WriteAllLines(@path +file,lines);
                            limit = c.Length + 1;
                        }
                        charstring = startstring(charstring.Length+1);
                    }
                }
            }
            while (Console.ReadKey(true).Key != ConsoleKey.Escape);
            string best = "";
            lines[0] = "last: "+charstring;
            md5 = CreateMD5(charstring);
            c = CommonPrefix(md5,pi);
            if (c.Length >= limit) {
                    best = charstring;
                    lines[1] = "best: "+best;
        }
        System.IO.File.WriteAllLines(@path +file,lines);
        Console.WriteLine("We exit at the point "+charstring);
        Console.WriteLine(charstring);
        Console.WriteLine(limit);
    }

    // This is from https://stackoverflow.com/questions/33709165/get-common-prefix-of-two-string .
    public static string CommonPrefix(string a, string b)
    {
        if (a == null)
                throw new ArgumentNullException(nameof(a));

        if (b == null)
                throw new ArgumentNullException(nameof(b));

        var min = Math.Min(a.Length, b.Length);
        var sb = new StringBuilder(min);
        for (int i = 0; i < min && a[i] == b[i]; i++)
                sb.Append(a[i]);

        return sb.ToString();
    }


    private static string startstring(int n) {
        string start = "";
        for (int i=0; i<n; ++i) {
                start += "a";
        }
        return start;
    }


    private static string endstring(int n) {
        string end = "";
        for (int i=0; i<n; ++i) {
                end += "z";
        }
        return end;
    }


    // This is from https://stackoverflow.com/questions/11454004/calculate-a-md5-hash-from-a-string
    public static string CreateMD5(string input)
    {
        // Use input string to calculate MD5 hash
        using (System.Security.Cryptography.MD5 md5 = System.Security.Cryptography.MD5.Create())
        {
                byte[] inputBytes = System.Text.Encoding.ASCII.GetBytes(input);
                byte[] hashBytes = md5.ComputeHash(inputBytes);

                // Convert the byte array to hexadecimal string
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < hashBytes.Length; i++)
                {
                        sb.Append(hashBytes[i].ToString("X2"));
                }
                return sb.ToString();
        }
    }

    // The idea is from https://artofproblemsolving.com/community/c163h1699980_how_to_find_the_next_string_in_c
    private static string Increase(string thing)
    {
        char[] charArray = thing.ToCharArray();
        bool differentcharacter = false;
        for (int i=0; i<charArray.Length; ++i) {
                if (charArray[i]!= 'z') {
                        differentcharacter = true;
                }
        }
        if (differentcharacter == false) {
                return thing;
        }
        bool carry = false;
        for (int i = charArray.Length - 1; i >= 0; i--)
        {
                char c = charArray[i];
                if (carry)
                {
                        if (c != 'z' && c != 'Z')
                        {
                                charArray[i] = ++c;
                                break;
                        }

                        charArray[i] = (char) (c - 25);
                } else
                {
                        if (c != 'z' && c != 'Z')
                        {
                                charArray[i] = (char) (c + 1);
                                break;
                        }

                        charArray[i] = (char) (c - 25);
                        carry = true;
                }
        }
        return new String(charArray);
        }

    }
}

Answer 1

MD-5 is a cryptographic hash-function, it was designed so that it is hard to find an input which produces a particular output.

So it's unlikely you will find an approach better than "brute force".

That said, MD-5 is known to have cryptographic weaknesses, so it's not out of the question to find a faster method.

Answer 2

If I understand things correctly, then what you're trying to do is called a 'preimage attack'. That's a lot harder than 'just' finding a hash collision. Apparently there is a known preimage attack for MD5, but it's only slightly better than a brute-force approach, so I don't think that'll be of any practical use here.

But the challenge you're referring to is more of a 'who can find the longest matching prefix', so it's about how efficient your code is and how patient you are.

---

Regarding efficiency, there are a few things you can do to speed it up:

• You're creating a new MD5 instance every time you want to generate an MD5 hash. Don't do that - create a single instance when your program starts and keep using that until the program ends.
• You're constantly converting between strings and byte arrays. That involves a lot of extra work and extra allocations, which will slow things down. Use byte arrays everywhere, and modify them in-place whenever possible.

---

Other things you can do that will make the code easier to understand and maintain:

• Code duplication: both file-writing and hash comparing are duplicated several times. Each of these only needs to occur once in the code.
• Main contains two nested loops and quite a few additional checks. A single loop should be sufficient, and its body only needs to check a hash, update the longest-match if necessary, 'increase' the input and check if it's time to write the current state to a file.
• Declaring local variables up-front, instead of as close to where they are used as possible, tends to make code more difficult to understand. I think the main reason why you'll sometimes see this style is because it used to be required in certain older languages.
• Type names like System.IO.File, System.TimeSpan, System.Security.Cryptography.MD5 and so on can be simplified to File, TimeSpan and MD5 thanks to using <namespace>; statements.

Answer 3

The basics:

• Use consistent indenting. Your editor can help if you want to move a block out a level, as in CreateMD5.

• Completed code shouldn't have commented out lines. If you want to leave something in for debugging, either use the built-in Debug class or write your own function which can be disabled with a flag.

• Your variable names are not good. dt1 could be startTime, cp could be lengthToBeat, c could be commonPrefix. Good variable names make your code self-documenting.

• Most of your code is in a single function, with just a few static helpers. The IO code should be moved out into other functions. You could move the string incrementation to a separate class.

In terms of optimization, the biggest win would be to use more than a single core on your machine. You would have to know what you are doing, but it will give you an immediate 4x speedup if you avoid contention. An added benefit is that this will force you to organize your code better. In terms of smaller improvements, the key is going to avoid doing unnecessary work. Look at CommonPrefix: you build up a string, but when you are done all you use is its length. If all you want is to count characters that match, you can have it return an int.

Similarly, if you think about this problem some more, it doesn't actually require you to convert the hash to a hex string. Given a byte array, you can easily count how many bytes match your target string. If you want it to start "31" then the first byte has to be 0x31. So full bytes (2 hex chars) are easy, and the only challenge is to handle single chars.

Another possible speedup would be to avoid the allocations and conversions involved in your string increment and hashing. Since your strings are all ASCII anyway, you could work directly with a byte[], increment it in place, and pass it straight to the hashing function.