6桁限定ならこういう変換もありかなーと。

App.java

package example.mdsample.java;

import java.io.UnsupportedEncodingException;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;

import javax.xml.bind.DatatypeConverter;

import org.apache.commons.lang3.ArrayUtils;
import org.apache.commons.lang3.StringUtils;

public class App {

    public static void main(String[] args) throws Exception {
        for (int i = 0; i < 10; i++) {
            App app = new App();
            long start = System.currentTimeMillis();
            System.out.println("result = "
                    + app.findPassword("hoge",
                            "4b364677946ccf79f841114e73ccaf4f"));
            long end = System.currentTimeMillis();
            System.out.println("Ellapsed Time: " + (end - start) + "ms");
        }
    }
  
    static final byte[] DIGIT_BYTES = new byte[] { 0x30, 0x31, 0x32, 0x33, 0x34,
        0x35, 0x36, 0x37, 0x38, 0x39 };
  
    static byte[] convertToDigitBytes(int i) {
      return new byte[] {
          DIGIT_BYTES[(i / 100000) % 10],
          DIGIT_BYTES[(i / 10000) % 10],
          DIGIT_BYTES[(i / 1000) % 10],
          DIGIT_BYTES[(i / 100) % 10],
          DIGIT_BYTES[(i / 10) % 10],
          DIGIT_BYTES[i % 10] };
    }
    
    private final MessageDigest digester;

    public App() throws NoSuchAlgorithmException {
        super();
        this.digester = MessageDigest.getInstance("MD5");
    }

    private byte[] hexDigest(byte[] b) throws NoSuchAlgorithmException,
            UnsupportedEncodingException {
        digester.reset();
        digester.update(b);
        return digester.digest();
    }

    public static class Result {

        public String password;
        public String hash;

        public Result(String password, String hash) {
            this.password = password;
            this.hash = hash;
        }

        @Override
        public String toString() {
            return "Result{" + "password=" + password + ", hash=" + hash + '}';
        }
    }

    private Result findPassword(String salt, String pw)
            throws NoSuchAlgorithmException, UnsupportedEncodingException {

        byte[] password = DatatypeConverter.parseHexBinary(pw);

        byte[] prefixBytes = (salt + "$").getBytes();
        for (int i = 0; i < 1000000; i++) {
            byte[] paramBytes = ArrayUtils.addAll(prefixBytes, convertToDigitBytes(i));
            byte[] hex = hexDigest(paramBytes);
            if (Arrays.equals(password, hex)) {
                String format = StringUtils.leftPad(String.valueOf(i), 6, '0');
                return new Result(format, DatatypeConverter.printHexBinary(hex));
            }
        }
        return null;
    }
}