Brute-force Vigenere Cipher using multiple threads

Question

I'm trying to brute force a Vigenere Cipher knowing only that the key length is 5+ characters and that the decrypted text has the word Hello, Andi. So I wrote this small Java program that tries to brute-force the key through a given numbers of threads and nested while loops.

Run.java (main class)

package vignere;

import java.io.IOException;


public class Run {

    public static void main(String[] args) throws IOException {
//number of threads you have and encrypted text file
        Brute brute = new Brute(4, "41259.txt.enc");

        Thread t1 = new Thread() {
            @Override
            public void run() {
                try {
                    brute.bruteF_thread(1);
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        };
        Thread t2 = new Thread() {
            @Override
            public void run() {
                try {
                    brute.bruteF_thread(2);
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        };
        Thread t3 = new Thread() {
            @Override
            public void run() {
                try {
                    brute.bruteF_thread(3);
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        };
        Thread t4 = new Thread() {
            @Override
            public void run() {
                try {
                    brute.bruteF_thread(4);
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        };

        t1.start();
        t2.start();
        t3.start();
        t4.start();

        try {
            t1.join();
            t2.join();
            t3.join();
            t4.join();

        } catch (Exception e) {
            e.printStackTrace();

        }

    }
}

And the class that handles the brute-force attack Brute.java

package vignere;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;

public class Brute {
    int totalCORE;
    Path path;

    public Brute(int totalCORE, String string) {
        this.totalCORE = totalCORE;
        this.path = Paths.get(string);
    }

    public void bruteF_thread(int threadNR) throws IOException {

        byte[] txt_enc = Files.readAllBytes(path);

        byte[] plaintxt = new byte[txt_enc.length];

        int shift = (256 / totalCORE) * (threadNR - 1);
        int moduloNr = 0;
        if (256 % totalCORE != 0 && totalCORE == threadNR) {
            moduloNr = 256 % totalCORE;
        }
        while (shift < ((256 / totalCORE) * threadNR) + moduloNr) {
            System.out.println(shift);

            int shift2 = 0;
            while (shift2 < 256) {
                // System.out.println(shift2);
                int shift3 = 0;
                while (shift3 < 256) {
                    int shift4 = 0;
                    while (shift4 < 256) {
                        int i = 0;

                        while (i < 40) {

                            // first char by shift
                            int charNr = txt_enc[i] & 0xff;
                            charNr = charNr + shift;
                            charNr = charNr % 256;
                            plaintxt[i] = (byte) charNr;
                            i++;

                            // second by shift2
                            charNr = txt_enc[i] & 0xff;
                            charNr = charNr + shift2;
                            charNr = charNr % 256;
                            plaintxt[i] = (byte) charNr;
                            i++;

                            // third one by shift3
                            charNr = txt_enc[i] & 0xff;
                            charNr = charNr + shift3;
                            charNr = charNr % 256;
                            plaintxt[i] = (byte) charNr;
                            i++;

                            // fourth by shift4
                            charNr = txt_enc[i] & 0xff;
                            charNr = charNr + shift4;
                            charNr = charNr % 256;
                            plaintxt[i] = (byte) charNr;
                            i++;

                        }
                        // after the array is filled
                        // convert it to string
                        String aString2 = new String(plaintxt);
                        if (aString2.indexOf("Andi") > 0) {
                            System.out.println("The code you are looking for is: " + shift + "-" + shift2 + "-" + shift3
                                    + "-" + shift3);
                            System.out.println(aString2);
                            // System.exit(1);
                        }
                        shift4++;
                    }
                    shift3++;
                }
                shift2++;
            }
            shift++;
            System.out.println(shift++);
        }

    }
}

And while I know that a lot of computation is required I would like to know if there is any way I could optimise this code, as it's painfully slow.

Answer 1

I'll have a try to decompose the problem into responsibilities:

1. You need a key generator that continiously produces unique keys of a certain key length that are used to shift characters
2. You need a Decoder that will decode an encoded Text with a given key
3. You need an indicator that your decoding was potentially successful.

1

public class KeyGenerator {

    private int currentKeyLength;

    public KeyGenerator(int minimumKeyLength) {
        this.currentKeyLength = minimumKeyLength;
    }

    public synchronized Key next() {

       // determine current key length

        byte[] keyBytes = new byte[currentKeyLength];

        // build next shift sequence

        return new Key(keyBytes);
    }

}

2

public class Decoder {    

    private EncodedText encodedText;
    private Key key;

    public Decoder(EncodedText encodedText, Key key) {
        this.encodedText = encodedText;
        this.key = key;
    }       

    public DecodedText decode() {

        byte[] keyBytes = key.getKeyBytes();
        byte[] decodedTextBytes = new byte[encodedText.getEncodedTextBytes().length];

        // decode encoded text bytes with key bytes

        return new DecodedText(decodedTextBytes);
    }       

}

3

public class DecodeSuccessfulIndicator implements Predicate<DecodedText> {

    private String referenceString;

    public DecodeSuccessfulIndicator(String referenceString) {
        this.referenceString = referenceString;
    }  

    @Override
    public boolean test(DecodedText decodedText) {
        return new String(decodedText.getDecodedTextBytes()).indexOf(referenceString) >= 0;
    }

}

4. I introduced some wrapper objects as byte arrays are not that expressive: EncodedText, Key and DecodedText

4

public class EncodedText {

    private byte[] encodedTextBytes;

    public EncodedText(byte[] encodedTextBytes) {
        this.encodedTextBytes = encodedTextBytes;
    }

    public byte[] getEncodedTextBytes() {
        return encodedTextBytes;
    }

}

public class Key {

    private byte[] keyBytes;

    public Key(byte[] keyBytes) {
        this.keyBytes = keyBytes;
    }

    public byte[] getKeyBytes() {
        return keyBytes;
    }

}

public class DecodedText {

    private byte[] decodedTextBytes;

    public DecodedText(byte[] decodedTextBytes) {
        this.decodedTextBytes = decodedTextBytes;
    }

    public byte[] getDecodedTextBytes() {
        return decodedTextBytes;
    }

}

Composing the elements

Now we have all responsibilities together we can couple them. I was really astonished as I found a proper application for streams. This is a JAVA 8 style solution:

First we create a stream of keys:

Stream<Key> keyStream = Stream.generate(new KeyGenerator(4)::next);

After that we load the encodedText:

EncodedText encodedText = new EncodedText(Files.readAllBytes(Paths.get("41259.txt.enc")));

Now we can decode the encoded text with every key in the stream and get a stream of decoded texts:

Stream<DecodedText> decodedTextStream = keyStream.map(key -> new Decoder(encodedText, key).decode());

After that we create a predicate that defines that we are only interested in potentially successful decoded texts:

DecodeSuccessfulIndicator decodeSuccessfulIndicator = new DecodeSuccessfulIndicator("andi");

Finally we define a filter on the stream and collect our results:

List<DecodedText> collect = decodedTextStream.filter(decodeSuccessfulIndicator::test).collect(Collectors.toList());

All together:

public class Run {

    public static void main(String[] args) throws IOException {

        Stream<Key> keyStream = Stream.generate(new KeyGenerator(4)::next);

        EncodedText encodedText = new EncodedText(Files.readAllBytes(Paths.get("41259.txt.enc")));

        Stream<DecodedText> decodedTextStream = keyStream.map(key -> new Decoder(encodedText, key).decode());

        DecodeSuccessfulIndicator decodeSuccessfulIndicator = new DecodeSuccessfulIndicator("andi");

        List<DecodedText> collect = decodedTextStream.filter(decodeSuccessfulIndicator::test).collect(Collectors.toList());

    }

}

Language sugar

One thing I did not adress until now: parallelism. You used threads to increase brute force speed. I want to suggest a different approach. As we are already using the JAVA 8 Streaming API we have only one thing to change to load our CPUs:

Change

Stream<DecodedText> decodedTextStream = keyStream.map(key -> new Decoder(encodedText, key).decode());

to

Stream<DecodedText> decodedTextStream = keyStream.parallel().map(key -> new Decoder(encodedText, key).decode());

Changing the key stream to a parallel stream will cause concurrency. Noticed the synchronized method in the KeyGenerator to work properly in parallel?

public class KeyGenerator {

    ... 

    public synchronized Key next() {
        ...
    }

}

Finally

I did a little research as I was interested in a solution for limiting streams by a certain condition. I had to implement a mystic interface called "Spliterator". Fortunately there was an abstract Base-class I could derive from even it may have a little drawback in performance. So Here it is:

public class KeySpliterator extends Spliterators.AbstractSpliterator<Key> {

    private Supplier<Key> keySupplier;

    protected KeySpliterator(Supplier<Key> keySupplier) {
        super(Long.MAX_VALUE, Spliterator.SIZED);
        this.keySupplier = keySupplier;
    }

    @Override
    public boolean tryAdvance(Consumer<? super Key> action) {

        Key key = keySupplier.get();

        if (key != null) {
            action.accept(key);
            return true;
        } else {
            return false;
        }

    }

}

So the method "KeyGenerator.next" has to return null if no more key is available.

And instantiating the keyStream will be a little different:

Stream<Key> keyStream = StreamSupport.stream(new KeySpliterator(new KeyGenerator(4)::next), true /* parallel */);

The only things that are left to implement:

1. The KeyGenerator.next-method
2. The decoding algorithm in the Decoder class

Answer 2

I'd like to suggest several improvements.

Refactoring / Code cleanup

1. Move IO operations into a separate class.

Currently, each thread needs to load input file. You can create a separate class that reads input and returns a string or byte array. As an alternative, you can read input file in main and then pass it to Brute instance(s).

2. Reduce duplication in Run.java.

You can move thread initialization and launch into a separate method (startBruteForce(int threadNumber, int threadCount, byte[] input)) and call it in a loop.

3. Implement Brute as Runnable.

Implementing Brute as Runnable will simplify thread initialization

(new Thread(new Brute(threadNumber, numberOfThreads, input)).start();

and eliminate possible concurrency issues with Brute fields.

You can move threadNr to Brute constructor and rename bruteF_thread to run. This way you'll need to create separate instances of Brute for each thread.

After this step, you can probably inline the method created at step 2.

4. Naming

Declare meaningful constants for magic values (40, 256, "Andi"), local variables and fields for intermediate values:

int minShift = (256 / totalCORE) * (threadNR - 1);
int maxShift = ((256 / totalCORE) * threadNR) + moduloNr);
for(int shift = minShift; shift < maxShift; shift ++) {
    //shift
}

Initialization code can be moved to the Brute constructor.

5. Move decoding into a separate method

You can create a method that accepts an array of generated shifts and returns "decoded" text:

byte[] decode(int[] shift) {
    for(int i=0; i<input.length; i++) {
         int shift = shift[i%shift.length];
         decoded[i] = //shift input[i]
    }
}

6. Move shift iteration into a separate method.

This way you can get rid of nested loops and replace them with an iteration based on shifts array. This is slightly more complicated because you'll need to implement methods that initialize, increment and range check shifts array.

After these steps Brute algorithm will have a clearer structure.

For simplicity, you can turn local variables used in several methods into fields. Then you'll get something like this:

public class Brute implements Runnable {
    private final byte[] input;
    private final byte[] decoded;
    private final int minShift;
    private final int maxShift;
    private final int[] key;

    public Brute(int threadNumber, int threadCount, byte[] input) {
        initFields();
    }

    @Override
    public void run() {
        while(isKeyInRange()) {
             tryToDecode();
             if(isDecoded()) {
                 displayResults();
                 return;
             }
             incrementKey();
        }
    }
} 

Performance

The algorithm is slow because it fails at the last possible moment: after decoding the whole input text. For example, some values of shift1 don't produce 'A', 'n', 'd' or 'i' anywhere in the string. In this case algorithm can move to the next value of shift1 without intermediate calculations.

You can apply several heuristics to improve the performance of the algorithm:

7. Implement efficient decoding

If you already processed input text for key {1,2,3,4} you don't need to process all of it again for key {1,2,3,5}

8. Partial analysis

For each value of shift1 you can partially decipher input text and use the results to eliminate knowingly false shift combinations.

For example: if deciphering for shift1 = 1 produces results like this:

P***q***A***X***n***
        ____   ____

then you need to search only around letters from "Andi". Moreover, you can predict possible values for shift2 without iteration.

9. Start with a clue

As you only need to determine the position where "Andi" appears in the input text, you can re-implement algorithm to check all available positions rather than brute-force all possible keys.

Minor issues:

• It seems that your implementation only checks for keys of length 4. Are you sure about that?
• Do you really need to shift for 256? Are there any limitations on character range in decoded/encoded text?

Answer 3

I'm trying to brute force a Vigenere Cipher knowing only that the key length is 5+ characters and that the decrypted text has the word Hello, Andi. So I wrote this small Java program that tries to brute-force the key

As hinted in default locale's point 9, you're brute forcing over the wrong space. If your space is keys of length 4 from an alphabet of 256 values, that's a search space of 4294967296 keys. But if the ciphertext is 4000 characters, the 11-character crib gives you a search space of 3990 offsets at which the crib might be found. (Since the comments suggest that you really have a 16-character crib, you should use that instead to reduce false positives).

In other words, my high-level review is that you should throw almost all of the code away and start from scratch with a different algorithm. Without filling in all the gaps:

public ... decryptVigenereWithCrib(String ciphertext, String crib)
{
    Set<String> candidateDecryptions = new HashSet<String>();
    for (int offset = 0; offset + crib.length() <= ciphertext.length(); offset++)
    {
        checkCrib(ciphertext, crib, offset, candidateDecryptions);
    }

    // Here you may want to return candidateDecryptions, print them all, try to apply
    // further heuristics to select the best one, ...
}

public void checkCrib(String ciphertext,
                      String crib,
                      int offset,
                      Set<String> candidateDecryptions)
{
    String subCiphertext = ciphertext.substring(offset, offset + crib.length());
    String candidateKey = decrypt(subCiphertext, crib);

    // If the crib is longer than the key, candidateKey will contain multiple copies
    // of the key.
    // TODO Decide how you want to select the maximum key length
    for (int keyLength = 4; keyLength < ...; keyLength++) {
        // TODO Implement isRepeatedString
        if (isRepeatedString(candidateKey, keyLength)) {
            // candidateKey starts at position offset, but we want the key from position 0
            // so we have to rotate it.
            int rot = keyLength - (offset % keyLength);
            String key = candidateKey.substring(rot, keyLength) +
                         candidateKey.substring(0, rot);
            candidateDecryptions.add(decrypt(ciphertext, key));
        }
    }
}

This should run fast enough that you don't need multi-threading. When I applied this technique to prove to a merchant bank that their API's use of Vigenère encryption to "protect" transaction data passing from my client's web shop to their credit card payment gateway via the customer's browser was completely insecure, it found the key instantaneously. (Very shortly afterwards they brought out an updated API which supported modern cryptographic algorithms).