36

For school, I have to do an exercise in which I have to decrypt files by brute force attack.

There are a lot of different files in different file formats. The files have been encrypted using XOR or the caesar algorithm.

I know how to try every possible key to decrypt the files but, how can I know if the file is being decrypted with the right key or not?

  • 7
  • 18
    In general, you can't, and that's precisely why one-time pads are secure. – Nate Eldredge Apr 9 '16 at 1:51
  • Look at the distribution of data - make a histogram if necessary. Most types of encryption are intentionally engineered to create a rather uniform data distribution that's indistinguishable from random data - but not from a a jpeg or other file formats that have some sort of vaguely yet visibly skewed data distribution; i.e. a pattern. Of course, if you're doing one-byte XORing or simple substitution ciphers, just run a brute force script. Chances are it's a one-byte XOR key (only 255 possible outputs) or it's a fixed shift key (only [number of letters in the alphabet] possible outputs) – jDo Apr 9 '16 at 14:21
  • This sounds like a pretty cool exercise. What university/course is this? Does the professor post lecture notes online? – rookie Apr 9 '16 at 15:51
  • It is a small part of a course about load balancing at Epitech (france). We have to make a UI in which the user puts files encrypted or not and we have to distribute the tasks to find some data in it (email, phone number, ip) over many processes and machines over a network. The subject is not available online but if you want it, i could send it to you. – juan michelle Apr 9 '16 at 16:52
52

You really can't, if you're just encrypting / decrypting text.

If you know that the encrypted string is "kdo" and the encryption method is a Caesar shift, the plaintext could just as easily be "IBM" as "HAL". You'd have to have some idea of what the plaintext "looks like". For instance, if you know the plaintext is the name of a Stanley Kubrick character, you'd have a decent idea of which one it should be.

If you have a longer string, it's much easier to narrow things down. A large text file has much fewer intelligible results than the three-character example above. But you'll still need to determine whether it's decrypted yourself.

On the other hand, if you're decrypting an entire file in some specific format (.docx, etc), you can be reasonably sure the file is decrypted if the parsing program (Word, etc) can read it.

  • 30
    Since this is a school assignment, it is reasonable to expect a simple way to detect cleartext - likely discussed in class, and likely whose histogram is close to English (or whatever language the class is taught in) – atk Apr 9 '16 at 4:01
  • 1
    Just a sidenote, but actually there are possibilites to detect whether a file was decrypted with the correct key. They are pretty complex though and not most likely not relevant for OPs question, but you can use language-detection to determine whether the file decrypted correctly. Files with a header can be parsed by checking whether the header was decrypted correctly, which would be the equivalent of the language-check. Actually the test you proposed for docx-files is a - not exactly elegant - implementation of exactly that approach. – Paul Apr 11 '16 at 0:42
18

You absolutely can tell with varying degrees of certainty if a file, or even string, was successfully decrypted. Most of the challenges at cryptopals depend on it. I have begun to make a tool for ciphertext bruteforce and analysis that automates this very task. You can find it here if you want to take a look.
(it needs a lot of cleaning up, don't judge me)

My goal originally in this project was to improve my efficiency in CTF crypto challenges with a simple brute-force tool, but I'm starting to work on implementing a lot more analysis. As it stands, it can bruteforce all caesar, single-byte XOR, atbash, and a few encodings, with repeating-key XOR developed but not integrated yet.

The way it works now

  • takes input ciphertext string or file of newline-delimited ciphertext strings
  • attempts to decrypt with entire keyspace of supported ciphers
  • after every decrypt attempt, runs a detection function on cleartext to determine if the decrypted text is English
  • displays most likely guesses

The one thing that makes this process finicky is how the thresholds for English detection must be adjusted depending on ciphetext length. It defaults to requiring 60% of the cleartext to be words and 75% of the cleartext to be letters to register a match. This setting rarely gives false positives, and even less frequently false negatives, on medium to long length cleartexts (anything over a few strings). When used on short length ciphertexts however, some false positives will pop up and many false negatives will get by. In testing, I have had to lower the thresholds by 30% or more to detect a match on some short strings, and in the process generate many more false positives that I have to sift through to find the real match.

I strongly recommend working through the cryptopals challenges from the beginning if you are interesting in learning more about making oracles and breaking crypto. It starts easy and progresses into real-world attacks, like making a Bleichenbacher Oracle, part of what makes the DROWN attack work.

tl;dr

you need to make a module that detects English and apply it to the result of every decryption attempt. or just fork mine and make it better.
in cases where the cleartext is not going to be English or another language, some more advanced analysis is required.

  • So what is the teacher expects you to do this? This is probably an assignment that has been done for years, they will know what students will try. So they put in one or two French or Chinese documents, or a compiled program without much text in it. How do you detect that? – SPRBRN Apr 11 '16 at 8:44
  • @SPRBRN If his assignment is to decrypt files by brute force attack then this is exactly how the teacher would expect him to do it. Do you have a different way? I highly doubt the teacher expects the students to look at each decryption attempt manually for every single key in the keyspaces of all common classic ciphers. If you really needed to detect French or Chinese you can implement the same strategy with dictionaries of those countries. What I don't understand is why you think their teacher would do this. As if the teacher would intentionally try to stop people from doing English analysis? – cremefraiche Apr 11 '16 at 9:05
10

If you have some idea what the cleartext is, you can use that knowledge guess when you've might have cracked the ciphertext.

If you think that the cleartext is english, for instance, start looking for english words in your decrypt attempt.

If you think the cleartext is a zip file, zip files have a signature at the beginning of the file. Look for that signature.

If you think the cleartext is an email, look for telltale email headers.

In general, you could try to look for the "information content" of the decrypt attempt. Plaintext normally has a lower information content than ciphertext, though this isn't true for a simple caesar cipher.

But you need to start with some inking of what the cleartext might contain, even if (as above) it's merely "a lower information content score than the ciphertext".

7

The other answers here are excellent for the general case. For a class assignment, I suspect that the professors want to make it very easy to tell when you have the file decrypted.

For example, are the files you're decrypting text files that show a message when they're correctly decrypted? If so, you can take a dictionary in your language and check wether a large proportion of the words in the message are in the dictionary. If you're using English, I would guess a threshold of 50% of words being in an English dictionary as a good number to use - an incorrectly decrypted file will be almost completely gibberish, but you don't want to ignore the correct plaintext if it has a few words, like proper nouns or technical jargon, that don't happen to be in your dictionary.

2

If the encrypted file is a text you need to check if the phrases inside the file have a sense or not, but if you need to discover something that it's not a word or a phrase (es. password or random letters) you must try all different possibilities. For example, I have a login password (random letters) encrypted with Caesar cipher. I must try, in the worst case, all 26 possibilities (assuming we are using lower case international alphabet) to check if the password is correct.

1

Many file formats start with a magic number (a byte sequence) that you can look for. Wikipedia has a list.

0

Other answers have covered most aspects, but another point is that, if you have access to the API that created the encrypted files, you could encrypt your own know file and brute force it (here you have something against to compare).

Once you get the key use it on the other files.

  • 1
    I am not the downvoter but your plan has a gap. The API or function which encrypted the text would take something like a shift value (in the case of a caesar cipher) or password as an input in addition to the plaintext. Your plan would be a great way to unit test the code but does not guarantee or prove that when run on real data that the output is the decrypted text. – Freiheit Apr 8 '16 at 20:33
  • @Freiheit thanks for your feedback, I think you are correct in case the shift value or password is unique to each file, but if it is shared my approach could work to find candidate shift values faster (in this case I assume the simplest option, a shared shift/password) – Felipe Pereira Apr 8 '16 at 20:48

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.