Score:1

Crypto

How to measure the length of the 128-bit PRNG cycle?

Tom

1/28/23, 5:00 PM

I have keyed 128-bit PRNG. It passed PractRand and Dieharder tests, but I have no idea what is expected cycle lengh of it (for different keys and different seeds).

Is there way to estimate it, through analysis outputs of this generator? I'm trying to analyze cycles in 16-bit parts of 128-bits outputs. 16-bit numbers repeats in truncated 16-bit parts of 128-bit output in average in every $6331708$ steps. For example number $14649$ ocurres in low 16 bits irregular after:

$1385856, 6793856, 4734720, 4043776, 17823744, 3705088, 5609216, 1174784, 3718656, 181504, 14063616, 13729024, 10346880, 15782016, 1561088, 1996672, 988544$

steps (and it looks similar when we check every other 16-bit number, with ither keys). But on the basis of such an analysis of consecutive 16-bit generator parts, can any conclusions be drawn about the cycle of the entire generator?

By the way, shouldn't we expect a random 16-bit number to occure once in every $2^{16}$ steps? At first randomly choosen 16-bit numbers occures to rare for me or am I misunderstanding something?

0 + 0

pseudo-random-generator

fgrieu

1/28/23, 5:10 PM

It can be experimentally demonstrated that a PRNG is insecure or has short period. No method examining it's output can determine that it's secure or has long period. For this, it's needed to examine how the PRNG works.

Tom

1/28/23, 5:18 PM

Ok, I have to consider, that I have no theory about period. So there is no way to know anything about period of PRNG? So it doesn't matter if it passes PractRand to 2^42 bytes, it can go into cycle of legth $2^{50}$ or $2^{100}$ and we can't find out how it is, by just analyzing outputs?

Maarten Bodewes

1/28/23, 5:58 PM

By definition (?), the output of the RNG should not tell you anything about the state of the PRNG. So just looking at parts of the output, you will not gain much if any insight in the possibility of a cycle. You can only find irregularities, but those should show up in the testing. If the tests fail then I guess that if it is a cycle or not is inconsequential :)

fgrieu

1/28/23, 8:14 PM

Exactly. Unless the period is lower (with a little margin) than the length tested, a statistical test operating on the output of the PRNG can't find the period. Again, statistical tests are useful only to prove that bad PRNGs are bad, or/and have short period. When a test does not find a defect / short period, we can reach no conclusion about the PRNG tested. Much like after seeing an ant safely going across a bridge, we can reach no positive conclusion about the bridge. We need to see it's design schematic, and inspect its construction.

kodlu

1/28/23, 9:05 PM

your statement is imprecise. if those are gap distributions for a particular 16 bit “window”, have you checked *all* 16 bit windows? is that gap distribution typical for the whole set of 16 bit windows?

Tom

1/29/23, 11:08 AM

@kodlu I made it wrong, there can't be so big gaps and there are not (I made wrong Python code).

user2357

1/30/23, 4:51 PM

@fgrieu what about lfsr where the longest period is calculated and it could be achieved by the considerations with primitive polynomials? I just was reading about something like that in the book titled understanding cryptography.

Score:3

Crypto

poncho

1/28/23, 8:36 PM

Is there way to estimate it, through analysis outputs of this generator?

As the comments said, not really (unless the generator was real bad).

I'm trying to analyze cycles in 16-bit parts of 128-bits outputs. By the way, shouldn't we expect a random 16-bit number to occure once in every $2^{16}$ steps?

What a good PRNG should do is stir in all bits of the state together, hence looking at truncated 16-bit chunks shouldn't tell you anything.

On the other hand, you appear to list gaps in occurrences of a specific 216 bit value (14649), and those gaps do look quite odd. If the PRNG was good, we'd expect the gaps between occurances to follow an exponential distribution (with the mean at 65536, as you said); while you will sometimes see gaps considerably larger than the mean, you should almost never see a gap as much as 100 times the mean (and you show even larger ones) - this is a 'win-the-lottery-multiple-times' type event. The fact that you appear to would indicate either a) I'm not interpreting the data correctly, b) you're not measuring the gap correctly, or c) the PRNG is seriously nonuniform.

Checking for nonuniformity is straight-forward - just run the PRNG, and count how many times you see each value - if you see values whose count is a large multiples of the standard deviation from the mean (in either direction), you have a serious problem.

Of course, if this is supposed to be a cryptographically secure random number generator, well, the requirements for that are significantly stricter...

0 + 0

Tom

1/29/23, 11:06 AM

You are right, I got my code wrong and measured these repetitions wrong. With such deviations, this generator would surely fail the tests. Anyway, I have to work on the theory about the cycles of this generator.