1
$\begingroup$

For a challenge, I need to find the key that enciphered a text.

I know that the key is of length N (invariable). There is no assurance that the key is only alphabetical or alphanumeric, but it could be a reasonable assumption.

I know that the original text is alphabetical only, no number, but there is no assurance that the text is lowercase or uppercase only. It would be a reasonable assumption that the text has lowercase and uppercase characters.

The actual encryption is similar to the one of a Vigenere cipher, in that it uses a rolling key to XOR the input, character by character going like (pseudo code, don't try to run this in any language) :

ciphertext = ""
n = 0 ; //key iterator
for character in input:
    ciphertext += key[n] XOR character;
    n++;
    if(c >= N) { // reset key iterator when reaching the known length of the key
        c = 0;
    }
return ciphertext

The output is not directly usable as text and the input has both uppercase and lowercase characters.

How should I go about breaking the encrypted text ?

What I thought about:

Extract from the encrypted text the characters encrypted by the same letter of the key, for example, isolate all characters encrypted with key[0], and run statistical analysis on it. My problem is that the presence of uppercase and lowercase letters makes statistical analysis difficult, being unable to differentiate the same letters in uppercase or lowercase. We now have 52 possible letters instead of 26, on a text that is too short to use this method. (around 450 characters, for a 8char long key, it means only 56char by set)

Go the known plaintext way, trying to find commonly used words. The problem is that he text is most likely either in french, or english, and the longer the word, the most likely it is that it's not present in the text. I think this is a last resort solution.

Simply bruteforce the text. Assuming a key length of 8char, with a charset of 0-9a-zA-Z, we've got 62^8 (several hundreds thousands of billions) possible permutations, which is impossible to cover.

What could I do to resolve this, or reduce the time it would take to solve ? I was wondering is there was a way to know if the input text is either in lowercase or uppercase from the encrypted text, or if there is a way to manipulate the encrypted text to put it all in uppercase ... That would help with the statistical analysis a bit, even if I won't most likely have not enough data for a quality analysis.

$\endgroup$
  • $\begingroup$ $62^8$ is 48 bits. Perfectly possible to cover, cfr. the DES cracker, 72 quadrillion keys. $\endgroup$ – Ruben De Smet Mar 9 '18 at 21:18
  • $\begingroup$ I should have been clearer on that point. While it is possible to do so, it is impossible to bruteforce this way in a short time (under an hour with an average computer), unless my rudimentary bruteforce script was so badly done that my performances were not even close to good. $\endgroup$ – Jay Zus Mar 10 '18 at 23:08
  • $\begingroup$ You're 14 bits short of DES. DES cracker did it in 56 hours. Given that your system is way simpler, you can build an alike machine that does this in seconds. Perfectly possible to cover, and I would indeed assume that modern standard computers can break it fast too. $\endgroup$ – Ruben De Smet Mar 12 '18 at 8:34
  • $\begingroup$ Well, after redoing my work, I've seen that I've made a mistake. The sets corresponding to the columns were not of 56char, but of more than 400. I don't know hat I did the first time... It gave enough possibilities to run statistical analysis and I've found the most present letter, assumed it was E, and ran a XOR to find the original letter. It worked. I also found out that there were tools that do it for you, like xortools. $\endgroup$ – Jay Zus Mar 12 '18 at 14:13
  • $\begingroup$ I tested xortool and I can confirm that my script was bad, it is near instantaneous using it :-( $\endgroup$ – Jay Zus Mar 12 '18 at 14:50
3
$\begingroup$

After more time on this challenge, here is what I've done to solve it.

Divide the text by N columns, where N is the length of your key.

Run frequency analysis on each column. Given enough data, you will most likely get a character that is present far more often than the others. Since my text was in french, it was the letter e.

For each column, find one instance of the value that is supposed to be an 'e' and XOR that data with the letter 'e' to find the Nth letter of the key.

Given enough data, you will find an 'e' for every column, giving you all the letters of the key. Try decrypting the text with the key, and voilà, you get the original text.

Once I've made up this way of solving the puzzle, I found out that it was a really common way to solve a XOR encryption, and that tools existed that could do it for you far faster than manually.

For example, xortool : https://github.com/hellman/xortool

xortool -l 8 input.bin -c65

-l is the length of the key, -c is the hexadecimal value of the most frequent letter in the language you think the text is in.

That command is near instantaneous.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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