How to reverse modified string back into MD5 hash given the method used to modify the string?

Question

I am working with some MD5 hashes that have been turned into number sequences using the methods shown below. Given the code and example hash below, how can I "reverse" the effect of the getString() method and turn a numerical sequence back into an MD5 hash?

For example, encrypt("umadbro"); returns "1518918615824625494170109603025017352201241" because the MD5 hash is passed through the getString() method. The MD5 hash for "umadbro" is 9759ba9ef6fe5eaa6d3c1efaad34c9f1. I need a method that takes a string of numbers modified by the getString() method and converts it into its MD5 hash. For example: reverseMethod("1518918615824625494170109603025017352201241"); should output "9759ba9ef6fe5eaa6d3c1efaad34c9f1" (The input parameter is the modified string of numbers and the output is the MD5 hash of the original string). NOTE: I am not looking for a method to crack the MD5 hash. I only need a method that reverses the effect of the getString() method shown below.

    public String encrypt(String source)
        {
            try
            {
                MessageDigest md = MessageDigest.getInstance("MD5");
                byte[] bytes = md.digest(source.getBytes());
                return getString(bytes);
            }
            catch (Exception e)
            {
                e.printStackTrace();
            }
            return null;
        }

    private String getString(byte[] bytes) //this takes an md5 hash and turns it into a string of numbers.
    // How can I reverse the effect of this method?
    {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < bytes.length; i++)
        {
            byte b = bytes[i];
            sb.append(0xFF & b);
        }
        return sb.toString();
}

not sure if that is possible since different hashes will have the same representation. E.g. "97", "0133", "0F01" and "010501" would all have "151" as result of getString. If there was a separator between the numbers, it would be no problem — user85421, Jun 03 '17 at 20:07
Possible duplicate of [Converting A String To Hexadecimal In Java](https://stackoverflow.com/questions/923863/converting-a-string-to-hexadecimal-in-java) and [Is it possible to decrypt md5 hashes?](https://stackoverflow.com/q/1240852/608639) — jww, Jun 04 '17 at 07:25

score 2 · Answer 1 · answered Jun 03 '17 at 20:07

2

This is not possible without trying all combinations and comparing. The problem is that getString doesn't return a number that is unique for the given hash value as bytes.

For instance if the bytes are valued 0216 hex then 02 becomes "2" in decimals string encoding and 16 becomes "22". So your method would return "222" as the concatenation of both. Now if we do the same thing for 1602 then it will result in "22" and "2", and concatenation will still result in "222". And this can happen for each and every byte combination in the byte array.

So although the result is likely to still be relatively secure hash, the chance of finding a collision is much higher. What you can do is to return a large set of hashes of which 1 will result in a match, but it would take a lot of calculations; if you want to compare you're better off putting your result through getString and compare the much less secure hashes (even less secure than MD5 already is).

answered Jun 03 '17 at 20:07

Maarten Bodewes

90,524
13
150
263

I can crack hashes with a rainbow table cracker. Your solution would be extremely helpful, the only problem is I don't know exactly how to do it in Java. How would one go about writing code for a method that generates all possible hashes from the modified string? – Java Weenis Jun 03 '17 at 20:17
Note that if you will try and reverse it you have one advantage: the values are all in the range 0 to 255. That means that the first digit has a large chance of being `'1'` or `'2'`. So you can use that information to better guess where the boundaries between the byte values are. – Maarten Bodewes Jun 03 '17 at 20:17
@JavaWeenis How would you verify the result? – Maarten Bodewes Jun 03 '17 at 20:18
I can crack the hash with a rainbow table cracker and plug it back into the program and see if it outputs the same string of numbers. – Java Weenis Jun 03 '17 at 20:19
That would only be useful if you want to find a collision input for the hash-turned-number. And I'm not even sure about that, you can just try inputs until your `toString(hash(input))` returns a collision. – Maarten Bodewes Jun 03 '17 at 20:20
Why do you say "although the result is likely to still be relatively secure hash"? – TheGreatContini Jun 03 '17 at 20:22
There are 2^128 possible MD5 hashes. Although this will significantly reduce the number of possible output values of the combined hash function you will need more advanced math to calculate the new number of possible hashes. However, it is *quite possible* that it won't reduce 2^128 that significantly and I don't see how this weakens the MD5 hash function itself. – Maarten Bodewes Jun 03 '17 at 20:24
We are probably seeing this from a different angle. We know the collision resistance is broken. We also know that short inputs can easily be brute forced. So from my viewpoint, it's an insecure hash becoming even less secure. You might be looking at it in terms of inverting long inputs. – TheGreatContini Jun 03 '17 at 20:27
@Marteen Bodewes Ultimately my goal is to crack the md5 hashes but I don't know much about bytes. I want to get the raw md5 hash to plug it into a cracker. This 0xFF & b is stopping me from getting the hash. – Java Weenis Jun 03 '17 at 20:28
1

@JavaWeenis just modify the code in the cracker to apply getString after it does md5. – TheGreatContini Jun 03 '17 at 20:30
Imagine 15 boundaries to separate 16 bytes. Now place them at every possible position in your string with decimals. Of course the captured decimals must be at least one digit and at most have the value 255. But that's still a lot of possibilities. The method already indicated by me and @TheGreatContini is a much more likely to be practical. – Maarten Bodewes Jun 03 '17 at 20:33
Actually it's only 2 possibilities in this case. – Tesseract Jun 03 '17 at 21:09
@SpiderPig List two using separators and I'll list another one. It's a large string though, I give you that. – Maarten Bodewes Jun 03 '17 at 22:14
I already listed two in my answer. Good luck finding a third. – Tesseract Jun 03 '17 at 22:19
Hmm, you may be right. Ah, you've proven it, I just did it by hand. Must be a puzzle of some kind, the chance of only having two possibilities should be pretty small. – Maarten Bodewes Jun 03 '17 at 22:19
I did some more testing. Seems like the probability of having exactly 2 combinations is around 12%. On average there are around 100 combinations. – Tesseract Jun 03 '17 at 22:39
Hmm, 12 percent is still pretty high, did not expect that. You probably just fed in a fungous amount of hash values or random numbers? That also means that the security is only about 7 bits smaller (or 3.5 bits out of 64 of the collision) that is, if MD5 was a secure hash in the first place. – Maarten Bodewes Jun 03 '17 at 23:51
Something like that. I put random strings through Java Weenis's `encrypt` method. – Tesseract Jun 04 '17 at 00:18

score 2 · Accepted Answer · answered Jun 03 '17 at 21:01

I tried to write some code that finds all possible combinations and it turned out there are a lot less then I anticipated. Only 2 in this case. And it takes very little time to find them.

import java.util.ArrayList;
import java.util.Arrays;

public class Comb {
  static long combinations(String str, int startIdx, int numBytes, ArrayList<byte[]> combinations, byte[] combination) {
    if(startIdx >= str.length()) {
       if(numBytes == 16) {
         combinations.add(combination.clone());
         return 1;
       } else return 0;
    }
    if(numBytes > 15) return 0;
    combination[numBytes] = (byte)(str.charAt(startIdx) - '0');
    long result = combinations(str, startIdx + 1, numBytes + 1, combinations, combination);
    if(startIdx < str.length() - 1 && str.charAt(startIdx) != '0') {
      combination[numBytes] = (byte)((str.charAt(startIdx) - '0') * 10 + (str.charAt(startIdx + 1) - '0'));
      result += combinations(str, startIdx + 2, numBytes + 1, combinations, combination);
    }
    if(startIdx < str.length() - 2) {
      combination[numBytes] = (byte)((str.charAt(startIdx) - '0') * 100 + (str.charAt(startIdx + 1) - '0') * 10 + (str.charAt(startIdx + 2) - '0'));
      if(str.charAt(startIdx) == '1') result += combinations(str, startIdx + 3, numBytes + 1, combinations, combination);
      if(str.charAt(startIdx) == '2' &&
        (str.charAt(startIdx + 1) < '5' || str.charAt(startIdx + 1) == '5' && str.charAt(startIdx + 2) < '6')) {
          result += combinations(str, startIdx + 3, numBytes + 1, combinations, combination);
      }
    }
    return result;
  }

  public static void main(String[] args) {
    ArrayList<byte[]> combinations = new ArrayList<>();
    System.out.println(combinations("1518918615824625494170109603025017352201241", 0, 0, combinations, new byte[16]));
    for(byte[] c: combinations) {
      System.out.println(Arrays.toString(c));
    }
  }
}

The output of this is:

2
[15, -67, -70, -98, -10, -2, 94, -86, 109, 60, 30, -6, -83, 52, -55, -15]
[-105, 89, -70, -98, -10, -2, 94, -86, 109, 60, 30, -6, -83, 52, -55, -15]

And the second solution it found is indeed the correct one.

How to reverse modified string back into MD5 hash given the method used to modify the string?

2 Answers2