5
\$\begingroup\$

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.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Does your code handle the case where the word "Andi" is the output of two threads (ex. half of it in each thread)? \$\endgroup\$ Feb 1, 2017 at 0:34
  • \$\begingroup\$ @HeshamAttia yes, as every thread just tries a complete shift. \$\endgroup\$
    – Andi Domi
    Feb 1, 2017 at 10:26
  • 1
    \$\begingroup\$ Are there any requirements in the decrypted string other than having the word Andi? The reason i am asking is that literally any string can be decoded to "Andi" with the right key. If you have the string "Abcd" and you want to convert it to "Andi", you could easily calculate the key by using the Vigenere table. \$\endgroup\$ Feb 1, 2017 at 22:11
  • 1
    \$\begingroup\$ Yes, actually the decoded string will have "Hello, Andi Domi " but i chosen the shortest word to keep the execution time at the minimum, but it's still long. And there is a high chance the key may be 5char long. So the execution time, by addition another while loop, will skyrocket. That's why I'm trying to optimise my code :/ \$\endgroup\$
    – Andi Domi
    Feb 1, 2017 at 22:16
  • 2
    \$\begingroup\$ This changes things a lot, could you please update your question with this information. \$\endgroup\$ Feb 1, 2017 at 22:31

3 Answers 3

5
\$\begingroup\$

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;
    }

}
  1. 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
\$\endgroup\$
4
+50
\$\begingroup\$

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).

  1. 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.

  1. 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.

  1. 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.

  1. 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]
    }
}
  1. 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:

  1. 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}

  1. 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.

  1. 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?
\$\endgroup\$
5
  • 1
    \$\begingroup\$ First of all, thank you for your compressive answer! Also i would like to address the fact that, after running the program and letting him do its job, I found no decoded message meaning the key was not actually of length 4 but probably higher, and also toaddress the steps you mentioned and the one i took. From step 1 to 6 I have nothing to say, those are a work of art and I will try to implement them right away. But I cannot fully understand the steps from 7 to 9. \$\endgroup\$
    – Andi Domi
    Feb 2, 2017 at 21:18
  • \$\begingroup\$ The thing is that if i try to do a partial analysis for keys 123 i will get a lot of false positives which should be checked manually, not a great thing if I have to add another shift to the whole program. But, your idea on step 8, I can add another “fake character” that will play the role of a shift which will always be equal to char * And then search for Andi*, And* ,Andi , Adi ,*ndi , In this case will cover all the possible cases if he * character falls inside the word Andi. \$\endgroup\$
    – Andi Domi
    Feb 2, 2017 at 21:18
  • \$\begingroup\$ Also I was thinking of doing the reverse. Decoding the message may be a painful job as the message perse has a lot of characters so I was actually thinking of encoding the hint I have and then search for it in the encoded message for a match. The problem in this case would be that I could not use the fake character. From what the description says the key can have all 256 characters of ascii but there is a high chance the key itself will be alphanumeric word so it MAY fall into the [33-127] interval but there is no guarantee to that.. \$\endgroup\$
    – Andi Domi
    Feb 2, 2017 at 21:18
  • \$\begingroup\$ Good luck with the reverse! The fake character might be a good idea, but in 8 I meant something else. The idea is that for a given value of shift1 you can decode characters on positions: 0, 4, 8, etc. Then, if decoded[4] is "n" you only need to check that decoded[3] is "A", decoded[5] is "d" and decoded[6] is "i". This will give you all the shifts right away. It's getting more complicated when the key is longer than 4, though. \$\endgroup\$ Feb 3, 2017 at 3:10
  • \$\begingroup\$ @AndiDomi wow, thanks for the bounty. Didn't expect that, tbh. Much appreciated. \$\endgroup\$ Feb 10, 2017 at 16:31
3
\$\begingroup\$

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).

\$\endgroup\$
5
  • \$\begingroup\$ Thank you for your answer, because I'm a newbie in programming I will need some time to understand your high level code and implement it. But I have a question. How can you understand the position of "Andi Domi" (9char word)if the key is 8 digits? If I understood it correctly you search for a char in the 'decoded input text' that falls inside the 9char word, and then try to match the other digits. And you do this for different key lengths until you find a match. Is this correct? \$\endgroup\$
    – Andi Domi
    Feb 6, 2017 at 15:30
  • 1
    \$\begingroup\$ @AndiDomi, not quite. And now that I come to explain it, I realise I've got a small bug in my pseudocode. Vigenère is almost symmetric in the key and the plaintext: repeat the key to get a keystream as long as the plaintext and it becomes symmetric. So if you extract the substring which corresponds to the crib and decrypt with the plaintext, you get the keystream. If decrypting 11 chars from offset 3 gives SDPSDFQWGDK then either the key is at least 11 chars or you missed. If offset 17 gives KCORDKCORDK then it's probably a hit with key RDKCO. \$\endgroup\$ Feb 6, 2017 at 15:42
  • \$\begingroup\$ What you are saying is that with the "tip word" {Hello, Andi Domi} we can do a character difference with the 16 characters of the decoded text and then see the difference(shift) between the two 16char strings. Because the encoding is always symmetric there should be a repetition of the shift. And this is the best case scenario for this exact cause , especially if we know there is period of the key in the tip word (a 16char key is not really feasible to break), but what if I only had the word Andi and the key was greater than 4 and the word fell inside the full key? \$\endgroup\$
    – Andi Domi
    Feb 6, 2017 at 16:04
  • \$\begingroup\$ I believe that next time we'll have something similar, without a hint and a longer key to play with. Something I was actually thinking I may try on a GPU if I can find a library that allows you to run java code on it \$\endgroup\$
    – Andi Domi
    Feb 6, 2017 at 16:07
  • \$\begingroup\$ @AndiDomi, a 16-char key is perfectly feasible to break. You just need a decent heuristic to tell you whether a candidate decryption looks like English text. E.g. if it's at least 80% A-Za-z and at least 80% of the continuous runs of letters are in an English dictionary, it's probably correct. If you don't have a crib you can either try candidate key lengths using the same heuristic or you can use auto-correlation, but that's getting well outside the scope of this question. \$\endgroup\$ Feb 6, 2017 at 16:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.