0
$\begingroup$

I am designing a pseudo random bit generator (PRBG) and I am using the NIST SP 800-22 suite to analyze the random characteristics of my PRBG. It turns out that my PRBG passes 14 out of 15 tests, and fails the Discrete Fourier transform (Spectral) test as can be seen in the Table below. I have already tested different samples of size 150 and the results are similar to those in the table.

I sincerely appreciate any advice you can give me to improve the spectral characteristics of my PRBG.

Table 1

$\endgroup$
3
  • 1
    $\begingroup$ We cannot tell you how to improve the generator if we don't know how it was constructed. $\endgroup$
    – kodlu
    Commented Dec 21, 2023 at 2:30
  • 1
    $\begingroup$ Designing a PRBG for cryptographic use based on result of statistical tests of it's output is an erroneous design methodology (in a nutshell: because statistical tests make no use of the internal structure of the generator, that they are not even given; when the opposite assumption is made in attacks on PRBG in cryptography, since Kerckhoffs). Many have used that erroneous design methodology. $\endgroup$
    – fgrieu
    Commented Dec 21, 2023 at 6:25
  • 1
    $\begingroup$ Thank you very much for your reply Paul Uszak and Merry Christmas to you too. My PRBG does pass the frequency test, remember that for p-value uniformity analysis, the significance level is 0.0001. $\endgroup$ Commented Dec 21, 2023 at 20:09

1 Answer 1

1
$\begingroup$

A comment asks:

I would like to know if there are techniques that allow me to alter the spectral characteristics of a generator.

Yes there are. For example, one can pass the output of the generator in a scrambler like:

Multiplicative_(self-synchronizing)_scrambler

Data scrambler used in V.34 modems. Source of illustration: Wikipedia.

For most PRBG, that addition will help towards making the PRBG pass the spectral test (and typically every test except perhaps the Linear Complexity Test). In FPGA it adds a few registers (here 23 bits) and one three-input XOR gate. In software it adds like 3 lines of code

static uint32_t scr;                  // scrambler state (23 used bits)
b = ((scr>>22) ^ (scr>>17) ^ b) & 1;  // apply the scrambler to bit b
scr = scr + scr + b;                  // update scrambler state

However, that addition is of no help in making the PRBG cryptographically secure: given the output of the modified PRBG and the structure of the scrambler, it's easy to reconstruct the output of the original PRBG (except it's first outputs if the initial state of the LFSR is unknown). Therefore any test that the original PRBG fails can be can be turned into one that the modified PRBG fails (and it can be proven that this test remains valid if the original test is, that is a true RNG passes it). Notice that knowing the structure of the PRBG is an explicit hypothesis made about an attacker, since Kerckhoffs.

More generally, it's easy to make a PRBG that passes the NIST SP 800-22 suite, or any valid predefined statistical test suite, yet is not cryptographically secure at all. Thus it would be very wrong to conclude that a PRBG is cryptographically secure on the sole basis of passing statistical test suites, as hundreds of incorrect published papers do (which would make them immediately rejected in a peer-reviewed journal of the IACR). Truth is, such tests can only conclude that a PRBG is not secure (if they fail consistently), or be inconclusive on that standpoint (if they pass).

Any convincing argument of security for a PRBG must consider it's internal structure. Statistical tests do not.

$\endgroup$
5
  • 1
    $\begingroup$ I think that it's 150 bit streams, not 150 byte long samples. That's how Julian gets 150/150 passes. $\endgroup$
    – Paul Uszak
    Commented Dec 22, 2023 at 12:53
  • 1
    $\begingroup$ @PaulUszak Sorry for the lack of clarity, I am actually taking samples of size 150, where each of the 150 sequences is of period $2^{20}$ $\endgroup$ Commented Dec 22, 2023 at 15:23
  • $\begingroup$ @fgrieu that's true, I have tested 150 sequences, each of period $2^{20}$. Thank you very much for your comments, I have already started to analyze them in order to improve my PRBG. $\endgroup$ Commented Dec 22, 2023 at 16:14
  • $\begingroup$ @Jullian : The term "period" is usually understood as the number of steps in a cycle of a sequence that ultimately repeats. The proper terms for the number of bits or bytes in each sequence tested are "size" or "length" of the sequence tested. $\endgroup$
    – fgrieu
    Commented Dec 22, 2023 at 16:17
  • $\begingroup$ @fgrieu thank you for the clarification. $\endgroup$ Commented Dec 22, 2023 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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