Tell me more ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.
up vote 3 down vote favorite

I am trying to find some measurement for identifying and distinguishing between compressed and random data. I tried this first by computing the entropy of such data, the entropy value is extremely high (almost maximum) in both cases, so that way does not seem to work as a distinguisher.

I read about the chi square algorithm but I've never used it (actually I still have some problems with interpreting the results). Does anybody know if this algorithm can lead to better results?

share|improve this question
1  
I am not an expert in this, but the NIST tests might do a better job. – mikeazo♦ Aug 15 '12 at 13:07
Wikipedia has a pretty good description of Pearson's chi-squared test. The challenge, really, is coming up with a suitable null hypothesis to test; for example, even very poor pseudorandom streams will usually satisfy the simple hypothesis that the frequencies of individual bytes are uniformly distributed, no matter what test you use. – Ilmari Karonen Aug 15 '12 at 14:01

1 Answer

up vote 1 down vote

The NIST tools are a good starting point.

There is no general-purpose algorithm that will always distinguish compressed from random data

However, if you want to try the chi-squared test, you can compute a histogram of the frequency of all byte values (how many 0 bytes you saw in the data, how many 1 bytes you saw, etc.), and then use the chi-squared test to test whether this appears to deviate from what you'd expect for uniform-random data.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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