What statistics can be used to identify pseudorandom data?

Question

I'm working on some code that attempts to identify files whose contents appear to be "random". As such, I'm looking for statistical measures that can be used to identify such randomness.

I've implemented the following so far:

• Shannon entropy of the sample (i.e. -∑ p(x_i) log₂ p(x_i) over the sample X)
• Bytewise sample variance (0.0 is a perfect score)
• Bitwise mean (0.5 is a perfect score)
• Bitwise mean distributed across bits 0 to 7 of each byte (looking for any significant variance)
• Percentage of bytes within the range 0x20 ≤ b ≤ 0x7E (37.11% is a perfect score)
• Bit-pair counts (i.e. checking for equal counts of 00, 01, 10, 11)
• Repeated byte distances (i.e. looking for xx, x*x, x**x, x***x, ... patterns)

These seem to give a reasonable measure of uniform "randomness", in that 128 bytes generated by concatenating two SHA512 hashes can easily be distinguished from ASCII text or an executable file simply by looking at the statistics.

However, I'd like to know if there are any other strong indicators that I should look into that might indicate that the sample data was generated by a cryptographic PRNG.

Update: To be absolutely clear, I'm not trying to test the quality of a PRNG as a cryptographic randomness source. I'm trying to distinguish between non-random files (e.g. executables, JPEGs, archives, etc.) and random files (e.g. TrueCrypt keyfiles). My tests so far are either used as ways to identify obviously non-random data (e.g. ASCII text) and data that isn't uniformly distributed in some way. I'm looking for other ways to test this.

Answer 1

During the AES competition, the organizing body (the NIST) went to the trouble of running extensive statistical testings on the output of the 15 submitted block ciphers, with what was believed to be the gold standard of such tests, the Diehard tests. They found nothing, of course. Comments from cryptographers at that time were that these tests were a bit ridiculous in the context of cryptographic algorithms (unofficial comments, of course: it would be discourteous to embarrass the host of the event); it was good for Public Relations that someone runs them, but nothing worth noting was expected from it.

This illustrates the difference between statistical randomness, as is needed for instance to power big simulations of physical systems, and unpredictability, which is required for security. Consider for instance the following PRNG:

• Set a counter to a 128-bit seed.
• To produce the next 128 bits of the PRNG, increment the counter by 1, then encrypt that value with AES and an all-zero key, yielding the 128 bits.

This PRNG will successfully pass all the tests of the Diehard suite; it is statistically "perfect" as far as the tests are concerned (departure from pure alea might be detectable after generating about 2⁷¹ bits, i.e. more than 200 millions of terabytes). However, for security, it is terrible, since it is trivial to predict future output once 128 bits of output have been observed (decrypt these 128 bits with AES and an all-zero key: this will give you the current counter value).

Summary: a cryptographically secure PRNG produces output which is indistinguishable from randomness; not only with statistical tests, but also by someone who knows exactly the specific PRNG algorithm which was potentially used. If you have a statistical tool which can show that a given sequence of bytes comes from a PRNG, then you have proven not only that the PRNG is not cryptographically secure, but also that it is awfully bad at it. Even Dave's hash is "random" from the point of view of Diehard tests.

In shorter words, your tool won't catch randomness which was generated with some expertise, but it won't catch most non-randomness from complete amateurs either. With such tools, you are not targeting "non-cryptographers who should know better than to use homemade schemes", but rather "chimpanzees who should not be allowed to touch a keyboard".

Note: good steganography tools encrypt data before stuffing it into the transport medium, precisely to avoid detection from statistical tool. Encryption also should yield bits indistinguishable from randomness.

Answer 2

http://www.fourmilab.ch/random/ uses the following

• Chi-square test
• Arithmetic mean
• Monte Carlo Pi estimation
• Serial Correlation Coefficient

You might want to add "incompressibility" too (this also means you might need to identify compressed files in order to eliminate them). Dan D's Diehard (and Dieharder) suggestion looks like a very thorough solution. (Edit: Dieharder is strictly targeted at testing PRNGs, not snapshots of their output, and definitely not suitable for small data samples.)

Your task shares some of the problems involved in statistical File Carving and forensic searching for encrypted data: the smaller the data set the harder it is to be definitive about whether it's "random".