4

Is there any benefit in determining how random a given file, stream, signal is?

I guess this would be useful to determine

  1. If something is (poorly) encrypted
  2. To verify the proper encryption of a file, data (GCM, SALSA20, or unknown cipher)
  3. To detect that a covert signal is being sent

Assuming I'm the role of either "Bob" or "Mallory", how would I measure how random a given stream of 1's and 0's are? (using any cipher method)

8
  • 1
    If you could do this, how would #2 apply? Why do you think that measuring randomness on the result of a cryptographic algorithm would be a metric for security?
    – schroeder
    Nov 25 '15 at 1:23
  • 1
    programmers.stackexchange.com/questions/147134/… may have some applicable information on this subject.
    – mti2935
    Nov 25 '15 at 1:26
  • 1
    @schroeder I think it might be a metric when observing blackbox or closed source implementations where the developer says "trust us". Nov 25 '15 at 1:35
  • 1
    But, how? Even random data might have patterns
    – schroeder
    Nov 25 '15 at 2:14
  • 2
    Detecting whether data is random or not doesn't really tell you if it's encrypted though. Highly compressed data is going to be largely indistinguishable from compressed data. Nov 25 '15 at 2:47
1

Oh boy, philosophy time. What is randomness? Can randomness be measured? What is a signal anyway?

Intuitively we can say that Thing A is more random than Thing B if it has more higher entropy. Entropy is one of those concepts that's easy to define and talk about, but actually measuring it from a data set is a statistician's nightmare. If your RNG outputs aaaaaaa... either your RNG sucks lemons, or you hit the one in a 10-n chance. With only one data point, it's impossible to tell.

For any statistical analysis of randomness to be at all meaningful you need at least a million samples generated in a lab environment where you can prove that your RNG was properly seeded for each sample. And even then you have to be very careful about which statistical tests you use because they all have a bias towards certain types of patterns. Trying to draw any conclusions about the quality of the randomness with less rigor than this will be ... inconclusive at best.

Bottom line: measuring cryptographic entropy in practice is hard and best left to researchers.


So that's the theoretical answer. In practice you can get a very rough idea of the amount of randomness in a string or file using the methods mentioned in comments / other answers: run it through a compression tool (which is a sub-category of Kolmogorov complexity tests), or one of the entropy-estimating stats tests mentioned in @EdwardBarnard's answer.

This type of thing is probably good enough for distinguishing an encrypted file from a plaintext file, but probably couldn't tell the difference between a compressed file and and encrypted file, or for that matter between a properly encrypted file and a badly encrypted file.


As for detecting covert signals, you're kinda out of luck if you're looking for a general solution. Tell me which off-the-shelf statistical tests you're using, and I'll design a steganography method that fools it. To have any hope of detecting this, you need to know a fair amount about the statistical properties of both the carrier signal, and the expected hidden signal, and design a detection algorithm around this. And of course the more noise naturally occurring in the carrier signal, the more places for covert signals to hide.

0

The Wikipedia article Randomness tests answers both questions (benefits of measuring randomness; how to do so). As the OP comments point out, randomness is not useful for measuring the validity/security of an encryption.

The closest use related to cryptography would be in evaluating pseudo-random number generators or other sources of randomness.

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.