How one can find a string whose MD5 hash has a specific prefix?

Question

I've heard that there is a string that contains only the letters a to z whose MD5 hash begins with the hexadecimal prefix 314159265358 and the rest can be arbitrary. How can one find such a string and how long would the search take on a normal laptop?

Answer 1

The only way to find a hash with a specific value (disregarding preimage attacks, which MD5 is still secure against) is to hash values until you find one that matches. 314159265358 is 12 hexadecimal characters, which is 48 bits. You would expect to find a specific 48 bit prefix after 2⁴⁷ guesses with probability 50%, so the question becomes how fast can you do 2⁴⁷ hashes on "a normal laptop"?

My laptop is getting pretty old now (2013 I think) but I ran hashcat on it in benchmark mode to see how well it could do. The GPU (GT 730M) was able to do 535.6 MH/s, so I would expect 2⁴⁷ hashes to take around 73 hours. A GTX 1080 appears to achieve around 25 GH/s, so that would only take around an hour and a half. Of course, that's only for a 50% chance; it could take more or less time than that, but it's a decent estimate.

That the hashed string contains only a-z is mostly irrelevant, as hash functions take arbitrary input and deterministically output a fixed number of bits. Since the input is restricted to fewer characters you may end up with a larger string to hash, which could cause the hash to be slower as it's hashing more data. MD5 appears to operate on a 512 bit block, but due to its padding you can only hash 447 bits before it uses 2 blocks (which would presumably cause it to take approximately twice as long, but I haven't tested). 447 bits rounds down to 440/8 = 55 bytes, so you can hash 55 characters before losing performance. 55 characters with 26 possible values is 26⁵⁵; log₂(26⁵⁵) ~= 258, which is significantly larger than the 128 bit output size, hence I would expect that almost every possible MD5 output could be generated by hashing a string of [a-z]{1,55}.

Answer 2

There is an infinite amount of strings that will have an MD5 result starting with whatever fixed string you like, for the simple reason that the input space of MD5 is infinite while the output one is finite and limited to 128 bits.

You can of course not find them with one operation, you have basically to test them all an stop when you are happy.

So in your case you start with a, compute MD5, try with your criteria, stop here or go to next case b... until z, then aa until az, ba until bz and then until zz, then aaa, etc.

Then you can apply various optimizations, including using lists of precomputed hashes that you can find online. Have a look at "Rainbow Tables", for example here: http://project-rainbowcrack.com/table.htm Some may offer you "reverse search", but of course that can not be exhaustive.

As for the time it may take, as we say in French: "it depends". There is absolutely no way to give you true precise definite numbers for this kind of performance question, it depends too much on the hardware.

By the way, what is a "normal" laptop?