Password Bruteforcer

Question

Just an idea I had for a Java exercise. Cracking a password like "testing" takes at least 15 minutes, so obviously it's not as efficient as it can be. What are your thoughts? I also never worked with multithreading, so I can imagine I could be doing things better there.

public class AlgoTester implements Runnable {
    private static final char[] possibleChars = { 'a', 'b', 'c', 'd', 'e', 'f', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o',
            'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };
    private static int[] arrayIndices;
    private static String testPassword = "testing";
    private static final int passwordLength = testPassword.length();
    private static boolean foundPassword = false;
    private final static int threadCount = 5;
    private static String passwordFound = "";

    public static void main(String[] args) {
        arrayIndices = new int[passwordLength];
        for (int i = 0; i < arrayIndices.length; i++) {
            arrayIndices[i] = 0;
        }
        for (int i = 0; i < threadCount; i++) {
            new Thread(new AlgoTester()).start();
        }

    }

    private synchronized static boolean advanceIndicies() {
        synchronized (arrayIndices) {
            if (foundPassword)
                return false;
            int maxValue = possibleChars.length - 1;
            for (int i = 0; i < passwordLength; i++) {
                int inverse = arrayIndices.length - i - 1;
                if (arrayIndices[inverse] == maxValue) {
                    if (inverse - 1 == -1)
                        return false;
                    arrayIndices[inverse] = 0;
                    continue;
                } else {
                    arrayIndices[inverse] = arrayIndices[inverse] + 1;
                    return true;
                }
            }
            return false;
        }
    }

    private synchronized static String genPassword() {
        synchronized (arrayIndices) {
        StringBuilder builder = new StringBuilder();
        for (int i : arrayIndices) {
            builder.append(possibleChars[i]);
        }
        String returning = builder.toString();
        System.out.println(Thread.currentThread().getName() + ": Checking: " + returning);
        return returning;
    }
    }

    private static boolean checkPassword() {
        // TODO Auto-generated method stub
        return (foundPassword = genPassword().equals(testPassword));
    }

    @Override
    public void run() {
        while (!foundPassword) {
            if (checkPassword()) {
                passwordFound = genPassword();
                System.out.println("----------------------");
                System.out.println("Found Password: " + passwordFound);
                System.out.println("----------------------");
                foundPassword = true;
            }
            if (!advanceIndicies()) {
                return;
            }
        }

    }

}

Answer 1

It's hard to decide where to begin. OK: no comments whatsoever. You know how it works now, but it will not be obvious next month if you do anything but sit idly in a dark room being fed through a tube thinking about this code.

---

Indicies is not a word. Don't write code on a napkin, everything can spell check English nowadays.

---

I also never worked with multithreading, so I can imagine I could be doing things better there.

It is best to learn how (and when) to do it and then try and come here. Don't just write something that compiles and throw at our face.

---

It is easier on the brain if you split this on a class that is your "driver", "main", "starter" which has a main() and does the instantiation and invocations and another one that is instantiated and called. I am not talking about correctness, obviously both approaches work, but the one I described above is clearer and wastes less cognitive power.

---

You forgot you were writing Java and accidentally wrote a C return statement.

return (foundPassword = genPassword().equals(testPassword));

You could afford another line, your IDE wouldn't run out of memory:

foundPassword = genPassword().equals(testPassword);
return foundPassword;

---

Responsibilities are a salad. See that advanceIndices checks if the password has been found. It was supposed to advance the indices but it is doing way more than that.

---

Performance-wise, the cost of synchronization is too high. A correct approach would be to partition the problem in n subproblems - where n is the number of threads you have - of almost the same size and solve each one in its own thread, with less synchronization.

Hypothesize that you have an array with 40 valid characters and 5 threads. Make thread A check all possible passwords that start with one of the first eight characters, thread B check all possible passwords that start with one of the next eight characters and so on until thread E.

Then throw in a volatile boolean flag that indicates termination which all threads refer to every now and then to know if they can stop because a thread found a solution.

It needs to be volatile so that any thread that reads it will see the most recently written value. You should know about this before attempting multithread programming in Java.

---

Summing it up

• Learn how to do it before bashing your head against the wall.
• Parallelization is good for this problem but you did it wrong, see the item above.

Answer 2

private static boolean foundPassword = false;

As this is accessed by multiple threads, it should be volatile.

That said, though, your multithreading is really flawed, all of the threads just deadlock and 1 is allowed to do all the work.

First, multiple worker threads only work if you've got work for several threads to do. In your case, you'd be better off if you could somehow offset each thread by a value (if we treat passwords as numbers in base-(your character set size) then you could say thread 1 starts at 0000, thread 2 starts at 0001, thread 3 starts at 0002...) and then advance by threadcount steps. So the threads interleave, rather than doing the same work:

Thread 1 does cases 1, 5, 9, 13...
Thread 2 does cases 2, 6, 10, 14...
Thread 3 does cases 3, 7, 11, 15...
Thread 4 does cases 4, 8, 12, 16...

Like that, you can run threads in parallel without them doing the same work over and over and over.