ForumsHQ

I was having a rather spirited debate with someone the other day regarding the use of MD5 Hashs. My friend, who knows enough about computers to turn one on, insisted that MD5, like any other encryption, could be easily cracked using a brute force attack.

After a few hours of discussing it with him, he refused to back off from his position so I decided to write a program to prove to him how wrong his idea is. So I built a program that would allow you to set certian restrictions on a key generator such as allowable characters and the length of the key. It would then build a randomly generated key, appply an MD5 hash to that key, and launch a brute force sequential attack to try and duplicate the hash.

The program will gen a key from 3 to 9 characters long. Obviously a 3 character string will be matched quickly. My program can do it in about 32 seconds. A 4 character string can take about 45 minutes to match. A 5 character string can take 3 days to match. It only gets worse from that point.

This program was a lot of fun to work on. I though I would share the story behind it and a screen shot of the program for any of you who are interested in cryptography.

This picture is from one of my debugging test runs after making a few changes to the data displayed on the screen.

Can you do that for TW?

Quote from: SouthernCross on July 22, 2011, 09:01:22 PMCan you do that for TW?

Do... what? Break an MD5 hash? It's doable obviously, the question is how much time/computer power are you willing to invest. As you see from that screen shot just a 5 character key has 7,339,040,224 possible combinations and even at over 100 million keys per hour it would take 3 days to run through all those possibilities. If you use the entire 256 character set it takes more than 2x that amount of time.

The question is not "can it be done", that is of course a yes. The question is "is it practical". The answer to that is almost always no due to the time involved.

As you can see in this runtime report:
Brute Force attack started at 7/22/2011 10:39:38 PM
Finished with strings 1 characters long. 7/22/2011 10:39:38 PM Runtime: 00:00:00.0370021 Attempts: 94
Finished with strings 2 characters long. 7/22/2011 10:39:38 PM Runtime: 00:00:00.3280188 Attempts: 8,743
Finished with strings 3 characters long. 7/22/2011 10:40:04 PM Runtime: 00:00:26.4105106 Attempts: 813,100
Finished with strings 4 characters long. 7/22/2011 11:20:56 PM Runtime: 00:41:18.4647601 Attempts: 75,618,301

The time required to process all the options grows exponentially as the length of the string grows. By the time you get up to 7 character strings you're talking about 72,057,594,037,927,936 possible combinations (with the entire 256 byte character set). At exactly 100 million keys per hour that would take 72,057,594 hours (3,002,399 Days or 82 years) to run every possible option. That's with the program running non stop 24/7/365.25.

Now it's obvious that nobody has that kind of time to wait and it's unlikely that a computer could withstand the program running at 50% CPU capacity for that period of time. There are other methods that can be explored that would produce a faster result and I am exploring putting some of those options to work in this program as we speak.

This runtime report is doing the same as the one above but using the entire 256 byte character set instead of just the 94 keyboard characters. Notice the very large jump in the time required for each one to complete:

Brute Force attack started at 7/22/2011 11:42:16 PM
Finished with strings 1 characters long. 7/22/2011 11:42:16 PM Runtime: 00:00:00.0300017 Attempts: 256
Finished with strings 2 characters long. 7/22/2011 11:42:18 PM Runtime: 00:00:02.1811248 Attempts: 65,281
Finished with strings 3 characters long. 7/22/2011 11:51:35 PM Runtime: 00:09:18.2989329 Attempts: 16,646,656

a GPU, particularly the Radeon HD 5x00 and 6x00 series can brute force MD5 hashes VERY quickly... in fact, a Radeon HD can even crack SHA-256 2 quite quickly...

FPGAs can crack MD5 fast too... but un-optimized software written generically for a CPU will be significantly slower..

check this out...



FPGA MD5 Cracker - Part 1

an nVidia Quadro FX570m VGA. With the list of 2200 hashes, oclcrack was able to do 1.84e10 comparisons per second. I think it is a pretty good number for this GPU.

@ http://sghctoma.extra.hu/index.php?p=entry&id=11

Oh believe me, I know there are vastly better ways to match a MD5 hash. The conversation that started all of this though was dealing specifically with a sequential brute force attack and the program was written to perform just that. I knew going into this that it would be as bad as it is. The point behind the program was to prove that to the person I was debating with.

After sending this program to my friend I decided to see if I could make a better version. The original was made to his exact specifications as far as how it did the attack.

I recoded several parts of the program last night and this is the result. As you can see it is much faster than the first method.

can you rewrite it to support OpenCL, and or CUDA?