How to create a fast MD5 algorithm in Java or C#

Question

I have a MD5 hash (for example "5d41402abc4b2a76b9719d911017c592") and I want to find another string that has the same hash. So far I have created two algorithms (one in Java and another in C#) but they run really slow. At the moment I can only process around 100,000 hashes per second. Are there any other algorithms I should use to speed things up?

This is an example of the algorithm I'm currently using in Java (I have the original hash stored in originalHash, then I generate hashes of other strings that are just numbers and compare the hashes):

import java.security.*;
import java.math.*;

public class b {
public static void main(String args[]) throws Exception{
    String s="Hello";
    MessageDigest m=MessageDigest.getInstance("MD5");
    m.update(s.getBytes(),0,s.length());
    String originalHash = new BigInteger(1,m.digest()).toString(16);
    System.out.println("MD5: " + originalHash);

    for (long i = 0; i < 9223372036854775807L; i++)
    {
        String iString = i + "";
        m.update(iString.getBytes(),0,iString.length());
        iString = new BigInteger(1,m.digest()).toString(16);
        if (originalHash.equals(iString))
        {
            System.out.println("Found MD5: " + iString);
            break;
        }
        if (i%1000000 == 0)
        {
            System.out.println("Count: " + (long)i/1000000 + "M");
            System.out.println("Sample Hash: " + iString);
        }
    }
}
}

What is wrong with the standard implementation of both languages? — rekire
– rekire, Commented Apr 28, 2012 at 4:03
fastest way I could think of is to figure out how many processing cores you have and spin off that many threads and if you are using C# just use the built in crypto libraries. I'm with everyone else though...seems kinda flaky...so why do you need this? — Jared
– Jared, Commented Apr 28, 2012 at 4:05
Try comparing the arrays instead of converting to string representation and comparing that. Also MD5Cng is faster than MD5Managed in C#. Finally, if this is for actual hash breaking, oclHashcat will provide better performance than you'll ever get with Java. — Ry-
– Ry- ♦, Commented Apr 28, 2012 at 4:06
Check you assignment if you need fast MD5 or find collision. To my understanding these are 2 different issues. Also consider adding "homework" tag to your question (probably instead of "hash"). — Alexei Levenkov
– Alexei Levenkov, Commented Apr 28, 2012 at 4:45
I don't think this can be done, in a reasonable amount of processing time. Whereas it's possible to find two strings that have the same MD5 hash, finding a single string that has the given MD5 hash is a much more computationally-intense problem. I think your teacher is trying to convince you that it can't be done, by setting you up to fail. — Dawood ibn Kareem
– Dawood ibn Kareem, Commented Apr 28, 2012 at 4:45

GalacticJello · Accepted Answer · 2012-04-28 04:23:36Z

2

You need to take a peek at GPU programming. You can run thousands of threads to check your hash against your sequentially incrementing number at a time, and the GPU model fits your problem definition well. One example of a hash cracker is oclHashCat.

Otherwise, you could distribute your computation across multiple machines to run the hashes in parallel, like bringing up a hadoop cluster.

Another option is to pre-compute all possible hashes using rainbow tables, and just doing a lookup.

Of course, you could just do a "google" for "md5 hash lookup" and just input your existing MD5 hash and get the string result.

If you are trying to find a random collision between your chosen input and any other value, well... you may be waiting a bit.

answered Apr 28, 2012 at 4:23

GalacticJello

11.5k2 gold badges28 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Pritesh · Accepted Answer · 2012-04-28 04:32:59Z

0

When you are looking at big number crunching and performance (latency) is concern Stack based VM like Java/.Net are not a good option. To get this done in Java implement algorithm in C++ and call it through Java Native Interface. In .Net world use unsafe code to access bytes through pointers. Definitely in both cases you will have to take care of stability/memory management as there would be no Platform/Framework taking care of it for you.

answered Apr 28, 2012 at 4:32

Pritesh

1,9707 gold badges32 silver badges48 bronze badges

Collectives™ on Stack Overflow

How to create a fast MD5 algorithm in Java or C#

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related