Speeding up brute force algorithm

Question

The code is no longer relevant but I want to know how I can make it faster. It uses only about 10% of my CPU. Any advice about best practices, better algorithms, or how to make the existing one faster are welcome. This is purely for the purpose of personal learning.

public class BruteForce {
public static void main(String[] args) throws Exception {

    // Password dictionary
    FileInputStream fstream = new FileInputStream("C:/list.txt");
    BufferedReader BufferedReader1 = new BufferedReader(new InputStreamReader(new DataInputStream(fstream)));
    // Read File Line By Line
    String input;
    long counter = 0;
    Long start = System.currentTimeMillis();
    while ((input = BufferedReader1.readLine()) != null) {
        if(counter%1000000 == 0){
            System.out.println(counter + ": " + input);             
        }
        counter++;

        // Generate ID using published class
        byte[] pub = ppg.Indors.getPublicKey(input);
        // We could use getId, but we get a weird signed/unsigned problem 
        byte[] pub2 = MessageDigest.getInstance("SHA-256").digest(pub);
        // Get account ID
        BigInteger BigInteger = new BigInteger(1, new byte[]{pub2[7],pub2[6],pub2[5],pub2[4],pub2[3],pub2[2],pub2[1],pub2[0]});

        // Request balance for ID
        String url = "http://localhost:1811/ppg?request=egtBalance=" + BigInteger.toString();
        URL obj = new URL(url);
        HttpURLConnection con = (HttpURLConnection) obj.openConnection();
        con.setRequestMethod("GET");
        BufferedReader BufferedReader2 = new BufferedReader(new InputStreamReader(con.getInputStream()));
        String inputLine;
        StringBuffer response = new StringBuffer();
        while ((inputLine = BufferedReader2.readLine()) != null) {
            response.append(inputLine);
        }
        BufferedReader2.close();
        // Check balance bigger than 0
        if (!response.toString().contains("balance\":0")) {
            System.out.println("Found:" + input);
        }
    }
    System.out.println("Speed (tries/sec): " + counter*1000/(System.currentTimeMillis()-start));
    BufferedReader1.close();
}
 }

Answer 1

A huge amount of you work is just plain work that has to be done.... (the joys of brute-forcing).

MessageDigest

On the other hand, this work is unnecessary:

byte[] pub2 = MessageDigest.getInstance("SHA-256").digest(pub);

This should be replaced with:

MessageDigest digest = MessageDigest.getInstance("SHA-256");

for (..... ) {

    digest.reset();
    byte pub2 = digest.digest(pub);

Accessing the security API's in every loop is a lot of wasted time, and MessageDigest classes are designed to be reused.

Parallelism...

A lot of the work you do involves getting and managing URL's... this is slow work that can be done in parallel with the hard work of generating the key hashes.

I would recommend one thread that builds a stream of hashes (with the relevant input stored) and feeds them in to a BlockingQueue with a limited queue size... then, have the controlling thread read these off the queue, and 'farm' them out to a number of other threads that create and check the URL's against the server.

The parallelsim could give you orders-of-magnitude performance improvements.... (but will heavily load the server you are bruting...)

Answer 2

+1 to @rolfl and a few other notes:

1. You are creating a new URLConnection in every iteration. I guess it results a new TCP connection too. With a better HTTP library (Apache HttpClient, for example) you could reuse the same connection for multiple HTTP requests and save the time of connection open and close. Sorry, that's not true, JDK supports keep-alive.

2. You should close the streams in a finally block or use try-with-resources. See Guideline 1-2: Release resources in all cases in Secure Coding Guidelines for the Java Programming Language

3. I don't think that you need the thread-safe capability of StringBuffer, so you could use the faster StringBuilder.

4. Furthermore, instead of the while loop you could use IOUtils.toString() which also does the buffering for you.

   final String response;
   final InputStream inputStream = con.getInputStream();
   try {
       response = IOUtils.toString(inputStream, "UTF-8");
   } finally {
       inputStream.close();
   }
   

5. Your statistics could show invalid data because if you change the system date System.currentTimeMillis() will reflect that. I suggest using System.nanoTime() or a stopwatch class (Guava, Apache Commons).

6. The variable names should be more expressive. For example, BigInteger should express the purpose of the variable. Furthermore, try to follow the Code Conventions for the Java Programming Language.

7. Check LineIterator in Apache Commons IO. It would save you a few statements and would provide easier maintenance and better readability.