Cracking a MD5 hash from numerical input

Question

I am trying to crack one of multiple MD5 hashes that have been created from numerical input.

I have a sample of 1000 MD5 hashes that are generated from numerical input. I know that the input is somewhere between 10^6 and 10^27.

Is there any chance to reliably crack 1 hash from my sample (or conclude back to a more limited range of possible inputs)?

I tried to calculate how long it would need me to crack a hash from my sample manually when being able to calculate 10^9 hashes per second from numerical input (with oclHashcat) but there is no chance I'll ever get the result while still alive.

So are there any really big rainbow tables out there, any mathematical methods or MD5 weaknesses that I don't know about which could help me?

I'm assuming that there is no way to calculate even an "approximate" distance between two MD5 inputs from the hashes, so that given my samples I cannot deduce a reduced numeric range of possible inputs, which would also help (- but which is obviously not far from cracking).

So since MD5 is said to be so weak, any chance to crack it in practice with big numerical inputs?

Answer 1

While it is considered as insecure, MD5 is still considered as preimage resistant, so your best option is still brute-force.

Knowing some information about the input will help you in the brute-force process, but there's no known weakness which might help you.

Answer 2

Obviously it's too late to help you here, but why not answer anyway. The short answer is that your understanding is correct: there isn't much you can do looking at the hashes themselves to determine the range of possible values. Your only option is variations of brute-force, but if the numbers are spread over the entire search space then there isn't anything anyone can do even with all of the worlds computing power. Still, here are the kinds of things I would try:

1. Pre-computed hash lookup

For a simple (unsalted) MD5 hash this is the easiest starting point. A quick google search will find you any number of services that will "crack" MD5 hashes for you because they already contain a huge database of MD5 values for a wide variety of inputs. Unfortunately for you these are typically aimed at cracking passwords, so none of the ones I found online contain number-only inputs, especially in the range you are looking at (most contain real words, variations on words, combinations of words, or all combinations of alphanumeric strings up to certain lengths). So unfortunately this doesn't work for you.

2. Estimating the range of values

Your first goal therefore should be to figure out what the potential range of values is. You should be able to at least figure out if you can crack this in a reasonable amount of time. You do this, quite simply, by starting from the bottom of your range (1000000) and working your way up, one number at a time, for some reasonable amount of time (maybe an hour?). You quoted a hash rate of 1e9/s (or 1GHs/s). After an hour that means you will have tried out 3.6e12 numbers. Did you find a match?

2a. you found a match in an hour!

If yes you found a match, then problem solved! You can even start to estimate the range of values the numbers occupy and how long it might take to find them all. To some extent, this is a variation on the German tank problem. I'm not going to pretend to know how to do the math accurately off the top of my head, so you could either ask around for help estimating the total range of numbers from your data (and therefore how long you might expect it to take to find them all), or try something naive like:

hours_to_crack_everything = 1000/number_found_in_first_hour

Obviously your estimate will get more accurate as you find more. Importantly there is always a chance you just got very lucky. It could be that the numbers cover the full range of allowed values (1e6-1e27 and there just happened to be one in the first few trillion values. The odds of this happening are very tiny (3.6e-15), so if you do find a value it virtually guarantees that the numbers cover a much smaller range, but who knows maybe you just won the lottery (although to be fair your odds of winning the lottery are much, much better).

2b. One hour, no match

If you didn't find a match in an hour then you are probably screwed. You said in a comment that you have 11.5 days available (10e6 seconds). After an hour you've already used up ~1/300th of your available time. As a result given that you've only covered a minuscule fraction of your search space in a much larger fraction of your available time, then most likely it will not be possible for you to find a single hash in the allotted time period. I'd probably just let my hash box run (because that is the only available option for you that I can think of), but you will most likely fail.

3. Faster hashing?

Worth a mention: these days you can get hashing rigs (for a few thousand dollars) with much higher hash rates. However, the same basic math applies. Even with a hash rate a factor of 1000 higher, with such a large search space there are only two options: either the numbers don't fill up the entire search space, in which case there is hope, or they do fill up the entire search space, which is far too large to be able to brute force with today's technology.

Ironically, your odds of success would have been higher if they had been passwords instead of numbers.