Keith and Dawg 2 Solution

By: Jason Yang

Flag: ywterqtwe

Solution

Basically, brute force it. Calculate every possible password using the letters q, w, e, r, t, and y, and keep going until you find the right hash.

Firstly, we use a built in Java function to calculate md5 hashes:

MessageDigest md = MessageDigest.getInstance("md5");
md.update(s.getBytes(), 0, s.length());
return new BigInteger(1, md.digest()).toString(16);

where s is the string to be hashed.

Then, we need to iterate over every single letter combination of a certain length. If the password isn’t found, then increment the length and repeat until it is found. We can do this by representing each combination with length n and o characters as an integer from 0 to $$o^n-1$$. Using a for loop, each of these integers can be converted to base o, then converted to a string using each digit as the index in the character set array, then hashed. If the loop is completed and the hash is still not found, n is incremented, and the loop repeated.

Of course, this is clearly not the most efficient algorithm. An improvement would be using multithreading. In the example, four threads are created, using the Iterator class to get the integer representing the character combination. The method getNext() is synchronized to prevent multiple threads from accessing the method concurrently and performing the same hash. Because the method is synchronized, it presents a bottleneck, as all thread must block until the method finishes. As a result, as much computation is placed in the thread and not in the getNext() method, which only needs to increment the integer. A CountDownLatch is used to block the main thread until all four hashing threads have completed, either when all combinations of length n have been tested or when the hash has been found. Once the CountDownLatch unblocks, the main thread either moves on and increments n (in the first case), or reports a successfully reversed hash (in the second case).

Full Solution

import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.concurrent.CountDownLatch;

public class Reverse {

    public String check;
    public String[] chars = {"q", "w", "e", "r", "t", "y"}; 

    public int length;
    public int count = 0;
    public boolean found = false;
    public Iterator it;

    public CountDownLatch latch;

    public static void main(String[] args){
        new Reverse().run();
    }

    public void run(){
        int maxLength = 10;
        int threads = 4;

        check = "b81b28baa97b04cf3508394d9a58caae";
        long beginTime = System.nanoTime();
        length = 1;
        while (length <= maxLength && !found){
            latch = new CountDownLatch(threads);
            it = new Iterator(length, chars);
            for (int i = 0; i < threads; i++){
                Thread t = new Thread(new Hash(), "hash");
                t.start();
            }
            try {
                latch.await();
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
            length++;
        }
        long endTime = System.nanoTime();
        long time = endTime - beginTime;
        System.out.println(String.format("%f hashes/second", (double) count / time * 1000000000d));
        System.out.println(String.format("%f seconds", time / 1000000000d));
    }

    public static String md5(String s){
        try {
            MessageDigest md = MessageDigest.getInstance("md5");
            md.update(s.getBytes(), 0, s.length());
            return new BigInteger(1, md.digest()).toString(16);
        } catch (NoSuchAlgorithmException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        return null;
    }

    public class Hash implements Runnable {

        @Override
        public void run() {
            int index = -1;
            while ((index = it.getNext()) >= 0 && !found){
                String s = "";
                for (int i = it.n - 1; i >= 0; i--){
                    int num = (int) Math.floor(index / Math.pow(it.o, i));
                    index -= num * Math.pow(it.o, i);
                    s += chars[num];
                }
                String hash = md5(s);

                count++;
                if (hash.equals(check)){
                    found = true;
                    System.out.println(s);
                    System.out.println(hash);
                }
            }
            latch.countDown();
        }

    }

    public class Iterator {

        public final int n;
        public final int o;
        public int index;

        public Iterator(int size, String[] chars){
            n = size;
            o = chars.length;
            this.index = 0;
        }

        public synchronized int getNext(){
            if (index < (Math.pow(o, n))){
                int tmp = index;
                index++;
                return tmp;
            }
            return -1;
        }

    }

}