0
$\begingroup$

I'm trying to statistically anayze random number generators, i.e., generators which are intended to produce truly random sequences of bytes (integers in the range [0..255]). An incredibly helpful answer on here (Expected standard deviation of random binary data) has pointed me in the direction of performing Chi-Square testing on data. I believe I've understood this and implemented it accordingly and can follow all calculations in there.

To test my understanding, I've first collected massive amounts of data which come from a generator that is arguably good (the CSPRNG of the Linux Kernel). I've collected rougly $250 \cdot 10^9$ bytes of data (250 GB). This is the distribution of characters:

$$\left( \begin{array}{cccccccccccccccc} 1010966001 & 1010976991 & 1010887488 & 1010948243 & 1010949190 & 1010934553 & 1010917522 & 1010874898 & 1010930071 & 1010980459 & 1010952497 & 1010919164 & 1011010055 & 1011037805 & 1010926897 & 1010893562\\ 1010942296 & 1010977576 & 1010892288 & 1010947126 & 1010893758 & 1010891819 & 1010931300 & 1010954491 & 1010955681 & 1010941487 & 1010924343 & 1010883070 & 1010951658 & 1010965997 & 1010963238 & 1010905981\\ 1010993133 & 1010953999 & 1010917479 & 1010998971 & 1010893851 & 1010941162 & 1010908262 & 1010920158 & 1010993261 & 1010931826 & 1010975359 & 1010946839 & 1011012098 & 1010916290 & 1010972240 & 1010908297\\ 1010972291 & 1010987647 & 1010897830 & 1010934125 & 1010945903 & 1010964191 & 1010942402 & 1010967532 & 1010951110 & 1010925373 & 1010986320 & 1010922827 & 1010952648 & 1010953384 & 1010971172 & 1010963271\\ 1010960728 & 1010905023 & 1010945309 & 1010967246 & 1010951352 & 1010918808 & 1010872008 & 1010976774 & 1010969050 & 1010905604 & 1010881371 & 1010961491 & 1010927386 & 1010923038 & 1010952101 & 1010940779\\ 1010941149 & 1010983955 & 1010939022 & 1010895198 & 1010920462 & 1010932243 & 1010943817 & 1010972391 & 1010923768 & 1010906746 & 1010916839 & 1010978691 & 1010933593 & 1010943920 & 1010907036 & 1010965189\\ 1010912902 & 1010924036 & 1010905632 & 1010987306 & 1010904971 & 1010937804 & 1010976976 & 1010889794 & 1010851229 & 1010946839 & 1010930434 & 1010969428 & 1010977693 & 1010926171 & 1010980490 & 1010882169\\ 1010961365 & 1010876693 & 1010984288 & 1010967918 & 1010926974 & 1010931104 & 1010922436 & 1010975984 & 1010942746 & 1010879443 & 1010963442 & 1010949653 & 1010920686 & 1010950924 & 1010954975 & 1010919343\\ 1010916919 & 1010893135 & 1010932617 & 1010931028 & 1010953514 & 1010946336 & 1010874006 & 1010949886 & 1010946408 & 1010919972 & 1010933623 & 1010944638 & 1010918804 & 1010910417 & 1010948180 & 1010924548\\ 1010952714 & 1010910696 & 1010967418 & 1010924316 & 1010901209 & 1010917153 & 1010927221 & 1010922785 & 1010913319 & 1010961108 & 1010965367 & 1010923774 & 1010956655 & 1010932756 & 1010943145 & 1010959839\\ 1010902057 & 1010937300 & 1010894215 & 1010954705 & 1010946686 & 1010919565 & 1010960715 & 1010962030 & 1010930489 & 1010937969 & 1010923175 & 1010924144 & 1010967562 & 1010974277 & 1010937684 & 1010895821\\ 1010925188 & 1010953235 & 1010897286 & 1010977090 & 1010924147 & 1010947516 & 1010923802 & 1010943058 & 1010903071 & 1010904599 & 1010940461 & 1010949700 & 1010987516 & 1010938254 & 1010896618 & 1010980031\\ 1010933359 & 1010929155 & 1010903726 & 1010921884 & 1010947029 & 1010950279 & 1010937089 & 1010934314 & 1010925524 & 1010895195 & 1010897302 & 1010901076 & 1010961624 & 1010942690 & 1010923176 & 1010928225\\ 1010871220 & 1010904368 & 1010967581 & 1010941080 & 1010879547 & 1010954499 & 1011001377 & 1010912651 & 1010895522 & 1010943091 & 1010952233 & 1010914450 & 1010926001 & 1010905592 & 1010928990 & 1010975526\\ 1011009526 & 1010942261 & 1010954044 & 1011011959 & 1010940244 & 1010955991 & 1010942391 & 1010895238 & 1010910814 & 1010899109 & 1010948671 & 1010973726 & 1010939240 & 1010987253 & 1010899653 & 1010937320\\ 1010966670 & 1010950801 & 1010947870 & 1010955096 & 1010922876 & 1010921403 & 1010908364 & 1010973666 & 1010937391 & 1010889507 & 1010916100 & 1010917292 & 1010969773 & 1010908227 & 1010912085 & 1011023901\\ \end{array} \right)$$

Doing the math on those numbers I compute a Chi-Square test statistic of around 244.393. I further find that

$$p = \Pr[\chi^2_{255} > 244.393] \approx 0.672515$$

This is a surprisingly awful result for the huge amount of input data and very good underlying CSPRNG. Does this mean that with around 33% probability the numbers are not following a uniform distribution?

What mistake am I making in my thinking and is there a way to correct it or choose a better approach to the analysis I'm conducting?

$\endgroup$

1 Answer 1

0
$\begingroup$

If the numbers you've provided are correct, I've independently checked that your $244.393$ number and the probability $0.67$ are correct.

Note that to reject the null hypothesis ("the generator generates numbers uniformly") at a 5% level, we need $p < 0.05$, i.e. a very large chi-squared statistic. For any value of $p$ larger than 0.05, we say "we do not have sufficient evidence to reject the null hypothesis." Even though your chi-squared value is moderately large, the test suggests that it is still reasonable that it may have arisen by chance, rather than from non-uniformity in the generator.

$\endgroup$
1
  • $\begingroup$ Thanks, this makes a lot of sense. I was thinking about this the wrong way. $\endgroup$
    – itecMemory
    Oct 26, 2021 at 22:13

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.