1
$\begingroup$

I'm writing a function that will allow me to analyze the randomness of some input data and return some stats about the probability of this data to be random.

Obviously it should be based on two things:

  • How often each byte value is found / not found (randomness / distribution)

  • And how much data we have (certainty)

So among the outputs of my function will be two values:

  • "randomness" (0 - 100) which tells how random the bytes look (regardless of how much data we have)
  • "randomlike" (0.001 - 99.999) which tells the general likelihood of the whole data to be random (a combination of randomness and length).

Is there a famous approach for this or I have to rethink the whole logic from scratch? This is probably something widely used in cryptography because this is how we can test keys: the decrypted data is highly random until the key is right.

I'm not looking for any particular language, just the math/logic approach.

One thing that puzzles me is: What does 50% randomness correspond to? Is it a subjective thing (like an art...) or math has some scientific ways to define what "50% randomness" means.

Improve this question
$\endgroup$
4

4 Answers 4

Reset to default
0
$\begingroup$

In terms of a measure of randomness, the usually accepted measure is Shannon entropy. In this sense for example 2 random bits which are 00 1/2 of the time, 01 1/4 of the time, 10 1/8 of the time and 11 1/8 of the time would represent 1.75 bits of random (from $\frac12+2\times\frac14+3\times\frac18+3\times\frac18$).

In your example then, if we sample $N$ bytes and byte $i$ comes up $b_i$ times we compute $p_i=b_i/N$ and then sum $$-\sum_ip_i\log_{256}p_i$$ and that is the "proportion" of a byte's worth of random that you are getting with each byte. By taking $N$ larger you get a tighter confidence interval for your estimate and I'll defer to better statisticians on the details.

BUT note that if you generate bytes just by listing them 0, 1, 2,..., 255, 0, 1, 2... then this will score (very close to) 1 even though most people would say this is not very random at all.

For a measure of how likely a sample is to be producing uniform random bytes, you should perform a Pearson $\chi^2$ test on the data.

For more general randomness tests also consider Marsaglia's Diehard tests.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ @FlorianB that idea is related to the kolmogorov complexity of a string, which measures "compressibility" of a string in terms of the smallest program (in some fixed programming language) that could produce that string. It is uncomputable though, and of limited practical use. One can make statements of the form that "random strings have high kolmogorov complexity" though (and it is useful within complexity theory). $\endgroup$
    – Mark
    Mar 11, 2021 at 0:02
  • $\begingroup$ But isn't the computation of an accurate $H$ still an open question, i.e. what is $p_i$ in the general case (including autocorrelation)? $\endgroup$
    – Paul Uszak
    Oct 14 at 22:59
1
$\begingroup$

As you're asking in Cryptography Stack Exchange (as opposed to, say, Math or Statistics), I assume you want to test not just for any randomness, but for cryptographically secure randomness.

In cryptography, we define security properties by saying that there exists no adversary that can break it—that no program can solve a given problem related to it. In the case of cryptographic randomness, we say that:

  • There is no program that can, given the entire history of our random sequence, predict the next bit with better probability than the uniform distribution (i.e. better than 1/2).
  • The above remains true, even if the state of the RNG (but not its key) is leaked.

Unfortunately for someone in your position, "there is no" is an incredibly strong claim--one that it is impossible to completely prove without unautomatable mathematical trickery unique to each "there is no"-style claim. The cryptographic primitives we herald as secure are "proven" in one of two ways:

  • They are published and the entire security community is invited to try to invent a program that breaks it.
  • They are proven to be unbreakable iff some other primitive they are based on is unbreakable.

Neither of these is particularly automatable for a simple randomness-detector function; the former requires thousands of person-years of expert human interaction, and the latter requires an automated theorem prover, which is intractable in the general case and would require your RNG-tester to take in not just the stream of bits, but the RNG code itself.

To put it another way, the question you're asking is how to short-circuit an entire field of R&D—if someone had a good answer for you, it would be very exciting news in the field :P

(I do wonder if you could try to use genetic programming to evolve an adversary, to at least eliminate the most "obviously" broken CSPRNGs. If you do go down that route, YMMV as I haven't tried it—make sure it eliminates already-known-to-be-broken-for-cryptography RNGs like xorshift before expecting it to be useful.)

Improve this answer
$\endgroup$
1
  • $\begingroup$ But what if the randomness comes from a TRNG? Doesn't the Heisenberg Uncertainty principle and Quantum indeterminacy "prove" / guarantee randomness? $\endgroup$
    – Paul Uszak
    Oct 14 at 22:44
0
$\begingroup$

This is not really a direct answer to my question, so I won't select it as such, but in many contexts of coding I believe this can be very helpful for a lot of people looking for the same thing:

In my case, my initial goal was to help determine whether some data was encrypted or not in case of partial data loss in a custom database. Data can be values/entries (easy), but also files which can be of any type... So I wrote a function that I can use for this but that I may also use in the future in other use cases where bytes are the subject of the analysis (would work very well for network traffic too).

What I do is measure the randomness of the original data, decrypt it (or so I think) and measure again. The difference of randomness between before/after gives me a clue on whether the data was encrypted in the first place (could be used to try keys as well).

The approach I ended up using is not very academic or "official" but after much testing I found that it works quite well in practice. It goes like this:

  • Compress the data with Zlib and get the compressed size
  • Assume that the compressed size of perfectly random data would be PRCS = originalSize + 9 + 1575 * ln(1 + originalSize/10000000) (this adds what I found to be the approximate waste)
  • Establish the compression randomness as compRandom = (compSize/PRCS) ^ 1.58 * 100
  • Count the number of printable characters, which I defined as [\n\r\t\x20-\x7e]. Since these represent 98 of the possible 256 bytes, a perfectly random data should produce a ratio of nbPrintableChars/originalSize = 98/256
  • So the printability (in %) can be adjusted this way: printBalance = (nbPrintableChars/originalSize) ^ 0.72187 * 100 producing 50 for perfectly random data.
  • I then mixed the two (compression randomness, and printability balance) : randomlike = (compRandom + (100 - 2 * abs(printBalance-50)) ) / 2 (a printBalance of 50 attracts compRandom towards 100 while 0 or 100 attracts it towards 0)
  • From testing a lot of data types (inc. perfectly random) I wrote this function that determines a percentage of confidence = 100 - ( 100 / (1 + log(2.5 + 0.12 * originalSize) ^ 5) ). It makes sense that the confidence only becomes significant above 256 since this is the number of states of a byte.
  • And finally, I defined the general randomness percentage as: randomness = 50 + (randomlike - 50) * confidence / 100, where 0.01 is definitely not random, 99.99 is very random, and 50 means we have no idea.

You may want to turn all that into 0-1 values but I needed percentages.

So again, definitely not very academic but I thought it could be useful to many coders in some practical contexts.

PS: if you find that 50% does not represent what you would consider as half-random, then 1.58 is the only value to change. This could be a parameter of the function that is set based on the use case.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ It would have helped if you had said "determine whether some data was encrypted or not" in the question. Notwithstanding, your confidence is not the 'famous' metric that you were looking for as $p$ values arise from statistical analyses of common distributions. $\endgroup$
    – Paul Uszak
    Mar 11, 2021 at 12:31
-2
$\begingroup$

I [sic] have to rethink the whole logic from scratch?

Not entirely, but the complexities make this harder that it appears.

"randomness" (0 - 100) which tells how random the bytes look (regardless of how much data we have)

This is still somewhat of an open question for the general case of auto-correlated samples. The simple Shannon $\log$ formula is no use whatsoever as it is impossible to adequately populate set $p_i$ of $-\sum p_i \log p_i$. Similarly $\chi^2$ values fail for exactly the same reason; defining the domain of the probability mass function for the sample distribution. Simple Shannon only works for uncorrelated data, like perhaps testing keys from good sources.

And for the same reason again, the more common measure of cryptographic entropy, min.entropy $(H_{\infty})$ is also very problematic in the general case. An example of how hard and varied general entropy measurement can be seen on this page. Many of those techniques are various forms of compression.

Anyway you'd have to shift your metrics away from 0 - 100, towards 0 - 1 bits/bit or 0 - 8 bits/byte of Shannon entropy. The measurement effectiveness is inversely related to the degree of auto-correlation (loosely).

"randomlike" (0.001 - 99.999) which tells the general likelihood of the whole data to be random (a combination of randomness and length).

This need to be changed to a $p$ value of the certainty that whatever randomness test suite (NIST STS, TestU01, diehard, dieharder, ent, AIS-31, pkzip, FIPS 140 etc.) you run is accurate. It ranges 0 - 1, and 'famously' we tend to exclude values within 1% - 5% of the tails (suite dependant). And you do get $p = 0.0005$ as false negatives because imagine an output domain like (it's a TRNG random walk):-

domain

If you test the blue box, the data is appears highly biased and it fails. If you test the green box, as the data is uniform it passes. And yet it's a good TRNG overall. Randomness is pesky like that.

What does 50% randomness correspond to?

However you manage to measure the Shannon entropy, 50% $\equiv$ 0.5 bits/bit or 4 bits/byte. So there would be a half cup of stuff that varies unpredictably, and a half cup that remains constant/so auto-correlated that it might as well be constant.

The family of paq8 compressors are pretty efficient, and running your data through one will give you a good estimate of the amount of randomness but not a certainty for the reasons above.

Improve this answer
$\endgroup$

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.