24
$\begingroup$

If we have to determine a file is encrypted or not, can we use Shannon's entropy algorithm on the file?

As discussed here, the entropy (in bits per byte) being closer to 0 is considered as more orderly and being closer to 8 is considered more random.

Intuitively this might be generating false positives a lot. Can any one explain if this approach is appropriate to determine given a random file is encrypted or not?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ pure random files will have the most, followed by encrypted, then by compressed. audio and image files have less, text even less, ht/xml way less... see youtube.com/watch?v=T0MVe4aud30 the real smoking gun for encrypted files is a uniform distribution of bit values, see around 15m on the video specifically. $\endgroup$
    – dandavis
    Jun 29, 2016 at 6:32
  • 1
    $\begingroup$ Shannon entropy is defined for a process that generates a random output not for strings of data. Kolmogorov complexity is uncomputable (and would only be minimally bigger for an encrypted file than for the equivalent plaintext). So you're pretty much left with trying the compress the file (e.g. using gzip/deflate) and checking if it gets smaller. $\endgroup$
    – CodesInChaos
    Jun 29, 2016 at 15:05
  • $\begingroup$ I'm pretty sure /etc/entropy.bin is not encrypted and it has no meaningful headers. $\endgroup$
    – Joshua
    Jun 30, 2016 at 2:02
  • $\begingroup$ Good encryption does NOT necessarily lead to high entropy! Imagine you encrypt cipher stream of a stream cipher with the same cipher. This leads to a lot of zeroes, but its encryption is strong. Similar things can be achieved with block ciphers. I can't verify now, but I guess this video contains examples: media.ccc.de/v/31c3_-5930-en-saal_6-201412291400-funky_file_formats-_ange_albertini $\endgroup$
    – bot47
    Jun 30, 2016 at 9:29

2 Answers 2

Reset to default
34
$\begingroup$

You are likely going to have both false positives and false negatives if you try to use Shannon entropy for this.

  • Many compressed files would have close to 8 bits of entropy per byte, resulting in false positives.
  • Any encrypted file that has some non-binary encoding (like a file containing an ASCII-armored PGP message, or just a low entropy header) could have a lower entropy, resulting in false negatives.
  • If Format Preserving Encryption is used , this might result in false negatives too

It may work as a heuristic, but you should not rely on the results being correct.

Improve this answer
$\endgroup$
16
  • 2
    $\begingroup$ You could, however, check the first 4-8 bytes of the file and see if the magic number is or isn't part of a list of known compressed files or binary files. Having PNG, PK, MZ, GIFa, PDF or similars as the first bytes, will tell you that the file is not encrypted. This requires a massive lookup list for detection. $\endgroup$
    – Ismael Miguel
    Jun 29, 2016 at 14:49
  • 2
    $\begingroup$ That is a good point. But, your point is slightly mute when you know the structure of these files. Yes, the content could be encrypted, but, it would be a corrupted file (I would be surprised if i saw a valid encrypted PNG) or it has somewhere in it's structure saying that "this is encrypted". I agree with the premise that you can't do this reliably, but you can rule out some "points" by knowing the file structure. And answering to your question, you can't know for sure that a file composed of scrambled bytes is just garbage (E.g.: random mojibake) or really encrypted. $\endgroup$
    – Ismael Miguel
    Jun 29, 2016 at 15:04
  • 1
    $\begingroup$ @IsmaelMiguel Perhaps not PNG, but borrowing from my comment to Will's answer: I can use a perfectly valid TIFF container to hold a binary PGP-encrypted message, which file will almost certainly quite happily call a TIFF image and move on with life. (I'm even quite sure I could make one that holds both a PGP-encrypted message and a real image, which opens and displays fine!) $\endgroup$
    – user
    Jun 29, 2016 at 15:11
  • 2
    $\begingroup$ @IsmaelMiguel that is a PNG that is both valid and encrypted, as you said you would be surprised to see. It's not difficult to find more examples, or indeed to generate them. $\endgroup$
    – OrangeDog
    Jun 29, 2016 at 17:19
  • 3
    $\begingroup$ Conversely I can run an encrypted file through a uuencode/base64/ascii85 and produce a file with respectively less entropy. $\endgroup$
    – Aron
    Jun 30, 2016 at 1:05
6
$\begingroup$

Yes its a good indicator and no there won't be many false positives.

A high-entropy file indicates that a file is either well-encrypted, well-compressed or just contains truly random bytes.

Most compression formats have recognizable headers etc so these can be easily distinguished.

Most people do not have files of random bytes lying around - why would they?

Strong cryptography strives for ciphertext indistinguishability. Which is a necessary property for security, but which also makes it stand out.

So imagine you are the police or border agent interrogating a suspect. There is a file on their computer that is seemingly random. You will conclude that it must be encrypted, and demand the suspect hand over the keys.

People also strive to find "distinguishers" for standard ciphers and encryption formats. For example, trucrypt.

Hiding a message, beyond just encrypting it, is called steganography.

Improve this answer
$\endgroup$
15
  • 4
    $\begingroup$ Not "well" encrypted. Even very broken encryption algorithms can be random enough that Shannon entropy is close to maximum. (E.g. nonce reuse with a stream cipher.) $\endgroup$
    – otus
    Jun 29, 2016 at 6:49
  • 3
    $\begingroup$ ... or compressed, or binary ( just do an entropy calculation of your MP3 or video collection). Entropy calculation by itself won't cut it. You said it yourself by pointing to compressed files and the need to check their headers - which goes beyond entropy calculation, fixing the false-positive issue @otus pointed at in his answer. Note that the question didn't ask how to differ files, but if entropy calculation suffices to identify. It obviously doesn't. $\endgroup$
    – e-sushi
    Jun 29, 2016 at 9:38
  • 2
    $\begingroup$ I'm pretty sure that, with for example a reasonable-length MP3 or a reasonable-size JPEG photo, the well-known headers are going to be completely dwarfed by the payload data. Hence, the headers won't significantly affect the overall "entropy" of that file. And I can use a perfectly valid TIFF container to hold a binary PGP-encrypted message, which file will almost certainly quite happily call a TIFF image and move on with life. $\endgroup$
    – user
    Jun 29, 2016 at 14:18
  • 2
    $\begingroup$ I think commenters may be overly fixated on the word "determine" in the question. This answer does not take that literally and considers this a more practical than academic question. I give +1 here because I expect this technique should work well in practice, quickly and easily paring down a large hard drive into relatively few candidates which can then be examined more carefully. As an extra step, any compressed archives found should be exploded and the contents scanned in the same way. $\endgroup$
    – wberry
    Jun 29, 2016 at 15:44
  • 2
    $\begingroup$ RE base64 encoding, if you take XML plaintext and base64 encode that, you can visually see the patterns in the encoded text. With practice one could learn to recognize certain plaintexts in the encoded form. base64 is not a scramble and will not greatly affect the entropy measure. $\endgroup$
    – wberry
    Jun 29, 2016 at 15:45

Your Answer

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

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